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:
- 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.
- 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.
- 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.
- 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
EntityManager::createEntity(). I suspect you are missing one or more .cpp files. \$\endgroup\$