summary refs log tree commit diff stats
diff options
context:
space:
mode:
authorKelly Rauchenberger <fefferburbia@gmail.com>2018-02-07 14:13:32 -0500
committerKelly Rauchenberger <fefferburbia@gmail.com>2018-02-07 14:13:32 -0500
commit97d7fb425da906947cc45e11fadb35f708da50d6 (patch)
treeae1a4a5bbbce97e5dcf50e7390f005fe9be61356
parentda3df061699203eccc9a0c98becaee3ce8050a4f (diff)
downloadtherapy-97d7fb425da906947cc45e11fadb35f708da50d6.tar.gz
therapy-97d7fb425da906947cc45e11fadb35f708da50d6.tar.bz2
therapy-97d7fb425da906947cc45e11fadb35f708da50d6.zip
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.
-rw-r--r--src/component.h4
-rw-r--r--src/entity_manager.cpp11
-rw-r--r--src/entity_manager.h235
-rw-r--r--src/system.h15
-rw-r--r--src/system_manager.h43
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 @@
2#define COMPONENT_H_F0CE4573 2#define COMPONENT_H_F0CE4573
3 3
4class Component { 4class Component {
5public:
6
7 virtual ~Component() = default;
8
5}; 9};
6 10
7#endif /* end of include guard: COMPONENT_H_F0CE4573 */ 11#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 @@
4#include "entity_manager.h" 4#include "entity_manager.h"
5 5
6template <> 6template <>
7std::set<int> EntityManager::getEntitiesWithComponents<>(std::set<std::type_index>& componentTypes) 7std::set<EntityManager::id_type> EntityManager::getEntitiesWithComponents<>(
8 std::set<std::type_index>& componentTypes)
8{ 9{
9 if (cachedComponents.count(componentTypes) == 1) 10 if (cachedComponents.count(componentTypes) == 1)
10 { 11 {
11 return cachedComponents[componentTypes]; 12 return cachedComponents[componentTypes];
12 } 13 }
13 14
14 std::set<int>& cache = cachedComponents[componentTypes]; 15 std::set<id_type>& cache = cachedComponents[componentTypes];
15 for (auto& entity : entities) 16 for (id_type entity = 0; entity < entities.size(); entity++)
16 { 17 {
17 EntityData& data = entity.second; 18 EntityData& data = entities[entity];
18 bool cacheEntity = true; 19 bool cacheEntity = true;
19 20
20 for (auto& componentType : componentTypes) 21 for (auto& componentType : componentTypes)
@@ -28,7 +29,7 @@ std::set<int> EntityManager::getEntitiesWithComponents<>(std::set<std::type_inde
28 29
29 if (cacheEntity) 30 if (cacheEntity)
30 { 31 {
31 cache.insert(entity.first); 32 cache.insert(entity);
32 } 33 }
33 } 34 }
34 35
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 @@
2#define ENTITY_MANAGER_H_C5832F11 2#define ENTITY_MANAGER_H_C5832F11
3 3
4#include <map> 4#include <map>
5#include <vector>
5#include <typeindex> 6#include <typeindex>
6#include <set> 7#include <set>
7#include <cassert> 8#include <stdexcept>
8#include "component.h" 9#include "component.h"
9#include "algorithms.h" 10#include "algorithms.h"
10 11
11class EntityManager { 12class EntityManager {
12 private: 13private:
13 struct EntityData {
14 std::map<std::type_index, std::unique_ptr<Component>> components;
15 };
16 14
17 std::map<int, EntityData> entities; 15 struct EntityData {
18 std::map<std::set<std::type_index>, std::set<int>> cachedComponents; 16 std::map<std::type_index, std::unique_ptr<Component>> components;
17 };
19 18
20 int nextEntityID = 0; 19 using database_type = std::vector<EntityData>;
21 20
22 template <class T, class... R> 21public:
23 std::set<int> getEntitiesWithComponentsHelper(std::set<std::type_index>& componentTypes)
24 {
25 componentTypes.insert(typeid(T));
26 22
27 return getEntitiesWithComponents<R...>(componentTypes); 23 using id_type = database_type::size_type;
28 }
29 24
30 template <class... R> 25private:
31 std::set<int> getEntitiesWithComponents(std::set<std::type_index>& componentTypes)
32 {
33 return getEntitiesWithComponentsHelper<R...>(componentTypes);
34 }
35 26
36 public: 27 database_type entities;
37 EntityManager() = default; 28 std::vector<bool> slotAvailable;
38 EntityManager(const EntityManager& copy) = delete; 29 std::map<std::set<std::type_index>, std::set<id_type>> cachedComponents;
39 30
40 int emplaceEntity() 31 id_type nextEntityID = 0;
41 {
42 // Find a suitable entity ID
43 while ((entities.count(nextEntityID) == 1) && (nextEntityID >= 0))
44 {
45 nextEntityID++;
46 }
47 32
48 if (nextEntityID < 0) 33 template <class T, class... R>
49 { 34 std::set<id_type> getEntitiesWithComponentsHelper(
50 nextEntityID = 0; 35 std::set<std::type_index>& componentTypes)
36 {
37 componentTypes.insert(typeid(T));
51 38
52 while ((entities.count(nextEntityID) == 1) && (nextEntityID >= 0)) 39 return getEntitiesWithComponents<R...>(componentTypes);
53 { 40 }
54 nextEntityID++;
55 }
56 41
57 assert(nextEntityID >= 0); 42 template <class... R>
58 } 43 std::set<id_type> getEntitiesWithComponents(
44 std::set<std::type_index>& componentTypes)
45 {
46 return getEntitiesWithComponentsHelper<R...>(componentTypes);
47 }
59 48
60 // Initialize the data 49public:
61 int id = nextEntityID++;
62 entities[id];
63 50
64 return id; 51 EntityManager() = default;
65 }
66 52
67 void deleteEntity(int entity) 53 EntityManager(const EntityManager& copy) = delete;
68 {
69 assert(entities.count(entity) == 1);
70 54
71 // Uncache components 55 id_type emplaceEntity()
72 for (auto& cache : cachedComponents) 56 {
57 if (nextEntityID >= entities.size())
58 {
59 // If the database is saturated, add a new element for the new entity.
60 entities.emplace_back();
61 slotAvailable.push_back(false);
62
63 return nextEntityID++;
64 } else {
65 // If there is an available slot in the database, use it.
66 id_type id = nextEntityID++;
67 slotAvailable[id] = false;
68
69 // Fast forward the next available slot pointer to an available slot.
70 while ((nextEntityID < entities.size()) && !slotAvailable[nextEntityID])
73 { 71 {
74 cache.second.erase(entity); 72 nextEntityID++;
75 } 73 }
76 74
77 // Destroy the data 75 return id;
78 entities.erase(entity); 76 }
77 }
78
79 void deleteEntity(id_type entity)
80 {
81 if ((entity >= entities.size()) || slotAvailable[entity])
82 {
83 throw std::invalid_argument("Cannot delete non-existent entity");
79 } 84 }
80 85
81 template <class T, class... Args> 86 // Uncache components
82 T& emplaceComponent(int entity, Args&&... args) 87 for (auto& cache : cachedComponents)
83 { 88 {
84 assert(entities.count(entity) == 1); 89 cache.second.erase(entity);
90 }
91
92 // Destroy the data
93 entities[entity].components.clear();
85 94
86 EntityData& data = entities[entity]; 95 // Mark the slot as available
87 std::type_index componentType = typeid(T); 96 slotAvailable[entity] = true;
88 97
89 assert(data.components.count(componentType) == 0); 98 if (entity < nextEntityID)
99 {
100 nextEntityID = entity;
101 }
102 }
90 103
91 // Initialize the component 104 template <class T, class... Args>
92 std::unique_ptr<T> ptr = std::unique_ptr<T>(new T(std::forward<Args>(args)...)); 105 T& emplaceComponent(id_type entity, Args&&... args)
93 T& component = *ptr; 106 {
94 data.components[componentType] = std::move(ptr); 107 if ((entity >= entities.size()) || slotAvailable[entity])
108 {
109 throw std::invalid_argument("Cannot delete non-existent entity");
110 }
95 111
96 // Invalidate related caches 112 EntityData& data = entities[entity];
97 erase_if(cachedComponents, [&componentType] (std::pair<const std::set<std::type_index>, std::set<int>>& cache) { 113 std::type_index componentType = typeid(T);
98 return cache.first.count(componentType) == 1;
99 });
100 114
101 return component; 115 if (data.components.count(componentType))
116 {
117 throw std::invalid_argument("Cannot emplace already-existent component");
102 } 118 }
103 119
104 template <class T> 120 // Initialize the component
105 void removeComponent(int entity) 121 std::unique_ptr<T> ptr(new T(std::forward<Args>(args)...));
122 T& component = *ptr;
123 data.components[componentType] = std::move(ptr);
124
125 // Invalidate related caches
126 erase_if(
127 cachedComponents,
128 [&componentType] (
129 std::pair<const std::set<std::type_index>, std::set<id_type>>& cache) {
130 return cache.first.count(componentType) == 1;
131 });
132
133 return component;
134 }
135
136 template <class T>
137 void removeComponent(id_type entity)
138 {
139 if ((entity >= entities.size()) || slotAvailable[entity])
106 { 140 {
107 assert(entities.count(entity) == 1); 141 throw std::invalid_argument("Cannot delete non-existent entity");
142 }
108 143
109 EntityData& data = entities[entity]; 144 EntityData& data = entities[entity];
110 std::type_index componentType = typeid(T); 145 std::type_index componentType = typeid(T);
111 146
112 assert(data.components.count(componentType) == 1); 147 if (!data.components.count(componentType))
148 {
149 throw std::invalid_argument("Cannot delete non-existent component");
150 }
113 151
114 // Destroy the component 152 // Destroy the component
115 data.components.erase(componentType); 153 data.components.erase(componentType);
116 154
117 // Uncache the component 155 // Uncache the component
118 for (auto& cache : cachedComponents) 156 for (auto& cache : cachedComponents)
157 {
158 if (cache.first.count(componentType) == 1)
119 { 159 {
120 if (cache.first.count(componentType) == 1) 160 cache.second.erase(entity);
121 {
122 cache.second.erase(entity);
123 }
124 } 161 }
125 } 162 }
163 }
126 164
127 template <class T> 165 template <class T>
128 T& getComponent(int entity) 166 T& getComponent(id_type entity)
167 {
168 if ((entity >= entities.size()) || slotAvailable[entity])
129 { 169 {
130 assert(entities.count(entity) == 1); 170 throw std::invalid_argument("Cannot delete non-existent entity");
131 171 }
132 EntityData& data = entities[entity];
133 std::type_index componentType = typeid(T);
134 172
135 assert(data.components.count(componentType) == 1); 173 EntityData& data = entities[entity];
174 std::type_index componentType = typeid(T);
136 175
137 return *((T*)data.components[componentType].get()); 176 if (!data.components.count(componentType))
177 {
178 throw std::invalid_argument("Cannot get non-existent component");
138 } 179 }
139 180
140 template <class... R> 181 return *dynamic_cast<T*>(data.components[componentType].get());
141 std::set<int> getEntitiesWithComponents() 182 }
142 {
143 std::set<std::type_index> componentTypes;
144 183
145 return getEntitiesWithComponentsHelper<R...>(componentTypes); 184 template <class... R>
146 } 185 std::set<id_type> getEntitiesWithComponents()
186 {
187 std::set<std::type_index> componentTypes;
188
189 return getEntitiesWithComponentsHelper<R...>(componentTypes);
190 }
147}; 191};
148 192
149template <> 193template <>
150std::set<int> EntityManager::getEntitiesWithComponents<>(std::set<std::type_index>& componentTypes); 194std::set<EntityManager::id_type> EntityManager::getEntitiesWithComponents<>(
195 std::set<std::type_index>& componentTypes);
151 196
152#endif /* end of include guard: ENTITY_MANAGER_H_C5832F11 */ 197#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 @@
4class Game; 4class Game;
5 5
6class System { 6class System {
7 public: 7public:
8 System(Game& game) 8 System(Game& game)
9 : game(game) {} 9 : game(game) {}
10 10
11 virtual void tick(double dt) = 0; 11 virtual ~System() = default;
12 12
13 protected: 13 virtual void tick(double dt) = 0;
14 Game& game; 14
15protected:
16
17 Game& game;
15}; 18};
16 19
17#endif /* end of include guard: SYSTEM_H_B61A8CEA */ 20#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 @@
5#include <memory> 5#include <memory>
6#include <map> 6#include <map>
7#include <typeindex> 7#include <typeindex>
8#include <stdexcept>
8#include "system.h" 9#include "system.h"
9 10
10class SystemManager { 11class SystemManager {
11 private: 12private:
12 std::list<std::unique_ptr<System>> loop;
13 std::map<std::type_index, System*> systems;
14 13
15 public: 14 std::list<std::unique_ptr<System>> loop;
16 template <class T, class... Args> 15 std::map<std::type_index, System*> systems;
17 void emplaceSystem(Game& game, Args&&... args)
18 {
19 std::unique_ptr<T> ptr = std::unique_ptr<T>(new T(game, std::forward<Args>(args)...));
20 std::type_index systemType = typeid(T);
21 16
22 systems[systemType] = ptr.get(); 17public:
23 loop.push_back(std::move(ptr));
24 }
25 18
26 template <class T> 19 template <class T, class... Args>
27 T& getSystem() 20 void emplaceSystem(Game& game, Args&&... args)
28 { 21 {
29 std::type_index systemType = typeid(T); 22 std::unique_ptr<T> ptr(new T(game, std::forward<Args>(args)...));
23 std::type_index systemType = typeid(T);
24
25 systems[systemType] = ptr.get();
26 loop.push_back(std::move(ptr));
27 }
30 28
31 assert(systems.count(systemType) == 1); 29 template <class T>
30 T& getSystem()
31 {
32 std::type_index systemType = typeid(T);
32 33
33 return *((T*)systems[systemType]); 34 if (!systems.count(systemType))
35 {
36 throw std::invalid_argument("Cannot get non-existent system");
34 } 37 }
38
39 return *dynamic_cast<T*>(systems[systemType]);
40 }
41
35}; 42};
36 43
37#endif /* end of include guard: SYSTEM_MANAGER_H_544E6056 */ 44#endif /* end of include guard: SYSTEM_MANAGER_H_544E6056 */