Article
files/QUESTIONS

How to Calculate Paths to Multiple Destinations

Alex J. Champandard on September 21, 2007

Let’s say your FPS bot needs to go to multiple places to pickup ammo, a weapon, and a health pack. How do you make sure the pathfinding takes into account the location of each object to provide the best overall path, rather than wander around picking up each object individually?

As Ian Morrison asks, ” You mention algorithms that allow A* to search for multiple targets. I’ve tried to find such algorithms with the usual suspects (Google, Wikipedia, GameDev.net), but haven’t managed to come up with anything. What should I be searching for to find information on this?”

Overview

This is quite an interesting topic for two reasons:

  • It’s theoretically challenging to solve this problem efficiently. You have to think wisely about your choice of algorithm and its application.

  • There’s a non-negligible behavioral aspect on top this. Are certain targets more important than others? Are certain targets optional? How do you measure the cost-reward trade off?

There are many different approaches you can take, ranging from academic algorithms to game developer hacks… I’ll cover a few of them in this article.

Figure: The Pathematics algorithm expresses targets as rewards in a graph. (See below.)

Brute Force

The first possible approach is to compute all the possible shortest paths between the points you’re interested in: the destination points and the origin (call these points P). You can do this in three ways:

  1. Apply any single-pair algorithm (e.g. A*) to every unique pair of points in P. If you have few target points in P, then this approach is going to be the most efficient as you only need to consider unique pairs in P once.

  2. Apply single-source algorithms (e.g. Dijkstra) to every point in your set P. This option make sense if you have many different bots considering the same target points, so path computation is shared.

  3. Apply an all-pairs algorithm (e.g. Floyd-Warshall) once to the set of points P. It only makes sense to do this if you need to solve many such pathfinding problems for different bots. Try to make it more efficient than the average O(n3) if you can! (See this article of mine on all-pairs pathfinding.)

Once you have the shortest paths and the distances between all points in your set P, you’ll need another algorithm that tries all the different combinations of paths to find the best one. When there are few points, you can use brute force, but otherwise you’ll have to find an approximate solution. It’s like the traveling salesman problem, which is NP-hard, so try to keep it simple!

Heuristic Problem Solver

Alternatively, you can take the problem-solving approach (not just pathfinding) and use a real planner. But what’s interesting is that the same algorithms are used for planning than for pathfinding, specifically A*! So you can just solve these multiple-destination problems with your current pathfinder… if you’re clever about it.

The catch, however, is that you need to change your heuristic to guide the pathfinder to find a path that includes multiple targets. Here’s what you need:

  • A conservative estimate of the total path length of the best solution.

  • A way to estimate the quality of a step in the graph, but how?

Creating a good heuristic isn’t trivial. In the worst case, it could end up being slower than a well engineered “brute-force” solution. So it’ll require lots of experimentation… By the time you’ve got a good heuristic, you’ll find you might as well write a specialized algorithm!

Custom Algorithms

In my thesis (RAR 1.5 Mb), I developed an specialized algorithm called Pathematics. In retrospect, it’s an interesting combination of planning and reinforcement learning. Here’s how it works…

  1. Run a single source algorithm (e.g. Dijkstra) to calculate paths to all points in the graph from the origin (this is stored as a spanning tree). In my thesis, I do the computation with an incremental level-of-detail algorithm which works surprisingly well.

  2. Assign a reward value to points in the network, and traverse the spanning tree towards the source, accumulating the reward along the way. So if you encounter another target point of the same value, the reward will double.

  3. From the source of the spanning tree, you move towards the direction of most reward, as this provides the best combined path.

As with most specialized algorithms, There are a few catches:

  • If you follow the best reward greedily, your bot might end up getting stuck and oscillating. For example, if you have two equally valuable items in opposite directions, the reward values oscillate.

  • There are certain combinations of rewards that can’t be taken into account by the spanning tree. For example, the reward of a point cannot always flow down two separate paths (unless they are of similar distance to the source).

There are simple tricks to solve this. Firstly, increase the reward of nearby points so that the bot is biased towards collecting local items first. Secondly, decrease the reward that flows from a branch of the tree in an opposite direction, so that the bot doesn’t turn around regularly.

The Best Compromise

For all these solutions, the hardest part is deciding how to express the problem for the algorithm to solve it in a realistic way. So instead, a better solution for current games would be to keep a single-target pathfinders, and find better ways of using it.

To make sure you get bang for buck, try the following:

  • Have two categories of objects: primary and secondary. Plan paths only for primary objects, and keep checking for local detours to secondary objects on-the-fly.

  • Make another representation of your navigation graph with rooms and even sectors. This high-level representation will regroup many of your targets together, so you can decide which single target to head for using the traditional A*.

In summary, this pathfinding problem is very obvious in action games. When bots fail to make short detours, they look stupid; when they pick a suboptimal destination, it’s not ideal either. There are lots of reasons to look into this problem, but the theoretical ramifications go deep! It’s definitely one to research further…

Discussion 1 Comments

Andrew on September 21st, 2007

Interesting, will bookmark this. Its a kind of harder travelling salesman problem, and no doubt lots of games simply randomise a location to move to (eg: UT 2004), or aim to move towards a certain preferred weapon (the "primary category" of object), but providing the level design is good enough, enough ammo is found regardless of the location chosen to get to.

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!