# Jeux vidéo > Jeux vidéo (Discussions générales) > Le coin des développeurs >  [Algo] Déplacement fluide dans un jeu 3DIso par tiles (et client/serveur)

## Moen

Bonjour, aujourd'hui un peu d'algo et d'optimisation, et des questions évidement.

Pour mon projet je me suis posé la question : *"Comment rendre des déplacements réaliste en jeu en ligne 2D tout en réduisant fortement la complexité coté serveur et les échanges réseau?"*

L'un des gros problèmes des moteurs iso à sprite, c'est que les mouvement des créatures _ET_ des personnages sont saccadés ou robotique, en effet ils se déplacent de bloc en bloc (tiles), et pour des raisons de performance, les blocs sont généralement assez gros (~70cm de large dans T4C) Donc quand on veut légèrement se déplacer vers le haut ou le bas, on se retrouve à forcement avec un personnage qui se balade sur 70cm, le rendu n'est pas terrible. Le moyen le plus évident de rendre l'action plus fluide c'est de réduire la taille des cellules. Oui mais, dans ce cas là, coté serveur, que se passe-t-il ? Si je passe d'une structure qui gère l'état du terrain (sol, eau, boue...) de 3000*3000 à 6000*6000, ma mémoire explose, juste en doublant la précision, et tout ça pour des déplacements fluides. (pour ceux qui n'ont pas lu mon projet (ici) sachez que je fais du javascript histoire de me mettre des battons dans les roues de la performance!!)
C'est comme ça que fonctionne T4C, encore aujourd'hui, et c'est pas terrible (alors que c'est du bon vieux c++). Pourtant on pourrait mieux faire !

Je pose le problème en termes simples : j'ai un render engine en 3Diso (donc 2d), dans lequel je veux gérer des collisions réalistes, où les personnages auront un déplacement qui aura l'air naturel autant que se peut et le tout sans tuer les perfs du serveur, et en interdisant la triche.

La solution qui me parait la plus évidente : avoir deux échelles différentes, coté client ou coté serveur.

