Return to Answer

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

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 cover location AND it is not in line of sight of an enemy AND it is within 10 m of a healing pickup AND the agent walked an even number of steps to reach it"

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.

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

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 cover location AND it is not in line of sight of an enemy AND it is within 10 m of a healing pickup AND the agent walked an even number of steps to reach it"

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.

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.

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

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 cover location AND it is not in line of sight of an enemy AND it is within 10 m of a healing pickup AND the agent walked an even number of steps to reach it"

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.

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 goal) {
          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.

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.