QuadTree
In this elective, I learned the fundamental aspects of modern game engine architecture, specifically focusing on the Entity Component System (ECS). Together with our lecturer, we built our own SFML-based 2D engine. He also provided a Tank vs. Tank game, where two players compete to hit each other with ricocheting bullets. These bullets not only have the ability to hit the tanks but can also collide with each other.
To enhance the game’s performance, I implemented a quadtree (a spatial partitioning structure) to reduce the number of collision checks performed each frame, improving the overall efficiency.
Overview:
3rd semester (10.2023 – 02.2024)
„Game Engine Elective“ submission
Language: C++
Engine: engine developed during elective by lecturer Valentin Klink
Important Learnings:
Understanding engine fundamentals
First hands on a C++ project
Implemeting a low level system
Benchmarking performance
Quadtree works, but only usefull after a certain threshold of compared colliders
Personal goals:
Adding a QuadTree(QT)-logic to make the game more performant for large numbers of bullet-entities
Making the logic as solid as possible
Making the logic scaleable for further work with other types of entities
List of submission contributions to the pre-made engine:
CollisionManager enhanced (new classes QuadTree and QuadTreeNode)
CollisionManager has new functionality to control QT
CollisionManager separates QT-shapes from non QT-shapes
Debugging: Engine shows current FPS and bullet Count
Debugging: Additional inputs to control testing (instructions via HUD)
Debugging: Toggle debug-visualizations (DebuggingText & Lines)
How the QuadTree works:
The main QT holds one root QT-node. Every QT-node consists of 4 quarters. Every quarter can hold another QT-node.
Every leaf-quarter checks for it’s current entities for collision. QT collision get’s currently checked for bullets to bullets.
One quarter can hold a pre-defined maximum amount of entities before it’s subdivided into another QT-node.
The number of maximum entities in one quarter can be set in CollisionManager.h (class QuadTree -> m_maxQuarterEntries)
The order of the quarters is always NW = 0, NE = 1, SE = 2, SW = 3 (clockwise, numbers for indices).
The QT can be activated/deactivated during runtime (switching between old and new collision-checking)
Key Findings:
The QT really works!
It starts paying of at a larger amount of bullets, in my testings (with my hardware) the threshold was at
around >= 100 bullets. Bellow that, the old method currently is more performant.
Performance comparision for high bullet count (~300)
What went well:
I had wanted to work on a C++ project for a long time, and I finally had a good opportunity to start one. Early on, I encountered a problem where the game crashed at a rather unspecified point. After investigating, I realized that I was assigning values through a dangling pointer in one of the functions. This experience taught me more about the nature of pointers and memory management. For future projects, I’ll prefer using smart pointers.
For debugging, I initially relied on std::cout with #ifdef directives to categorize the output, but quickly, the console messages became overwhelming. This led me to explore a more efficient debugging approach, and that’s when I truly appreciated the powerful debugging tools in Visual Studio, especially breakpoints.
As a C++ beginner with some experience in C#, this project was a big challenge. But eventually, I reached a point where I realized I was already halfway through, and that gave me the motivation to keep going. This realization came after I had to tackle the dangling pointer issue.
One of the best feelings was when error messages no longer appeared after making adjustments. I’m also proud of the ability to switch between the old and new collision detection methods during runtime. This feature allowed me to compare both methods‘ performance and verify if there was any noticeable difference.
Known Flaws:
Limited Collider Support: Only circle colliders of a certain size are treated as QT entries. It might be beneficial to implement a hierarchical quadtree structure that can handle more complex objects like tanks and walls. Tanks could fit this structure well, especially since their circle collider is exactly four times the size of the basic collider.
No Neighbor Cell Check: The current implementation doesn’t check neighboring cells, which can lead to situations where bullets visually collide but aren’t detected because they’re in different cells. I anticipated this issue from the beginning, but I’m actually surprised it didn’t occur as frequently as expected. That said, it’s still noticeable when closely examining the edges of the screen.
Code Quality: The code could use significant improvements. Specifically, the way pointers, references, and copies are handled as function arguments isn’t always ideal. It’s clear this project was a C++ beginner’s effort, and there’s room for major optimization and clean-up.
Since this is a beginner project, I recommend checking out my more recent C++ work for improvements in both code quality and functionality.