Coté serveur, le monde est découpé par exemple en une grille de 3000x300 cases, d'1m de coté. Ces cases peuvent représenter les collisions absolues (genre : "Rien ne traverse cette case", ou "les créatures de taille X ne passent pas", ou "les créatures volantes et les projectile des armes passent (eau toxique...)" etc ...)
Premier effet de bord, ça réduit la précision des collisions qui se retrouvent à la précision d'1m, mais on verra qu'on peut tricher pour les améliorer coté client (ça répartie la charge et le serveur suinte moins de sang pendant l'effort)
Mieux, on peut ne représenter des structures qui ne contiennent que les infos utiles. Pour les collisions, pas besoin d'un tableau de 3000x3000, mais juste un hash des cases réellement en mode collision (on met par défaut les collisions classique genre 'Sol').

Coté client maintenant, on va pouvoir tricher, en multipliant par 3 la précision des cases, déjà parce que c'est totalement virtuel, il n'y aura pas besoin de maintenir un tableau de 3000 cases², juste un jeu de coordonnées qui ira jusqu'à 9000*, maintenant une pression sur une touche de clavier va nous faire nous déplacer d'une unité client, donc 1/3 d'unité serveur, on se retrouve avec une précision de 33cm, c'est mieux !
Par conséquence on informe le serveur uniquement au moment de changer de cellule, donc 1/3 des déplacements se retrouvent à être validés, mais à l'écran c'est nickel. (à la louche, parce qu'il y a les déplacements diagonaux)

Problème 1 : Que faire en cas de déco/reco propre. On va stocker la position 'client' de l'utilisateur au moment de la déco, et au moment de la reco on valide la position client par rapport à la position serveur (pour éviter le cheat!), si on est dans la même tranche de division sur une case (serveur) qui n'est pas en collision, c'est vendu.

Problème 2 : que faire en cas de crash coté client. On aura pas l'info coté client, ou une info qui sera erronée. Dans ce cas c'est l'information coté serveur qui dictera le comportement, on aura un personnage qui aura légèrement bougé, mais au final pas de grand malheur. (idem pour ceux qui tenteraient de tricher en envoyant n'importe quoi comme coord)

Problème 3 : le serveur crashe, dans ce cas time warp, on se retrouve là où le serveur à sauvé pour la dernière fois, c'est con mais j'ai pas de bonne idée pour éviter la triche.

Bon, c'est bien sympas tout ça mais on a toujours pas de collision au pixel. En effet, mais là encore on peut gruger visuellement coté client!
Un perso peut marcher sur une case 'collision', mais ne peux pas atteindre une case au delà de la case de collision, en fait il ne peut pas la traverser. C'est subtil mais ça permet de faire effet sympas. Bien sur le serveur verra toujours l'utilisateur sur une case sans collision. On peut faire une collision autour d'un arbre tout en laissant les joueurs frôler le tronc

Pour plus de réalisme maintenant il faudrait conserver l'orientation d'une créature. (pour des compétences de discrétions ou autre), mais c'est une autre histoire !!



Des idées pour améliorer mon algo ?! Vous voyez un endroit où ça peut coincer ?! Ou même un meilleur algo pour gère les mêmes problématiques.
N'oubliez pas que je le fais pour répondre à mes contraintes (2D, javascript...) il y a des choses bien plus malignes à faire avec des langages compilés memory safe, mais je ne peux pas compter dessus vu que je ne contrôle pas 100% de ma mémoire ^^

----------


## war-p

Pour avoir rencontré ce genre de problèmes, le mieux reste d'animer la transition entre deux case, ça permet déjà d'avoir des mouvements moins saccadés, après l'idée d'avoir une précision plus importante côté client est très sympa (j'avais déjà testé le truc) mais c'est vite compliqué et il faut voir si on peut pas faire de l'abus (il faut pas oublier que côté client, on peut injecter du js).

----------


## Louck

Bon mon message a été supprimé par magie. Je te répondrai plus en détails.

Mais pour résumer ce que j'allais dire: "Charger toutes les cases en mémoires pour les manipuler ou les afficher, c'est mal. Et ton problème vient probablement à ce niveau (dont ton algo)."


EDIT: Tu as un steam momomoen ?

----------


## Tomaka17

Par contre tu sembles croire que 9000x9000 ça fait exploser ta mémoire.
Ça ne fait "que" 81 mébioctets multiplié par le nombre d'octets par case. En javascript c'est pas simple de réduire l'occupation mémoire, mais n'importe quel jeu de nos jours bouffe plusieurs centaines de Mo voire plusieurs Go.

Si j'étais toi je me prendrais pas trop la tête à optimiser l'occupation mémoire.

----------


## war-p

Le problème c'est qu'avec les js, t'as vite des perfs pourrav'...

----------


## rOut

Et si tu faisais un truc du style :
 Les actions utilisateur génèrent des modifications sur la vitesse et la direction du mouvement (par exemple aucune touche appuyée : vitesse = 0, flèche de gauche appuyée : vitesse = 5, direction = [-1,0]) Les clients communiquent vers le serveur uniquement les changements de vitesse des personnages qu'ils contrôlent. Les clients calculent localement l'impact des vitesses et direction de chaque créature visible et mettent à jour leur affichage directement. Le serveur calcule également sa propre version de l'impact des vitesses et directions, et également les collisions éventuelles. Le serveur notifie chaque client du résultat de son calcul, c'est à dire des positions "officielles" et des vitesses/directions des créatures visibles, soit de temps en temps, soit dès qu'il y a une modif dûe à une collision / déblocage, pour les clients concernés. Les clients prennent en compte les données du serveur pour corriger leurs données locales et corriger d'éventuelles déviations dans l'affichage.

Les inconvénients à prendre en compte :
 Si l'utilisateur s'énerve sur les touches il peut y avoir beaucoup de modifs à envoyer au serveur, mais on peut imaginer un temps minimal d'appui pour que l'appui soit effectivement considéré comme une modification de la vitesse. Il faut prendre en compte le délai de communication entre client/serveur pour éviter que la position envoyée par le serveur fasse revenir l'affichage local en arrière

----------


## Moen

> Pour avoir rencontré ce genre de problèmes, le mieux reste d'animer la transition entre deux case, ça permet déjà d'avoir des mouvements moins saccadés, après l'idée d'avoir une précision plus importante côté client est très sympa (j'avais déjà testé le truc) mais c'est vite compliqué et il faut voir si on peut pas faire de l'abus (il faut pas oublier que côté client, on peut injecter du js).


C'est déjà prévu l'animation entre deux cases j'ai oublié de préciser. Mais ça ne donne pas de granularité fine. C'est clairement un hack d'avoir deux granularité différentes.




> Bon mon message a été supprimé par magie. Je te répondrai plus en détails.
> 
> Mais pour résumer ce que j'allais dire: "Charger toutes les cases en mémoires pour les manipuler ou les afficher, c'est mal. Et ton problème vient probablement à ce niveau (dont ton algo)."
> 
> 
> EDIT: Tu as un steam momomoen ?


En fait j'ai posé le tableau chargé en mémoire pour l'exemple, en réalité j'ai déjà un chargement adaptatif qui ne charge que 5% des zones autours des joueurs présents (mais cet algo lui même n'est pas forcement bon pour les perfs, faudrait que je bench)
Yep j'ai steam. Mais je suis dessus uniquement le soir assez tard.




> Par contre tu sembles croire que 9000x9000 ça fait exploser ta mémoire.
> Ça ne fait "que" 81 mébioctets multiplié par le nombre d'octets par case. En javascript c'est pas simple de réduire l'occupation mémoire, mais n'importe quel jeu de nos jours bouffe plusieurs centaines de Mo voire plusieurs Go.
> 
> Si j'étais toi je me prendrais pas trop la tête à optimiser l'occupation mémoire.





> Le problème c'est qu'avec les js, t'as vite des perfs pourrav'...


Et oui, la magie du Js. En C ou C++ (j'ai fais beaucoup de C++) c'est pas grand chose, en JS où le caractère de base est Unicode, ça fait vite beaucoup de données en mémoire, même s'il s'agit de bourrage.

PS : J'ai réfléchis à mon soucis de granularité, le but c'est d'avoir de la fluidité pour que ça soit plus sympas (et plus moderne) et aussi d'avoir plus de précision pour des actes genre le roleplay, donc il faut que les autres utilisateurs puissent être au courant aussi. Ça retire mon point sur la réduction des appels réseau.

----------


## Louck

> En fait j'ai posé le tableau chargé en mémoire pour l'exemple, en réalité j'ai déjà un chargement adaptatif qui ne charge que 5% des zones autours des joueurs présents (mais cet algo lui même n'est pas forcement bon pour les perfs, faudrait que je bench)
> Yep j'ai steam. Mais je suis dessus uniquement le soir assez tard.


C'est déjà ca, de charger partiellement le terrain.
Par contre j'ai du mal à voir pourquoi il faut charger des "cases" en mémoires. Quand tu parles de "cases", c'est une entité ? Ou c'est une case du terrain de jeu ?

----------


## war-p

Tiens d'ailleurs en parlant de performances, aujourd'hui j'ai découvert qu'en JS, il valait mieux parcourir les tableaux à l'envers si on veut un truc performant! Genre for(var i in maListe){} et à peu près 20 fois plus lent que var i = maList.length; while(i--){} ...  ::trollface::

----------


## Tomaka17

Faut comparer avec "var i = 0, l = maList.length; while (i++ < l)", sinon c'est biaisé.

Le "for (var i in maList)" prend toutes les clés (même non numériques) dans l'ordre de leur création.

----------


## war-p

Oui, je sais, mais c'était juste un élément de comparaison, il apparait d'après des tests que la solution avec le while(i--) et la plus performante de toute... Après, bon c'est du JS, faut pas trop chercher à comprendre, hein.

PS : Après, perso j'ai pas poussé les tests hein, j'ai juste remarqué que c'était effectivement plus rapide, mais c'est vrai qu'il faudrait tester ta solution.

----------


## doomeer

Ce que je ferais, c’est que j’aurais une grille pour le terrain et les collisions, mais pas pour les joueurs.

Par exemple si le joueur est en (x = 17.8, y = 4.3) alors le joueur est quelque part entre les cases (17, 4), (18, 4), (17, 5), (18, 5).

Ce que ça implique :
- pour les tests de collision avec le décor il faut vérifier non pas une case mais plusieurs (celles sur lesquelles le joueur déborde) ;
- pour les tests de collision avec les autres joueurs c’est un peu plus compliqué (mais pas beaucoup plus, la collision entre deux cercles c’est une trivialité, après ça dépend du nombre de joueurs)-;
- on ne stocke plus les joueurs dans un tableau, et s’il y a beaucoup de joueurs il faut donc envisager l’utilisation d’un quadtree ou d’une structure similaire pour pouvoir chercher qui est près d’un endroit donné (mais s’il n’y a qu’une dizaine de joueurs on s’en fout)-;
- le joueur peut faire une taille différente de 1x1, par exemple 2x2 s’il a trop mangé ou 0.5x0.5 s’il s’agit de Phil Defer ;
- le joueur peut se trouver n’importe où sans restriction, aller en diagonale, tout ce que tu veux.

L’étape suivante c’est de virer aussi la grille pour le décor  ::):

----------


## Moen

c'est plus hardcore que ma version encore, mais ça serait l'idéal. Mais globalement tu as quand même une grille de collision coté client mais ta granularité est plus fine (ici 1/10 de case)

Il faut forcement une validation des collisions coté serveur, sinon il est trop facile de tricher, par contre j'aimerais que les déplacements des joueurs soient visibles chez tous les autres clients, histoire que les demi déplacement (quelques pas sur le coté) transparessent aussi chez les autres joueurs. C'est plus sympas pour le RP !

Oui je vais devoir abandonner le tableau pour la position des joueurs.

Pour les joueurs je vise plutôt 200 places voir plus.

----------


## rOut

Ben c'est ce que je proposais. Pour la détection des collisions, tu peux faire ça via un vrai moteur physique, tu as même des librairies pour faire ça en javascript / 2D. A voir si ca consomme beaucoup.

----------


## doomeer

> c'est plus hardcore que ma version encore, mais ça serait l'idéal. Mais globalement tu as quand même une grille de collision coté client mais ta granularité est plus fine (ici 1/10 de case)
> […]
> Pour les joueurs je vise plutôt 200 places voir plus.


J’ai mis des exemples avec des 1/10e mais je pensais représenter la position par une paire de flottants, donc la granularité est celle des flottants en fait  ::P: 

200 joueurs ça va, les quadtrees ou assimilé seront pas nécessaires sauf si tu as vraiment beaucoup de tests de collision à la seconde.



> Ben c'est ce que je proposais. Pour la détection des collisions, tu peux faire ça via un vrai moteur physique, tu as même des librairies pour faire ça en javascript / 2D. A voir si ca consomme beaucoup.


Je pense que tant qu’il s’agit de tester si un cercle touche un autre cercle ou un carré (une case), le moteur physique est assez superflu ^^ Le test de collision entre deux cercles c’est deux lignes (suffit de tester si la distance est inférieure à la somme des rayons). Pour cercle-carré c’est plus chiant mais c’est pas la mort non plus.

----------


## rOut

Non mais tester juste des cercles ça signifie que tu dois garder les positions synchronisées. Je proposais de ne synchroniser que les changements de vitesse / direction, ce qui justifie le moteur physique pour les calculs. Ça permet aussi d'envisager des effets physiques de chocs, explosion, etc par exemple.

----------

