Show HN: A non-recursive C Quadtree https://ift.tt/rMKhxZq

Show HN: A non-recursive C Quadtree Wazzup Beijing, You might have seen a HSHG written by me the other day (supahero1/hshg, post: https://ift.tt/8Ya1X65 ), 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). 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 https://ift.tt/8eloDvr June 8, 2023 at 02:34PM