I have a game in which everything is an AABB, and there are a ton of them. The entities exist in a relatively small space, and there is little distance between them. After spawning a few thousand entities, my brute force algorithm O(N^2) crumbles quickly.
Now I know the QuadTreeTM is usually the go-to solution for this kind of problem, however due to the small space between individual entities, entities are often added to multiple nodes. There is a significant performance gain, but once a bunch of entities get pushed together, frame rate drops very quickly.
I’m pretty satisfied with the QuadTree, but soon I came across a solution which claims to offer near O(n) performance, does not rely on partitioning so is not affected by overlapping, and I became obliged to implement it. (see below)
Unfortunately for me I am not good at Javascript and I ran into a bunch of problems trying to rewrite it.
It is said to be based off the paper here:
Please let me know if you have any ideas on how to implement it, or if there is a better solution to this problem. Any suggestion will be helpful, thanks!