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 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)

Answer 1

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.

Answer 2

For broad-phase collision detection, a spatial index like a quad-tree (since it's 2D) or a grid will do. I've linked to Metanet Software's tutorial before; it outlines a grid-based scheme. Of course, your game doesn't even need to use grids so extensively. Just store each actor in a hidden grid and collide it with objects in the same and neighboring cells.

Answer 3

Here's a good algorithm, similar to reinier's suggestion.

Answer 4

The whole point of selecting a good spatial hierarchy is to be able to quickly select only the objects that need testing. (Once you've found out that small subset, the square-root is probably not going to hurt that much anymore)

I'm also interested in what the best / most optimal method is for 2d spatial indexing of highly dynamic objects.

Quadtree / kd-tree seem nice, but they're not too good with dynamic insertions. KD-trees can become unbalanced.

Just a random thought, if your entities are points a double insertion-sorted structure (by X and Y) in combination with a binary search might be something to try..?

Answer 5

this blog has a good writeup of one solution (as well as a number of other good articals)