As I understand it, modern pathfinding uses ideas such as Boids steering on top of traditional A* and Dijkstra's algorithm.

It's easy to find recommendations for implementing Dijkstra's algorithm efficiently in say C++. That is I can find out what are the typical data structures to use.

With Boids steering I cannot find anything that definitively says what is the recommended way to go. You have these moving units and you need to be able to find for each unit all the nearby units to apply steering or whatever else.

What kind of data structure can I use to perform these nearest neighbour queries efficiently?

  • \$\begingroup\$ Consider checking Box2Ds b2DynamicTree for 2D. It also lists a 3D algorithm that was its source for inspiration from the bullet libarary. It is fast. \$\endgroup\$
    – akaltar
    May 31 '17 at 23:18

It turns out there are lots of data structures that are commonly used for this, which might be why you've had trouble identifying a single canonical recommendation. Each one has different characteristics and trade-offs.

Check out the Wikipedia article on nearest neighbour search for an overview, and specifically the fixed-radius near neighbours flavour which is probably most relevant to what you want to do.

One relatively simple method suggested by the second link is to divide your world into a grid of square (2D) or cubic (3D) cells. Each cell becomes a "bucket" into which you record your entities, moving them to a new bucket as they travel around the world.

When you want to find the nearest neighbours to a given entity, then they must be either in the same bucket or one of the 8/26 adjacent buckets (assuming your search radius is less than or equal to the bucket spacing).

For a large world and with entities that aren't super-tightly concentrated, this can let you skip evaluating the vast majority of entity pairs when searching for neighbours.

Of course, even from this high-level description, there are many implementations possible. The bucket lookup device could be a hash table, which itself can be implemented multiple different ways. It's likely to be difficult to identify which implementation is objectively "best" for a given game, so instead I'd recommend focusing on implementing it in a way that you find clear and friendly to work with first. If that version turns out to be a performance bottleneck in practice, then you can post a new question with the specifics of your implementation and profiling results, either here or on the Code Review exchange, to get suggestions for how to eke out more performance.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .