A bottleneck I've hit is querying Quadtrees for finding nearby locations. It's much faster than comparing each location, but I'd like to find faster methods that work for moving locations. Profiles done have shown that this factor is the responsible for nearly 99% of all cpu time, so even microperformance improvements to the concept or alternative ideas are welcome.
\$\begingroup\$
\$\endgroup\$
2
-
1\$\begingroup\$ Can you show us your current method? And do you have a particular search window, or can a point be arbitrarily far away and still count as a nearest neighbor for your purposes if none are closer? \$\endgroup\$– DMGregory ♦May 15, 2022 at 16:39
-
\$\begingroup\$ Constraints are enforced for my case, but I discovered an alternative myself. I'll answer it below in a moment. \$\endgroup\$– TheGamerPlayzMay 15, 2022 at 17:57
Add a comment
|
1 Answer
\$\begingroup\$
\$\endgroup\$
An alternative I found was Spatial Hashing.
The basics work as such: If I was given a 100x100 world, it would be split into 10x10 chunks. Each chunk holds all the entities in its 10x10 world area. Searching for them is as simple as only getting the chunks guaranteed to have neighbors. For example, searching a 3x3 square (43, 43).
I did a bit more optimization and had chunks that were encompassed by a search radius to automatically add them all and only to check the distance of individuals on the edges of the 3x3 surrounding (43, 43). Some profiling shows that this spatial hashing is at least 600-2000% faster in my case, and it was exceedingly simple,