2D Game: Fast(est) way to find x closest entities for another entity - huge amount of entities, highly dynamic
artificial-intelligence, distance, hierarchy, spatial
Solution
The simplest approach is to use a grid. It has several advantages:
- simple
- fast
- easy to add and remove objects
- easy to change the grid to a finer detail if you are still doing too many distance checks
Also, make sure you don't do a squareroot for every distance check. Since you are only comparing the distances, you can also compare the distance squared.
Problem
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 behaviour. For each soldier, to update it's 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)