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.
Source Code:
Adaptive Quadtree with SDL
Adaptive Quadtree without SDL
Github:
Adaptive Quadtree with SDL
Adaptive Quadtree without SDL
Improvements, bug reports or fixes would be greatly appreciated! 
oh this is actually very cool, thank you
This is interesting.
Again, excellent stuff thanks – this is exactly the sort of solution to the problem I was having previously.
My tile map using the previous quadtree would not cater for rescaling which this does.
Many thanks
You’re welcome! Always happy to know that it’s useful for someone
1. Remove the #include “Object.h” in Quadtree.cpp
2. Include it in Quadtree.h
3. Remove class Object in Quadtree.h
The result will be the same, but the inclusion should be done this way.
Sorry for my English, it’s not my first language x)
I did that to keep the Quadtree class modular and reduce the compiling time. It also avoids circular dependency.
As mentioned, this is primarily to avoid circular inclusions
How I perform a QueryRange to find objecs that intersetc with a rectangle ?
Querying for rectangles should be pretty straightforward to implement. It’s very similar to the GetObjectsAt() function in the Quadtree class except instead of passing a Point, you pass a Rect which may have top, down, left, right variables like the Object class. Then you might want to create a contains() function similar to the contains(Object *) function for Rect and use that in your Query() function (which has similar structure as GetObjectsAt()).
now that you mention it, it was really easy, by the way,this new dynamic implementation was very good, congratulations.
Thanks
mm i’m implementing your dynamic quadtree, but ( i’m wrong probably ) isn’t there a problem in the AddObject ? once you add an object, if it’s the third object (reachedMaxObjects) then it CreateLeaves and moveObjectsToLeaves, but in case there are three objects that are really really close to each other then it continues to subdivide itself, and if three objects are in the same position is stack overflow, am i wrong ?