Discussion :

[sakipu]

Hello,

Je suis en train de développer un jeu avec des amis.

Une bonne partie des échanges réseaux est implémentée et je pensais attaquer maintenant l'indexation spatiale.

Le client utilisera la structure de donnée de son moteur 3d je suppose, qui gerera les requetes spatiales, les colisions, etc...
Mais du coté du serveur, je ne dois gerer pratiquement que les requetes spatiales.

Je n'ai que peu d'expérience dans ce genre de développement. J'ai donc commencer à me plonger dans le r tree qui me parait adapté.

Je post en fait pour vous présentér la façon dont je pensais gerer les échanges concernant les différents éléments visibles et mobiles, et voir si je suis dans le bon.

J'imagine donc que lorsque l'on démarre le serveur, il va charger ce r tree.
Quand il doit envoyer ce genre de données(éléments visibles et mobiles) au client, ce dernier va recevoir les éléments et les charger dans son moteur. Et c'est ce moteur qui dira visible ou pas.
En gros on calcule une fois de chaque coté, ce n'est pas un problème en soi...

Donc si ça se déroule de cette manière, le serveur parcourera l'arbre sans arret pour trouver les éléments visibles pour chaque client (il y a surement de l'opti à faire, mais globalement...).

Voila, je pense que en gros ce post décrit la façon dont je pensais procéder.
Qui est peut-être loin de la façon plus "conventionelle"...

Je vous remercie d'avance...

[kain_tn]

Hello!

Tu peux peut-être faire un tour sur le site de Mangos; tu trouveras peut-être ton bonheur dans leur documentation Doxygen.

Si tu arrive à une solution intéressante, ça peut être utile de la partager sur le forum au vu du nombre de réponses que tu as eu pour ton post!

[Emmanuel Deloget]

Que ce soit le client qui teste la visibilité, c'est une mauvaise idée. Tu te retrouvera plus vite que tu ne le pense avec des clients qui voient tout (ne serais-ce qu'en analysant le protocole).

Pourquoi demander au client de recalculer ce que le serveur a déja calculé ? Autant envoyer au client juste les données nécessaires, et point final. En utilisant la notion de cohérence spatiale, le serveur doit pouvoir effectuer le tri visible/pas visible de manière efficace. Il ne fait pas ce parcours sans arrêt, il le fait toutes les N millisecondes si quelque chose (PJ, PNJ ou même élément du décors ...) a bougé (ce qui sera probablement le cas).

[sakipu]

Merci pour vos réponses,

j'ai épluché un peu mangos mais c'est pas évident.
J'ai donc commencé...

Donc en gros le serveur ne fait rien si rien ne se passe.

Si un client bouge, tous les autres clients recevront son nouveau segment, et ce client qui a bougé se verra updater son champs de visiblité.
Si quoique ce soit d'autre bouge, ce sera envoyé aux clients ayant une visiblité dessus.

De cette manière, un client aura toujours une vue à jour je pense.

Il y a tout de même un minimum d'écart de millisecondes pour envoyer un paquet entres 2 mouvements d'un même client.

Voila, qu'en pensez vous ? Ca fait quand même pas mal de petits paquets...


Merci

[Emmanuel Deloget]

Merci pour vos réponses,

j'ai épluché un peu mangos mais c'est pas évident.
J'ai donc commencé...

Donc en gros le serveur ne fait rien si rien ne se passe.

Si un client bouge, tous les autres clients recevront son nouveau segment, et ce client qui a bougé se verra updater son champs de visiblité.
Si quoique ce soit d'autre bouge, ce sera envoyé aux clients ayant une visiblité dessus.

De cette manière, un client aura toujours une vue à jour je pense.

Il y a tout de même un minimum d'écart de millisecondes pour envoyer un paquet entres 2 mouvements d'un même client.

Voila, qu'en pensez vous ? Ca fait quand même pas mal de petits paquets...


Merci

C'est pour ça qu'il existe des algorithmes qui contrent la latence. TU peux faire des recherches google sur "latency" et "dead reckoning" pour t'aider.

[Mindiell]

Le client utilisera la structure de donnée de son moteur 3d je suppose, qui gerera les requetes spatiales, les colisions, etc...

Tout comme les objets visibles, le client ne doit pas gérer les collisions. C'est au serveur de le faire, sinon tu verras apparaitre des clients qui "traverseront" les murs...

Pour moi, toute commande client doit aller au serveuur qui renvoit simplement les positions de tous les objets/persos régulièrement, voire une confirmation. Mais, pour moi, il est plus simple de renvoyer régulièrement les positions, caracs des objets/persos : suivant les demandes clients bien entendu.

[SoniX]

Certains choix dépendent du type de jeux, de la vitesse des déplacements des joueurs, du temps de réaction que tu considères comme tolérable.

