From 97d7fb425da906947cc45e11fadb35f708da50d6 Mon Sep 17 00:00:00 2001
From: Kelly Rauchenberger <fefferburbia@gmail.com>
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/entity_manager.h | 235 ++++++++++++++++++++++++++++++---------------------
 1 file changed, 140 insertions(+), 95 deletions(-)

(limited to 'src/entity_manager.h')

diff --git a/src/entity_manager.h b/src/entity_manager.h
index a36d720..9068fe3 100644
--- a/src/entity_manager.h
+++ b/src/entity_manager.h
@@ -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 */
-- 
cgit 1.4.1