Quad trees (or more commonly octrees or k-d trees) are ubiquitous in the world of games and are a very efficient method of spatial partitioning. They allow the application developer to organize a set of points or objects in 2D or 3D space based on their location within that space, which can then be used to retrieve that object or nearby objects. For a full description of what a quad tree is and how they work, check out the wikipedia article on them.
Quad trees are very useful for games because they make it very quick to organize and store objects with spatial data, and if done right they can minimize the amount of extra data to save space. They are useful for physics, collision, and even simple queries such as finding nearest objects. They can be a little daunting at first, but once you've implemented one you'll see that they're not so bad after all!
For this project I worked in C# so I could easily draw my data with the .Net Graphics library (Note that the thumbnail image is actually the 3D demo I built with Vulkan. I'll talk more about that at the end). I wanted to give this a stab without just blindly copying some code from the internet or from a book and that presented some challenges. After a few iterations I had a simple quad tree implementation that could successfully insert objects, but I noticed a big issue very quickly. I initially started with about 100 points inserted into the tree and tried to ramp up the number to 1000, but almost every time I tried I would get a stack overflow. I found that if I kept the number of objects below 300 I could pretty consistently avoid the stack overflow, but I knew this would be a problem. I decided that it was more important to get a search method implemented before I fixed the stack overflow, so I kept my data set small so I could continue development. I knew that doing a circle-rectangle overlap test would be a great way to search for data points in the quad tree so I implemented a function to search for all points in the quad tree within a given radius of a given point. My first attempt worked for many cases, but was not quite behaving right which I attributed to missing some edge cases in the circle overlap test. I knew that this should be a simple overlap test, but since I was focusing on the quad tree itself, I turned to Real Time Collision Detection by Christer Ericson to find a faster solution. I found a very simple overlap test that worked in less lines of code than my first attempt and covered all the edge cases elegantly. But while looking through this book I came across an interesting method of initializing a quad tree where the tree is essentially pre-built down to it's max depth at initialization time. Since I knew that the depth of my tree was causing the stack overflow, I thought that this might be a possible solution to my problem. To test this I created a new implementation, and with the pre-allocated tree I was able to easily handle many more objects. The key piece of design that I was missing was that I was trying to divide my tree so that there was only every one object per quad, after all this is often how quad trees are described. In doing so my tree depth became much deeper than it needed to be which would easily overflow the stack. This also meant that instead of storing singular objects, I now needed to store a list of objects.
To make use of my newly working quad tree, I set up a demo of a fire spreading through a forest. This is a great use of the quad tree as a fire only spreads within a certain distance. This is a great example where the naive solution would result in O(n^2) time and a quad tree results in O(log n) time. The demo worked great given the limited problem set, but I really wanted to see how it would behave with a much larger set. While looking through Real Time Collision Detection for a solution to sphere-rectangle collision I came across a method of creating a quad tree by pre-building to the max depth. Since I knew the tree depth and recursion was the cause of the stack overflow issue I thought this might be a solution. It turns out that this did actually solve the overflow issue! With a pre-built tree, I could easily populate it with over 10,000 objects without hitting a stack overflow.
After seeing how well a pre-built tree could handle a large problem set I wanted to fix my original quad tree and see how the two compare. It was pretty simple to fix, I just had to implement depth tracking and stop subdividing the tree once that depth was hit, as well as keeping a list of items instead of a single reference. After implementing the changes the original tree can now handle over 10,000 objects, but also avoid allocating parts of the tree that will never contain data. The cool thing is that the dynamic tree is actually slightly more performant than the pre-built tree because there are often less quads to cull away during search.
The final touch was to compare the three methods of searching for nearby points, the naive nested for-loop, the pre-built quad tree, and the dynamic quad tree. I created a new windows form that allows the user to tweak the parameters of the test and then compare the performance of each method. It's pretty rewarding to see that as the data size increases, the quad trees outperform the naive method by at least a factor of 10. Most of the time the queries take less than a millisecond to complete even with 10,000 points which is a great solution for any real time application.
This was a fun little project and a great learning experience. I had so much fun with this project that I ended up replicating the simulation in 3D using Vulkan and instance rendering. I could see some potential to turn this into a small game, and with the Vulkan framework I had from my classes it was pretty easy to get the rendering working and a basic input loop. To my surprise, taking this project just that one step further turned out to be an even better learning experience! I had to change my Vulkan framework a bit to support instancing in the way I needed, and of course porting my quad tree from C# to C++ posed some extra challenges as well. In the end I now have two awesome quad tree demos, and a good perspective on quad tree implementation in two languages which is awesome.
Typically I include some code snippets in these writeups, but this project is complicated enough that I'm only going to include the github link to the 2D demo. Check out the demo videos for a better look below!
Github link: https://github.com/zachmakesgames/QuadTreeDemo