Je suppose que tu décris un jeux avec un contrôle directe de l'avatar (contrairement au mode 'point & click'), qui est le plus critique à réalisé.
La solution la plus simple consiste à faire tous les traitement (déplacement, collision, visibilité) sur le serveur.
Mais c'est aussi celle qui amène le plus grand 'lag' au niveau client, ce qui est généralement insupportable (hormis en réseau local, ou dans qlq cas particulier).
Dans ce cas, ton client n'est plus qu'un afficheur/transmetteur de commande et tu es sur de n'avoir jamais de désynchros.

Si tu veux plus de dynamique pour les mouvements des avatars (cas général donc), il faut avoir recours à une combinaison de techniques complémentaires pour supporter le lag et les incohérences générées entre les clients et le serveur.
Le client doit géré les collisions, puisque qu'il gére les déplacement de l'avatar localement. Mais le serveur doit aussi géré les collision et exclure ou 'recaler' les client qui serait hors des zones accessible.
Le client doit également gérer les déplacement 'fluides' des autres clients entre deux mise à jour serveur (un genre d'interpolation/extrapolation).
Côté serveur, selon le nombre de joueur/bots que tu souhaites géré, il peut être utile de géré la fréquence des envois d'information en fonction de la distance par rapport à un joueur (on envoi moins fréquement les déplacement des trucs qui sont loin)

Concernant le nombre de petit paquets, c'est incontournable dans ce type de jeux (en contrôle direct), comme les joueurs on la liberté de bouger tout le temps comme ils veulent, les mises à jour de positions et autres informations circulent en permanence. C'est la 'base' de ce genre de jeux.
Tu peux quantifier les déplacement dans le temps en utilisant une base de temps fixe pour l'envoi des changement de position (client vers serveur et serveur vers clients), ceci te permet de maîtriser la bande passante VS précision et qualité des mouvements.

Ce qu'il faut savoir, c'est plus ton jeu utilise des temps de réponse court, plus ca sera difficile ! Dans un MMORTS classique, les combat dure plusieurs secondes et les décalage de positionnement d'un client par rapport a l'autre n'ont pas une grande influence. Par contre, dans un jeu type Unreal, le temps de réaction est très court et les positions sont critique, et il faut des système biens plus complexe côté client et serveur pour que ca marche.

[sakipu]

Merci pour ces réponses précieuses.

C'est effectivement un jeu ou on contrôle un personnage directement.

Donc pour le moment les update se passent comme ça:

coté serveur:
J'ai un moteur dans lequel je met les objets suceptibles de bouger. Il utilise un système de dead reckoning pour simuler les mouvements de tout objet mobile, et comme tout est centralisé là, je peux gerer les intervalles de temps pour envoyer les update.
Les objets sont dans un rtree. Quand j'envoie des update d'objets à un client, je prends ce qu'il y a autours de lui à une distance x, avec, à la limite, un système qui check s'il y a vraiment besoins d'update (il faut voir si j'y gagne vraiment en trafic réseau par rapport au temps cpu).
J'hésite à utiliser un BSP a coté du rtree uniquement pour gerer les collisions, ou bien tout mettre directement dans le rtree.
Les locs seront adaptées aux update venant du client évidemment pour ne pas avoir 2 mondes différents.

coté client:
Il gère aussi les collisions dans un bsp + un système de dead reckoning pour les autres objets + un rtree afin qu'il puisse "passiver" les objets "trop loin" dont il n'a pas envie de faire des calculs inutiles.
Il envoie ses update quand il change de vitesse ou de direction,avec un peu de souplesse pour éviter un flood d'update.


Ca fait pas mal de calcul des 2 cotés, m'enfin c'est dur d'éviter ça. Si vraiment ça ram de trop coté client, il faudra une solution, mais en attendant ça va.
Je compte tout de même optimiser un max ces calculs récurrents.


Merci encore, c'est vraiment intéressant.

[gusgus]

Je te conseil de jeter un coup d'oeuil a ce site pour les collisions:
http://www.gaffer.org/game-physics/networked-physics

Comme dit précédemment, il faudrait préciser le type de jeux viser: 1 seconde de latence est-elle acceptable?Cela changera radicalement les algo.

[sakipu]

Très instructif, ce lien merci.

Le type de jeu serait un mmorpg (et oui encore...).
Une seconde de latence est donc inacceptable.

Pour un peu de détail technique, serveur et client sont implémentés en java, ils utilisent java.nio pour le réseau. Le client utilise jmonkey comme moteur 3d.

Voila, je ne sais pas trop quoi préciser sans partir dans un long roman.

Mais en gros, ça demande des algos assez complexes pour ce genre de calcul.