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.

5 files changed, 184 insertions, 124 deletions

@@ -2,6 +2,10 @@
 #define COMPONENT_H_F0CE4573
 
 class Component {
+public:
+
+  virtual ~Component() = default;
+
 };
 
 #endif /* end of include guard: COMPONENT_H_F0CE4573 */
@@ -4,17 +4,18 @@
 #include "entity_manager.h"
 
 template <>
-std::set<int> EntityManager::getEntitiesWithComponents<>(std::set<std::type_index>& componentTypes)
+std::set<EntityManager::id_type> EntityManager::getEntitiesWithComponents<>(
+  std::set<std::type_index>& componentTypes)
 {
   if (cachedComponents.count(componentTypes) == 1)
   {
     return cachedComponents[componentTypes];
   }
 
-  std::set<int>& cache = cachedComponents[componentTypes];
-  for (auto& entity : entities)
+  std::set<id_type>& 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<int> EntityManager::getEntitiesWithComponents<>(std::set<std::type_inde
 
     if (cacheEntity)
     {
-      cache.insert(entity.first);
+      cache.insert(entity);
     }
   }
 
@@ -2,151 +2,196 @@
 #define ENTITY_MANAGER_H_C5832F11
 
 #include <map>
+#include <vector>
 #include <typeindex>
 #include <set>
-#include <cassert>
+#include <stdexcept>
 #include "component.h"
 #include "algorithms.h"
 
 class EntityManager {
-  private:
-    struct EntityData {
-      std::map<std::type_index, std::unique_ptr<Component>> components;
-    };
+private:
 
-    std::map<int, EntityData> entities;
-    std::map<std::set<std::type_index>, std::set<int>> cachedComponents;
+  struct EntityData {
+    std::map<std::type_index, std::unique_ptr<Component>> components;
+  };
 
-    int nextEntityID = 0;
+  using database_type = std::vector<EntityData>;
 
-    template <class T, class... R>
-    std::set<int> getEntitiesWithComponentsHelper(std::set<std::type_index>& componentTypes)
-    {
-      componentTypes.insert(typeid(T));
+public:
 
-      return getEntitiesWithComponents<R...>(componentTypes);
-    }
+  using id_type = database_type::size_type;
 
-    template <class... R>
-    std::set<int> getEntitiesWithComponents(std::set<std::type_index>& componentTypes)
-    {
-      return getEntitiesWithComponentsHelper<R...>(componentTypes);
-    }
+private:
 
-  public:
-    EntityManager() = default;
-    EntityManager(const EntityManager& copy) = delete;
+  database_type entities;
+  std::vector<bool> slotAvailable;
+  std::map<std::set<std::type_index>, std::set<id_type>> 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 <class T, class... R>
+  std::set<id_type> getEntitiesWithComponentsHelper(
+    std::set<std::type_index>& componentTypes)
+  {
+    componentTypes.insert(typeid(T));
 
-        while ((entities.count(nextEntityID) == 1) && (nextEntityID >= 0))
-        {
-          nextEntityID++;
-        }
+    return getEntitiesWithComponents<R...>(componentTypes);
+  }
 
-        assert(nextEntityID >= 0);
-      }
+  template <class... R>
+  std::set<id_type> getEntitiesWithComponents(
+    std::set<std::type_index>& componentTypes)
+  {
+    return getEntitiesWithComponentsHelper<R...>(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 <class T, class... Args>
-    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<T> ptr = std::unique_ptr<T>(new T(std::forward<Args>(args)...));
-      T& component = *ptr;
-      data.components[componentType] = std::move(ptr);
+  template <class T, class... Args>
+  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<const std::set<std::type_index>, std::set<int>>& 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 <class T>
-    void removeComponent(int entity)
+    // Initialize the component
+    std::unique_ptr<T> ptr(new T(std::forward<Args>(args)...));
+    T& component = *ptr;
+    data.components[componentType] = std::move(ptr);
+
+    // Invalidate related caches
+    erase_if(
+      cachedComponents,
+      [&componentType] (
+        std::pair<const std::set<std::type_index>, std::set<id_type>>& cache) {
+          return cache.first.count(componentType) == 1;
+        });
+
+    return component;
+  }
+
+  template <class T>
+  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 <class T>
-    T& getComponent(int entity)
+  template <class T>
+  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 <class... R>
-    std::set<int> getEntitiesWithComponents()
-    {
-      std::set<std::type_index> componentTypes;
+    return *dynamic_cast<T*>(data.components[componentType].get());
+  }
 
-      return getEntitiesWithComponentsHelper<R...>(componentTypes);
-    }
+  template <class... R>
+  std::set<id_type> getEntitiesWithComponents()
+  {
+    std::set<std::type_index> componentTypes;
+
+    return getEntitiesWithComponentsHelper<R...>(componentTypes);
+  }
 };
 
 template <>
-std::set<int> EntityManager::getEntitiesWithComponents<>(std::set<std::type_index>& componentTypes);
+std::set<EntityManager::id_type> EntityManager::getEntitiesWithComponents<>(
+  std::set<std::type_index>& componentTypes);
 
 #endif /* end of include guard: ENTITY_MANAGER_H_C5832F11 */
@@ -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 */
@@ -5,33 +5,40 @@
 #include <memory>
 #include <map>
 #include <typeindex>
+#include <stdexcept>
 #include "system.h"
 
 class SystemManager {
-  private:
-    std::list<std::unique_ptr<System>> loop;
-    std::map<std::type_index, System*> systems;
+private:
 
-  public:
-    template <class T, class... Args>
-    void emplaceSystem(Game& game, Args&&... args)
-    {
-      std::unique_ptr<T> ptr = std::unique_ptr<T>(new T(game, std::forward<Args>(args)...));
-      std::type_index systemType = typeid(T);
+  std::list<std::unique_ptr<System>> loop;
+  std::map<std::type_index, System*> systems;
 
-      systems[systemType] = ptr.get();
-      loop.push_back(std::move(ptr));
-    }
+public:
 
-    template <class T>
-    T& getSystem()
-    {
-      std::type_index systemType = typeid(T);
+  template <class T, class... Args>
+  void emplaceSystem(Game& game, Args&&... args)
+  {
+    std::unique_ptr<T> ptr(new T(game, std::forward<Args>(args)...));
+    std::type_index systemType = typeid(T);
+
+    systems[systemType] = ptr.get();
+    loop.push_back(std::move(ptr));
+  }
 
-      assert(systems.count(systemType) == 1);
+  template <class T>
+  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<T*>(systems[systemType]);
+  }
+
 };
 
 #endif /* end of include guard: SYSTEM_MANAGER_H_544E6056 */