Quel est le conteneur le plus efficace pour stocker des objets de jeu dynamiques? [fermé]

20

Je fais un jeu de tir à la première personne et je connais beaucoup de types de conteneurs différents, mais je voudrais trouver le conteneur le plus efficace pour stocker des objets dynamiques qui seront ajoutés et supprimés du jeu assez fréquemment. EX-Bullets.

Je pense que dans ce cas, ce serait une liste pour que la mémoire ne soit pas contiguë et qu'il n'y ait jamais de redimensionnement en cours. Mais j'envisage également d'utiliser une carte ou un ensemble. Si quelqu'un a des informations utiles, je l'apprécierais.

J'écris ceci en c ++ d'ailleurs.

J'ai également trouvé une solution qui, je pense, fonctionnera.

Pour commencer, je vais allouer un vecteur de grande taille. Disons 1000 objets. Je vais garder une trace du dernier index ajouté dans ce vecteur pour que je sache où sont les fins des objets. Ensuite, je vais également créer une file d'attente qui contiendra les indices de tous les objets qui sont "supprimés" du vecteur. (Aucune suppression réelle ne sera effectuée, je saurai juste que cet emplacement le libère). Donc, si la file d'attente est vide, j'ajouterai au dernier index ajouté dans le vecteur + 1, sinon j'ajouterai à l'index du vecteur qui était à l'avant de la file d'attente.

msawayda
la source
Une langue spécifique que vous ciblez?
Phill.Zitt
Cette question est trop difficile à répondre sans un bon nombre de détails supplémentaires, y compris la plate-forme matérielle, le langage / les frameworks, etc.
PlayDeezGames
1
Conseil de pro, vous pouvez stocker la liste gratuite dans la mémoire des éléments supprimés (vous n'avez donc pas besoin de la file d'attente supplémentaire).
Jeff Gates
2
Y a-t-il une question dans cette question?
Trevor Powell
Notez que vous n'avez pas à garder la trace du plus grand index ni à préallouer un certain nombre d'éléments. std :: vector s'occupe de tout cela pour vous.
API-Beast

Réponses:

33

La réponse est toujours d'utiliser un tableau ou std :: vector. Les types comme une liste chaînée ou une carte std :: map sont généralement absolument horribles dans les jeux, et cela inclut certainement des cas comme des collections d'objets de jeu.

Vous devez stocker les objets eux-mêmes (pas des pointeurs vers eux) dans le tableau / vecteur.

Vous voulez une mémoire contiguë. Vous en avez vraiment très envie. L'itération de toutes les données dans la mémoire non contiguë impose un grand nombre de manquements au cache en général et supprime la possibilité pour le compilateur et le CPU d'effectuer une prélecture du cache efficace. Cela seul peut tuer les performances.

Vous souhaitez également éviter les allocations de mémoire et les désallocations. Ils sont très lents, même avec un allocateur de mémoire rapide. J'ai vu des jeux obtenir une bosse FPS 10x en supprimant simplement quelques centaines d'allocations de mémoire à chaque image. Il ne semble pas que ça devrait être si mauvais, mais ça peut l'être.

Enfin, la plupart des structures de données dont vous vous souciez pour la gestion des objets de jeu peuvent être implémentées de manière beaucoup plus efficace sur un tableau ou un vecteur qu'avec un arbre ou une liste.

Par exemple, pour supprimer des objets de jeu, vous pouvez utiliser swap-and-pop. Facilement implémenté avec quelque chose comme:

std::swap(objects[index], objects.back());
objects.pop_back();

Vous pouvez également simplement marquer les objets comme supprimés et mettre leur index sur une liste gratuite pour la prochaine fois que vous devez créer un nouvel objet, mais il est préférable de faire le swap-and-pop. Il vous permet de faire une boucle for simple sur tous les objets vivants sans ramification à part la boucle elle-même. Pour l'intégration de la physique des balles et similaires, cela peut être une amélioration significative des performances.

Plus important encore, vous pouvez trouver des objets avec une simple paire de recherches de table à partir d'une stabilité unique en utilisant la structure de la carte des emplacements.

Vos objets de jeu ont un index dans leur tableau principal. Ils peuvent être recherchés très efficacement avec juste cet index (beaucoup plus rapide qu'une carte ou même une table de hachage). Cependant, l'index n'est pas stable en raison du swap et du pop lors de la suppression d'objets.

Une carte de slot nécessite deux couches d'indirection, mais les deux sont de simples recherches de tableaux avec des indices constants. Ils sont rapides . Très rapide.

L'idée de base est que vous avez trois tableaux: votre liste d'objets principale, votre liste d'indirection et une liste gratuite pour la liste d'indirection. Votre liste d'objets principale contient vos objets réels, où chaque objet connaît son propre ID unique. L'ID unique est composé d'un index et d'une balise de version. La liste d'indirection est simplement un tableau d'index de la liste d'objets principale. La liste libre est une pile d'index dans la liste d'indirection.

Lorsque vous créez un objet dans la liste principale, vous trouvez une entrée inutilisée dans la liste d'indirection (à l'aide de la liste libre). L'entrée dans la liste d'indirection pointe vers une entrée inutilisée dans la liste principale. Vous initialisez votre objet à cet emplacement et définissez son ID unique sur l'index de l'entrée de liste d'indirection que vous avez choisie et la balise de version existante dans l'élément de liste principal, plus un.

