Entity-Component Part 2: Entities

In the second part of this article series on entity-component systems, we are going to take a look at how entities can be managed. Don't forget to read part one which explained the very basics of the entity-component paradigm. Today we are finally going to start writing some actual code on entities management.

The manager

Some implementation define the manager (the big class reponsible for handling entities and their components) as a singleton. To allow for some flexibility, we are going to allow multiple instances of an entity manager to be created. However the entity handlers are going to store a reference to said manager. These references will be weak references, which is going to allow the entities to check whether the manager still exists or not. If you have already messed around with weak references in C++, you will know that they need to be instantiated from shared pointers. This means that every instance of a manager will have to have a shared pointer to itself. Thus, we need to prevent the manager from being instantiated on the stack. Also, don't try creating shared pointers to this in a class, it just won't work. To allow for this, we need to use the enable_shared_from_this feature. Let's write some code and discuss it afterwards.

class EntityManager : public std::enable_shared_from_this<EntityManager> {
public:
    EntityManager(const EntityManager &manager) = delete;
    EntityManager &operator=(const EntityManager &manager) = delete;

    static std::shared_ptr<EntityManager> makeInstance()
    {
        return std::shared_ptr<EntityManager>(new EntityManager());
    }

private:
    EntityManager() = default;
};

First, the manager extends enable_shared_from_this, which will allow us to call shared_from_this() later to get a shared pointer to the current instance of EntityManager. We have made the default constructor private so that it can only be instantiated dynamically via the makeInstance method. We've also deleted the copy methods because we shouldn't be able to copy a manager.

Entity definition

In our system, an entity is simply going to be an identifier. These identifiers will be reused after being discarded and we are thus going to need an invalidation method. To do so, we are going to store the entity version alongside its identifier. When an entity is discarded, its identitifier will be placed in a recycling list and its version will be incremented so that all future calls to the ECS done with an outdated entity handler will be discarded.

The entity identifiers and version numbers will be stored as 32-bits unsigned integers. This means that our system will support 4,294,967,296 concurrent entities, and a total of 18,446,744,073,709,551,616 entities throughout a runtime session, which should be enough, right? To allow for some flexibility, we are going to make the types configurable in case you need more entities.

typedef uint32_t EntityId;
typedef uint32_t EntityVersion;

Now that we have this, we can very simply define an entity:

class Entity {
public:
    Entity() = default;

    Entity(std::shared_ptr<EntityManager> manager, EntityId id, EntityVersion version) :
        _id(id), _version(version), _manager(manager)
    {}

    Entity(std::weak_ptr<EntityManager> manager, EntityId id, EntityVersion version) :
        _id(id), _version(version), _manager(manager)
    {}

    Entity(const Entity &entity) = default;
    Entity &operator=(const Entity &entity) = default;

private:
    friend class EntityManager;

    std::weak_ptr<EntityManager> _manager;
    EntityId _id;
    EntityVersion _version;
};

There, simple, easy. As you can see we are keeping a weak pointer to the entity manager, which allows us to check that the manager still exists without keeping it from being deallocated, which would have happened had we used a shared pointer. We can also define comparison operators between entities.

bool Entity::operator==(const Entity &entity) const
{
    shared_ptr<EntityManager> manager1 = _manager.lock();
    shared_ptr<EntityManager> manager2 = entity._manager.lock();

    if (!manager1 || !manager2) {
        return false;
    }

    return _version == entity._version && _id == entity._id && manager1 == manager2;
}

bool Entity::operator!=(const Entity &entity) const
{
    return !(*this == entity);
}

The first step to comparing entities is to check whether they share the same manager and whether those are still valid or not. the lock method on weak pointers allows us to transform it to a shared pointer used to dereference it. If the objects it points to is to longer valid, it will return a shared pointer to nullptr. The rest of the code is quite easy to understand.

Creating and deleting entities

To create entities, the manager will have to know which is the next entity identifier that can be used, as well as the version for each entity. Furthermore, is order to be able to reuse entity identifiers, we are going to store a list of identifiers that can be used.

class EntityManager {
    EntityId _nextEntity = 0;
    std::vector<EntityId> _freeList;
    std::vector<EntityVersion> _entityVersion;
};

This code should be quite explicit. Note that initially, no entity can be used because the list of free entities is empty. Thus, let's implement a method to grow the storage capacity of the manager.

