Discussion :

[cb-bk]

Bonjour,

Tout d'abord désolé si je ne poste pas dans la bonne section, ma question est liée à la structure de communication client serveur pour un jeu vidéo mais n'est pas un problème de code, juste de concept, je ne sais donc pas si je n'aurais pas mieux du poster dans la section réseau.
J'aimerais avoir votre avis :

Alors, l'idée est simple et pas originale pour 2 sous, écrire un serveur pour une application massivement multi-users en 2D. Users oui, car ce n'est pas vraiment un jeu, plus une application où l'on pourrait se déplacer et voir les autres utilisateurs connectés marcher à côté de nous (+ chat, + gestion de pas mal de trucs niveau donnée), en gros, je pense l'appli comme un jeu mais ça n'en est pas un

Ce que j'ai pour l'instant :
Quand je lance le serveur celui-ci lance un thread qui servira a servir les utilisateurs connectés (thread "service"), le premier thread lui écoute et accepte les connexions entrantes. Une fois un utilisateur connecté il est ajouté à un vecteur et un nouveau thread est lancé, qui contient le socket, pour recevoir les infos du client (touche enfoncée, ...) et calculer sa position.

De là j'ai quelques questions, j'ai pas mal pu me renseigner sur des serveurs déjà existant mais je n'ai pas toujours eu de réponse sur la façon précise dont ils faisaient les choses.
Je gère le mouvement de la façon suivante :
Le client envoi au serveur l'appuie sur une touche (touche UP enfoncée, touche UP relachée, ...) et de là le serveur (le thread client) calcule le déplacement en fonction du temps resté appuyé. A intervalle régulier le serveur (le thread de "service") interroge tous les threads clients pour connaitre leur position et envoi les données aux clients.
Pendant ce temps le client calcule lui aussi le déplacement (best quess) et corrige en fonction des données une fois reçues.

Déjà, est ce une bonne façon de faire? J'ai pu voir que certains jeux envoyaient des données au serveur à chaque frame quasiment, puis écoutaient immédiatement la réponse du serveur pour faire le rendu. Ici je n'envoie au serveur que des changements d'états et j'actualise le client à intervalle régulier. Il faut savoir qu'il ne s'agit justement pas d'un jeu et des légères desynchros sont tout a fait acceptables.

En suite, il faudrait que chaque client ne reçoive les coordonnées que des joueurs à proximité, et je ne sais pas trop comment faire, j'aimerais autant que possible éviter de devoir parcourir le vecteur entier de client alors qu'il n'y en aurait que quelques un de visible au final. J'ai tout de suite pensé aux quadtree, en définissant dès le début l'arbre, et avec chaque thread qui placerait l'utilisateur automatiquement là où il faut dans l'arbre, mais malheureusement cela reviendrait a beaucoup de manipulations de pointeurs au travers des threads et je ne sais donc pas si ça serait idéal (un thread liste un noeud pendant qu'un autre thread vient s'ajouter, ou s'enlève). J'avais aussi pensé à remplir l'arbre à chaque intervalle dans le thread de service et après a simplement dire aux threads client de ne n'envoyer au client que la partie qui les concerne. Qu'en pensez vous?
Au passage, j'ai toujours une zone d'ombre sur l'utilisation des quadtree, tant qu'un utilisateur est dans une zone on lui envoi les coordonnées de tous les joueurs dans cette même zone, mais dès qu'il arrive près d'une autre zone, que se passe t'il? il recoit les données qu'une fois entré dedans? :/ bien sur que non, il faut donc quasiement à chaque fois envoyer les positions de au moins 1 et au max 4 noeuds? P-e même que les quadtree ne sont pas du tout idéal pour cette utilisation, si vous avez des algo ou des conseils sur ça je suis preneur. Merci.

