Entity component system design. Should ID of entities be continuous?

Question

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?

Answer 1

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.

Answer 2

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.