void EntityManager::growCapacity()
{
    size_t newSize;

    if (_entityVersion.size() > 0) {
        newSize = _entityVersion.size();

        while (newSize <= _nextEntity) {
            newSize *= 2;
        }
    } else {
        newSize = 256;
    }

    _entityVersion.resize(newSize, 0);
}

This function is rather simple. If our arrays are empty at first, we initialize their size at 256. Otherwise, we double their capacity until we can store the next required entity identifier. Note that this function should be private. We now have everything we need to create entities.

Entity EntityManager::create()
{
    EntityId id;
    EntityVersion version;

    if (_freeList.empty()) {
        if (_nextEntity > numeric_limits<EntityId>::max()) {
            throw runtime_error("Entity id out of bounds");
        }

        growCapacity();
        id = _nextEntity++;
        version = _entityVersion[id] = 1;
    } else {
        id = _freeList.back();
        _freeList.pop_back();
        version = _entityVersion[id];
    }

    return Entity(shared_from_this(), id, version);
}

Firstly, when there is no identifier to recycle, the identifier will be the next available. In case we don't have enough space for it, we increase the capacity, and also check if we run out of identifiers. Note that the initial version of any entity is 1. The reason for this will be made clearer later. Otherwise, if the free list is not empty, we just get an available identifier and associated version number. Finally, we can create the entity using the shared_from_this function we discussed in the first part. This function is private and is only called from the entities. This EntityManager and Entity need to be friends. Now, on to deletion.

void EntityManager::destroy(Entity &entity)
{
    if (!entity || entity._manager.lock() != shared_from_this()) {
        return;
    }

    if (++_entityVersion[entity._id] != 0) {
        _freeList.push_back(entity._id);
    }

    entity._manager.reset();
}

The first thing to note here is the !entity in the first condition. This is something we are going to implement next. So firstly we test whether the current manager is the one associated with the entity to destroy. Then, we increment the entity version number to make it invalid for previous entity handlers that may still be used throughout the program. If this version number becomes 0, it means that we have exceeded the maximum number of versions, and the entity is thus not added to the recycling list. Finally, the pointer to the manager stored in the entity is reset. Finally, let's write the last method for today in the manager, which is really straightforward, and that I will thus not explain. Just note that we don't test that the manager is valid because we will only call this function from the entities. This function, just like destroy, is private.

bool EntityManager::isEntityValid(const Entity &entity) const
{
    return entity._id < _nextEntity && entity._version == _entityVersion[entity._id];
}

Back to entities

These last functions test the validity of an entity handler and destroy said entity. Given what has been said before, they should be fairly explicit, and I will thus not explain them.

Entity::operator bool() const
{
    return isValid();
}

bool Entity::isValid() const
{
    shared_ptr<EntityManager> manager = _manager.lock();

    if (!manager) {
        return false;
    }

    return manager->isEntityValid(*this);
}

void Entity::destroy()
{
    shared_ptr<EntityManager> manager = _manager.lock();

    if (manager) {
        manager->destroy(*this);
        _manager.reset();
    }
}

Final words

That's it for today. We can now create and destroy entities and check that existing entities are still valid. In the next part, we are going to mess with components, because right now the system is fairly useless. As always, all feedback is welcome.

Entity-Component Part 1: What? Why? How?

So you have just finished developing the class for the zombie knight of your upcoming game. His animation is smooth, his AI perfect, you are proud. He had a lot in common with the mad cleric you developed two weeks ago, except for the way he fights, so you just copy-pasted the parts that were similar. You are not going to modify those any time soon anyway, are you? The next day, your friend comes over with a great idea for a new kind of magic for the player. Great, let's implement it. So you start with the zombie knight. Then you remember you also have to modify the code for the mad cleric. And for the ogre. And for the... oops!

What if the common behavior for all your ennemies was unified. Write once, use for everything. Wouldn't that be glorious? My friends, welcome to the magical world of Entity-Component.

What's that?

Entity-Component (or Entity-Component-System), also known as ECS, is an architectural patterns that allows great flexibility is the way entities are managed. Components can be added or removed at runtime from entities, hence adding, removing or modifiying the behavior of entities. The behavior itself is described in systems by requesting all the existing entities having components of a given type.

An entity is only an identifier, an abstract object. It holds no behavior at all. An entity contains components. It can only have one of each component.

A component is data. It defines an aspect of an entity, for example its physical properties in the scene (position, velocity, size), it emitting light (color, intensity), or its animation to be displayed.

A system is a piece of code that retrieves all the entities that have certain types of components and does things on them. For instance, by retrieving all the entities with physical properties, you can make them move through the scene in an unified piece of code. Similarily, by retrieving all the entities emitting light and with physical properties, you can light your scene up from those entities.

