2D Game: Fast(est) way to find x closest entities for another entity - huge amount of entities, highly dynamic

Question

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)

Answer 1

You can simply use a grid to solve your query. It has several advantages like:

• It is simple and easily understandable.

• It is fast.

• Can easily add or remove the objects.

• And at last, it is easy to change the grid to a finer detail if you are still performing too many distance checks.

Also, make sure you don't do a square root for every distance check. Since you are only comparing the distances, you can also compare the distance squared.