Lorsque vous détruisez un objet, vous effectuez le swap-and-pop comme d'habitude, mais vous incrémentez également le numéro de version. Vous ajoutez ensuite également l'index de liste d'indirection (partie de l'ID unique de l'objet) à la liste libre. Lorsque vous déplacez un objet dans le cadre du swap-and-pop, vous mettez également à jour son entrée dans la liste d'indirection vers son nouvel emplacement.

Exemple de pseudo-code:

Object:
  int index
  int version
  other data

SlotMap:
  Object objects[]
  int slots[]
  int freelist[]
  int count

  Get(id):
    index = indirection[id.index]
    if objects[index].version = id.version:
      return &objects[index]
    else:
      return null

  CreateObject():
    index = freelist.pop()

    objects[count].index = id
    objects[count].version += 1

    indirection[index] = count

    Object* object = &objects[count].object
    object.initialize()

    count += 1

    return object

  Remove(id):
    index = indirection[id.index]
    if objects[index].version = id.version:
      objects[index].version += 1
      objects[count - 1].version += 1

      swap(objects[index].data, objects[count - 1].data)

La couche d'indirection vous permet d'avoir un identifiant stable (l'index dans la couche d'indirection, où les entrées ne se déplacent pas) pour une ressource qui peut se déplacer pendant le compactage (la liste d'objets principale).

La balise de version vous permet de stocker un ID dans un objet qui pourrait être supprimé. Par exemple, vous avez l'id (10,1). L'objet avec l'index 10 est supprimé (par exemple, votre balle frappe un objet et est détruite). L'objet à cet emplacement de mémoire dans la liste d'objets principale a alors son numéro de version bumpé, lui donnant (10,2). Si vous essayez de rechercher à nouveau (10,1) à partir d'un ID périmé, la recherche renvoie cet objet via l'index 10, mais peut voir que le numéro de version a changé, de sorte que l'ID n'est plus valide.

Il s'agit de la structure de données la plus rapide que vous puissiez avoir avec un ID stable qui permet aux objets de se déplacer dans la mémoire, ce qui est important pour la localisation des données et la cohérence du cache. C'est plus rapide que n'importe quelle implémentation d'une table de hachage possible; une table de hachage doit à tout le moins calculer un hachage (plus d'instructions qu'une recherche de table), puis doit suivre la chaîne de hachage (soit une liste chaînée dans le cas horrible de std :: unordered_map, soit une liste d'adresses ouvertes dans toute implémentation non stupide d'une table de hachage), puis doit faire une comparaison de valeur sur chaque clé (pas plus cher, mais peut-être moins cher, que la vérification de la balise de version). Une très bonne table de hachage (pas celle de n'importe quelle implémentation de la STL, car la STL exige une table de hachage qui optimise pour différents cas d'utilisation que ceux auxquels vous jouez pour une liste d'objets de jeu) pourrait économiser sur une indirection,

Il existe différentes améliorations que vous pouvez apporter à l'algorithme de base. Utiliser quelque chose comme un std :: deque pour la liste d'objets principale, par exemple; une couche supplémentaire d'indirection, mais permet aux objets d'être insérés dans une liste complète sans invalider les pointeurs temporaires que vous avez acquis à partir du slotmap.

Vous pouvez également éviter de stocker l'index à l'intérieur de l'objet, car l'index peut être calculé à partir de l'adresse mémoire de l'objet (this - objets), et encore mieux n'est nécessaire que lors de la suppression de l'objet, auquel cas vous avez déjà l'id de l'objet (et donc index) comme paramètre.

Excuses pour la rédaction; Je ne pense pas que ce soit la description la plus claire possible. Il est tard et il est difficile de l'expliquer sans passer plus de temps que moi sur des exemples de code.

Sean Middleditch
la source
1
Vous échangez un deref supplémentaire et un coût d'allocation / gratuit (swap) élevé à chaque accès pour un stockage «compact». D'après mon expérience avec les jeux vidéo, c'est un mauvais métier :) YMMV bien sûr.
Jeff Gates
1
Vous ne faites pas vraiment la déréférence que souvent dans des scénarios du monde réel. Lorsque vous le faites, vous pouvez stocker le pointeur renvoyé localement, surtout si vous utilisez la variante deque ou si vous savez que vous ne créerez pas de nouveaux objets tant que vous aurez le pointeur. Itérer sur les collections est une opération très coûteuse et fréquente, vous avez besoin de l'ID stable, vous voulez un compactage de la mémoire pour les objets volatils (comme les balles, les particules, etc.), et l'indirection est très efficace sur le matériel du modem. Cette technique est utilisée dans plusieurs moteurs commerciaux à très hautes performances. :)
Sean Middleditch
1
D'après mon expérience: (1) Les jeux vidéo sont jugés sur les performances les plus défavorables, et non sur les performances moyennes des cas. (2) Vous avez normalement 1 itération sur une collection par trame, donc le compactage «rend votre pire cas moins fréquent». (3) Vous avez souvent plusieurs allocations / libérations dans une seule trame, le coût élevé signifie que vous limitez cette capacité. (4) Vous avez des derefs illimités par image (dans les jeux sur lesquels j'ai travaillé, y compris Diablo 3, souvent le deref était le coût de perf le plus élevé après une optimisation modérée,> 5% de la charge du serveur). Je ne veux pas rejeter d'autres solutions, juste pour souligner mes expériences et mon raisonnement!
Jeff Gates
3
J'adore cette structure de données. Je suis surpris que ce ne soit pas plus connu. C'est simple et résout tous les problèmes qui me font me cogner la tête depuis des mois. Merci d'avoir partagé.
Jo Bates
2
Tout débutant lisant ceci devrait se méfier de ce conseil. C'est une réponse très trompeuse. "La réponse est toujours d'utiliser un tableau ou std :: vector. Les types comme une liste chaînée ou une std :: map sont généralement absolument horribles dans les jeux, et cela inclut certainement des cas comme des collections d'objets de jeu." est grandement exagéré. Il n'y a pas de réponse "TOUJOURS", sinon ces autres conteneurs n'auraient pas été créés. Dire que les cartes / listes sont "horribles" est aussi une hyperbole. Il y a BEAUCOUP de jeux vidéo qui les utilisent. "Le plus efficace" n'est pas "le plus pratique" et peut être interprété comme un "meilleur" subjectif.
user50286
12

