How to cope with obstacles in * Pathfinding to achieve the "best, best goal"?

Question

I am working on finding the A * path for a top-down grid game. The problem that I encountered is probably the easiest to understand in the image below. Asterisks are players / NPCs. A yellow asterisk is the current NPC that wants to go to X. Red asterisks are NPCs, which in this case are obstacles. The yellow cells are the walls, the white cells are the floor. While the entire path to the goal is really inaccessible, I still want to get the path to the next best location (in this case, spot number 8).

I can easily overcome obstacles, but I don’t know how to do it, as I describe. If I stop him as soon as he gets into an obstacle, he will not work properly, stopping at 3. If I go to the tile in the closed list with the smallest distance from the final target, if the final target is on the other side of the wall, as an example, she can ruin things also very badly.

Any suggestions? I feel that something is not so obvious with me, so please forgive the idiocy here.

Thanks Tim

Answer 1

Here's an idea based on the relaxation problem :

First, solve the shortest path problem for all vertices of the graph that do not have NPCs. You can use one Dijkstra algorithm application, starting from the target node, to get the shortest path to / from the target at each vertex.

Then try to find the shortest path in the complete problem. Use A * with the shortest path information obtained when starting Dijkstra as a heuristic; this is permissible, since the shortest path in the NPC problem is always no less than the shortest path in the relaxed task. Track the best path so far and return it when the search space is exhausted (as I wrote in the comment).

If you think this is expensive, then understand that you only need to run Dijkstra; You can reuse the information obtained for each A * run on the same graph.

(Caveat emptor: I have not tried any of this.)

Answer 2

One method is to calculate the path from the source to the destination without considering the NPC blocking, and then check for the blocking NPC directly on the path. If so, take the first blocking NPC on the path, and then calculate the path again. Rinse and repeat until you can no longer reach your destination. When this happens, you can take the point immediately before the last blocking NPC on the last successful path as the “next best” destination.

This should reflect well on your examples, but if there are two blocked entrances to the destination, this method will go further. Also, in the worst case scenario, you will have to run the shortest path algorithm as many times as there are NPCs.

The method provided by larsmans is much better than this, since you only need to start Dijkstra and A * once. I present this only as an idea of ​​the approaches you can take.