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)

Lurleen

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

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

don't forget to close the question by selecting the most useful answer. – Slipshod

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.

Slipshod

+1 for the square, a lot of people don't realise how expansive the function really is, and how simple it is to avoid it ;) – Bunchy

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.

Dumont

quadtree is not the best probably since for every moving object, you have to remove it from the tree and reinsert it. A potentially expensive operation. Or you have to rebuild the tree every frame again. – Slipshod

@reinier: I think you'd do some testing to figure out how often you need to update the quadtree. You can always slow down that rate and increase the radius of objects to test collisions against. Admittedly, fast-moving objects may fly out of the enlarged radius anyway, but those were the problematic ones in the first place. – Dumont

same argument goes for the grid ;^) – Slipshod

@reinier: So what's the complaint against quadtrees, then? Perhaps you're saying that you have to remove and insert the point every time, but the grid remove and insert and have less complexity. That would make sense. – Dumont

Answer 3

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..?

Clamatorial

if it's not needed, why use it? – Slipshod