From 97d7fb425da906947cc45e11fadb35f708da50d6 Mon Sep 17 00:00:00 2001 From: Kelly Rauchenberger Date: Wed, 7 Feb 2018 14:13:32 -0500 Subject: Changed EntityManager to dense vector This should improve speed, because entity lookup will be O(1) instead of O(log n). Deletion is also O(1). Insert stays at potentially O(n), but still should be overall faster than the previous method. Also replaced some asserts with exceptions. Also made Component polymorphic so that deletion actually works properly. --- src/component.h | 4 + src/entity_manager.cpp | 11 +-- src/entity_manager.h | 235 +++++++++++++++++++++++++++++-------------------- src/system.h | 15 ++-- src/system_manager.h | 43 +++++---- 5 files changed, 184 insertions(+), 124 deletions(-) diff --git a/src/component.h b/src/component.h index 2cbdc9d..b81dbee 100644 --- a/src/component.h +++ b/src/component.h @@ -2,6 +2,10 @@ #define COMPONENT_H_F0CE4573 class Component { +public: + + virtual ~Component() = default; + }; #endif /* end of include guard: COMPONENT_H_F0CE4573 */ diff --git a/src/entity_manager.cpp b/src/entity_manager.cpp index 9ad758b..f792e17 100644 --- a/src/entity_manager.cpp +++ b/src/entity_manager.cpp @@ -4,17 +4,18 @@ #include "entity_manager.h" template <> -std::set EntityManager::getEntitiesWithComponents<>(std::set& componentTypes) +std::set EntityManager::getEntitiesWithComponents<>( + std::set& componentTypes) { if (cachedComponents.count(componentTypes) == 1) { return cachedComponents[componentTypes]; } - std::set& cache = cachedComponents[componentTypes]; - for (auto& entity : entities) + std::set& cache = cachedComponents[componentTypes]; + for (id_type entity = 0; entity < entities.size(); entity++) { - EntityData& data = entity.second; + EntityData& data = entities[entity]; bool cacheEntity = true; for (auto& componentType : componentTypes) @@ -28,7 +29,7 @@ std::set EntityManager::getEntitiesWithComponents<>(std::set +#include #include #include -#include +#include #include "component.h" #include "algorithms.h" class EntityManager { - private: - struct EntityData { - std::map> components; - }; +private: - std::map entities; - std::map, std::set> cachedComponents; + struct EntityData { + std::map> components; + }; - int nextEntityID = 0; + using database_type = std::vector; - template - std::set getEntitiesWithComponentsHelper(std::set& componentTypes) - { - componentTypes.insert(typeid(T)); +public: - return getEntitiesWithComponents(componentTypes); - } + using id_type = database_type::size_type; - template - std::set getEntitiesWithComponents(std::set& componentTypes) - { - return getEntitiesWithComponentsHelper(componentTypes); - } +private: - public: - EntityManager() = default; - EntityManager(const EntityManager& copy) = delete; + database_type entities; + std::vector slotAvailable; + std::map, std::set> cachedComponents; - int emplaceEntity() - { - // Find a suitable entity ID - while ((entities.count(nextEntityID) == 1) && (nextEntityID >= 0)) - { - nextEntityID++; - } + id_type nextEntityID = 0; - if (nextEntityID < 0) - { - nextEntityID = 0; + template + std::set getEntitiesWithComponentsHelper( + std::set& componentTypes) + { + componentTypes.insert(typeid(T)); - while ((entities.count(nextEntityID) == 1) && (nextEntityID >= 0)) - { - nextEntityID++; - } + return getEntitiesWithComponents(componentTypes); + } - assert(nextEntityID >= 0); - } + template + std::set getEntitiesWithComponents( + std::set& componentTypes) + { + return getEntitiesWithComponentsHelper(componentTypes); + } - // Initialize the data - int id = nextEntityID++; - entities[id]; +public: - return id; - } + EntityManager() = default; - void deleteEntity(int entity) - { - assert(entities.count(entity) == 1); + EntityManager(const EntityManager& copy) = delete; - // Uncache components - for (auto& cache : cachedComponents) + id_type emplaceEntity() + { + if (nextEntityID >= entities.size()) + { + // If the database is saturated, add a new element for the new entity. + entities.emplace_back(); + slotAvailable.push_back(false); + + return nextEntityID++; + } else { + // If there is an available slot in the database, use it. + id_type id = nextEntityID++; + slotAvailable[id] = false; + + // Fast forward the next available slot pointer to an available slot. + while ((nextEntityID < entities.size()) && !slotAvailable[nextEntityID]) { - cache.second.erase(entity); + nextEntityID++; } - // Destroy the data - entities.erase(entity); + return id; + } + } + + void deleteEntity(id_type entity) + { + if ((entity >= entities.size()) || slotAvailable[entity]) + { + throw std::invalid_argument("Cannot delete non-existent entity"); } - template - T& emplaceComponent(int entity, Args&&... args) + // Uncache components + for (auto& cache : cachedComponents) { - assert(entities.count(entity) == 1); + cache.second.erase(entity); + } + + // Destroy the data + entities[entity].components.clear(); - EntityData& data = entities[entity]; - std::type_index componentType = typeid(T); + // Mark the slot as available + slotAvailable[entity] = true; - assert(data.components.count(componentType) == 0); + if (entity < nextEntityID) + { + nextEntityID = entity; + } + } - // Initialize the component - std::unique_ptr ptr = std::unique_ptr(new T(std::forward(args)...)); - T& component = *ptr; - data.components[componentType] = std::move(ptr); + template + T& emplaceComponent(id_type entity, Args&&... args) + { + if ((entity >= entities.size()) || slotAvailable[entity]) + { + throw std::invalid_argument("Cannot delete non-existent entity"); + } - // Invalidate related caches - erase_if(cachedComponents, [&componentType] (std::pair, std::set>& cache) { - return cache.first.count(componentType) == 1; - }); + EntityData& data = entities[entity]; + std::type_index componentType = typeid(T); - return component; + if (data.components.count(componentType)) + { + throw std::invalid_argument("Cannot emplace already-existent component"); } - template - void removeComponent(int entity) + // Initialize the component + std::unique_ptr ptr(new T(std::forward(args)...)); + T& component = *ptr; + data.components[componentType] = std::move(ptr); + + // Invalidate related caches + erase_if( + cachedComponents, + [&componentType] ( + std::pair, std::set>& cache) { + return cache.first.count(componentType) == 1; + }); + + return component; + } + + template + void removeComponent(id_type entity) + { + if ((entity >= entities.size()) || slotAvailable[entity]) { - assert(entities.count(entity) == 1); + throw std::invalid_argument("Cannot delete non-existent entity"); + } - EntityData& data = entities[entity]; - std::type_index componentType = typeid(T); + EntityData& data = entities[entity]; + std::type_index componentType = typeid(T); - assert(data.components.count(componentType) == 1); + if (!data.components.count(componentType)) + { + throw std::invalid_argument("Cannot delete non-existent component"); + } - // Destroy the component - data.components.erase(componentType); + // Destroy the component + data.components.erase(componentType); - // Uncache the component - for (auto& cache : cachedComponents) + // Uncache the component + for (auto& cache : cachedComponents) + { + if (cache.first.count(componentType) == 1) { - if (cache.first.count(componentType) == 1) - { - cache.second.erase(entity); - } + cache.second.erase(entity); } } + } - template - T& getComponent(int entity) + template + T& getComponent(id_type entity) + { + if ((entity >= entities.size()) || slotAvailable[entity]) { - assert(entities.count(entity) == 1); - - EntityData& data = entities[entity]; - std::type_index componentType = typeid(T); + throw std::invalid_argument("Cannot delete non-existent entity"); + } - assert(data.components.count(componentType) == 1); + EntityData& data = entities[entity]; + std::type_index componentType = typeid(T); - return *((T*)data.components[componentType].get()); + if (!data.components.count(componentType)) + { + throw std::invalid_argument("Cannot get non-existent component"); } - template - std::set getEntitiesWithComponents() - { - std::set componentTypes; + return *dynamic_cast(data.components[componentType].get()); + } - return getEntitiesWithComponentsHelper(componentTypes); - } + template + std::set getEntitiesWithComponents() + { + std::set componentTypes; + + return getEntitiesWithComponentsHelper(componentTypes); + } }; template <> -std::set EntityManager::getEntitiesWithComponents<>(std::set& componentTypes); +std::set EntityManager::getEntitiesWithComponents<>( + std::set& componentTypes); #endif /* end of include guard: ENTITY_MANAGER_H_C5832F11 */ diff --git a/src/system.h b/src/system.h index af3fb77..489afd0 100644 --- a/src/system.h +++ b/src/system.h @@ -4,14 +4,17 @@ class Game; class System { - public: - System(Game& game) - : game(game) {} +public: + System(Game& game) + : game(game) {} - virtual void tick(double dt) = 0; + virtual ~System() = default; - protected: - Game& game; + virtual void tick(double dt) = 0; + +protected: + + Game& game; }; #endif /* end of include guard: SYSTEM_H_B61A8CEA */ diff --git a/src/system_manager.h b/src/system_manager.h index 087b71c..e2c98cb 100644 --- a/src/system_manager.h +++ b/src/system_manager.h @@ -5,33 +5,40 @@ #include #include #include +#include #include "system.h" class SystemManager { - private: - std::list> loop; - std::map systems; +private: - public: - template - void emplaceSystem(Game& game, Args&&... args) - { - std::unique_ptr ptr = std::unique_ptr(new T(game, std::forward(args)...)); - std::type_index systemType = typeid(T); + std::list> loop; + std::map systems; - systems[systemType] = ptr.get(); - loop.push_back(std::move(ptr)); - } +public: - template - T& getSystem() - { - std::type_index systemType = typeid(T); + template + void emplaceSystem(Game& game, Args&&... args) + { + std::unique_ptr ptr(new T(game, std::forward(args)...)); + std::type_index systemType = typeid(T); + + systems[systemType] = ptr.get(); + loop.push_back(std::move(ptr)); + } - assert(systems.count(systemType) == 1); + template + T& getSystem() + { + std::type_index systemType = typeid(T); - return *((T*)systems[systemType]); + if (!systems.count(systemType)) + { + throw std::invalid_argument("Cannot get non-existent system"); } + + return *dynamic_cast(systems[systemType]); + } + }; #endif /* end of include guard: SYSTEM_MANAGER_H_544E6056 */ -- cgit 1.4.1