8
\$\begingroup\$

I'm quite unsure how I should allocate/resemble my entities within my entity system. I have various options, but most of them seem to have cons associated with them. In all cases entities are resembled by an ID (integer), and possibly has a wrapper class associated with it. This wrapper class has methods to add/remove components to/from the entity.

Before I mention the options, here is the basic structure of my entity system:

  • Entity
    • An object that describes an object within the game
  • Component
    • Used to store data for the entity
  • System
    • Contains entities with specific components
    • Used to update entities with specific components
  • World
    • Contains entities and systems for the entity system
    • Can create/destroy entites and have systems added/removed from/to it

Here are my options, that I have thought of:

Option 1:

Do not store the Entity wrapper classes, and just store the next ID/deleted IDs. In other words, entities will be returned by value, like so:

Entity entity = world.createEntity();

This is much like entityx, except I see some flaws in this design.

Cons

  • There can be duplicate entity wrapper classes (as the copy-ctor has to be implemented, and systems need to contain entities)
  • If an Entity is destroyed, the duplicate entity wrapper classes will not have an updated value

Option 2:

Store the entity wrapper classes within an object pool. i.e. Entities will be return by pointer/reference, like so:

Entity& e = world.createEntity();

Cons

  • If there is duplicate entities, then when an entity is destroyed, the same entity object may be re-used to allocate another entity.

Option 3:

Use raw IDs, and forget about the wrapper entity classes. The downfall to this, I think, is the syntax that will be required for it. I'm thinking about doing thisas it seems the most simple & easy to implement it. I'm quite unsure about it, because of the syntax.

i.e. To add a component with this design, it would look like:

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

As apposed to this:

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

Cons

  • Syntax
  • Duplicate IDs
\$\endgroup\$
10
\$\begingroup\$

Your IDs should be a mixture of index and version. This will allow you to reuse IDs efficiently, use the ID to quickly find components, and makes your "option 2" much easier to implement (though option 3 can be made much more palatable with some work).

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

That will allocate a new 32-bit integer which is a combination of a unique index (which is unique amongst all live objects) and a version tag (which will be unique for all objects that ever occupied that index).

When deleting an entity, you increment the version. Now if you have any references to that id floating around, it will no longer have the same version tag as the entity occupying that spot in the pool. Any attempts to call getEntity (or a isEntityValid or whatever you prefer) will fail. If you allocate a new object at that position the old IDs will still fail.

You can use something like this for your "option 2" to ensure it just works without worries about old entity references. Note that you must never store an entity* since they might move (pool.push_back() could reallocate and move the whole pool!) and only use entity_id for long-term references instead. Use getEntity to retrieve a faster-to-access object only in local code. You could also use a std::deque or similar to avoid pointer invalidation if you wish.

Your "option 3" is a perfectly valid choice. There's nothing inherently wrong with using world.foo(e) instead of e.foo(), especially since you probably want the reference to world anyway and it's not necessarily better (though not necessarily worse) to store that reference in the entity itself.

If you really want the e.foo() syntax to stick around, consider a "smart pointer" that handles this for you. Building off the example code I gave up above, you could have something like:

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

Now you have a way to store a reference to an entity which uses a unique ID and which can use the -> operator to access the entity class (and any method you create on it) quite naturally. The _world member could be a singleton or global, too, if you'd prefer.

Your code just uses an entity_ptr in place of any other entity references and goes. You could even add automatic reference counting to the class if you'd like (somewhat more reliable if you update all that code to C++11 and use move semantics and rvalue references) so that you can just use entity_ptr everywhere and no longer think heavily about references and ownership. Or, and this is what I prefer, make a separate owning_entity and weak_entity types with only the former managing reference counts so you can use the type system to differentiate between handles that keep an entity alive and those which just reference it until it is destroyed.

Note that the overhead is very low. The bit manipulation is cheap. The extra lookup into pool is not a real cost if you access other fields in entity soon after anyway. If your entities are truly just ids and nothing else then there might be a bit of extra overhead. Personally, the idea of an ECS where entities are just IDs and nothing else seems a bit... academic to me. There's at least a few flags you'll want to store on the general entity, and larger games will probably want a collection of the entity's components of some kind (inlined linked list if nothing else) for tools and serialization support.

As a rather final note, I intentionally did not initialize entity::version. It doesn't matter. No matter what the initial version is, so long as we increment it each time we're fine. If it ends up close to 2^16 then it'll just wrap around. If you end up wrapping around in ways that make old IDs stay valid, switch to larger versions (and 64-bit IDs if you need). To be safe, you should probably clear out entity_ptr any time you check it and it is empty. You could make empty() do this for you with a mutable _world_ and _id, just be careful with threading.

\$\endgroup\$
  • \$\begingroup\$ Why not contain the ID within the entity structure? I'm quite confused. Also could you use std::shared_ptr/weak_ptr for owning_entity and weak_entity? \$\endgroup\$ – miguel.martin Jul 1 '13 at 4:21
  • \$\begingroup\$ You can contain the ID instead if you want. The only point is that the value of the ID changes when an entity in the slot is destroyed while the ID also contains the index of slot for efficient lookup. You can use shared_ptr and weak_ptr but be aware that they are meant for individually allocated objects (though they can have custom deleters to alter that) and so are not the most efficient types to use. weak_ptr in particular may not do what you want; it stops an entity from being fully deallocated/reused until every weak_ptr is reset while weak_entity would not. \$\endgroup\$ – Sean Middleditch Jul 1 '13 at 4:46
  • \$\begingroup\$ It'd be a lot easier to explain this approach if I had a whiteboard or wasn't far too lazy to draw this up in Paint or something. :) I think visualizing the structure makes it exceedingly clear. \$\endgroup\$ – Sean Middleditch Jul 1 '13 at 4:47
  • \$\begingroup\$ gamesfromwithin.com/managing-data-relationships This article seems to present some-what the same thing you said in your answer, is this what you mean? \$\endgroup\$ – miguel.martin Jul 1 '13 at 10:01
  • 1
    \$\begingroup\$ I'm the author of EntityX, and the reuse of indices has bothered me for a while. Based on your comment, I've updated EntityX to also include a version. Thanks @SeanMiddleditch! \$\endgroup\$ – Alec Thomas Aug 18 '13 at 15:34
0
\$\begingroup\$

I'm actually working on something similiar right now, and have been using a solution that's closest to your number 1.

I have EntityHandle instances returned from the World. Each EntityHandle has a pointer to the World (in my case, I just call it EntityManager), and the data manipulation/retrieval methods in the EntityHandle are actually calls to the World: e.g. to add a Component to an entity, you can call EntityHandle.addComponent(component), which will in turn call World.addComponent(this, component).

This way the Entity wrapper classes are not stored, and you avoid the extra overhead in syntax you'd get with your option 3. It also avoids the issue of "If an Entity is destroyed, the duplicate entity wrapper classes will not have an updated value", because they all point to the same data.

\$\endgroup\$
  • \$\begingroup\$ What happens if you make another EntityHandle to resemble the same entity, and then you try to delete one of the handles? The other handle will still have the same ID, which will mean that it "handles" a dead entity. \$\endgroup\$ – miguel.martin Jul 1 '13 at 6:38
  • \$\begingroup\$ That's true, the other remaining handles will then point to the ID that no longer "holds" an entity. Of course, situations where you delete an entity and then try to access it from elsewhere should be avoided. The World could for example throw an exception when trying to manipulate / retrieve data associated with a "dead" entity. \$\endgroup\$ – vijoc Jul 1 '13 at 6:48
  • \$\begingroup\$ While it is best avoided, in the real world this will happen. Scripts will hold on to references, "smart" game objects (like seeking missiles) will hold on to references, etc. You really need a system that is either able to properly in all cases cope with stale references or which tracks and zeroes out weak references. \$\endgroup\$ – Sean Middleditch Jul 1 '13 at 7:09
  • \$\begingroup\$ The World could for example throw an exception when trying to manipulate / retrieve data associated with a "dead" entity Not if the old ID is now allocated with a new entity. \$\endgroup\$ – miguel.martin Jul 1 '13 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.