Allocation d'entités au sein d'un système d'entités

9

Je ne sais pas trop comment allouer / ressembler à mes entités au sein de mon système d'entités. J'ai différentes options, mais la plupart d'entre elles semblent avoir des inconvénients. Dans tous les cas, les entités ressemblent à un ID (entier) et peuvent éventuellement être associées à une classe wrapper. Cette classe wrapper a des méthodes pour ajouter / supprimer des composants à / de l'entité.

Avant de mentionner les options, voici la structure de base de mon système d'entités:

  • Entité
    • Un objet qui décrit un objet dans le jeu
  • Composant
    • Utilisé pour stocker des données pour l'entité
  • Système
    • Contient des entités avec des composants spécifiques
    • Utilisé pour mettre à jour des entités avec des composants spécifiques
  • Monde
    • Contient des entités et des systèmes pour le système d'entités
    • Peut créer / détruire des entités et y ajouter / supprimer des systèmes

Voici mes options, auxquelles j'ai pensé:

Option 1:

Ne stockez pas les classes d'encapsuleur d'entité et stockez simplement l'ID suivant / les ID supprimés. En d'autres termes, les entités seront retournées par valeur, comme ceci:

Entity entity = world.createEntity();

Cela ressemble beaucoup à entityx, sauf que je vois des défauts dans cette conception.

Les inconvénients

  • Il peut y avoir des classes d'enveloppe d'entité en double (car le copy-ctor doit être implémenté et les systèmes doivent contenir des entités)
  • Si une entité est détruite, les classes wrapper d'entité en double n'auront pas de valeur mise à jour

Option 2:

Stockez les classes d'encapsuleur d'entité dans un pool d'objets. c'est-à-dire que les entités seront retournées par un pointeur / référence, comme ceci:

Entity& e = world.createEntity();

Les inconvénients

  • S'il y a des entités en double, lorsqu'une entité est détruite, le même objet entité peut être réutilisé pour allouer une autre entité.

Option 3:

Utilisez des ID bruts et oubliez les classes d'entités wrapper. L'inconvénient à cela, je pense, est la syntaxe qui sera nécessaire pour cela. Je pense à faire cela, car il semble le plus simple et le plus facile à mettre en œuvre. Je ne suis pas sûr à ce sujet, à cause de la syntaxe.

ie Pour ajouter un composant avec cette conception, cela ressemblerait à:

Entity e = world.createEntity();
world.addComponent<Position>(e, 0, 3);

Comme apposé à cela:

Entity e = world.createEntity();
e.addComponent<Position>(0, 3);

Les inconvénients

  • Syntaxe
  • ID en double
miguel.martin
la source

Réponses:

12

Vos identifiants doivent être un mélange d' index et de version . Cela vous permettra de réutiliser efficacement les ID, d'utiliser l'ID pour trouver rapidement des composants et de rendre votre "option 2" beaucoup plus facile à implémenter (bien que l'option 3 puisse être rendue beaucoup plus agréable avec du travail).

struct entity {
  uint16 version;
  /* and other crap that doesn't belong in components */
};

std::vector<entity> pool;
std::vector<uint16> freelist;
typedef uint32 entity_id; /* this shoudl be a wrapper class */

entity_id createEntity()
{
  uint16 index;
  if (!freelist.empty())
  {
    pool.push_back(entity());
    freelist.push_back(pool.size() - 1);
  }
  index = freelist.pop_back();

  return (pool[id].version << 16) | index;
}

void deleteEntity(entity_id id)
{
   uint16 index = id & 0xFFFF;
   ++pool[index].version;
   freelist.push_back(index);
}

entity* getEntity(entity_id id)
{
  uint16 index = id & 0xFFFF;
  uint16 version = id >> 16;
  if (index < pool.size() && pool[index].version == version)
    return &pool[index];
  else
    return NULL;
 }

Cela allouera un nouvel entier 32 bits qui est une combinaison d'un index unique (qui est unique parmi tous les objets actifs) et d'une balise de version (qui sera unique pour tous les objets qui ont déjà occupé cet index).

