Working on my game, I'm at the point where I need to track all of the units in the world so that I can do nearest-neighbor checks for combat. This is an RTS-like game, with potentially thousands of small automated units moving around.
I've been looking into KD-Trees and Quadtrees (especially Point Quadtrees). I'm still trying to learn the details of how they work, but so far Point Quadtrees are making the most sense to me. However, I'm getting the impression that KD-Trees are quicker to search, which is important with the number of points I'll have in the tree.
On the other hand, in my case, I'm going to be tracking a massive number of units that are always moving. From frame to frame, their positions will always be different. Quadtrees are apparently faster to rebalance than KD-Trees, but I don't know if that is applicable when you are rebalancing every point in the tree.
I'm wondering if it would be better in this case to just scrap the tree each frame and rebuild it from scratch, rather than try to rebalance every single point in the tree? If a Quadtree is quicker to rebalance, does that also mean it is quicker to build from scratch? If so, that might be more important for performance than the KD-Tree's search speed, depending on how much of a burden it is to create the tree, but I don't know...