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

Posted by Pygmy on Stack Overflow See other posts from Stack Overflow or by Pygmy
Published on 2009-08-13T12:43:45Z Indexed on 2010/05/22 22:50 UTC
Read the original article Hit count: 186

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)

© Stack Overflow or respective owner

Related posts about game

Related posts about artificial-intelligence