Minority Opinions

Not everyone can be mainstream, after all.

Multi-Destination Pathfinding

leave a comment »

There are games that involve creatures running around on a three-dimensional tiled grid.  Some of them involve an artificial intelligence of sorts that chooses a destination, and finds a way to get there.  One such game has been annoying me by selecting sub-optimal destinations.  When two or more destinations are equally desirable, it tries to choose the closest; unfortunately, it selects the closest in absolute coordinates, even if it means walking right past (or even through) another one to get there.

Unfortunately, the solution may be worse than the cure.  The current system iterates over possible destinations only once, at the beginning, before using the A* algorithm with a very basic distance heuristic to calculate the path.  The heuristic needs to be fast, because the game is already strapped for CPU resources; in fact, many players would accept a less-optimal path if it means better FPS.  But selecting the closest destination by path distance means either pathing to each destination individually, or iterating over each destination within the heuristic.  And the former is almost certainly far too slow.

The latter, for certain situations, might speed things up.  Once a destination, any destination, is found, pathfinding can stop.  If the closest destination in absolute terms is on the other side of a wall or (more frequently) on another floor, this can save hundreds of steps, potentially thousands of tile checks.  On the other hand, the average savings is likely to be much smaller; perhaps several steps and dozens of tile checks.  Is this enough to make up for iterating over every possible destination on every tile check, when the possibilities range from a meager few to tens of thousands?  I honestly don’t know.

That’s why I’m researching ways to reduce the number of heuristic calculations.  It is possible to clump multiple tiles together into a node that can act as single space for A* purposes, but doing so requires storing node connectivity information.  (In this case, using more memory to save CPU cycles is acceptable as long as the memory isn’t egregiously wasted.)  The map is very dynamic, so updating the node map would also need to be fast.  There may even need to be separate node maps for walking, flying, and swimming.

The big question from what I’ve read so far is whether it’s better to have all nodes be rectangular prisms to eliminate intra-node pathfinding, or allow complex nodes to reduce the number of nodes traversed by the main A* method.  Another potential optimization would mark nodes as dead ends, leaving them entirely untouched by pathfinding that doesn’t start or end there, but I’m not entirely certain there’s a good way to do it without unacceptably suboptimal paths in certain situations.

Where should I be looking for answers to these questions?  Is there a fast library that has already solved such a problem?


Written by eswald

4 Jun 2013 at 7:05 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s