Je m'inquiète aussi, si il y a trop d'utilisateurs connectés (la cible de l'application concerne plus de 26000 personnes) n'y a t'il pas un risque de récupérer des données qui ne concerne pas le même temps?
A un temps T tout le monde est à une position X, mais le temps de lire toutes les coordonnées pour les envoyer aux clients, n'y a t'il pas un risque de l'utilisateur 0 soit en fait à une nouvelle position? l'instant T étant dépassé avec le temps du calcul..

Merci, encore désolé si je ne poste pas au bon endroit

[nouknouk]

Quelques réflexions :

Une fois un utilisateur connecté il est ajouté à un vecteur et un nouveau thread est lancé

Pour un grand nombre d'utilisateurs, le modèle "un thread par client" est moins efficace que l'utilisation d'un thread par groupe de clients (voire un thread pour tous les clients). Cf. la notion de select/poll (NIO en Java) qui permet d'avoir une attente bloquante d'un thread sur un groupe de sockets en attente de lecture.

la cible de l'application concerne plus de 26000 personnes

Alors là, on rentre dans un registre très particulier, car avec 26k clients, si tu veux mettre tout ça sur un unique serveur, cela reviendrait à dire que tu alloues pour chaque client un 'timeframe' moyen de ... 0.038 milliseconde, ou 38 microsecondes par seconde écoulée et par client.
Avec de tels chiffres, pas besoin de faire un dessin: c'est intenable même avec un énorme serveur.

Il faut donc voir dès le départ pour travailler sur un cluster de serveurs tournant en parallèle, du partitionnement de l'espace, etc...

Retour sur terre: Ces techniques sont extrêmement complexes et demandent une énorme expérience dans plusieurs domaines (parallélisation, réseau, ...). Autant dire que seuls quelques professionnels hautement pointus dans ces domaines sont capables de pondre une architecture viable pour du massivement online à cette échelle.

Je ne parlerai même pas des besoins en infrastructure réseau (et en bande passante: de l'ordre du Gigabit/sec !) et les besoins en serveurs qui représentent à eux seuls un coût énorme.

[cb-bk]

Ok merci pour ta première remarque, je viens de chercher sur internet et je suis tombé sur cette article :
http://kovyrin.net/2006/04/13/epoll-...k-programming/
Qui présente bien comment gérer plusieurs sockets sur un seul thread.

Concernant les 26k utilisateurs en effet, si je veux pouvoir accueillir une charge aussi énorme c'est pas possible ^^ heureusement c'est que la cible, en gros il y aura maximum 26k d'inscrits, après j'espère qu'ils ne viendront pas tous en même temps , mais ça devrait aller. Je fixerais surement une limite haute de connectés, 1000 ou 2000 semble plus raisonnable? Sur le genre de serveur dédié que l'on trouve chez OVH ou autre hébergeurs, enfin encore ça ne sera pas trop compliqué de faire quelques stress tests une fois le serveur en place.

Concernant mes autres questions (voir les utilisateurs autour de soi en utilisant les quadtree), a tu une idée?

merci

[nouknouk]

Je fixerais surement une limite haute de connectés, 1000 ou 2000 semble plus raisonnable?

Etant donné que ça fait 26 fois moins, c'est forcémenet plus raisonnable, tout au moins envisageable pour un seul serveur.

Sur le genre de serveur dédié que l'on trouve chez OVH ou autre hébergeurs, enfin encore ça ne sera pas trop compliqué de faire quelques stress tests une fois le serveur en place.

A partir de là tout dépend de ce que ton serveur doit faire comme traitement ! Il y a une incroyable différence entre les extrêmes:
- du serveur qui relaie "bêtement" les flux de données d'un client aux autre clients situés à proximité
- au serveur qui gère un monde en 3D, avec moteur physique pour animer des interactions complexes d'objets (une pyramide de boites de conserve qui se casse la figure), les collisions de tous les joueurs avec l'environnement, les autres clients, etc...

L'option 1 pourrait faire tenir 1000 ou 2000 joueurs en simultané sans souci sur un serveur basique type RPS à 10€ / mois chez OVH. Le facteur limitant pourrait même arriver plus vite à cause de la bande passante (10Mbits en continu chez OVH, et 100Mbits uniquement en 'pic occasionnel') que du côté des capacités de traitement du processeur du serveur.

L'option 2 te permettra de gérer au mieux quelques dizaines de clients au total sur un serveur Dual ou Quadri Core haut de gamme d'OVH. Clairement, la limite sera la capacité de ton processeur à calculer la physique, les collisions, ...

Concernant mes autres questions (voir les utilisateurs autour de soi en utilisant les quadtree), a tu une idée?

A nouveau, tout dépend de ce que tu veux faire. Il y a beaucoup de possibilités plus ou moins complémentaires:
- Du partitionnement basique (une map de 300x300 est subdivisée en sous parties fixes de 10x10 et seules les infos qui changent des quelques parties de 10x10 aux alentours de ton client sont transmises)
- Au partitionnement dynamique (les subdivisions évoluent au cours du temps en fonction de la concentration de 'charge' de chaque partie de la map (plus il y a de charge dans un endroit restreint, plus cet endroit sera subdivisé)
- En passant par une trnasmission adaptative des mises à jour en fonction des besoins en précision (je recevrai un update toutes les 50ms des actions du joueur juste à côté de moi ; un update toutes les 2000ms du joueur situé plus loin, à la limite de mon champ de vision), etc...

Il y a énormément d'autres paramètres, notamment le(s) type(s) d'interactions entre les clients nécessitant plus ou moins de 'temps réel', les choix ergonomiques (un déplacement avec pathfinding en cliquant sur la destination - genre RTS - n'a rien à voir en termes réseaux avec un déplacement contrôlé par les touches et/ou la souris genre FPS), etc..., etc..., etc...

Bref:

- autant on pouvait d'ores et déjà dire qu'une solution supportant 26k utilisateurs n'était pas envisageable quelle que soit le reste des choix faits.

- autant quand on revient à une base "plus réaliste", il faut ensuite connaître un maximum de détails concrets pour pouvoir non seulement dimensionner un minimum le système à priori mais également pour choisir les techniques à utiliser pour l'implémentation (réseau, optimisation des calculs, ...).

[Mat.M]

Tu veux faire une sorte de Second Life mais avec Chat en quelque sorte?

Quand je lance le serveur celui-ci lance un thread qui servira a servir les utilisateurs connectés (thread "service"),

Avant de passer à la programmation multithreading qui est complexe je conseille de commencer avec un simple timer et 2 ou 3 entités clientes.

De là j'ai quelques questions, j'ai pas mal pu me renseigner sur des serveurs déjà existant mais je n'ai pas toujours eu de réponse sur la façon précise dont ils faisaient les choses.
Je gère le mouvement de la façon suivante :
Le client envoi au serveur l'appuie sur une touche (touche UP enfoncée, touche UP relachée, ...) et de là le serveur (le thread client) calcule le déplacement en fonction du temps resté appuyé

Non je ne ferais pas comme cela .
Pour l'interaction avec son avatar j'effectuerais la gestion entièrement coté client pour ne transmettre qu'au serveur les nouvelles coordonnées au serveur.
Si tu envoies au serveur une commande du genre "touche UP appuyée" et que le serveur calcule tout tu risques d'avoir des problèmes de désynchronisation ou de latence..

tu as parlé de vecteur tu peux parfaitement utiliser une Finite State Machine ou machine à état c'est à dire que c'est une pile qui comporte des commandes pour chaque avatar que tu envoies au serveur


Ceci dit je te conseille plutot de mettre en pratique tout cela plutot que de rester dans la théorie.
La théorie c'est bien mais il y a souvent de grandes différences avec la mise en pratique.
Donc tu auras aussi vite fait de commencer des bouts de code et faire des ajustements plutot que de se poser des questions existentielles.
Bien sur il faut savoir là ou on veut aller

PS j'ai un projet similaire

[cb-bk]

Concernant l'application le serveur n'aurait pas grand chose à gérer, du moins comparé a des jeux en 3D avec moteur physique et tout le tralala.
Ici pas de path finding non plus, l'utilisateur se déplace avec les flèches du clavier et le serveur renvois la position. Quoi que je repenserais à la navigation au clic, à voir ce qui sera le plus intuitif pour les futurs utilisateurs. En gros tu peux voir le coeur de l'appli comme un GTA 1 "peace" (pas de quêtes ni rien, pas d'armes, pas de cibles, ...). Il y aura surement des PNJ mais rien de bien compliqué.

La seule vérification que devra faire le serveur au niveau positionnement c'est les collisions avec les bâtiments sur le monde, même pas dit que l'on gère les collisions entre joueurs.

L'appli comportera quelques mini jeux, là aussi le serveur devra intervenir vu qu'ils seront multijoueurs (1-8 joueurs max).

Merci pour les infos pour les subdivisions je vais essayer de me renseigner sur les "dynamic space partitionning"

>Mat.M
J'ai déjà écrit un mini jeu de course multithreaded pour 4 joueurs (affichage tout en console win32 << geek inside, il marche pas mal d'ailleurs ) et là tant que j'écris les specs du projet je préfère ne pas commencer a coder (le projet n'est pas encore sure de partir) ^^ mais j'y réfléchit en fonction des questions que je m'était posé pour mon premier jeu.
Sinon au niveau des mouvement gérés par le client humm... c'est sur que rien n'est sensible sur l'appli mais dans un soucis de travail bien fait je préfère ne pas laisser une porte grande ouverte aux utilisateurs qui se téléporteront + fly hack + speed hack etc

[nouknouk]

pas grand chose à gérer[...]pas de path finding non plus[...]peace[...]rien de bien compliqué[...]collisions[...]quelques mini jeux[...]

Attention, ici c'est encore plus vrai qu'ailleurs: l'enfer se cache dans les détails, et un choix qui peut paraître anodin au départ peut à lui seul faire tomber la capacité en nombre de clients de ton serveur de façon impressionnante.

Deux exemples tous cons:

- tous tes petits jeux sont des jeux en tour par tour (jeu de carte, puissance 4, poker, ...) sauf un qui est un pong (=> gros besoins en temps réel)

- contrairement à ce que tu sembles croire:
* le pathfinding ne requiert quasiment rien en calculs côté serveur (le client lui enverra ce qu'il aura calulé le serveur vérifiera basiquement une fois pour toutes), ni en bande passante => un paquet de quelques centaines d'octets avec une liste de points à recevoir et relayer pour le serveur ; le délai de transmission n'est pas critique (sur un chemin planifié de 10sec, on peut rattrapper quelques centaines de ms côté client sans souci).
* par contre, un système de guidage "aux flêches clavier" implique un update envoyé par chaque client toutes les xx millisecondes, de la prédiction côté client (dead reckoning, etc...) => gros besoins en "temps réel", en bande passante, en calcul côté serveur.

Je le redirai même une seconde fois tellement c'est d'autant plus critique que tu ne t'es visiblement jamais frotté à ce genre de joyeuseté: l'enfer se cache dans les détails !

Amha, un préalable totalement indispensable est de faire une liste exhaustive des fonctionnalités que tu comptes implémenter, et dimensioner précisément pour chacune d'entre elles (à l'aide de proof of concepts par exemple):
- les besoins et la fréquence des calculs côté client
- les besoins et la fréquence des calcul côté serveur
- les besoins en réseau (bande passante, QoS, latence, temps de réponse du serveur, fréquence des paquets, ...).

PS:

PS j'ai un projet similaire

Ca m'intéresse ! On a droit à un spoiler ?

re-PS: moi aussi (parlons plutôt de proof of concept, pas plus).

[cb-bk]

Je regarde tout ça.

[Mat.M]

Salut,

@ Cb-Bk j'ai visité ton site web belles réalisations
Ok c'est bien compris pour le jeu de course

@Nouknouk: c'est simplement une idée de projet.
Je ferais cela éventuellement avec Direct3d et sockets TCP-IP
Il faut que je finisse mon jeu de tactique temps réel de batailles napoléoniennes présenté ici dans la section "Forum"
J'aimerais y implémenter la partie réseau 2 joueurs

[Sivrît]

Tu pourrais peut-être regarder du côté de stendhal. C'est un rpg multijoueur en 2d. Je ne sais pas à quel point c'est massif, mais ça me semble assez proche de ce que tu cherches à faire. Ça pourrait être intéressant de voir quels écueils ils ont rencontrés.

[cb-bk]

Sympa Sivrit, apperement Stendhal a été développé avec Arianne, un framework open source pour faire des jeux en lignes. Je suis au boulot là donc je n'ai pas passé trop de temps mais je regarderais du côté de leur serveur Marauroa les choix qu'ils ont fait.
Merci Mat.M

[unmanos]

Bonjour,

Comme l’on dit plusieurs personnes, l’idée d’utiliser un thread pour chaque client dans le cadre d’un serveur MMO me parait très mauvaise, d’autant que contrairement a un serveur de mail ou ftp, il y a énormément d’interaction entre les différents utilisateurs, tu risque de passer beaucoup de temps dans des locks et t’arracher les cheveux (ou autre chose) quand il faudra debugger un dead locks qui se produit uniquement sur les serveurs releases (que de bons souvenirs).

Même en ayant un serveur minimaliste, il me parait difficile de faire tourner 26K clients en simultané, ne serait ce que pour la gestion bas niveau (sockets, sécurité, système). Il faut donc trouver un architecture qui puisse fonctionner avec des clusters, et la franchement d’expérience c’est possible mais pas simple, surtout quand il y a un grand niveau d’interactivité entre les objets ^^

Il y aussi quelque chose qu’on oublie très souvent, c’est qu’un serveur de jeux ce n’est pas juste une application passive qui se contente de distribuer l’information aux clients… Idéalement ca doit être une application active, capable de faire des tests de collision et de prendre des décisions de manière autonome. A mon avis, le serveur fait partie du jeu et ne doit pas être considéré comme une application a part.

Ps : moi aussi j’ai un projet similaire que je développe avec mon frangin.

[cb-bk]

Le rôle de mon serveur serra:
Calculer les déplacements des utilisateurs en fonction des touches appuyés
Renvoyer la position calculée ainsi que celle des utilisateurs environnant
Dispatcher les messages instantanés entre les utilisateurs

Il faut donc de la "géolocalisation", là j'ai cette solution :
Créer un quadtree au chargement du monde et associer les utilisateurs à un noeud selon leur position, à chaque rafraichissement le serveur envoie aux users les coordonnées de toutes les personnes du noeud.
Quand un user se déplacera il faudra donc dynamiquement le faire passer d'un noeud à l'autre.

Ici ça peut être pas mal d'avoir un thread par noeud? qui gérerait tous les users présent et dispatcherait le user à un autre thread (créé si besoin) dès que le joueur quitte la zone. T'en penses quoi?

P.S : 26k c'est le nombre de personnes dans la cible, après ils ne seront pas tous connectés en même temps ^^ (j'espère )

[unmanos]

Difficile a dire ca depend de ton monde. Pour ce genre de chose j'aurais tendance a plutot utiliser une dbvt (Dynamic Bounding Volume Tree) beaucoup plus efficace pour ce genre d'application (peut supporter beaucoup d'update/query). Ca peut aussi servir pour les collisions cote client et cote serveur.

Il y a une bonne implementation dans la lib de physique bullet.