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