1
\$\begingroup\$

I am implementing an entity-component system. Below is my current implementation in c++.

using ID = std::uint32_t;

class Entity {
public:
    Entity(ID index): index_{index} {
    }

    ID index() const;

private:
    const ID index_;
};

ID Entity::index() const
{
    return index_;
}

class Entity_factory {
public:
    Entity generate();

    void destory(ID id);
private:
    ID count_ = 0;
    std::unordered_set<ID> idle_IDs_;
};

Entity Entity_factory::generate()
{
    if (!idle_IDs_.empty()) {
        const ID id = *idle_IDs_.begin();
        idle_IDs_.erase(idle_IDs_.begin());
        return Entity {id};
    }

    assert(count_ != std::numeric_limits<ID>::max());
    return Entity {count_++};
}

void Entity_factory::destory(ID id)
{
    assert (id < count_);
    idle_IDs_.insert(id);
}

Note I use a hash table to keep track of all "destroyed" ID so I can use it again. This way, all the entity index will be as continuous as possible, so I can store components in a pool and refer them through index without wasting much memory. Another choice I can think is at component pools create a separated "index" array to keep track of entity and store all entity continuous. Which why do you prefer? Or do you have a better solution to this problem?

\$\endgroup\$
2
\$\begingroup\$

The concern that @philipp mentioned can be eliminated with a bit of fancy bit manipulation.

Rather than treat your Entity's ID as a single 32-bit value, split that value into two parts, one which represents the index slot in your array and another that represents an ever increasing, potentially rolling over version value.

struct EntityID  
{
  uint32_t index   : 24;
  uint32_t version : 8;
};

In this use case, you can have approximately 16.7 million different entities in your pool. Each entity will be assigned 255 different version values before they roll over, skipping 0 as a sentinel value.

So you end up with an array of EntityID indexed based index. So when you want to lookup an entity, you simply go to that index, compare the version values between the stored reference and the value in the array and if they match, the index is still valid. If they differ, the reference is stale and you can thus assume that entity has since been destroyed and react accordingly.

My personal choice is to use this approach mainly for cataloging entity ids and validating whether they're still valid at runtime and then store the components in their own separate pools per type.

For this to work, my component pool relies on two arrays to manage its memory. The first array is a simple sparsely populating array where the index from the entity ID holds the offset index in the second array that is maintained as a densely populated array of component types.

The benefit here is during processing of components, I can simply iterate the second array and avoid any lookup performance bottlenecks. Worse case scenario, I take several constant time lookup hits when I fetch a component by entity id which seems reasonable.

template<typename T> T** GetComponents() const {
  return componentPool;
}

template<typename t> T* GetComponent(const EntityId& entityId) 
{
  if ( IsEntityIdValid( entityId ) ) 
  {
    uint32_t index = componentEntityArray[ entityId.index ];
    return &componentPool[ index ];
  }
  else
    return nullptr;
}

bool IsEntityIdValid(const EntityId& entityId) const 
{
  if ( entityId.index < 0 || entityId.index >= MAX_ENTITIES )
    return false;

  return entityIdArray[ entityId.index ].version == entityId.version;
}

void DestroyEntity(EntityId entityId) {
  if ( entityId.index >= 0 && entityId.index < MAX_ENTITIES ) 
  {
    entityIdArray[ entityId.index ].version++;
    entityIdFreeListQueue.add( entityId.index );
  }
}

The other benefit is that now your entityIdArray is also a sparse array but contiguous. The lookup is constant time either way, so that should not impact performance, if at all.

I would suggest however to make the queue use a first-in, first-out strategy. This avoids the concern with version numbers being incremented too high for a single slot, except in situations where you create and destroy a single entity repeatedly in a row.

\$\endgroup\$
  • \$\begingroup\$ This is the approach I generally use in this situation. I'll use a 64 bit ID to give myself a bit of space, and then stick a bunch of useful information in there. e.g. Some small integer to identify who owns it from a network perspective (network peer ID/index), some ID identifying what kind of entity it is, an incrementing counter, etc. I usually use bit twiddling to generate this info, so that other parts of the code don't start relying on certain information being in the ID itself, but that's just personal preference rather than a hard rule. (Could also use private + friending) \$\endgroup\$ – Bryan Robertson Jul 24 '17 at 16:47
  • \$\begingroup\$ Can I just store version and additional information in the entity array and use entity id as an index? \$\endgroup\$ – Lesley Lai Jul 24 '17 at 19:24
  • \$\begingroup\$ Well the advantage of having your incrementing version number baked into the ID, is that if you come across an ID value in the debugger, you can know for sure which entity it refers to. If you just have a raw index, then that ID could refer to multiple different entities throughout the game's lifetime, which is less than ideal. Also if your ID is more complex, it's harder to accidentally end up with a valid ID because of uninitialised memory or some other bug (e.g. a memory stomp bug). \$\endgroup\$ – Bryan Robertson Jul 24 '17 at 20:06
  • \$\begingroup\$ @Naros If an entity dies, why don't just swap it with the end of the array/vector and then erase it (which calls container destructor)? I don't see why this index value is so important, because I see it coming up frequently. But then again, I go with the entity is a pure integer route.. Why do you need 8 bits for this index? What are those 2^8 - 1 states of the entity you need to watch out for? For me, that would be useful if those states identify all the components an EntityId has. \$\endgroup\$ – Nikos Sep 9 '18 at 0:14
  • \$\begingroup\$ @Nik-Liz The whole premise here is to reuse entity ids that have since been destroyed to avoid running into potential issues in long-running simulations. From your perspective, index = your pure integer value and then version is just a numeric value that you increase every time that entity dies. When an entity dies, you push the EntityID onto a stack and reuse those EntityIDs first before allocating any new ones. \$\endgroup\$ – Naros Sep 10 '18 at 16:31
0
\$\begingroup\$

I would recommend you to always assign a fresh ID to a new entity. Very strange bugs can happen if you try to refer to an entity by ID, but that entity got destroyed and replaced by something completely different in the meantime.

If you want to use object pooling (which usually makes most sense for objects with a large memory footprint and little dynamic allocation), keep separate indexes which are only relevant for the pool itself.

\$\endgroup\$
  • \$\begingroup\$ One additional question: do you think having a vector (or array) of bitsets inside the entity factory a good idea? I can store information about whether an entity or its component exist this way. \$\endgroup\$ – Lesley Lai Jul 22 '17 at 23:20
  • \$\begingroup\$ @LesleyLai Whether or not it's a good idea depends on how exactly you are going to use it and for what purpose. \$\endgroup\$ – Philipp Jul 22 '17 at 23:53
  • \$\begingroup\$ I will use it to check whether an entity of a certain ID exists. And if it does exist, then what components it has. This way, I can do some bit flags checking when adding or deleting a component about whether its prerequisites are satisfied. \$\endgroup\$ – Lesley Lai Jul 23 '17 at 0:10
  • \$\begingroup\$ So the ID's are also the indexes of the vector/array? Then that's a bad idea, because then deleted ID's will continue to consume memory, which means you will run out of memory sooner or later. Use a hash map instead. The information which entity has which components is something I would rather manage in the Entity class instead of a separate data structure. But I have no good objective reason for that preference besides "it feels right". \$\endgroup\$ – Philipp Jul 23 '17 at 0:18
  • \$\begingroup\$ Thank you! I will stick with the hash table solution now since I want to entities to be immutable objects. \$\endgroup\$ – Lesley Lai Jul 23 '17 at 0:28

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.