You might have seen a HSHG written by me the other day (supahero1/hshg, post: https://news.ycombinator.com/item?id=34210305), which I also shared here. Well, I've quickly come to the realization that while grids are really nice, they really suck at handling objects of varying sizes. The HSHG could handle 500k objects of very similar sizes at 60FPS, and this Quadtree handles 100k objects of all sizes (can vastly vary or be similar, doesn't matter) in a similar amount of time. Also, while HSHG was really close to being O(n), this Quadtree is much worse, of course resembling O(log n).

The way how I achieve lack of recursivity is doing a modified depth-first search. A modified one, because I first add all child nodes to the stack before descending to the first one of them, so the maximum stack length is depth * 3 + 1, and I assume no madman will want to go over the depth of 20 (by default, can be changed).

For some reason, this time around, running this on my laptop actually results in worse performance than I get on my PC, whereas the situation was the reverse with the HSHG haha. No clue why. Some lack of dirty optimizations I suppose.

This time, no JavaScript port. I just wanted to whip out this Quadtree real quick (took me a week in total, from scratch) to use in some other project of mine. However, I do hope some people can make use of it, or maybe learn how non-recursive Quadtrees work, idk.

On the other hand, this time I included a nice OpenGL + GLFW display showing exactly what's happening and how the Quadtree divides and merges its nodes. You can move around with your mouse (by dragging), and you can click LMB to warp to the fastest object in your view, which then you can deactivate (stop following the entity) by pressing RMB.

Hope you enjoy!

~don_shadaman