I spent a lot of time last year studying and implementing quad trees to try and add some extra tools to my game programming tool kit. It didn't take long to grasp the concept and get a working implementation, and that implementation led to both the 2D and 3D demos I presented previously. While both demos do what they're supposed to, I noticed that the 2D version had some performance issues that I wasn't happy with. The issue is that at each step of the simulation the number of quad tree searches increases exponentially. I already made a simple optimization that ensured objects in the center of a cluster did not continue to check for neighbors, and that did help a lot but it wasn't enough.
While the 3D demo seems to perform very well, the spikes in processing time I was observing in the 2D demo kept eating at me. The problem was that this project started as an attempt to hone some skills that felt dull during an interview. I was asked a question that involved spatial partitioning and I couldn't produce a quad tree on the spot and I struggled with a basic implementation of a spatial grid. But it was another part of the problem, another requirement that got me to start thinking outside of the box. The problem didn't just require spatial partitioning, it also required some way to keep track of islands within a set of spatially partitioned data. I spent a while thinking about this part of the problem as well, and one day I realized that I had a whole set of graph related tools that would be perfect for this! I started thinking about how a forest could be an undirected graph, and how I could use this to quickly find islands in the forest. I then realized that if the forest is set up in a way to be an undirected graph, I don't actually need the quad tree for the bulk of the simulation at all! Each tree in the forest would have a connection to its neighbors, and it would be trivial to send updates between known neighbors rather than having to find neighbors at each simulation update.
This new outlook was the key to this optimization. Once I had built the tree (or any other form of spatial partitioning really) I could compute a directed graph where each object contained a link to its neighbors. Then all I would need to do each update was have the objects that were on fire update their neighbors directly instead of querying the quad tree. It turns out that this is a trivial optimization for this particular simulation. Once the trees in the forest were randomly generated and placed in the quad tree, I just needed to walk the list of trees and find their neighbors. The cool thing about this method is that if building the tree would take n log n time, then revisiting each node in the tree and finding its neighbors should be somewhere similar to n log n as well. This makes the time complexity 2(n log n), or just n log n! The memory complexity is not too bad either, but as the density of the forest grows the complexity would grow significantly.
So I went and added this simple optimization as an option that can be toggled in the app and set about to test it. The best part is that you can't tell that anything has changed other than each update is significantly faster. The fire still spreads as it should, and the user can still extinguish areas of the forest and they will reignite just as they should. Its a magnificent blend of spatial partitioning and graph theory and it opens the doors to some other neat applications of graph theory to a simulation. The one downside of this method is that the spread radius becomes fixed by nature of searching for neighbors within that radius. If this radius never changes then this is a great option, however if it changes often this would be a problem. The solution to changing the radius is to rebuild the neighbor links (but not the quad tree!). From my testing with 3000 objects this can be anywhere upwards of 50ms. Thats not a lot of time to wait, but if the render thread has to wait for it to complete the user will certainly notice. If the radius only needs to update periodically this latency could be handled on a separate thread, or if the radius only ever shrinks it would be simple to build the neighbor graph with the maximum radius and perform radius checks. The last option however will likely perform similarly to the quad tree however.
All in all though, this optimization saves a significant amount of time. In my testing I found that the worst case time for just the quad tree could be upwards of 15ms to complete one update, while the maximum for the neighbor graph was only 0.350ms. Thats a 97.6% speed up of the worst frame which is truly impressive! I'm very happy with this improvement as well as a new outlook on spatial problems. This is a great lesson that all of the stuff we think is boring in college can end up saving our bacon in the weirdest ways. Don't neglect what you learned, there's always a time and place for those weird algorithms that you thought you would never use!
There's still one more potential for improvement in this demo, and that would be to refactor the quad tree implementation to not use recursion. I believe that removing recursion could add another significant speedup to this demo as well as completely and finally fix the stack overflow issue that I originally had, but perhaps thats a project for another time.
Thanks for reading, catch you next time!