Pyramid Panic - Feature - QuadTree Optimizations

---

Problem To Solve: Bottleneck

Profiling the project showcased two major bottlenecks when attempting to have the project scale. These two bottlenecks were the rendering loop and the physics loop. Both of these required iterating over every game object in the world and doing comparisons regarding the position of the object relative to others (with Rendering determining what to draw, and the PhysicsManager checking for collisions).

Solution: QuadTree

Both of these bottlenecks can be reduced if a lower time complexity solution was present for determining whether objects are reasonably close to one other. QuadTree's are an excellent complicated data structure which solves this particular niche very well, reducing the time complexity of object bounding lookups.

---

Implementation Details

QuadTree.cpp & QuadTree.h

The QuadTree created can be found in the Engine/External/QuadTree.h and Engine/External/QuadTree.cpp files respectively. This was written in C++ 11, fully compatible with Mac and Windows, taking advantage of STL and smart pointers.

The implementation includes three classes, QuadTreeBounds, QuadTreeNode and QuadTree. QuadTreeBounds represents the x/y/width/height boundaries, used internal by the QuadTree and used when requesting from the QuadTree all objects with your passed in QuadTreeBounds. QuadTreeNode is a private class inside of QuadTree which represents each Quad. The QuadTree class wraps the QuadTreeNode’s, allowing for a more user friendly way to use the QuadTreeNodes while also encapsulating the logic better.

The QuadTree implementation also does not rely on treating objects as x/y points, and can instead treat them themselves as bounds. Objects straddling the bounds between quads are placed in both nodes, however lookup utilizes Sets to avoid duplicates.

GameManager::repopulateQuadTree & GameManager::getObjectsInBounds

GameManager, the singleton found in Engine/Managers/GameManager.cpp, which wraps most systems in the game, contains the QuadTree. Upon object creation in the methods present in GameManager.h, it now lazyInserts created gameObjects into the QuadTree by default. The repopulateQuadTree method was implemented to wrap refreshing the QuadTree. This is an expensive call which clears it completely, creating a new one, then inserts all existing game objects into it (this is to be used on scene transitions or times when the entire QuadTree must be refreshed). The getObjectsInBounds method wraps requesting from the QuadTree all objects within a certain bounds, exposing the QuadTree’s read-only functionality to the rest of the game engine while keeping the QuadTree itself private.

SpriteRendererManager::prepareRenderingThread in SpriteRendererManager.cpp

The first system to utilize the QuadTree functionality exposed by GameManager is the rendering system. The modified code is in Engine/Managers/SpriteRendererManager.cpp, specifically in the prepareRenderingThread method. This method iterates over all objects, determines which ones should be drawn, and prepares all the data for drawing so the drawing pass can be as lean as possible. QuadTree’s were implemented, so rather than iterate over every object and check whether it is within the Camera’s boundaries manually, now it requests from GameManger all of the GameObjects that it can find which would currently fit the bounds of the screen, inherently culling all other objects.

---

Notes

SpriteRendererManager takes advantage of the QuadTree for culling, and replacing it with the previous Camera::isOnScreen technique that was used in the projects’ Alpha. Replacing Camera::isOnScreen with the QuadTree reduced the rendering loop heavily, as previously every object still had to be iterated over and checked whether it was culled individually, whereas now the QuadTree inherently omits culled objects entirely.

The profiler showed using Camera::isOnScreen for culling results in the SpriteRendererManager (when playing with 300 game objects) used slightly over 40% of the games CPU usage, however using the QuadTree instead, this amount is reduced to 24%, with a 6% increase in overhead regarding maintaining the QuadTree.

When increasing the amount of (Collider-less) game objects into the thousands, the SpriteRendererManager was using roughly 70% CPU usage with Camera::isOnScreen, however only 30%ish with the QuadTree. These informal benchmarks showcased a drastic increase in scalability, proving that QuadTree's were an appropriate solution to the original bottleneck.

---

Posted on Utopian.io - Rewarding Open Source Contributors

---