Tweaking AStar to find closest location to unreachable destination

I've implemented AStar in Java and it works ok for an area with obstacles where the chosen destination is reachable.

However, when the destination is unreachable, the calculated "path" is in no way to the closest location (to the unreachable location) but is instead some random path.

Is there a feasible way to tweak AStar into finding the path to the closest location to an unreachable destination?

Keep track of the node with the lowest EstimatedDistanceToEnd (ie. the lowest h(x)), and if no end-node is reachable to backtrack from, backtrack from that node instead.

• Simple. I love it! – John McDonald Aug 30 '12 at 14:15
• I just slapped my head and went "doh" when I read your answer. Thanks! – Shivan Dragon Aug 30 '12 at 15:19

This is not really an A* question. A* is all about finding a path from point A to point B. Even though it can be extended, the results could easily be messy and unpredictable. What you need instead is an algorithm that picks the closest reachable destination.

Here's one way to do this: If A* returns a valid path (start/end nodes in path match input nodes), return the path. Otherwise...

• Start searching from the initial node
• Traverse all linked nodes (remember to flag the visited ones to avoid infinite recursion)
• Compare distances to destination to find the closest node
• Something like Flood Fill seems appropiate en.wikipedia.org/wiki/Flood_fill note that you still need to A* from the start node to the node with the lowest distance. Also note that this always involves inspecting all connected nodes and can thus be extremely slow. – Roy T. Aug 30 '12 at 13:35
• Yes, it could be slow. But the slowness would most probably come from having the nodes scattered throughout the memory; that can be easily fixed. Also, it's possible to speed it up by sacrificing some accuracy - just skip links that are too far or point in the wrong direction. – snake5 Aug 30 '12 at 13:45
• @Roy: A*, BFS, and all similar pathfinding algorithms will be exactly as slow as flood-fill, because they all need to inspect every connected node to make sure there is no path to the end. There are however ways to alleviate this issue; see here. – BlueRaja - Danny Pflughoeft Aug 30 '12 at 14:22