Game Development Asked by user6256 on November 29, 2021

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.

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

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"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.

Answered by DMGregory on November 29, 2021

Get help from others!

Recent Answers

- Joshua Engel on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP