This project shows off a 2D multithreaded game engine, designed from scratch and implemented using C++ and SDL.
About the project
The whole project was completed from start of research to completed implementation in seven weeks time. The first three weeks consisted of pure research on multithreaded game engines, while the last 4 weeks were more about testing certain systems and creating the actual game engine from scratch.
The engine features an entity component system, controller support, keyboard and mouse support, asynchronous loading and multithreading. The core of the multithreading lies in the Task manager, the main thread and the worker threads.
A more in depth explanation on the project can be read in my paper .
Code Snippets
Task Manager
This code snippet shows how the task manager works. Important to note is the component map used in nearly all functions in the task manager. This is a map that holds a vector of components per component type. This map is used to create all tasks, and to execute these tasks. With this design, the task manager becomes a bottleneck when many threads want to access it at the same time, this will be changed in future version but could not be done in time for the deadline. The paper lays out several methods that could be used to get rid of this bottleneck, but they are untested.
1#include "pch.h"
2#include "TaskManager.h"
3#include "Components/RenderComponent.h"
4#include "Engine/Engine.h"
5#include "Game/Game.h"
6
7//Function called by a scene when it gets loaded as the active scene, it initializes all keys, counters and sets the reference to the component map
8//This map is used to create and execute all tasks
9void anx::TaskManager::SetComponentMap(std::map<size_t, std::vector<BaseComponent*>>& componentMap)
10{
11 m_NrThreads = ThreadPool::GetInstance().GetNrThreads();
12
13 m_pComponentMap = &componentMap;
14
15 m_Keys.clear();
16 m_Counters.clear();
17 m_LockedKeys.clear();
18 for(auto component: *m_pComponentMap)
19 {
20 if(!component.second.front()->IsLockedToMainThread())
21 {
22 m_Keys.push_back(component.first);
23 m_Counters[component.first].store(0);
24 }
25 else
26 {
27 m_LockedKeys.push_back(component.first);
28 }
29
30 }
31}
32
33bool anx::TaskManager::GetJobRequest(Task& task, bool mainThread)
34{
35 std::unique_lock<std::mutex>lock(m_TaskMutex);
36 //If the engine is notified to quit, make the worker thread exit the loop
37 if (m_Quit) return false;
38
39 if (m_Tasks[int(m_CurrentStage)].try_pop(task))
40 return true;
41
42 //If the main thread wanted to get a job, but all jobs were completed, make sure to notify a worker thread to create new tasks
43 if (mainThread)
44 {
45 m_TaskCondition.notify_one();
46 return false;
47 }
48
49 //When there are no tasks available, wait for more to become available if not al tasks have finished executing
50 if (!AllCountersZero())
51 {
52 m_TaskCondition.wait(lock);
53 return false;
54 }
55
56 m_NextStage = Stage((int(m_CurrentStage) + 1) % 5);
57 m_CurrentStage = Stage::SIZE;
58
59 //Reset the state of the task queue
60 ResetCounters();
61 ResetFlags();
62
63 if (m_NextStage == Stage::SWAPPF)
64 {
65 //Wait for the main thread to complete drawing before swapping the buffers
66 Engine::GetInstance().SyncWithMain();
67 }
68 if (m_NextStage == Stage::UPDATE)
69 {
70 //Wait for the main thread to complete handling input and cleaning resources before starting the next frame
71 Engine::GetInstance().SyncWithMain();
72 lock.unlock();
73 m_CurrentStage = m_NextStage;
74 //Create frame tasks for the new frame
75 CreateFrameTasks();
76 }
77
78
79 //Notify all waiting threads new tasks have been added, once possible sync with main happened
80 if(m_CurrentStage != Stage::UPDATE)
81 {
82 m_CurrentStage = m_NextStage;
83 }
84
85 m_TaskCondition.notify_all();
86 return false;
87}
88
89//Function used by the main thread to handle tasks that require SDL function calls
90bool anx::TaskManager::GetLockedJobRequest(Task & task)
91{
92 if (m_Quit) return false;
93
94 if (m_LockedTasks.try_pop(task))
95 return true;
96
97 m_TaskCondition.notify_one();
98 return false;
99}
100
101//Used by the input manager to add a command job to the job queue
102void anx::TaskManager::AddCommandJob(Command * pToAdd)
103{
104 if (!pToAdd) return;
105 //Create a new task with the command bound
106 Task newTask;
107 newTask.stage = Stage::COMMAND;
108 newTask.pCommand = pToAdd;
109 //Add the command to the task queue
110 m_Tasks[int(Stage::UPDATE)].push(newTask);
111 //Notify the condition variable that there is a new task available
112 m_TaskCondition.notify_one();
113}
114
115//Used by the scene to add a request to load a new scene
116void anx::TaskManager::AddLoadingJob(Scene * pToLoad)
117{
118 if (!pToLoad) return;
119 //Create a new task with the command bound
120 Task newTask;
121 newTask.stage = Stage::LOADING;
122 newTask.pScene = pToLoad;
123 //Add the command to the task queue
124 m_Tasks[int(Stage::UPDATE)].push(newTask);
125 //Notify the condition variable that there is a new task available
126 m_TaskCondition.notify_one();
127}
128
129//Can be called from anywhere, usually the constructor of a component
130//makes sure all components of type base get updated before tasks of dependantOn type get executed
131void anx::TaskManager::SetDependecny(size_t base, size_t dependantOn)
132{
133 m_Dependencies[base].push_back(dependantOn);
134}
135
136anx::Stage anx::TaskManager::GetCurrentStage() const
137{
138 return m_CurrentStage;
139}
140
141
142//This function has to get called after a certain task group has completed
143void anx::TaskManager::CheckDependencies(size_t componentHash)
144{
145 for (size_t i = 0; i < m_Keys.size(); ++i)
146 {
147 size_t key = m_Keys.at(i);
148 //If this component type has already been marked updated, ignore it
149 if (m_ComponentUpdated[key])
150 continue;
151 auto result = std::find(m_Dependencies[key].begin(), m_Dependencies[key].end(), componentHash);
152 //If this key was depending on the completed taskset, try to create the task set for the depending key
153 if(result != m_Dependencies.at(key).end())
154 {
155 CreateTasks(key, m_CurrentStage);
156 }
157 }
158}
159
160//Clears the counters for all component types that don't have to be updated this frame
161//Also marking these components complete and checks for dependant components
162void anx::TaskManager::ClearEmptyCounters()
163{
164 for (size_t i = 0; i < m_Keys.size(); ++i)
165 {
166 size_t componentHash = m_Keys[i];
167 if (!m_pComponentMap->at(componentHash).at(0)->ShouldExecuteStage(m_NextStage))
168 {
169 m_Counters[componentHash] = 0;
170 m_ComponentUpdated[componentHash] = true;
171 CheckDependencies(componentHash);
172 }
173 }
174 for (size_t i = 0; i < m_LockedKeys.size(); ++i)
175 {
176 size_t componentHash = m_LockedKeys[i];
177 if (!m_pComponentMap->at(componentHash).at(0)->ShouldExecuteStage(m_NextStage))
178 {
179 m_Counters[componentHash] = 0;
180 m_ComponentUpdated[componentHash] = true;
181 CheckDependencies(componentHash);
182 }
183 }
184}
185
186//Sets all counters to the number of the corresponding components in the current scene
187void anx::TaskManager::ResetCounters()
188{
189 if(m_NextStage == Stage::PHYSICSINIT)
190 {
191 size_t nrColliders = m_pComponentMap->at(m_ColliderHash).size();
192 m_Counters[m_ColliderHash] = nrColliders;
193 }
194 else if (m_NextStage == Stage::PHYSICSMAIN)
195 {
196 CreateBaseTasks(Stage::PHYSICSMAIN);
197 auto* physScene = Engine::GetInstance().GetCurrentGame()->GetCurrentScene()->GetPhysicsScene();
198 int size = int(physScene->GetTree()->GetNotEmptyNodes().size());
199 m_Counters[m_ColliderHash] = size;
200 }
201 else
202 {
203 for (size_t i = 0; i < m_Keys.size(); ++i)
204 {
205 size_t index = m_Keys.at(i);
206 m_Counters.at(index) = int(m_pComponentMap->at(index).size());
207 }
208 ClearEmptyCounters();
209 }
210}
211
212//Creates the base tasks for all component types in the current scene
213void anx::TaskManager::CreateBaseTasks(Stage stage)
214{
215 switch (stage)
216 {
217 case Stage::UPDATE:
218 case Stage::LATEUPDATE:
219 case Stage::SWAPPF:
220 //Try to create tasks for all component group types
221 for (size_t i = 0; i < m_Keys.size(); ++i)
222 {
223 CreateTasks(m_Keys.at(i), stage);
224 }
225
226 //Create locked tasks for all locked task groups
227 for (size_t i = 0; i < m_LockedKeys.size(); ++i)
228 {
229 CreateLockedTasks(m_LockedKeys.at(i), stage);
230 }
231 break;
232 case Stage::PHYSICSINIT:
233 {
234 auto* physScene = Engine::GetInstance().GetCurrentGame()->GetCurrentScene()->GetPhysicsScene();
235 physScene->StartUpdate();
236
237 size_t nrColliders = m_pComponentMap->at(m_ColliderHash).size();
238 size_t collidersPerTask = std::max(1, int(nrColliders / m_NrThreads));
239
240 size_t collidersHandled = 0;
241
242 while(collidersHandled < nrColliders)
243 {
244 Task newTask;
245 newTask.key = m_ColliderHash;
246 newTask.range = std::make_pair(collidersHandled, std::min(collidersHandled + collidersPerTask, nrColliders));
247 collidersHandled += collidersPerTask;
248 newTask.stage = stage;
249 m_Tasks[int(stage)].push(newTask);
250 }
251 break;
252 }
253 case Stage::PHYSICSMAIN:
254 {
255 auto* physScene = Engine::GetInstance().GetCurrentGame()->GetCurrentScene()->GetPhysicsScene();
256
257 int size = int(physScene->GetTree()->GetNotEmptyNodes().size());
258
259 int nrNodesPerTask = std::max(1,int(size / m_NrThreads));
260 int nrNodesHandled = 0;
261
262 while (nrNodesHandled < size)
263 {
264 Task newTask;
265 newTask.key = m_ColliderHash;
266 newTask.range = std::make_pair(nrNodesHandled, std::min(nrNodesHandled + nrNodesPerTask, size));
267 nrNodesHandled += nrNodesPerTask;
268 newTask.stage = stage;
269 m_Tasks[int(stage)].push(newTask);
270 }
271 }
272 break;
273 default: ;
274 }
275}
276
277//Reduces the component counter for the given component type by the given amount
278//If the counter becomes 0 as a result, it flages the component as completed and checks for dependant component types
279void anx::TaskManager::ReduceCounter(size_t componentHash, int toReduce)
280{
281 m_Counters.at(componentHash) -= toReduce;
282 if (m_Counters.at(componentHash) == 0)
283 {
284 m_ComponentUpdated[componentHash] = true;
285 CheckDependencies(componentHash);
286 }
287}
288
289std::vector<anx::BaseComponent*>& anx::TaskManager::GetComponents(size_t componentHash)
290{
291 return m_pComponentMap->at(componentHash);
292}
293
294void anx::TaskManager::Quit()
295{
296 m_Quit = true;
297 m_TaskCondition.notify_all();
298}
299
300anx::TaskManager::TaskManager()
301 :m_CurrentStage(Stage::SWAPPF), m_pComponentMap(nullptr), m_RenderHash(ComponentID<RenderComponent>::GetID())
302 ,m_ColliderHash(ComponentID<ColliderComponent>::GetID())
303{
304}
305
306//Function that created the actual tasks per component type and stage
307void anx::TaskManager::CreateTasks(size_t componentHash, Stage stage)
308{
309 int size = int(m_pComponentMap->at(componentHash).size());
310
311 if (!m_pComponentMap->at(componentHash).at(0)->ShouldExecuteStage(stage))
312 {
313 return;
314 }
315
316 std::vector<size_t>& dependencies = m_Dependencies[componentHash];
317 for (int i = 0; i < int(dependencies.size()); ++i)
318 {
319 //If one of the counter of the dependant task lists is not yet 0, don't create the tasks.
320 if (!m_Counters.at(dependencies.at(i)) == 0)
321 return;
322 }
323
324 int nrObjectsPerTask = std::max(int(size / m_NrThreads), 10);
325 int nrObjectsHandled = 0;
326
327 while (nrObjectsHandled < size)
328 {
329 Task newTask;
330 newTask.key = componentHash;
331 newTask.range = std::make_pair(nrObjectsHandled, std::min(nrObjectsHandled + nrObjectsPerTask, size));
332 nrObjectsHandled += nrObjectsPerTask;
333 newTask.stage = stage;
334 m_Tasks[int(stage)].push(newTask);
335 }
336
337 m_TaskCondition.notify_one();
338}
339
340//Same as previous function, but for the tasks locked to the main thread
341void anx::TaskManager::CreateLockedTasks(size_t componentHash, Stage stage)
342{
343 if(!m_pComponentMap->at(componentHash).at(0)->ShouldExecuteStage(stage))
344 {
345 return;
346 }
347
348 int size = int(m_pComponentMap->at(componentHash).size());
349
350 std::vector<size_t>& dependencies = m_Dependencies[componentHash];
351 for (int i = 0; i < int(dependencies.size()); ++i)
352 {
353 //If one of the counter of the dependant task lists is not yet 0, don't create the tasks.
354 if (!m_Counters.at(dependencies.at(i)) == 0)
355 return;
356 }
357 //If the number of components exceed the maximum number of components per task, create sets with the max size
358 if (size > m_MaxTaskSize)
359 {
360 for (int i = 0; i < size; i += m_MaxTaskSize)
361 {
362 Task newTask;
363 newTask.key = componentHash;
364 newTask.range = std::make_pair(i, std::min(i + m_MaxTaskSize, size));
365 newTask.stage = stage;
366 m_LockedTasks.push(newTask);
367 }
368 }
369 else
370 {
371 Task newTask;
372 newTask.key = componentHash;
373 newTask.range = std::make_pair(0, size);
374 newTask.stage = stage;
375 m_LockedTasks.push(newTask);
376 }
377 m_TaskCondition.notify_one();
378}
379
380//Base Function that starts the process of creating al frame tasks
381void anx::TaskManager::CreateFrameTasks()
382{
383 for (int i = 0; i < int(Stage::SIZE); ++i)
384 {
385 if (i == int(Stage::PHYSICSMAIN)) ++i;
386 CreateBaseTasks(Stage(i));
387 }
388}
389
390//Function that checks if all components have finished updating
391bool anx::TaskManager::AllCountersZero()
392{
393 //std::unique_lock<std::mutex>lock(m_CounterMutex);
394 for (size_t i = 0; i < m_Keys.size(); ++i)
395 {
396 size_t key = m_Keys.at(i);
397 if(m_Counters[key] > 0)
398 return false;
399 }
400 return true;
401}
402
403//Resets the completed flag per component type
404void anx::TaskManager::ResetFlags()
405{
406 for (size_t i = 0; i < m_Keys.size(); ++i)
407 {
408 m_ComponentUpdated[m_Keys.at(i)] = false;
409 }
410}Thread pool
The next code snippet shows the implementation of the thread pool. This pool holds a number of worker threads (depending on the number of physical cores in the system) that constantly pull tasks from the task manager and execute them using the current scene’s component map.
1#include "pch.h"
2#include "ThreadPool.h"
3#include "Engine/Engine.h"
4#include "TaskManager.h"
5#include "Game/Game.h"
6#include "Commands/Command.h"
7
8//Static variables used by the engine to signal a quit event
9std::mutex anx::ThreadPool::QuitMutex{};
10bool anx::ThreadPool::m_Quit = false;
11std::mutex anx::ThreadPool::m_GroupMutex{};
12std::condition_variable anx::ThreadPool::m_GroupCV{};
13
14//The destructor makes all threads exit and joins them before returning.
15anx::ThreadPool::~ThreadPool()
16{
17 m_Quit = true;
18 TaskManager::GetInstance().Quit();
19 for (size_t i = 0; i < m_Threads.size(); ++i)
20 {
21 TaskManager::GetInstance().Quit();
22 Engine::GetInstance().Quit();
23 m_Threads.at(i).join();
24 }
25}
26
27//Initialization function that created worker threads depending on the number of physical cores in the system
28void anx::ThreadPool::Init()
29{
30 m_NrThreads = std::thread::hardware_concurrency() - 1;
31
32 for (int i = 0; i < m_NrThreads; ++i)
33 {
34 m_Threads.emplace_back(std::thread{ &ThreadPool::InfiniteLoop, this });
35 }
36}
37
38anx::ThreadPool::ThreadPool()
39 :m_NrThreads(0)
40{
41}
42
43//Inifite loop function that gets executed by every worker thread until the game notifies the engine quit
44void anx::ThreadPool::InfiniteLoop()
45{
46 anx::TaskManager& manager = anx::TaskManager::GetInstance();
47 anx::Engine& engine = anx::Engine::GetInstance();
48 Task currentTask;
49
50 while(!engine.GetQuit())
51 {
52 //Get a job request from the task manager
53 bool hasTask = manager.GetJobRequest(currentTask);
54 //If we got a task, execute it depending on it's stage and component type
55 if(hasTask)
56 {
57 int size = currentTask.range.second - currentTask.range.first;
58 switch (currentTask.stage)
59 {
60 case Stage::UPDATE:
61 {
62 auto& components = manager.GetComponents(currentTask.key);
63 for (int i = currentTask.range.first; i < currentTask.range.second; ++i)
64 {
65 components.at(i)->Update();
66 }
67 manager.ReduceCounter(currentTask.key, size);
68 }
69 break;
70 //Physics init stage adds all collider components to the scene's quad tree
71 case Stage::PHYSICSINIT:
72 {
73 auto& components = manager.GetComponents(currentTask.key);
74 auto* physScene = Engine::GetInstance().GetCurrentGame()->GetCurrentScene()->GetPhysicsScene();
75 physScene->Insert(currentTask.range.first, currentTask.range.second);
76 manager.ReduceCounter(currentTask.key, size);
77 }
78 break;
79 //The main physics stage is going to process each node and check for collisions between collider components.
80 //This information is passed to the collider components by a adding a reference to either the overlapping or blocking entity list of the collider component
81 case Stage::PHYSICSMAIN:
82 {
83 auto* physScene = Engine::GetInstance().GetCurrentGame()->GetCurrentScene()->GetPhysicsScene();
84 auto& nodes = physScene->GetTree()->GetNotEmptyNodes();
85 for (int i = currentTask.range.first; i < currentTask.range.second; ++i)
86 {
87 physScene->ProcessNode(nodes[i]);
88 }
89 manager.ReduceCounter(currentTask.key, size);
90 }
91
92 break;
93 case Stage::LATEUPDATE:
94 {
95 auto& components = manager.GetComponents(currentTask.key);
96 for (int i = currentTask.range.first; i < currentTask.range.second; ++i)
97 {
98 components.at(i)->LateUpdate();
99 }
100 manager.ReduceCounter(currentTask.key, size);
101 }
102
103 break;
104 case Stage::SWAPPF:
105 {
106 auto& components = manager.GetComponents(currentTask.key);
107 for (int i = currentTask.range.first; i < currentTask.range.second; ++i)
108 {
109 components.at(i)->SwapPF();
110 }
111 manager.ReduceCounter(currentTask.key, size);
112 }
113 break;
114 //Command and Loading tasks don't use the component map of the current scene
115 case Stage::COMMAND:
116 currentTask.pCommand->Execute();
117 break;
118 case Stage::LOADING:
119 {
120 auto game = Engine::GetInstance().GetCurrentGame();
121 game->SetLoadingScreen();
122 while (!game->IsLoadingScreen()) { std::this_thread::sleep_for(std::chrono::milliseconds(1)); }
123 game->Load();
124 }
125 break;
126 default: ;
127 }
128
129 }
130 }
131}Quad tree
The following code snippet shows an implementation of a quad tree, that can be used in a multithreaded environment. A tradeoff has been made to accommodate multiple threads inserting new collider components without blocking by having the tree always be at max size. This means we don’t have to lock at runtime to split a node but gives us a performance hit if the objects with a collider are not distributed along the scene well. To compensate for this, each scene can choose how deep the tree goes, depending on how spread out the objects will be. Even though this seems like a big deal, multithreading should only be used in scenarios where we can split up the work anyways.
1#include "pch.h"
2#include "QuadTree.h"
3
4//Static vector holding all nodes in the current tree for easy access by the worker threads
5Concurrency::concurrent_vector<anx::QuadTree*> anx::QuadTree::pNodes{};
6
7anx::QuadTree::QuadTree()
8 :m_Level(-1), m_pNodes{nullptr, nullptr, nullptr, nullptr}, m_pDynamicObjects(Concurrency::concurrent_vector<ColliderComponent*>{}),
9 m_pStaticObjects(Concurrency::concurrent_vector<ColliderComponent*>{}), m_MaxLevel(5)
10{
11}
12
13anx::QuadTree::~QuadTree()
14{
15}
16
17//Function that builds the entire tree, give the level bounds and the number of levels in the tree
18anx::QuadTree * anx::QuadTree::BuildTree(const Rect & bounds, int levels)
19{
20 pNodes.reserve(500);
21
22 QuadTree* pRootNode = ObjectPool<QuadTree>::GetInstance().RequestObject();
23 pRootNode->Initialize(0, bounds);
24 pRootNode->m_MaxLevel = levels;
25 std::queue<QuadTree*> pQueue;
26 pQueue.push(pRootNode);
27
28 while(!pQueue.empty())
29 {
30 pQueue.front()->Split(levels, pQueue);
31 pQueue.pop();
32 }
33
34 return pRootNode;
35}
36
37//Function makes sure all our children are set to nullptr and the current node knows the number of total levels in the tree
38void anx::QuadTree::Initialize(int level, const Rect & bounds)
39{
40 for (int i = 0; i < 4; ++i)
41 {
42 m_pNodes[i] = nullptr;
43 }
44
45 m_Level = level;
46 m_Bounds = bounds;
47}
48
49void anx::QuadTree::Clear()
50{
51 //Clear all nodes from the node list
52 m_pStaticObjects.clear();
53 m_pDynamicObjects.clear();
54 for (int i = 0; i < 4; ++i)
55 {
56 if(m_pNodes[i] != nullptr)
57 {
58 m_pNodes[i]->Clear();
59 }
60 }
61 pNodes.clear();
62 m_Size = 0;
63}
64
65//Splits up a node into four sub nodes with each taking care of a quarter of the current node's bounds
66void anx::QuadTree::Split()
67{
68 if (m_pNodes[0]) return;
69
70 float subWidth = m_Bounds.width * 0.5f;
71 float subHeight = m_Bounds.height * 0.5f;
72 const Vector2& topLeft = m_Bounds.topLeft;
73
74 m_pNodes[0] = ObjectPool<QuadTree>::GetInstance().RequestObject();
75 m_pNodes[0]->Initialize(m_Level + 1, Rect(topLeft, subWidth, subHeight));
76
77 m_pNodes[1] = ObjectPool<QuadTree>::GetInstance().RequestObject();
78 m_pNodes[1]->Initialize(m_Level + 1, Rect({ topLeft.x + subWidth, topLeft.y }, subWidth, subHeight));
79
80 m_pNodes[2] = ObjectPool<QuadTree>::GetInstance().RequestObject();
81 m_pNodes[2]->Initialize(m_Level + 1, Rect({ topLeft.x, topLeft.y + subHeight }, subWidth, subHeight));
82
83 m_pNodes[3] = ObjectPool<QuadTree>::GetInstance().RequestObject();
84 m_pNodes[3]->Initialize(m_Level + 1, Rect({ topLeft.x + subWidth, topLeft.y + subHeight }, subWidth, subHeight));
85}
86
87//Base function called when the tree is being built
88void anx::QuadTree::Split(int maxLevel, std::queue<anx::QuadTree*>& pQueue)
89{
90 if (m_Level < maxLevel)
91 {
92 Split();
93 for (int i = 0; i < 4; ++i)
94 {
95 pQueue.push(m_pNodes[i]);
96 }
97 }
98}
99
100//Returns the index of the child node the rectangle completely fits into
101//Or -1 is the rectangle overlaps more than one sub node
102int anx::QuadTree::GetIndex(const Rect& collider)
103{
104 for (int i = 0; i < 4; ++i)
105 {
106 const Rect& bounds = m_pNodes[i]->GetBounds();
107 if (collider.IsInside(bounds))
108 return i;
109 }
110 return -1;
111}
112
113//Finds the correct node to add the collider to, if the collider overlaps multiple nodes, it gets added in all of the overlapping nodes
114void anx::QuadTree::Insert(const Rect& colliderBounds, ColliderComponent * pCollider)
115{
116
117 if(m_pNodes[0] != nullptr)
118 {
119 for (int i = 0; i < 4; ++i)
120 {
121 Rect bounds = m_pNodes[i]->GetBounds();
122 if (colliderBounds.IsOverlapping(bounds))
123 m_pNodes[i]->Insert(colliderBounds, pCollider);
124 }
125 }
126 else
127 {
128 //Add the colliders in the correct queue, the tree supports both static and dynamic colliders
129 if(pCollider->GetIsStatic())
130 m_pStaticObjects.push_back(pCollider);
131 else
132 m_pDynamicObjects.push_back(pCollider);
133
134 if (++m_Size == 2)
135 pNodes.push_back(this);
136 }
137
138}
139
140const anx::Rect & anx::QuadTree::GetBounds()
141{
142 return m_Bounds;
143}
144
145const Concurrency::concurrent_vector<anx::ColliderComponent*>& anx::QuadTree::GetDynamicObjects() const
146{
147 return m_pDynamicObjects;
148}
149
150const Concurrency::concurrent_vector<anx::ColliderComponent*>& anx::QuadTree::GetStaticObjects() const
151{
152 return m_pStaticObjects;
153}
154
155Concurrency::concurrent_vector<anx::QuadTree*>& anx::QuadTree::GetNotEmptyNodes()
156{
157 return pNodes;
158}
159
160int anx::QuadTree::GetNrTotalNodes()const
161{
162 return pNodes.size();
163}
164
165int anx::QuadTree::GetNrNodes()
166{
167 return int(std::pow(4,m_MaxLevel));
168}