déplacements dans un jeu en réseau 2D

Bonjour,

Je code depuis un petit bout de temps maintenant un jeu en réseau (client serveur) en java en 2d (déplacement droite-gauche et saut, comme les premiers mario) et je galère depuis un moment sur la gestion des déplacements, toutes les solutions que j'ai trouvé impliquent des aberrations coté client..

Tout d'abord, j'utilise le protocole TCP avec un Selector pour transmettre mes données, et je n'ai pas envie de passer en UDP, car la création d'une couche de gestion des erreurs me prendrai trop de temps.

L'idée sur laquelle j'étais parti était de créer un classe State qui encapsulerais un temps, un vecteur position et un vecteur vitesse. Le joueur possède un State courant, à partir duquel je peux recalculer sa position à tout moment.

Lors d'un déplacement, un State est créé et le joueur coté client commence à se déplacer (client-side prédiction), au même moment, le client envoie la demande de déplacement au serveur qui accepte ou refuse le déplacement et renvoie le nouveau State au client, qui doit ensuite recalculer sa position.

Dans la théorie cela semble pas mal, mais en pratique, le calcul du déplacement est totalement faussé car je n'arrive pas à avoir une mesure de temps absolue entre le serveur et le client et les laggs ne viennent pas arranger la donne... J'ai lu l'article http://gafferongames.com/game-physic...orked-physics/ mais l'auteur ne semble pas tenir compte de ces différences de temps, de plus il utilise le protocole UDP et envoie le State plusieurs fois par seconde alors que je ne veux envoyer ce State seulement lors du changement de direction, ou du saut.

Je suis donc ouvert à toute proposition, toute idée, tout lien, ou tout bout de code pouvant m'aider à gérer ça...

Merci d'avance.

Citation:

---

Envoyé par mytrill

Tout d'abord, j'utilise le protocole TCP avec un Selector pour transmettre mes données, et je n'ai pas envie de passer en UDP, car la création d'une couche de gestion des erreurs me prendrai trop de temps.

---

Et personellement, je trouve que tu n'as pas tort ;)

Citation:

---

L'idée sur laquelle j'étais parti était [...]

---

Je vais t'expliquer ce que j'ai pu apprendre du développement d'un petit moteur réseau pour un bomberman like, justement en TCP.

Je suis parti sur un moteur qui s'exécute à des temps discrets ; par exemple toutes les 20ms. Par convention, le temps dans une partie commence à zéro et les itérations du jeu se font donc à 0ms, 20ms, 40ms, ...

On parle bien ici de la logique du jeu, donc les calculs de collision, de changement de direction, etc... se feront uniquement pour ces valeurs là.
Cela ne t'empêche pas de calculer les positions intermédiaires pour l'affichage: si tu dois dessiner le perso à T=527ms, tu vas interpoler la position entre celles de 520ms et 540ms. Mais en aucun cas les actions de la logique de jeu ne seront répercutées à autre chose qu'un multiple de 20ms: si ton joueur appuie sur une touche pour changer de direction à 527ms, tu prendras l'action en compte dans ton moteur de jeu à la prochaine itération: à 540ms.

Voilà pour la base : on a donc un moteur qui calcule l'ensemble de l'état du jeu toutes les 20ms en fonction de l'état précédent.

Maintenant, on peut s'occuper de la partie réseau et des spécificités qu'elle entraîne:

1/ Il faut synchroniser les clients entre eux, histoire que tout le monde joue la partie en même temps, et donc que le temps de notre partie soit à peu près le même pour tout le monde (clients & serveur) au même moment.

2/ Il faut gérer les cas où on n'a pas encore reçu les mises à jour de l'autre client (latence réseau, erreur passagère, ...) et donc être capable d'anticiper ce qu'il a probablement fait.

3/ quand on anticipe ce que l'autre joueur fait (point précédent) et si (lorsqu'on reçoit finalement l'information) on se rend compte qu'on s'est trompé, il faut être capable de corriger l'erreur à postériori.



Les solutions que j'ai pu y apporter:
Je ne dis pas que ce sont les meilleures, hein

1/ pour la synchro, le principe est raltivement simple: un peu avant de commencer la partie, les clients envoient régulièrement un paquet 'PING' auquel le serveur répond immédiatement ('PONG', admettons). Quand le client reçoit la réponse PONG, tu peux calculer le temps passé entre l'envoie du PING et la réponse, ce qui correspond à un aller + un retour entre le client et le serveur, donc tu peux en déduire la latence entre chaque client et le serveur.

