6

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?

  • I edited your tag for C because there's no evidence of C++ anywhere. If you're actually programming in C++, tag C++. If you're programming in C, tag C. – DeadMG Dec 23 '14 at 19:52
  • I do not see why it matters, as the above code would be valid c and c++ code. Additionally, I am writing in both C and C++. – Daniel Martin Dec 23 '14 at 19:56
3

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.

  • Maybe I am misunderstanding your answer. When I remove the components and leave the entity there, how would it naturally 'skip' the entity? It would still look at entity id5, then even if there was no mass component, it would still look at mass[5]? Edited because I thought I found an answer, but upon thinking more about it I found that it still caused holes in the array. – Daniel Martin Dec 23 '14 at 20:22
  • @DanielMartin updated – Hey Dec 23 '14 at 21:13
  • Hmm, I see. I've always seen entities as just a wrapper over an ID, so I've always skipped over ECS implimentations where the Entity was more than that. However, it's looking more and more like there is no efficient way to handle an ECS where the Entity is merely an id and not a container for the various components it could have. – Daniel Martin Dec 23 '14 at 21:26
  • @DanielMartin I don't see why you can't have systems selectively process entities based on their components with an id-based system, though. I think you just need a way of defining what components a system requires. – Hey Dec 23 '14 at 21:31
  • You're right! I was stuck thinking, "How can I make this as fast as possible?" and not actually seeking an answer. One way that I see could be to create a list of IDs for each system - if I create an entity that would be affected by Gravity, have a gravityEntityList. This way, I can keep the entity ID matching with the index of it's components while having "holes" in those arrays. The system would just reference the corresponding array and cherry-pick from the various component arrays based on the id in the list. – Daniel Martin Dec 23 '14 at 21:37
0

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:

enter image description here

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.

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.