CODEWITHSUNDEEP
algorithmshortest-patha-star
whats canasta
whats canasta

Reputation: 781

Path finding algorithm difficulty

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.

Upvotes: 3

Views: 336

Answers (2)

btilly
btilly

Reputation: 46399

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.

Upvotes: 0

amit
amit

Reputation: 178411

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!

Upvotes: 2

Related Questions