Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

up vote 15 down vote accepted

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.

share|improve this answer
    
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
add comment

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
share|improve this answer
    
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
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.