A* Pathfinding Finding One of Many Goals

Question

I have my A* pathfinding algorithm right now working such that given a graph it can find the route from one starting node to one goal node.

This works well for many problems, but sometimes I find that multiple goal nodes are valid.

For example, in a game, an NPC might have to go to a switch to shut a door. If there are multiple switches that shut the door in question, it doesn't matter which switch it goes to - it just needs to go to one of them.

How can I augment my pathfinding algorithm to find the path to the best goal (the shortest path)? As in, the algorithm searches for multiple goals and when it finds just one, it returns the path to that one.

One solution would be to run the algorithm as many times as there are valid goals, but you can guess why that might be inefficient.

Answer 1

There are just two changes you need to make to your A* implementation handle multiple goals:

1. When expanding a node, instead of evaluating if(currentNode == goalNode) to decide whether to terminate your search, you instead evaluate a predicate using that node as input: if(IsGoal(currentNode))

   This lets you implement a completely arbitrary logic in your IsGoal() predicate - including checking whether the node is one of several available goals, or meets some implicitly defined goal criterion like "this node is a blue tile within a 15 unit radius of a red tile AND the player possesses the yellow key"

2. Modify your heuristic function to estimate the distance to the closest goal. This is the toughest part, but it's reasonably forgiving to get it wrong.

   As long as you never overestimate the distance, the algorithm will still return the correct result, so Heuristic(Node node) { return 0f; } is safe (this effectively falls back on Dijkstra's algorithm, exploring in all directions equally until a goal is found)

   The closer you can estimate the true distance, the more accurately A* will chase the most promising paths, and skip over redundant exploration of nodes away from the goals.

   A sample heuristic for a small number of goal tiles would be:

   float Heuristic(Node node, Position[] goals) {
     float closest = float.PositiveInfinity();
     foreach(var goal in goals) {
         float distanceSquared = (node.position - goal).squareMagnitude;
         closest = Min(closest, distanceSquared);
     }
     return Sqrt(closest);
   }

   For a larger number of goals, you may want to use a spatial partition to reduce redundant computation, or pre-compute some heuristic estimates for regions of your map.