1
\$\begingroup\$

Introduction

I am a newbie, so please take me easy :). I am writing a low-level game engine using C++, GLFW and also OpenGL. This is a continuation of Entity Component System Using C++ I've implemented the sugestions.

Modifications

Here's a rundown of the changes I've made since the last iteration:

  1. The entities are now stored in a contiguous array. Whenever an entity is removed, the last entity is moved to its place. This approach, however, raises a question: how can users identify each Entity if their positions are constantly changing? To address this, we provide users with an EntityKey, which contains a weak pointer to the entity, instead of direct access to the internal Entity.
  2. I've clearly differentiated between Entities and EntityKeys: The ECSManager only interacts with EntityKeys, while the internals (including the Systems) use Entities for their lightweight nature.
  3. I've introduced TagTypes, which are designed to be faster than the type_index used in the previous iteration. However, I'm uncertain about the extent of the improvements this change brings—it might be an overengineering effort. TagTypes allow us to tag Component types, System types, and combinations of Variadic templates (for caching in the SystemContext's update function). By using TagTypes, we can avoid the need for maps (instead of std::unordered_map<type_index ...>), as they index from 0.
  4. I've incorporated Archetypes into the system. Archetypes are structures that hold a std::unordered_set of entities, categorized based on the Components they contain. This feature could potentially enhance the speed of finding all entities with certain components, as we only need to perform an intersection operation. Before intersecting all the std::unordered_set's, we first check if the required data is available in the Cache.

Self-critique

I believe the TypeTag.h could be better organized; it currently appears cluttered. Although the solution I've implemented is the best I could come up with, I'm certain there are more efficient alternatives out there. I have mixed feelings about the EntityKey being a friend of the ECSManager. While it is functionally correct—preventing end users from creating their own EntityKey and accessing the Entity—it still raises some concerns.

I'm skeptical about the performance improvements brought by the Archetypes. I suspect the primary performance boost will come from the Cache system rather than the Archetypes. Initially, I intended for the EntityKeys to own the Entities, so that when an EntityKey goes out of scope, its associated Entity is also removed from the ECS. However, this proved challenging as it would couple the EntityManager to the ComponentManager. This coupling would be necessary for the destructor (of the shared pointer that should have been inside EntityKey), as the removal of an entity should be reflected in both systems. I found this coupling unacceptable, so I opted for a different solution where the EntityManager owns the Entities directly.

I welcome any feedback or suggestions you may have. Your input is greatly appreciated.

Source Code

Archetype.h

#pragma once

#include <unordered_set>

#include "Entity.h"

namespace std
{
    template<>
    struct hash<Entity>
    {
        std::size_t operator()(const Entity& entity) const { return std::hash<size_t>{}(entity.index); }
    };
}

inline bool operator==(const Entity& lhs, const Entity& rhs) { return lhs.index == rhs.index; }

class BaseArchetype
{
public:
    virtual void addEntity(Entity entity) = 0;
    virtual void removeEntity(Entity entity) = 0;

    virtual const std::unordered_set<Entity>& getEntities() const = 0;
};

template<typename ComponentType>
class Archetype : public BaseArchetype
{
public:
    void addEntity(Entity entity) override { entities.insert(entity); }
    void removeEntity(Entity entity) override { entities.erase(entity); }

    const std::unordered_set<Entity>& getEntities() const override { return entities; }

private:
    std::unordered_set<Entity> entities;
};

ArchetypeManager.h

#pragma once

#include "Cache.h"
#include "ArchetypeQuery.h"

class ArchetypeManager
{
public:
    ArchetypeManager()
        : archetypeQuery(archetypeStorage) { }

    template<typename ComponentType>
    void addComponent(Entity entity)
    {
        archetypeStorage.addComponent<ComponentType>(entity);
        cache.clear();
    }

    void removeEntity(Entity entity)
    {
        archetypeStorage.removeEntity(entity);
        cache.clear();
    }

    template<typename ComponentType>
    void removeComponent(Entity entity)
    {
        archetypeStorage.removeComponent<ComponentType>(entity);
        cache.clear();
    }

    template<typename ComponentType>
    const std::unordered_set<Entity>& getEntities() const
    {
        return archetypeStorage.getEntities<ComponentType>();
    }

    template<typename... ComponentTypes>
    std::unordered_set<Entity> findCommonEntities()
    {
        auto cachedEntities = cache.retrieve<ComponentTypes...>();
        if (cachedEntities) {
            return *cachedEntities;
        }
        else {
            std::unordered_set<Entity> entities = archetypeQuery.findCommonEntities<ComponentTypes...>();
            cache.store<ComponentTypes...>(entities);
            return entities;
        }
    }

    void clearCache() 
    {
        cache.clear();
    }

private:
    ArchetypeStorage archetypeStorage;
    ArchetypeQuery archetypeQuery;
    Cache<std::unordered_set<Entity>> cache;
};

ArchetypeQuery.cpp

#include "ArchetypeQuery.h"

ArchetypeQuery::EntitySet ArchetypeQuery::findCommonEntities(const std::vector<EntitySet>& entitySets) const
{
    auto smallestSetIt = findSmallestSet(entitySets);

    if (smallestSetIt->empty())
        return { };

    EntitySet commonEntities = *smallestSetIt;

    for (auto it = entitySets.begin(); it != entitySets.end(); ++it) {
        if (it == smallestSetIt)
            continue;

        commonEntities = intersectUnorderedSets(commonEntities, *it);
    }

    return commonEntities;
}

std::vector<ArchetypeQuery::EntitySet>::const_iterator ArchetypeQuery::
    findSmallestSet(const std::vector<EntitySet>& entitySets) const
{
    return std::min_element(entitySets.begin(), entitySets.end(),
        [](const EntitySet& a, const EntitySet& b) {
            return a.size() < b.size();
        });
}

ArchetypeQuery::EntitySet ArchetypeQuery::
    intersectUnorderedSets(const EntitySet& set1, const EntitySet& set2) const
{
    EntitySet intersection;

    for (const auto& entity : set1) 
        if (set2.find(entity) != set2.end()) 
            intersection.insert(entity);

    return intersection;
}

ArchetypeQuery.h

#pragma once

#include <iterator>
#include <algorithm>

#include "ArchetypeStorage.h"

class ArchetypeQuery
{
public:
    using EntitySet = std::unordered_set<Entity>;

    ArchetypeQuery(ArchetypeStorage& archetypeStorage)
        : archetypeStorage(archetypeStorage) { }

    template<typename... ComponentTypes>
    EntitySet findCommonEntities() 
    {
        std::vector<EntitySet> entitySets;
        (entitySets.push_back(archetypeStorage.getEntities<ComponentTypes>()), ...);
        return findCommonEntities(entitySets);
    }

private:
    EntitySet findCommonEntities(const std::vector<EntitySet>& entitySets) const;
    std::vector<EntitySet>::const_iterator findSmallestSet(const std::vector<EntitySet>& entitySets) const;
    EntitySet intersectUnorderedSets(const EntitySet& set1, const EntitySet& set2) const;

private:
    ArchetypeStorage& archetypeStorage;
};

ArchetypeStorage.h

#pragma once

#include <memory>
#include <vector>

#include "Archetype.h"
#include "TypeTag.h"

class ArchetypeStorage
{
public:
    template<typename ComponentType>
    void addComponent(Entity entity)
    {
        getArchetype<ComponentType>().addEntity(entity);
    }

    void removeEntity(Entity entity)
    {
        for (auto& archetype : archetypes)
            archetype->removeEntity(entity);
    }

    template<typename ComponentType>
    void removeComponent(Entity entity)
    {
        getArchetype<ComponentType>().removeEntity(entity);
    }

    template<typename ComponentType>
    const std::unordered_set<Entity>& getEntities()
    {
        return getArchetype<ComponentType>().getEntities();
    }

private:
    template<typename ComponentType>
    Archetype<ComponentType>& getArchetype()
    {
        size_t index = ComponentTypeTag<ComponentType>::index;
        if (index >= archetypes.size())
            archetypes.resize(index + 1);

        if (archetypes[index] == nullptr)
            archetypes[index] = std::make_unique<Archetype<ComponentType>>();

        return static_cast<Archetype<ComponentType>&>(*archetypes[index]);
    }

private:
    inline static std::vector<std::unique_ptr<BaseArchetype>> archetypes;
};

Cache.h

#pragma once

#include <optional>
#include <vector>

#include "TypeTag.h"

template <typename ResultType>
class Cache 
{
public:
    template <typename... ComponentTypes>
    void store(const ResultType& result) 
    { 
        size_t index = VariadicTypeTag<ComponentTypes...>::index;
        if (index >= cache.size())
            cache.resize(index + 1);
        cache[index] = result;
    }

    template <typename... ComponentTypes>
    std::optional<ResultType> retrieve() const 
    {
        size_t index = VariadicTypeTag<ComponentTypes...>::index;
        return index < cache.size() ? cache[index] : std::nullopt;
    }

    void clear() 
    { 
        cache.clear(); 
    }

private:
    inline static std::vector<std::optional<ResultType>> cache;
};

ComponentManager.h

#pragma once

#include "ComponentPool.h"
#include "TypeTag.h"

class ComponentManager
{
public:
    template<typename ComponentType, typename... Args>
    void addComponent(Entity entity, Args&&... args)
    {
        getComponentPool<ComponentType>().addComponent(entity, std::forward(args)...);
    }

    template<typename ComponentType>
    ComponentType& getComponent(Entity entity)
    {
        return getComponentPool<ComponentType>().getComponent(entity);
    }

    template<typename ComponentType>
    bool hasComponent(Entity entity) 
    {
        return getComponentPool<ComponentType>().hasComponent(entity);
    }

    void removeEntity(Entity entity)
    {
        for (auto& pool : componentPools)
            pool->relocateComponentToEntity(entity);
    }

    template<typename ComponentType>
    void removeComponent(Entity entity)
    {
        getComponentPool<ComponentType>().removeComponentFromEntity(entity);
    }


private:
    template<typename ComponentType>
    ComponentPool<ComponentType>& getComponentPool()
    {
        size_t index = ComponentTypeTag<ComponentType>::index;

        if (index >= componentPools.size())
            componentPools.resize(index + 1);

        if (componentPools[index] == nullptr)
            componentPools[index] = std::make_unique<ComponentPool<ComponentType>>();

        return static_cast<ComponentPool<ComponentType>&>(*componentPools[index]);
    }

private:
    inline static std::vector<std::unique_ptr<BaseComponentPool>> componentPools;
};

ComponentPool.h

#pragma once

#include <stdexcept>
#include <memory>
#include <optional>

#include "EntityExceptions.h"
#include "ComponentPoolExceptions.h"

class BaseComponentPool
{
public:
    virtual ~BaseComponentPool() = default;
    virtual void removeComponentFromEntity(Entity entity) = 0;
    virtual void relocateComponentToEntity(Entity entity) = 0;
    virtual bool hasComponent(Entity entity) const = 0;
};

template <typename ComponentType>
class ComponentPool : public BaseComponentPool
{
public:
    template<typename... Args>
    void addComponent(Entity entity, Args&&... args)
    {
        if (entity.index >= pool.size())
            pool.resize(entity.index + 1);

        pool[entity.index] = ComponentType(std::forward<Args>(args)...);
    }

    void relocateComponentToEntity(Entity entity) override
    {
        if (entity.index >= pool.size())
            throw EntityOutOfBoundsException(entity);

        pool[entity.index] = std::move(pool.back());
        pool.pop_back();
    }

    void removeComponentFromEntity(Entity entity) override
    {
        if (entity.index >= pool.size())
            throw EntityOutOfBoundsException(entity);

        pool[entity.index].reset();
    }


    ComponentType& getComponent(Entity entity) const
    {
        if (entity.index >= pool.size())
            throw EntityOutOfBoundsException(entity);

        if (!pool[entity.index])
            throw ComponentOutOfBoundsException(entity);

        return *pool[entity.index];
    }

    bool hasComponent(Entity entity) const override
    {
        return entity.index < pool.size() && pool[entity.index].has_value();
    }

private:
    inline static std::vector<std::optional<ComponentType>> pool;
};

ComponentPoolExceptions.h

#pragma once

#include <stdexcept>
#include <string>

#include "Entity.h"

class ComponentOutOfBoundsException : public std::runtime_error
{
public:
    ComponentOutOfBoundsException(Entity entity)
        : std::runtime_error(std::to_string(entity.index) + " is out of bounds!") { }
};

ECSManager.h

#pragma once

#include "SystemManager.h"

#include "EntityKey.h"

class ECSManager
{
public:
    ECSManager()
        : systemManager( SystemContext{ entityManager, componentManager, archetypeManager } ) { }

    EntityKey createEntity()
    {
        archetypeManager.clearCache();
        return { entityManager.createEntity() };
    }

    template<typename ComponentType, typename... Args>
    void addComponent(const EntityKey& key, Args&&... args)
    {
        Entity entity = key.getEntity();
        componentManager.addComponent<ComponentType>(entity, std::forward(args)...);
        archetypeManager.addComponent<ComponentType>(entity);
    }

    void removeEntity(const EntityKey& key)
    {
        Entity entity = key.getEntity();
        componentManager.removeEntity(entity);
        archetypeManager.removeEntity(entity);
        entityManager.removeEntity(entity);
    }

    template<typename ComponentType>
    void removeComponent(const EntityKey& key)
    {
        Entity entity = key.getEntity();
        componentManager.removeComponent<ComponentType>(entity);
        archetypeManager.removeComponent<ComponentType>(entity);
    }

    template<typename SystemType, typename... Args>
    requires std::derived_from<SystemType, System>
    void addSystem(Args&&... args)
    {
        systemManager.addSystem<SystemType>(std::forward<Args>(args)...);
    }

    template<typename SystemType>
    requires std::derived_from<SystemType, System>
    void removeSystem()
    {
        systemManager.removeSystem<SystemType>();
    }

    template<typename SystemType>
    requires std::derived_from<SystemType, System>
    bool hasSystem() const
    {
        return systemManager.hasSystem<SystemType>();
    }

    template<typename SystemType>
    requires std::derived_from<SystemType, System>
    void enableSystem(bool enabled)
    {
        systemManager.enableSystem<SystemType>(enabled);
    }

    void updateSystems(float deltaTime) 
    {
        systemManager.updateSystems(deltaTime);
    }

private:
    EntityManager entityManager;
    ComponentManager componentManager;
    ArchetypeManager archetypeManager;
    SystemManager systemManager;
};

Entity.h

#pragma once

struct Entity
{
    size_t index;
};

EntityExceptions.h

#pragma once

#include <stdexcept>
#include <string>

#include "Entity.h"

class EntityOutOfBoundsException : std::runtime_error
{
public:
    EntityOutOfBoundsException(Entity entity)
        : runtime_error("Entity: " + std::to_string(entity.index) + " is out of bounds!") { }
};

class EntityIsAlreadyDestroyedException : std::runtime_error
{
public:
    EntityIsAlreadyDestroyedException()
        : runtime_error("Attempted to access a destroyed entity") { }
};

EntityKey.h

#pragma once

#include <memory>

#include "EntityExceptions.h"

class EntityKey
{
public:
    bool operator==(const EntityKey& other) { return id == other.id; }

    bool isRemoved() const { return entity.expired(); }

private:
    EntityKey(std::weak_ptr<Entity> entity)
        : entity(std::move(entity)), id(IDCounter++) { }

    Entity getEntity() const 
    { 
        if (entity.expired()) 
            throw EntityIsAlreadyDestroyedException();

        return *entity.lock(); 
    }

private:
    std::weak_ptr<Entity> entity;
    size_t id;

private:
    inline static size_t IDCounter = 0;

    friend class ECSManager;
};

EntityManager.h

#pragma once

#include <memory>
#include <vector>

#include "EntityExceptions.h"

class EntityManager
{
public:
    std::weak_ptr<Entity> createEntity();
    void removeEntity(Entity entity);

    size_t getEntityCount() const { return entities.size(); }

private:
    inline static std::vector<std::shared_ptr<Entity>> entities;
};

EntityManager.cpp

#include "EntityManager.h"

std::weak_ptr<Entity> EntityManager::createEntity()
{
    auto entity = std::make_shared<Entity>(entities.size());
    entities.push_back(entity);
    return entity;
}

void EntityManager::removeEntity(Entity entity)
{
    if (entity.index >= entities.size() || entities.empty())
        throw EntityOutOfBoundsException(entity);

    if (entity.index < entities.size()) {   
        entities[entity.index] = entities.back();
        entities[entity.index]->index = entity.index;
    }

    entities.pop_back();
}

EntityManager.h

#pragma once

#include <memory>
#include <vector>

#include "EntityExceptions.h"

class EntityManager
{
public:
    std::weak_ptr<Entity> createEntity();
    void removeEntity(Entity entity);

    size_t getEntityCount() const { return entities.size(); }

private:
    inline static std::vector<std::shared_ptr<Entity>> entities;
};

System.h

#pragma once

#include "SystemContext.h"

class System
{
public:
    virtual ~System() = default;

    virtual void onAdded() = 0;
    virtual void update(float deltaTime, SystemContext& context) = 0;
    virtual void onRemoved() = 0;

    void enable(bool enabled) { this->enabled = enabled; }
    bool isEnabled() const { return enabled; }
private:
    bool enabled = true;
};

SystemContext.h

#pragma once

#include <iterator>

#include "ComponentManager.h"
#include "EntityManager.h"
#include "ArchetypeManager.h"
#include "Cache.h"

class SystemContext
{
public:
    template<typename... ComponentTypes>
    using UpdateFn = std::function<void(Entity entity, ComponentTypes&...)>;

    SystemContext(const EntityManager& entityManager, 
                  ComponentManager& componentManager,  ArchetypeManager& archetypeManager)
        : entityManager(entityManager), 
          componentManager(componentManager), archetypeManager(archetypeManager) { }

    template<typename ComponentType>
    bool hasComponent(Entity entity) const
    {
        return componentManager.hasComponent<ComponentType>(entity);
    }

    template<typename ComponentType>
    const ComponentType& getComponent(Entity entity) const
    {
        return componentManager.getComponent<ComponentType>(entity);
    }

    template<typename ComponentType, typename... Args>
    void createComponent(Entity entity, Args&&... args)
    {
        componentManager.addComponent<ComponentType>(entity, std::forward(args)...);
        archetypeManager.addComponent<ComponentType>(entity);
    } 

    template<typename... ComponentTypes>
    void updateEntitiesWithComponents(const UpdateFn<ComponentTypes...>& update) const
    {
        for (auto entity : archetypeManager.findCommonEntities<ComponentTypes...>())
            update(entity, componentManager.getComponent<ComponentTypes>(entity)...);
    }

private:
    const EntityManager& entityManager;
    ComponentManager& componentManager;
    ArchetypeManager& archetypeManager;
};

SystemExceptions.h

#pragma once

#include <stdexcept>

class SystemNotFoundException : public std::runtime_error
{
public:
    SystemNotFoundException(const std::string& systemType)
        : std::runtime_error("System not found: " + systemType) {}
};

class SystemAlreadyAddedException : public std::runtime_error
{
public:
    SystemAlreadyAddedException(const std::string& systemType)
        : std::runtime_error("System is already added: " + systemType) {}
};

SystemManager.h

#pragma once

#include <list>
#include <memory>
#include <stdexcept>

#include "System.h"
#include "SystemExceptions.h"
#include "TypeTag.h"

class SystemManager
{
public:
    SystemManager(const SystemContext& context)
        : context(context) { }

    template<typename SystemType, typename... Args>
    void addSystem(Args&&... args)
    {
        size_t index = SystemTypeTag<SystemType>::index;
        
        if(index >= systems.size())
            systems.resize(index + 1);

        if(systems[index])
            throw SystemAlreadyAddedException(typeid(SystemType).name());

        systems[index] = std::make_unique<SystemType>(std::forward<Args>(args)...);
        systems[index]->onAdded();
    }

    template<typename SystemType>
    void removeSystem()
    {
        size_t index = SystemTypeTag<SystemType>::index;

        if(index >= systems.size() || systems[index] == nullptr)
            throw SystemNotFoundException(typeid(SystemType).name());

        systems[index]->onRemoved();
        systems[index].reset();
    }

    template<typename SystemType>
    bool hasSystem() const
    {
        size_t index = SystemTypeTag<SystemType>::index;

        return index < systems.size() && systems[index];
    }

    template<typename SystemType>
    void enableSystem(bool enabled)
    {
        size_t index = SystemTypeTag<SystemType>::index;
        
        systems[index]->enabled(enabled);
    }

    void updateSystems(float deltaTime) 
    {
        for (auto& system : systems)
            if(system != nullptr && system->isEnabled())
                system->update(deltaTime, context);
    }

private:
    inline static std::vector<std::unique_ptr<System>> systems;

    SystemContext context;
};

TypeTag.h

#pragma once

struct BaseComponentTypeTag
{
    inline static size_t typeCounter = 0;
};

template <typename ComponentType>
struct ComponentTypeTag : public BaseComponentTypeTag
{
    inline static size_t index = typeCounter++;
};

struct BaseSystemTypeTag
{
    inline static size_t typeCounter = 0;
};

template <typename ComponentType>
struct SystemTypeTag : public BaseSystemTypeTag
{
    inline static size_t index = typeCounter++;
};

struct BaseVariadicTypeTag 
{
    inline static size_t typeCounter = 0;
};

template <typename... ComponentTypes>
struct VariadicTypeTag : BaseVariadicTypeTag 
{
    inline static size_t index = typeCounter++;
};

Note- I hope I didn't forget any files here

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Hm, I don't see the definition of EntityManager::createEntity(). I suspect you are missing one or more .cpp files. \$\endgroup\$
    – G. Sliepen
    Jul 3, 2023 at 20:47
  • \$\begingroup\$ I forgot EntityManager.h, you're right; Let me check again I have all the files. \$\endgroup\$ Jul 3, 2023 at 20:55
  • \$\begingroup\$ I think that's all. Sorry for the inconvenience; let me know if i forgot anything else \$\endgroup\$ Jul 3, 2023 at 21:01

1 Answer 1

2
\$\begingroup\$

Performance is important

The goal of an ECS is to improve performance when handling large numbers of objects. It does that by separating the components from the entities and storing them separately. However, your implementation might actually be slower and use more memory than if you had no ECS at all.

Again, both memory and CPU performance matter. You also want to think about how often you do certain operations: you probably are going to update() several systems every frame, and you might add and remove multiple entities each frame. You want high, and just as important, consistent performance.

There are a lot of memory allocations happening in your code. That is a problem, because it takes some CPU time to do the allocation, memory might get fragmented, and there is some bookkeeping overhead for each allocation, so even if you do new int you might use a lot more memory than sizeof(int). While you don't explicitly call new (which is good), the following things allocate memory:

  • std::unqiue_ptr<>: one allocation
  • std::shared_ptr<>: at least one allocation (see std::make_shared<>())
  • std::unordered_set<>: one allocation for each element in the set
  • std::vector<>: one contiguous allocation to hold all elements, but if you don't reserve() up front it might cause multiple allocations/deallocations while the vector is growing

What you want to achieve is that calls to update() require zero memory allocations, and that adding/removing entities and components also requires close to zero allocations.

A cache that you throw away whenever you add/remove components is pretty bad. Why not just in removeComponent() if you can just remove that one entity from the stored set of entities? And in addComponent(), check if you can just add it?

Instead of using a cache, it would be better to lay out data in memory so that it's efficient to add and remove components to begin with. Have a look at this Code Review question, where the poster has written an ECS framework that focussed heavily on keeping things in dense arrays and vectors, and having fast updates.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.