Il ne te reste plus qu'à ce que le serveur envoie un paquet pour dire 'C'EST MAINTENANT LE DEBUT DE LA PARTIE' et avec ta latence estimée, tu peux synchroniser tes clients entre eux.

Même si dans un premier temps, ça marche bien dans 90% des cas, tu peux dans un second temps améliorer en envoyant:
- non pas un seul paque PING, mais plusieurs de façon régulière
- non pas juste un paquet avant le début de la partie mais également tout au long de la partie

... tu peux avoir une estimation plus précise et qui s'adapte tout au long de la partie en cas de conditions réseau 'changeantes'.


2/ pour anticiper les mouvements, le plus simple est de partir du principe que si à l'instant T-20ms le joueur se dirigeait par exemple à droite, il y a de grandes chances qu'il fasse la même chose 20ms après, donc si on manque d'infos à l'instant T, on peut simplement recopier l'actino du joueur à l'itération précédente.


3/ Le problème du 'retour sur erreur' est le plus complexe.

Dans mon cas, je suis parti sur la solution suivante: mon moteur de jeu ne stocke pas uniquement le derneir état du jeu (celui du temps présent), mais garde en mémoire l'ensemble des états précédents sur 1 seconde par exemple (à 20ms par itération, ça nous fait 50 états).

Si on n'a pas reçu les états précédents par l'autre client, c'est pas grave: on a pu calculer les états intermédiaires avec la solution 2.

Si on a fait une prédiction qui s'est avérée fausse (par exemple à T-100ms, on croyait que le joueur allait à droite, en fait il s'est arrêté), on va mettre à jour l'état du joueur à T-100ms et on va recalculer l'ensemble des itérations en partant de T-100ms jusqu'au temps présent (donc 100ms/20ms = 5 itérations à recalculer).

On peut ensuite raffiner, comme par exemple ne garder les anciens états que lorsque c'est nécessaire (ie. quand on a fait de la prédiction).

Note: un thread à lire si ce n'est pas déjà fait.


En espérant que ça puisse te donner quelques idées.

Merci pour ta réponse.

Mon problème se situe principalement au niveau de la synchro finalement...

avec ton système, tu peux synchronisé les différents clients mais tu suppose que le temps que met le message à aller du client au serveur est le même que celui pour aller du serveur au client, je ne sais pas vraiment si je peux me permettre cette supposition.

Imaginons un client avec 300ms de ping (ce qui est beaucoup, mais courant...), si tu suppose lors de l'envoie de tes messages que les temps d'aller et de retour sont égaux, le client va "supposer" qu'il a 150ms de retard lorsqu'il reçoit un packet, mais il se peut que l'aller dure 80ms et que le retour dure 220, dans ce cas tu as une erreur de 70ms sur tous tes calculs, et dans mon cas, ça peut mener à des gros problèmes (l'exemple courant est un personnage qui saute sur le bord d'une plateforme, s'il attérit très près du bord sur le client, il peut être dans le vide sur le serveur ou vice versa...)

Je ne sais pas du tout si les temps d'aller et de retour de packet sur internet peuvent être très différents, mais je ne vois pas trop comment les calculer si on les considère différents.


EDIT : merci pour le post, je regarde ça :)

Citation:

---

Envoyé par mytrill

avec ton système, tu peux synchronisé les différents clients mais tu suppose que le temps que met le message à aller du client au serveur est le même que celui pour aller du serveur au client, je ne sais pas vraiment si je peux me permettre cette supposition.

---

c'est ce qui se passe effectivement dans 99.99% des cas sur le réseau: hors congestion rare et ponctuelle, les chemins aller et retours sont physiquement les mêmes.

Citation:

---

Imaginons un client avec 300ms de ping (ce qui est beaucoup, mais courant...), si tu suppose lors de l'envoie de tes messages que les temps d'aller et de retour sont égaux, le client va "supposer" qu'il a 150ms de retard lorsqu'il reçoit un packet, mais il se peut que l'aller dure 80ms et que le retour dure 220

---

Non, ça n'arrive pas. Ce genre de cas avec une différence entre l'aller et le retour est vraiment trop extrême.

Même si une différence se produit au pire tu auras quelques millisecondes de décalage, disons 10ms grand maximum, et ce décalage n'aura pour effet que d'augmenter d'autant la latence du client qui aura calculé la référence de temps le plus en retard. Et dans ce cadre, 10ms c'est pas vraiment bloquant.

Citation:

---