tableau de taille fixe (mémoire linéaire)
avec liste libre interne (O (1) alloc / free, indices stables)
avec des clés de référence faibles (la réutilisation de l'emplacement invalide la clé)
zéro déréférences de surcharge (quand elles sont connues-valides)

struct DataArray<T>
{
  void Init(int count); // allocs items (max 64k), then Clear()
  void Dispose();       // frees items
  void Clear();         // resets data members, (runs destructors* on outstanding items, *optional)

  T &Alloc();           // alloc (memclear* and/or construct*, *optional) an item from freeList or items[maxUsed++], sets id to (nextKey++ << 16) | index
  void Free(T &);       // puts entry on free list (uses id to store next)

  int GetID(T &);       // accessor to the id part if Item

  T &Get(id)            // return item[id & 0xFFFF]; 
  T *TryToGet(id);      // validates id, then returns item, returns null if invalid.  for cases like AI references and others where 'the thing might have been deleted out from under me'

  bool Next(T *&);      // return next item where id & 0xFFFF0000 != 0 (ie items not on free list)

  struct Item {
    T item;
    int id;             // (key << 16 | index) for alloced entries, (0 | nextFreeIndex) for free list entries
  };

  Item *items;
  int maxSize;          // total size
  int maxUsed;          // highest index ever alloced
  int count;            // num alloced items
  int nextKey;          // [1..2^16] (don't let == 0)
  int freeHead;         // index of first free entry
};

Gère tout, des balles aux monstres, des textures aux particules, etc. C'est la meilleure structure de données pour les jeux vidéo. Je pense que cela venait de Bungie (à l'époque du marathon / mythe), je l'ai appris à Blizzard, et je pense que c'était dans un jeu de programmation des joyaux à l'époque. C'est probablement partout dans l'industrie des jeux à ce stade.

Q: "Pourquoi ne pas utiliser un tableau dynamique?" R: Les tableaux dynamiques provoquent des plantages. Exemple simple:

foreach(Foo *foo in array)
  if (ShouldSpawnBaby(*foo))
    Foo &baby = array.Alloc();
    foo->numBabies++; // crash!

