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

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.

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.

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;)

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.

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.