Comment gérer un grand nombre de micros dans un jeu MMO

Comment les jeux comme Minecraft, ou vraiment n'importe quel jeu MMO qui a des micros, les gèrent-ils?

Dites que le terrain génère 3 gouttes de "saleté" à chaque fois que vous creusez ledit terrain. Supposons que chaque élément possède une animation de rotation calculée à chaque image. Si le nombre de micros dans le monde devient très élevé, ce serait une surcharge massive inutile dans le calcul de la trame pour un client dans un serveur donné, car il est probable que beaucoup de ces éléments de micros sont à des années-lumière de vous.

Donc, ce que je pensais, c'est que vous ne devez "faire des trucs" qu'avec les micros proches du joueur local, mais cela impliquerait toujours que chaque image que je dois vérifier si un autre élément de ramassage soit suffisamment proche pour commencer à animer.

Ma vraie question est: comment les autres MMO ont résolu ce problème?

En ne chargeant simplement que les parties du monde en mémoire qui sont proches du joueur. Tout le reste est suspendu au disque dur. Lorsqu'il y a un petit objet posé à environ deux kilomètres de là, le joueur ne peut pas le voir et ne peut pas interagir avec lui. Il n'y a donc aucune raison de le mettre à jour ou de l'envoyer au GPU pour le rendu. Plus l'objet et sa plage d'interaction sont petits, plus la plage autour du lecteur où vous devez le charger est faible.

En ce qui concerne la découverte de ce qui est proche du joueur: cela revient essentiellement à stocker le monde dans une structure de données optimisée pour la recherche spatiale. Les bons candidats pour ceux-ci sont le hachage spatial et les arbres multidimensionnels .

Vous avez deux choses très différentes à gérer:

1. Le serveur doit gérer le monde entier, de manière autoritaire. Pour cela, une communication avec N clients (où N est "massif") est nécessaire.

2. Le client pourrait , en principe, connaître le monde entier, mais ce n'est pas nécessaire . Pour le client, il suffit de savoir ce qui se trouve à proximité du joueur. En supposant, par exemple, un partitionnement de type grille plutôt grossier, il faudrait qu'il ne connaisse que la cellule du joueur et les 26 cellules autour du joueur (ou 8 cellules si vous avez une grille 2D). Une grille un peu plus fine est préférable, mais vous avez l'idée.

Maintenant, beaucoup de micros, qu'est-ce que "beaucoup"? Vous creusez peut-être 5 choses par seconde, c'est peut-être deux douzaines de numéros qui doivent être mis à jour sur le serveur, et le serveur devra peut- être les transmettre à un autre joueur dont la zone d'intérêt chevauche votre cellule. Pour un ordinateur, il s'agit d'une quantité de données assez ridicule et d'une quantité de calcul négligeable. Cela peut devenir un défi quand il y a des centaines / milliers de joueurs dans la même cellule (alors votre partition est trop grossière).

Le serveur n'a pas besoin de connaître, ni de se soucier de la rotation des micros ou de tels détails. Pourquoi le ferait-il?

Le client ne s'en soucie pas non plus, car ce n'est qu'un régal pour les yeux que le client peut fabriquer à la volée.

Ce qui est nécessaire du point de vue du serveur, c'est de savoir que vous creusiez (30, 40, 50) dans le nœud dans lequel vous vous trouvez, et il décide que cela engendre par exemple trois objets de type 5, ou un objet de type 7 avec un compte de 3. C'est tout ce qui compte et c'est tout ce qu'il vous dit. Il inclura également ces informations dans les données envoyées à une personne déplaçant sa zone d'intérêt sur la cellule de la grille plus tard (en supposant qu'elle soit toujours là à ce moment-là).

On dit au client que trois objets y sont apparus, bla bla. Maintenant, que le client affiche une carte ASCII où il y a maintenant un `` D '' ou qu'il montre un tas de saleté en rotation, c'est la même chose. Que les piles aient des rotations différentes ou que seules celles proches de votre joueur tournent, c'est la même chose. C'est juste des choses qui s'affichent sur votre moniteur, cela n'affecte personne d'autre.

