CODEWITHSUNDEEP
path-findinga-star
Mythics
Mythics

Reputation: 803

How to handle Obstacles in A* Pathfinding to reach 'next best' goal?

I'm working on A* pathfinding for a grid based top-down game. The issue I've came across is probably easiest to understand in the image below. Asterisks are players/NPCs. The yellow asterisk is the current NPC that wants to path to the X. The red asterisks are NPCs that in this case are obstacles. Yellow cells are walls, white cells are floor. While the entire path to the goal is indeed unreachable, I'm still wanting to get a path to the next best location (in this case, spot numbered 8).

I can easily have it path around obstacles, but not sure how to do exactly as I describe. If I stop it once it's hit an obstacle, it doesn't perform properly by stopping at 3. If I re-path to the tile in the closed list with the lowest distance from the end goal, if the end goal is on the other side of a wall as an example it can mess things up quite bad as well.

Any suggestions? I feel like I'm missing something otherwise obvious, so please forgive an idiocy here.

enter image description here

Thanks, Tim

Upvotes: 5

Views: 5367

Answers (2)

Aleksi Torhamo
Aleksi Torhamo

Reputation: 6632

One method would be to calculate the path from source to destination without taking blocking NPCs into account, then checking if there's any blocking NPC directly on the path. If so, take the first blocking NPC on the path into account, then calculate the path again. Rinse and repeat until you can't get to the destination anymore. When this happens, you can take the point just before the latest blocking NPC on the last successful path as the "next best" destination.

This should work well for your examples, but if there would be two blocked entrances to the destination, this method would go for the entrance that's further away. Also, in the worst case, you'd have to run the shortest path algorithm as many times as there are NPCs.

The method presented by larsmans is way better than this, since you only have to run Dijkstra and A* once. I only present this as an idea of the kinds of approaches you can take.

Upvotes: 0

Fred Foo
Fred Foo

Reputation: 363717

Here's an idea, based on problem relaxation:

First, solve the shortest-path problem for all vertices of a graph that has no NPCs. You can use a single application of Dijkstra's algorithm starting from the goal node to get the shortest path to/from the goal at each vertex.

Then attempt to find the shortest path in the full problem. Use A* with the shortest path information obtained by running Dijkstra's as the heuristic; it's admissible as the shortest path in the problem with NPCs is always at least as long as the shortest path in the relaxed problem. Keep track of the best path so far and return that when the search space is exhausted (as I posted in the comment).

If you think this is expensive, then realize that you only have to run Dijkstra's once; you can reuse the information obtained for each run of A* on the same graph.

(Caveat emptor: I didn't try any of this out.)

Upvotes: 7

Related Questions