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

Question

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.

Thanks, Tim

Answer 1

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