Donc, dans le cas concret où vous souhaitez faire pivoter uniquement les tas de saleté à proximité, vous pouvez simplement effectuer une vérification de la portée de tous les objets que vous connaissez. Étant donné que l'ensemble de données n'est pas volumineux, même la force brute sur tout fonctionnera.

Vous pouvez (et devriez) en fonction de la taille de votre partitionnement, tailler trivialement les cellules de grille trop éloignées.

Vous pouvez, bien sûr, sous-partitionner davantage votre cellule et utiliser quelque chose de super intelligent. Utilisez un kd-Tree si vous voulez, mais ne vous attendez pas à des gains énormes. Vous pouvez tailler des trucs avec Manhattan Distace, ou vous pouvez trier vos trucs dans une petite grille de votre choix ... mais pourquoi?

Un contrôle de distance (distance vraiment au carré, mais c'est la même chose pour vous) n'est que deux multiplications et un ajout (optimisé pour MUL, MADD, donc vraiment seulement deux opérations), suivi d'une branche ou d'un mouvement conditionnel. C'est à peu près aussi rapide que toute autre opération qui ne taille pas des cellules de grille entières à la fois. En fait, c'est quelque chose que vous pourriez même faire sur le GPU ...

En voyant comment vous aurez quelques centaines, ou tout au plus quelques milliers de contrôles de distance par rapport à la même position (la distance au carré fonctionne très bien), vous n'avez vraiment pas beaucoup de mal à faire ce calcul, d'autant plus que c'est plutôt un cache- itération amicale sur la mémoire contiguë, et avec des mouvements conditionnels, c'est très bon marché. Quelque chose comme (pseudocode) rot = r[i] + 1; r[i] = ((dx*dx+dy*dy) < DIST_SQ) ? rot : r[i];. C'est une itération sur un tableau de quelques centaines de valeurs par image. L'ordinateur s'en fiche de tout cela, ce sont des charges et des magasins contigus, une simple ALU, pas de succursales et seulement quelques milliers d'itérations.

Ce problème (plusieurs-à-un) n'est pas la même classe de problèmes (plusieurs-à-plusieurs) que sur le serveur. Vraiment, le client n'est pas le problème.

@ T.Sar écrit dans un commentaire que vous devriez vous pencher sur le concept de "morceau chargé" de Minecrafts pour plus d'informations. Si vous le faites, sachez que c'est assez compliqué dans Minecraft à cause des gens qui construisent des machines dans le jeu.

Une version très simplifiée suit:

Le monde est divisé en régions carrées (morceaux). Dans Minecraft, il y a également une division en hauteur, mais la plupart des mmos n'en ont pas besoin.

Le client du jeu ne se soucie que des régions proches du joueur. C'est beaucoup plus simple que de dessiner un cercle autour du joueur, mais parfaitement suffisant.

Dans Minecraft, les régions sont des blocs 16x16, et le client connaît les régions 9x9, 4 régions dans chaque direction. (4 régions est + le joueur régional est dans + 4 régions ouest = 9 régions au total. Même nord / sud)

Il n'y a rien de magique dans ces chiffres, utilisez ce qui a du sens dans votre jeu.

Le client anime uniquement les choses à l'intérieur de cette zone. Le serveur ne calcule que des choses comme les monstres errants dans les régions proches d' un joueur.

Lorsqu'un joueur se promène à l'intérieur d'une région, rien de spécial ne se produit, lorsqu'il traverse une frontière de région, le «bord de l'animation» est repoussé d'une région. Le client doit alors demander au serveur quelles régions il voit maintenant.

Il n'y a rien de mal à avoir plusieurs limites d'animation imbriquées. Par exemple, les objets animés tombent dans une zone 3x3, les monstres errants dans une zone 5x5 et montrent simplement le paysage dans une zone 9x9.

Le serveur conserve une "version figée" des régions qu'aucun joueur ne voit. Si cela prend beaucoup de mémoire, vous voudrez peut-être les décharger après un certain temps. Lorsqu'un joueur arrive ensuite, la région est rechargée sans que l'objet ne tombe. Vous devez être plus rapide la prochaine fois, joueur 1.