Bottleneck performance in ECS

Question

I've been looking into building an entity-component-system. Basically, an entity is just an id wrapped around a struct, components are data belonging to that entity(and reference said id), and systems are the code. Entities and components are all stored inside arrays, to allow fast iteration over each.

For example, an entity could have a Mass, Position and Velocity component. A GravitySystem would take in these three components, calculate some velocity (based off of the Mass) and add it to the Position component.

My problem is, what happens when an entity is removed from the middle of an array? One option is to have the last element of the array swap positions with the entity that was just removed, so that the array stays neatly packed. The downside is that I lose the ability to reference each element by same index number, ie Entity ID 5 is at index 5, and each component belonging to that entity is also located at index 5 within their own arrays.

A solution would be to just ask if entity[i] is "active" before each iteration. Something like,

void gravitySystem(entityList[], massList[], velocityList[], positionList[]) 
{
    for(int i = 0; i < 100; ++i) {
       if(entityList[i].isAlive == 1) {
         velocityList[i] += 9.81 * massList[i];
         positionList[i] += velocityList[i];
       }
       else {
         printf("The entity is dead, Jim.\n");
       }
     }
}

My problem with this solution is that if I were to have a huge list of entities, say 4M, going through this loop, then the if(entityList[i].isAlive==1) statement would have an impact on performance. Is there another solution that would remove this bottleneck? Perhaps one that would keep the array nice and packed without "holes" in it?

Answer 1

One possible solution would be to replace the entity with a new entity with no components. With the setup you have, this sounds like it would just be a matter of leaving the entity there and removing all the components referencing the entity's ID. Then, your systems should naturally skip that entity since it doesn't have the components they require.

At the same time, you can add the index to a list of "recyclable" entity indices. When creating new entities, if there's anything in that list, shift an index off of the list and use the entity at that index instead of placing it at the end. It will have no components at this point, so you can give it the new components, effectively making it a new entity.

This is assuming your systems will skip entities that don't have the required components. Ideally you could write something like this (c++):

class GravitySystem : public System<MassComponent, PositionComponent, VelocityComponent> {
    public:
    GravitySystem() {}

    void logic(Entity& e) {
        auto mass = e.get<MassComponent>();
        auto pos = e.get<PositionComponent>();
        auto vel = e.get<VelocityComponent>();
        vel->y += 9.81 * mass->value;
        pos->x += vel->x;
        pos->y += vel->y;
    }
};

And then in your game loop you write something like gravitySystem.process(entities), and it iterates over each entity and applies the logic on each entity that has the required components. Then you don't need to worry about IDs unless you need them for something else. Take a look at darkf/microecs for an example.

Answer 2

Simple solution is to use a free list and, of course, remove all components when requesting to remove an entity. Reuse the memory of an entity as an index to the next free entity when it is removed from the list (without actually removing it from the array or shuffling it around). This diagram should clarify the idea:

Code example:

struct Entity
{
    union Data
    {
         ...
         int next_free;
    };
    Data data;
};

struct Ecs
{
    ...
    vector<Entity> entities;
    int free_entity; // set to -1 initially
};   

int Ecs::insert_entity(const Entity& entity)
{
     if (free_entity != -1)
     {
          // If there's a free entity index available,
          // pop it from the free list and overwrite the
          // entity at that index.
          const int index = free_entity;
          free_entity = entities[free_entity].data.next_free;
          entities[index] = entity;
          return index;
     }
     else
     {
          // Otherwise insert a new entity.
          entities.push_back(entity);
          return entities.size() - 1;
     }
}

void Ecs::erase_entity(int entity_index)
{
     // Push the entity index to the free list.
     entities[entity_index].data.next_free = free_entity;
     free_entity = entity_index;
}

This will keep your indices from becoming invalidated, allow rapid reclaiming of vacant spaces, and keep your insertion and removal dirt cheap constant-time operations, and all without creating any new data structure or anything like that.

Of course whenever you have an array with "holes", it can start wasting memory if there's lot of vacant spaces where the client removed a whole bunch of things and never bothered to insert anything new. A way to mitigate that is to use a random-access sequence composed of blocks containing, say, 16 entities each. If a block becomes entirely empty, you can free its memory and replace it with a null pointer, to be reallocated later on if the client ever wants to reclaim the range of indices the block previously represented. That has the downside of slower random-access (a little more arithmetic to access the nth element), but does a better job of freeing memory as people remove elements from it. It's also compatible with the free list approach.