Lorsque vous supprimez une entité, vous incrémentez la version. Maintenant, si vous avez des références à cet identifiant flottant, il n'aura plus la même balise de version que l'entité occupant cet emplacement dans le pool. Toute tentative d'appel getEntity(ou un isEntityValidou ce que vous préférez) échouera. Si vous allouez un nouvel objet à cette position, les anciens ID échoueront toujours.

Vous pouvez utiliser quelque chose comme ça pour votre "option 2" pour vous assurer que cela fonctionne sans vous soucier des anciennes références d'entité. Notez que vous ne devez jamais stocker un entity*car ils pourraient se déplacer ( pool.push_back()pourraient réaffecter et déplacer l'ensemble du pool!) Et ne les utiliser qu'à la place entity_idpour des références à long terme. Utilisez getEntitypour récupérer un objet d'accès plus rapide uniquement dans le code local. Vous pouvez également utiliser un std::dequeou similaire pour éviter l'invalidation du pointeur si vous le souhaitez.

Votre "option 3" est un choix parfaitement valable. Il n'y a rien d'intrinsèquement mauvais à utiliser à la world.foo(e)place de e.foo(), d'autant plus que vous voulez probablement la référence de worldtoute façon et qu'il n'est pas nécessairement préférable (mais pas nécessairement pire) de stocker cette référence dans l'entité elle-même.

Si vous voulez vraiment que la e.foo()syntaxe reste, pensez à un "pointeur intelligent" qui gère cela pour vous. En vous basant sur l'exemple de code que j'ai abandonné ci-dessus, vous pourriez avoir quelque chose comme:

class entity_ptr {
  world* _world;
  entity_id _id;

public:
  entity_ptr() : _id(0) { }
  entity_ptr(world& world, entity_id id) : _world(&world), _id(id) { }

  bool empty() const { return _world != NULL && _world->getEntity(_id) != NULL; }
  void clear() { _world = NULL; _id = 0; }
  entity* get() { assert(!empty()); return _world->getEntity(_id); }
  entity* operator->() { return get(); }
  entity& operator*() { return *get(); }
  // add const method where appropriate
};

Vous avez maintenant un moyen de stocker une référence à une entité qui utilise un ID unique et qui peut utiliser l' ->opérateur pour accéder à la entityclasse (et à toute méthode que vous créez dessus) tout naturellement. Le _worldmembre peut également être un singleton ou un global, si vous préférez.

Votre code utilise simplement un entity_ptrà la place de toute autre référence d'entité et disparaît. Vous pouvez même ajouter un comptage automatique des références à la classe si vous le souhaitez (un peu plus fiable si vous mettez à jour tout ce code en C ++ 11 et utilisez la sémantique de déplacement et les références rvalue) afin que vous puissiez simplement utiliser entity_ptrpartout et ne plus penser intensément sur les références et la propriété. Ou, et c'est ce que je préfère, créez un type distinct owning_entityet weak_entityuniquement avec les anciens comptages de référence de gestion afin que vous puissiez utiliser le système de type pour différencier les descripteurs qui maintiennent une entité en vie et ceux qui la référencent jusqu'à sa destruction.