Why should I care?

Of course, as said earlier, an advantage of using ECS is how reusable most of your code becomes. The power of ECS arises from combining components. Imagine two components, on for light property (color, intensity), and one that defines a temporary object that will be deleted after a given amount of time. You already have a system for displaying lights, and one for deleting temporary objects when needed. By creating an entity with both those components, you can create flash of light without writing any logic, and you have reused components that can be used for other things. Creating new kinds of entities is now a matter of combining components, and sometimes writing systems to process entities with these new aspects.

But ECS can also make your cache happy. Indeed, an Entity-Component system can be written in a data-oriented way. For those who may not know, the data-oriented paradigms aims at improving memory coherence by using contiguous arrays of data instead of countless pointers referencing memory all over the place. This approach takes advantage of the CPU cache to reduce memory fetch times. In an ECS, this is done by allocating the components of a given type in a large continuous array for example. Iterating through it then induces less potential cache misses.

Oh my! It sounds like the Holy Grail of game development!

It is not!

The first problem you may encounter when using an ECS is how to make your systems communicate. Sure, any data can be transmitted using components, but is it wise for a system that handles a certain event, let's say the death of an ennemy in the game, to iterate all over the entities to find the one that just died? And if there had to be some kind of flags in components for every event is your game, your components may quickly become a mess. I have hinted at a possible solution: events. A solid event system (probably based on an observer pattern) would be a solution to handle such cases.

Another problem hinted at previously is the cost of iterating through the entities in every system. In areas such as collision detection, accelerating structures such a spacial partition structures can be used to filter out entities that need to be processed. However, by using clever tricks is the way entities are retrieved in the entities manager, filtering out uninteresting entities can be really efficient.

So, how do I do it?

Okay, here we go, let's use some pseudo-code and a lot of magic. Let's define some components.

struct PhysicalComponent {
    float x;
    float y;
    float dx;
    float dy;
};

struct PointLightComponent {
    float r;
    float g;
    float b;
};

struct LivingComponent {
    float health;
};

struct SpriteComponent {
    string filename;
}

And now let's make some entities

/**
 * Creates a particle that emits light of a random color
 * moving in a random direction.
 */
Entity createFunkyParticle() {
    Entity e = entitiesManager.create();

    PhysicalComponent phys = {0, 0, rand(), rand()};
    PointLightComponent light = {rand(), rand(), rand()};

    e.addComponent<PhysicalComponent>(phys);
    e.addComponent<PointLightComponent>(light);

    return e;
}

/**
 * Create an NPC.
 */
Entity createNPC() {
    Entity e = entitiesManager.create();

    PhysicalComponent phys = {0, 0, rand(), rand()};
    LivingComponent life = {100};
    SpriteComponent sprite = {"npc.png"};

    e.addComponent<PhysicalComponent>(phys);
    e.addComponent<LivingComponent>(life);
    e.addComponent<SpriteComponent>(sprite);

    return e;
}

Okay, let's make the entities move!

list<Entity> entities = entitiesManager.getEntitiesWith<PhysicalComponent>();

for (Entity e : entities) {
    PhysicalComponent phys = e.getComponent<PhysicalComponent>();

    e.x += e.dx;
    e.y += e.dy;
}

You can see that all the entities move with the same code. Yay. And now let's display all the things.

list<Entity> lights = entitiesManager.getEntitiesWith<PhysicalComponent, LightComponent>();

for (Entity e : lights) {
    PhysicalComponent phys = e.getComponent<PhysicalComponent>();
    LightComponent light = e.getComponent<LightComponent>();

    displayLight(light, phys.x, phys.y);
}

list<Entity> sprites = entitiesManager.getEntitiesWith<PhysicalComponent, SpriteComponent>();

for (Entity e : sprites) {
    PhysicalComponent phys = e.getComponent<PhysicalComponent>();
    SpriteComponent sprite = e.getComponent<SpriteComponent>();

    displaySprite(sprite.filename, phys.x, phys.y);
}

And now we have displayed our entities. All the entities with sprites will be displayed with the same code, and so will the entities representing lights.

Cool, what now?

Well, that's it for the moment. This article aimed at explaining the basics of an ECS and how it can help you. The pseudo-code has given you concrete example of simple tasks done in an entity-component fashion. In the next articles, we will be implementing an ECS in C++. If you see any error, or if you have feedback, contact me!