3

Problem:

Modify the A* algorithm we optimized for fewer turns. The algorithm will now find a path from (a,b) to ANY TILE ADJACENT TO (x,y), where (x+1,y) or (x-1,y) are favored when possible.

My attempted solution:

  1. Run the original A* algorithm from (a,b) to (x,y).
  2. Find the last coordinate in the path that travels through (x-1,) or (x+1,) if any.
  3. If there is a straight accessible vertical line from * to y in that coordinate plane, amend the path to follow that line.

Visual Demonstration: (path from S to E where X is inaccessible)

......S           .....S  
.     X           .    X
.          =>     .     
.                 .
E                E.

However I'm not sure that my solution would work in some cases, ie:

......S            .....S  
.     X            .    X
.X        ???     X.     
.                  .
E                E..

Can anyone think of a solution to this problem?

Note: The A* algorithm is generic other than factoring in the number of direction changes to favor less turns in the resulting path.

Improve this question
3
  • 1
    What does "favored when possible" mean? Does it mean that if there is a path of equal length to (x+1,y) and (x,y+1), then the path to (x+1,y) must be found? Or does it mean that if there is a path to (x+1,y) it must be found, even if longer? Also what does adjacent mean? Is (x+1,y+1) adjacent? Commented Apr 14, 2012 at 21:37
  • Favored when possible means only if it's still the shortest path. Adjacent doesn't include diagonals. Commented Apr 14, 2012 at 21:41
  • My friend has suggested: 1. find if the returned path last goes through the x+1 or x-1 plane. 2. run A* from start to either (x+1,y) or (x-1,y) (whichever side is closer). If the resulting path is shorter, return it instead. This seems to give the right solution as per my testing so far, but basically requires running the algorithm twice. Curious if there's anything more elegant. Commented Apr 14, 2012 at 21:43

2 Answers 2

Reset to default
2

A* is actually an informed version of Dijkstra's algorithm, thus it is actually designed [with admissible heuristic function] to find shortest path to ALL vertices [from a single source].

You can define all tiles adjacent to (x,y) as target vertices [A* can handle neatly multiple targets], and you will also need to modify the heuristic function, to give an admissible value to any target node. This can be done by simply modifying h'(tile) = max { h(tile) - 1 , 0} - but in some cases you might have better way to do it.

After establishing the above, we can derive the following modification to the original A*:

  1. Run A*, until you find a path to a target tile [after the extension of target tiles, as described above]. Let the length of the path be d.
  2. Now, continue to run A* with the current state, until the minimum f(tile) value for open nodes is strictly greater then d. You are guaranteed to find all tiles that are reachable from the source by a paths of length d, and specifically - you will find all target tiles which have path from the source of length d. [assuming admissible heuristic function].
  3. From all those tiles, you can chose the "prefered ones" and return a path to them. If there is not prefered tile found, return a path to an arbitrary target tile.

I hope that helps!

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thank you for the advice I must chew on it and see if I can get this to work.
0

Modify your heuristic function to give a slight boost to the points (x+1,y) and (x-1,y). Then if you're 2 steps from finishing the path, ties will be broken in favor of those 2 points.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.