dans ce cas tu as une erreur de 70ms sur tous tes calculs, et dans mon cas, ça peut mener à des gros problèmes (l'exemple courant est un personnage qui saute sur le bord d'une plateforme, s'il attérit très près du bord sur le client, il peut être dans le vide sur le serveur ou vice versa...)

---

L'erreur ne pose pas de souci de désynchronisation puisque quand les données réelles arriveront tu referas le calcul complètement, donc tu aboutiras au même résultat.
Les seuls cas où tu n'auras pas la même chose sur les différents clients et/ou le serveur, ce sont les cas où non seulement des données ne sont pas encore arrivées mais qu'en plus la prédiction s'est avérée fausse, ce qui est finalement peu courant dans les faits.

Et même dans ce cas la désynchro n'est que temporaire (de l'ordre d'un aller-retour) puisque dès que les données seront reçues, tout rentrera dans l'ordre. et même avec un ping énorme à 300ms, ça reste très peu de temps pour l'oeil humain (3/10èmes de secondes).

Citation:

---

je ne vois pas trop comment les calculer si on les considère différents.

---

On ne peut pas réellement puisque de toute façon ça peut varier légèrement pour chaque paquet.

D'un façon plus globale quand on commence dans le réseau multijoueurs, il faut se mettre une chose dans la tête: tu ne pourras JAMAIS palier à tous les soucis réseau que tes joueurs pourront rencontrer: ça ne sert à rien de se fixer ça comme objectif si ce n'est perdre du temps inutilement.

La seule chose à faire est de trouver des mécanismes pour palier aux plus gros soucis, à savoir: ceux qui sont les 3 à la fois: les plus 'visibles' par le joueur, qui se produisent le plus souvent, et qui sont le plus handicapants pour le gameplay.



PS: A noter une astuce parmi d'autres également: il y a un moyen très simple de faire diminuer artificiellement le ping, donc la probabilité d'entrer dans les cas où on utilise de la prédiction: il suffit d'ajouter du lag aux actions des joueurs.
Concrètement, si à T=500ms le joueur appuie sur la touche 'haut' pour saute, on ne va pas prendre en compte le saut à T=500ms mais trois itérations plus tard, à T=560ms. Pendant ce temps, ça ne nous empêche pas d'envoyer dès T=500ms le paquet sur le réseau et tu fais ainsi gagner 60ms articifiellement à ton réseau.

Au départ, ça peut sembler un peu délirant puisque ce mécanisme introduit un 'lag' même en local pour le joueur qui effectue l'action puisque son action n'est exécutée que 60ms plus tard. Mais dans les faits (et hors jeu très spécifique qui demande un très haut niveau de 'temps-réel'), 60ms c'est quasi impreceptible pour un joueur. Dans un bomberman like par exemple (où le joueur doit pourtant répondre rapidement à toute solicitation du joueur), le joueur ne ressentira aucune gène.

EDIT: Pour te donner une idée des ping moyens, fais un tour sur le site justping.com qui va te pinger le serveur de ton choix depuis un peu partout sur la planète. Un exemple avec un de mes serveurs OVH 'low cost'.

Tu peux constater que:
- le ping dépasse rarement les 50ms pour toute l'Europe
- qu'on tourne dans les 100 à 150ms pour les USA
- que pour atteindre les 300ms il faut regarder des cas très spécifiques à l'autre bout de la planète (Japon, Australie, Afrique du Sud).

Et d'ici à ce que les joueurs Asiatique représentent une part non négligeable de ton public, tu as un peu de temps devant toi je pense ;) Et même là, il sera toujours possible de louer un serveur supplémentaire en Asie ; rien de rhédibitoire en tout cas.

Très bien merci :)

Je vais voir pour faire un système similaire à ton bomberman.

Cependant, il y a un dernier truc qui m'échappe, le serveur envoie les positions de tous les joueurs toutes les 20ms ? Ou il ne les envoie qu'aux changements de direction(comme j'avais l'intention de faire)?

Et lorsque tu dis que le client stocke plusieurs états, que sont ces états exactement ? ce sont des objets qui contiennent un temps, une position et une vitesse comme mes States? Ces états sont générés toutes les 20ms ? pourquoi ne pas garder un état "courant" créé par exemple au moment ou le joueur commence son mouvement, et recalculer la position du joueur grâce à cet état plutôt que de recréer un état qui peut facilement être calculé toutes les 20ms?

Citation:

---

le serveur envoie les positions de tous les joueurs toutes les 20ms ? Ou il ne les envoie qu'aux changements de direction(comme j'avais l'intention de faire)?

---

Tu devrais commencer par faire que tu envoies l'état des commandes des joueurs (*) à chaque itération.
Si et seulement si pour une raison quelconque tu as des soucis avec cette solution (de bande passante consommée par exemple), tu pourras voir pour optimiser et n'envoyer les commandes que quand elles changent.