Notez que les frais généraux sont très faibles. La manipulation des bits est bon marché. La recherche supplémentaire dans le pool n'est pas un coût réel si vous accédez à d'autres champs entitypeu de temps après. Si vos entités ne sont vraiment que des identifiants et rien d' autre, il peut y avoir un peu de surcharge supplémentaire. Personnellement, l'idée d'un ECS où les entités ne sont que des identifiants et rien d'autre me semble un peu ... académique. Il y a au moins quelques indicateurs que vous voudrez stocker sur l'entité générale, et les grands jeux voudront probablement une collection de composants de l'entité (liste liée en ligne si rien d'autre) pour les outils et la prise en charge de la sérialisation.

Pour terminer, je n'ai pas intentionnellement initialisé entity::version. Ça n'a pas d'importance. Quelle que soit la version initiale, tant que nous l'incrémentons à chaque fois que nous allons bien. Si elle se rapproche, 2^16elle s'enroulera. Si vous finissez par vous déplacer de manière à ce que les anciens ID restent valides, passez à des versions plus grandes (et à des ID 64 bits si vous en avez besoin). Pour être sûr, vous devez probablement effacer entity_ptr chaque fois que vous le vérifiez et qu'il est vide. Vous pouvez le faire empty()pour vous avec un mutable _world_et _id, soyez juste prudent avec le filetage.

Sean Middleditch
la source
Pourquoi ne pas contenir l'ID dans la structure d'entité? Je suis assez confus. Pourriez-vous également utiliser std :: shared_ptr / faiblesse_ptr pour owning_entityet weak_entity?
miguel.martin
Vous pouvez contenir l'ID à la place si vous le souhaitez. Le seul point est que la valeur de l'ID change lorsqu'une entité dans le slot est détruite alors que l'ID contient également l'index du slot pour une recherche efficace. Vous pouvez utiliser shared_ptret weak_ptrmais sachez qu'ils sont destinés aux objets alloués individuellement (bien qu'ils puissent avoir des suppresseurs personnalisés pour modifier cela) et ne sont donc pas les types les plus efficaces à utiliser. weak_ptren particulier, peut ne pas faire ce que vous voulez; il empêche une entité d'être entièrement désallouée / réutilisée jusqu'à ce que tout weak_ptrsoit réinitialisé alors weak_entityqu'il ne le serait pas.
Sean Middleditch
Il serait beaucoup plus facile d'expliquer cette approche si j'avais un tableau blanc ou si je n'étais pas trop paresseux pour le dessiner dans Paint ou quelque chose. :) Je pense que visualiser la structure le rend extrêmement clair.
Sean Middleditch
gamesfromwithin.com/managing-data-relationships Cet article semble présenter un peu la même chose que vous avez dit dans votre réponse, est-ce ce que vous voulez dire?
miguel.martin
1
Je suis l'auteur d' EntityX , et la réutilisation des indices me dérange depuis un moment. Sur la base de votre commentaire, j'ai mis à jour EntityX pour inclure également une version. Merci @SeanMiddleditch!
Alec Thomas
0

Je travaille actuellement sur quelque chose de similaire et utilise une solution la plus proche de votre numéro 1.

J'ai des EntityHandleinstances de retour du World. Chacun EntityHandlea un pointeur sur le World(dans mon cas, je l'appelle juste EntityManager), et les méthodes de manipulation / récupération des données dans le EntityHandlesont en fait des appels au World: par exemple, pour ajouter un Componentà une entité, vous pouvez appeler EntityHandle.addComponent(component), qui à son tour appellera World.addComponent(this, component).

De cette façon, les Entityclasses wrapper ne sont pas stockées et vous évitez la surcharge supplémentaire de syntaxe que vous obtiendriez avec votre option 3. Cela évite également le problème de "Si une entité est détruite, les classes wrapper d'entité en double n'auront pas de valeur mise à jour ", car ils pointent tous vers les mêmes données.

vijoc
la source
Que se passe-t-il si vous créez un autre EntityHandle pour qu'il ressemble à la même entité, puis essayez de supprimer l'un des descripteurs? L'autre handle aura toujours le même ID, ce qui signifie qu'il "gère" une entité morte.
miguel.martin
C'est vrai, les autres poignées restantes pointeront alors vers l'ID qui ne «détient» plus une entité. Bien sûr, les situations dans lesquelles vous supprimez une entité puis essayez d'y accéder depuis un autre endroit doivent être évitées. Le Worldpourrait par exemple lever une exception lors d'une tentative de manipulation / récupération de données associées à une entité "morte".
vijoc
Bien qu'il soit préférable de l'éviter, cela se produira dans le monde réel. Les scripts conserveront les références, les objets de jeu «intelligents» (comme la recherche de missiles) conserveront les références, etc. références.
Sean Middleditch
Le Monde pourrait par exemple lever une exception en essayant de manipuler / récupérer des données associées à une entité "morte" Pas si l'ancien ID est maintenant alloué à une nouvelle entité.
miguel.martin