I'm working on a 2D game that has a huge amount of dynamic entities. For fun's sake, let's call them soldiers, and let's say there are 50000 of them (which I just randomly thought up, it might be much more or much less :)).
All these soldiers are moving every frame according to rules - think boids /flocking/steering behavior. For each soldier, to update its movement I need the X soldiers that are closest to the one I'm processing.
What would be the best spatial hierarchy to store them to facilitate calculations like this without too much overhead? (All entities are updated/moved every frame, so it has to handle dynamic entities very well)