13
\$\begingroup\$

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?

\$\endgroup\$
1
  • \$\begingroup\$ After a* telling me it is unreachable. I would simply move towards the target until I can't find a way to get closer in a few iterations. It won't be perfect, it can get horribly wrong but it would be fast and there is valid solution anyway \$\endgroup\$
    – WVrock
    Commented Sep 25, 2022 at 13:45

2 Answers 2

Reset to default
23
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Simple. I love it! \$\endgroup\$
    – John McDonald
    Commented Aug 30, 2012 at 14:15
  • \$\begingroup\$ I just slapped my head and went "doh" when I read your answer. Thanks! \$\endgroup\$
    – Shivan Dragon
    Commented Aug 30, 2012 at 15:19
1
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$
    – Roy T.
    Commented Aug 30, 2012 at 13:35
  • \$\begingroup\$ 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. \$\endgroup\$
    – snake5
    Commented Aug 30, 2012 at 13:45
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – BlueRaja - Danny Pflughoeft
    Commented Aug 30, 2012 at 14:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .