We don't use quadtrees or any sort of spatial separation in there, because unfortunately depending on the usage of a given search, we wind up having to search far too much of the planet to make it feasible. The amount of space that is being discussed there is also too high, and there is nothing in most of them. There are a lot of ships that can hit things that would be in a large number of buckets, and some that would hit them in all, so it becomes a very inefficient way of sorting them.
In TLF and Starward Rogue we don't have those same restrictions, so we use quadtrees and that's a big help. With AI War it would make the ram spiral out of control as well as it doesn't seem to be effective anyhow.
Instead we use what we call rollups, which are a lot of subsets of data based on uses. I believe there is something like 30ish distinct rollups per player per planet, or something on that order.
The core goal of spatial partitioning is that you want to iterate over as few things as possible for something like collisions. But spatial issues are not the core cause of iteration in AI War. Only when ships are stopping do they collide with anything at all, anyway. Otherwise they can fly right past one another. Shot hits are precalculated, not calculated on the fly, unlike in TLF or SR.
Instead our biggest problem -- by many orders of magnitude, and I use that term literally -- is target selection. It could be engineers deciding what to repair or build, ships deciding what to autotarget to shoot at, or who knows. We use a variety of tricks to help make those iterations as few as possible (the rollups are a huge part of that), but ultimately it's just a huge amount of data to crunch and there's no way around that. So we have a cross-frame way of breaking up that data and throttling it so that it doesn't completely overwhelm the framerate most of the time.
With something like the gravity stuff causing issues, it's probably either a matter of there needing to be a different lookup, or different uses of lookups, or else throttling to keep it from doing too many of those calculations in one frame. Most likely that's what would need to be done. It should already be using all the distance speedups like doing hacky general range checks first, then doing better approximations if it's even feasible that something is in range, etc.
If it proves to be absolutely a hog of a method, then it might be a candidate for some inlining of an existing method to avoid the cost of a method call that might happen a million times a second in the current iteration. And cutting that back from a million to something like a throttled 10k per second, potentially.
Something along those lines, anyhow.
