Previously, I have posted an article about a data structure for partitioning space called a Quadtree. It is a very basic implementation without any kind of optimizations, and it is also very static. It is static because the whole partitions of the quadtree is generated during setup time and it can’t grow depending on the number of objects thrown into the quadtree. I thought that it could be improved, so I decided to experiment by creating an adaptive version of the quadtree.
This version of the quadtree starts with only one node at the beginning that covers the whole area. As more objects are added to the quadtree, it will create four sub-nodes and move them to the sub-nodes if the objects fit into the sub-nodes. When the quadtree will grow depends on an arbitrary number of objects and therefore memory consumption will be varied depending on the size of the quadtree ( No need to create over 64 nodes if you only have 3 objects! ). Technically, it has no limit on how much it can grow.
I haven’t had the time to test its real-world performance but in theory, it should be more efficient than the previous implementation of the quadtree. It should be faster, more flexible, and the code should also look a lot simpler and more elegant. I adopted Go programming language idiom of making public methods starts with upper-case while the rest starts with lower-case.
As usual, I have the source code available for download for graphical version and bare-bones header and source files. However, I use SDL 2.0 for the graphical version this time.
Improvements, bug reports or fixes would be greatly appreciated!