Vous pouvez imaginer des cas avec plus de complications (comme des piles d'appels profondes). Cela est vrai pour tous les conteneurs de type tableau. Lors de la création de jeux, nous avons suffisamment de compréhension de notre problème pour forcer les tailles et les budgets sur tout en échange de performances.

Et je ne peux pas le dire assez: vraiment, c'est la meilleure chose qui soit. (Si vous n'êtes pas d'accord, publiez votre meilleure solution! Avertissement - doit résoudre les problèmes répertoriés en haut de cet article: mémoire linéaire / itération, O (1) alloc / free, indices stables, références faibles, zéro derefs de surcharge ou ont une raison incroyable pour laquelle vous n'en avez pas besoin;)

Jeff Gates
la source
Que voulez-vous dire par tableau dynamique ? Je pose cette question car DataArraysemble également allouer un tableau dynamiquement dans ctor. Donc, cela pourrait avoir une signification différente selon ma compréhension.
Eonil
Je veux dire un tableau qui redimensionne / memmoves pendant son utilisation (par opposition à sa construction). Un vecteur stl est un exemple de ce que j'appellerais un tableau dynamique.
Jeff Gates
@JeffGates J'aime vraiment cette réponse. Entièrement d'accord sur l'acceptation du pire des cas comme coût d'exécution standard. Il est très élégant de sauvegarder la liste de liens gratuits à l'aide d'un tableau existant. Questions Q1: But de maxUsed? Q2: Quel est le but du stockage de l'index dans les bits de poids faible de l'ID pour les entrées allouées? Pourquoi pas 0? Q3: Comment cela gère-t-il les générations d'entités? Si ce n'est pas le cas, je suggère d'utiliser les bits de poids faible de Q2 pour le nombre de générations court. - Merci.
Ingénieur
1
A1: Max utilisé vous permet de limiter votre itération. Vous amortissez également tout coût de construction. A2: 1) Vous passez souvent de l'élément -> id. 2) Cela rend la comparaison bon marché / évidente. A3: Je ne sais pas ce que signifie «générations». J'interpréterai ceci comme "comment différenciez-vous le 5ème élément alloué dans l'emplacement 7 du 6ème élément?" où 5 et 6 sont les générations. Le schéma proposé utilise un compteur global pour tous les créneaux. (Nous commençons en fait ce compteur à un nombre différent pour chaque instance de DataArray afin de différencier plus facilement les identifiants.) Je suis sûr que vous pouvez réorganiser les bits par suivi des éléments était important.
Jeff Gates
1
@JeffGates - Je sais que c'est un vieux sujet mais j'aime vraiment cette idée, pourriez-vous me donner quelques informations sur le fonctionnement interne de void Free (T &) par rapport à void Free (id)?
TheStatehz
1

Il n'y a pas de bonne réponse à cela. Tout dépend de l'implémentation de vos algorithmes. Allez-y avec celui que vous pensez être le meilleur. N'essayez pas d'optimiser à ce stade précoce.

Si vous supprimez souvent des objets et les recréez, je vous suggère de regarder comment les pools d'objets sont implémentés.

Edit: Pourquoi compliquer les choses avec les machines à sous et quoi pas. Pourquoi ne pas simplement utiliser une pile et retirer le dernier élément et le réutiliser? Donc, lorsque vous en ajoutez un, vous ferez ++, lorsque vous en popez un pour faire le suivi de votre index de fin.

Sidar
la source
Une pile simple ne gère pas le cas où les éléments sont supprimés dans un ordre arbitraire.
Jeff Gates
Pour être juste, son objectif n'était pas exactement clair. Du moins pas pour moi.
Sidar
1

Cela dépend de votre jeu. Les conteneurs diffèrent en ce qui concerne la rapidité d'accès à un élément spécifique, la rapidité avec laquelle un élément est supprimé et la rapidité avec laquelle un élément est ajouté.


  • std :: vector - L'accès rapide et la suppression et l'ajout à la fin est rapide. La suppression depuis le début et le milieu est lente.
  • std :: list - Itérer sur la liste n'est pas beaucoup plus lent qu'un vecteur mais accéder à un point spécifique de la liste est lent (car l'itération est fondamentalement la seule chose que vous pouvez faire avec une liste). L'ajout et la suppression d'éléments n'importe où est rapide. La plupart des frais généraux de mémoire. Non continue.
  • std :: deque - L'accès rapide et la suppression / l'ajout à la fin et au début est rapide mais lent au milieu.

Habituellement, vous voulez utiliser une liste si vous voulez que votre liste d'objets soit triée d'une manière différente de celle chronologique et que vous deviez donc insérer de nouveaux objets plutôt que les ajouter, autrement dit. Un deque a augmenté la flexibilité sur un vecteur mais n'a pas vraiment d'inconvénient.

Si vous avez vraiment beaucoup d'entités, vous devriez jeter un œil à Space Partitioning.

API-Beast
la source
Pas vrai re: liste. Les conseils de Deque dépendent entièrement des implémentations de Deque, dont la vitesse et l'exécution varient énormément.
métamorphose