Mais comme pour toute optimisation, il ne faut pas mettre la charrue avant les boeufs: commene par faire quelque chose de simple qui marche et n'optimise que si tu en as réellement et concrètement le besoin.

(*) ça ne prendra d'ailleurs guère plus qu'un octet ou deux. En effet, vu que tu es en TCP (donc aucune perte) et que tu as l'état précédent du jeu, le simple fait de savoir sur quelles touches appuie chaque joueur est suffisant pour calculer l'état suivant.

Citation:

---

Et lorsque tu dis que le client stocke plusieurs états, que sont ces états exactement ?

---

D'une façon générale c'est l'ensemble des données qui sont susceptible de changer à un moment de ta partie. Par exemple pour bomberman tu stockes:
- chaque bloc présent sur la carte
- la position de chaque joueur, de quel côté il regarde
- la position des bombes et leur timer avant qu'elles n'explosent
- la position des bonus
- la position des flammes pour les bombes qui sont en train d'exposer.

Le principe de base à respecter est que l'état à l'instant T plus les commandes des joueurs à ce même instant sont les seules données dont tu as besoin pour calculer tout ce qu'il faut pour l'état à l'instant T+1.

Même principe: ne t'embête pas au début et pour chaque état fais une copie complète (deep copy) de l'ensemble des données 'à la bourrin'.
Pour le bomberman, 50 états stockés représentent guère plus que quelques dizaines de Ko et la surcharge de CPU nécessaire pour réinstancier un état complet est négligeable comparée à la puissance d'un PC, même très vieux.

Si et seulement si ça pose souci à un moment donné, il sera toujours temps d'optimiser pour peu que ta première version ait été codé à peu près proprement.
Pour le bomberman par exemple, aucune des optimisations suggérées précédemment n'a été finalement nécessaire ; tout fonctionnait parfaitement dès la version de base, même sur un Atom Z anémique et un mémoire vive dispo de seulement 32Mo pour l'ensemble du jeu (applet Java).

Ok merci pour tes réponses :)

Je vais voir tout ça.

Merci pour ce thread ma fois bien utile qui explique assez clairement les choses.
Je l'ai lu et relu avec attention, étant donné que je suis confronté à ce problème en ce moment.

Pour compléter à partir de la réflexion que je mène, j'ajouterais que selon le type de jeu, il y a des commandes qui ne demandent pas à être anticipées et donc corrigées, car le joueur supporte volontiers une latence de la part du jeu.

Par exemple :
- dans un wargame, les troupes mettent quelques dixièmes secondes à réagir, ça ne nous gène pas
- dans un jeu de carte, on peut tolérer un certain temps entre le clic et l'affichage de la carte
- dans les jeux tour par tour
...

Dans ces cas-là, le plus simple/robuste/efficace selon moi, et d'envoyer la commande au serveur, pour que celui-ci valide son exécution "dans x ticks" ou "au tick N°13482", le tick étant le concept expliqué au début du premier post de nounouk.

Bonjour à nouveau,

Je continue ma discussion tout seul, mais je suis en plein dans le truc, et je me dis que quelqu'un qui tombera comme moi sur ce post sera content d'avoir une seconde expérience.

Je confirme donc tout ce que dit Nounouk.

Citation:

---

Envoyé par nouknouk

c'est ce qui se passe effectivement dans 99.99% des cas sur le réseau: hors congestion rare et ponctuelle, les chemins aller et retours sont physiquement les mêmes.

---

J'ai mis en place quelque chose qui ressemble beaucoup à ce que Nounouk propose, et voici les résultats.
On y voit un client/serveur, avec 2000 +/- 200 ms de ping entre l'un et l'autre.
La synchro est tout à fait tolérable.

Prochaine partie : la prédiction/correction.

[EDIT]Bon j'arrive pas à faire une capture vidéo de mon écran dans un format léger, du coup, je vais juste mettre les logs. Il faudra me faire confiance[/EDIT]

Server

Citation:

---

[2010-Oct-05 01:02:44.065947][][]: Pong reçus, délais : 00:00:02.062500 <=== ceci et le dernier ping (2 secondes et 62 millisecondes)
...
[2010-Oct-05 01:02:44.753447][][]: On envoi l'ordre de commencement du tour 250 sur la machine 1 <=== ici on envoi l'ordre au client
...
[2010-Oct-05 01:02:45.737822][][]: Le tour commence 250 commence <=== ici le tour commence sur le serveur

---

Client

Citation:

---

[2010-Oct-05 01:02:45.722197][][]: On a reçu de commencement du tour 250 <=== ici le tour commence sur le client, 15 ms avant le serveur

---