Hello everyone,

I am currently in the middle of creating my c++ game engine and I want to ask how do I implement entity references in a clean way. When I say “entity reference” I mean some form of handle that allows me to get a specific entity(with a unique ID) within an array.

In my engine I have a big fixed array of entities(an entity is just a struct) and a counter:

struct Entity
{
	uint32_t id;
	// other data
};

Entity entities[100];
uint32_t entityCount;

// iteration
for(int32_t i = 0; i < entityCount; ++i)
{
	Entity* entity = &entities[i];
	// do stuff
}

When I want to add an entity to the list i just use the entityCount as new index and increment it:

Entity* createdEntity = &entities[entityCount++];

When I want to remove an entitity from the list i move the last entity into the slot i want to delete:

uint32_t entityIndexToRemove = 1;
entities[entityIndexToRemove] = entities[--entityCount];

In this way I can keep the entities contigous in memory.

Since some entities get moved in the array when removing entities i need a way to get an entity based on the unique id. I am looking for a clean and fast way to create these references without having to look in the entire array to find the unique id.

Thanks.

On possibility, similar to what I'm currently using:

struct EntityReference
{
	Entity* pEntity;
};

std::shared_ptr<EntityReference> references[100];

// removing

uint32_t entityIndexToRemove = 1;

const auto lastIndex = --entityCount;
entities[entityIndexToRemove] = entities[lastIndex];
references[entityIndexToRemove].pEntity = nullptr;
references[entityIndexToRemove] = std::move(references[lastIndex]);
references[entityIndexToRemove].pEntity = &entities[entityIndexToRemove];

Since you are using pop&swap you are already not paying that much for deletion (I personally do not do this as I want the order of entities to be consistent). So you only ever need to update one handle.

You can also do it like the C# CLR is managing memory and have an indirection. Something like a second array and your Entity is just a wrapper around an index into that array. Something like

struct Entity
{
    public:
        EntityInstance* operator->() const
        {
            return EntityManager::GetEntityAt(index);
        }
        
    private:
        int index;
}

It however could have some benefits to do it this way when you also want to keep ref counting of how many references to that entity still exist, but I don't know if that fits into your engine design. However, this approach enables your ‘manager’ to rerange entities in the background without killing any reference.

Another option might be to use a hash set to find the instance to your entity ID. This might be slow in usual STL containers, which is why we implemented our own hash set especially for our game engine. We're using a robin-hood hash algorithm on a coherent block of memory, no buckets or linked lists at all, which makes lookups quiet fast. The clue about robin-hood hashing is that items with a smaller path are taking slots from items with a higher path and let those items bubble down a few slots. The lookup of an item then points into one of those slots and if the item doesn't match, the algorithm is iterating through the array for as long as the calculated path isn't reached. This depends however on the number of items currently stored but our tests with 10 million items resulted in near to no overhead as opposed to the STL