CODEWITHSUNDEEP
algorithmpath-findinga-star
user1012037
user1012037

Reputation: 501

Modified a-star pathfinding heuristic design

FIRST, The ideal path was (in order of importance):

1. shortest

My heuristic (f) was:

manhattan distance (h) + path length (g)

This was buggy because it favored paths which veered towards the target then snaked back.

SECOND, The ideal path was:

1. shortest
2. approaches the destination from the same y coordinate (if of equal length)

My heuristic stayed the same. I checked for the second criteria at the end, after reaching the target. The heuristic was made slightly inefficient (to fix the veering problem) which also resulted in the necessary adjacent coordinates always being searched.

THIRD, The ideal path:

1. shortest
2. approaches the destination from the same y coordinate (if of equal length)
3. takes the least number of turns

Now I tried making the heuristic (f):

manhattan distance (h) + path length (g) * number of turns (t)

This of course works for criteria #1 and #3, and fixes the veering problem inherently. Unfortunately it's now so efficient that testing for criteria #2 at the end is not working because the set of nodes explored is not large enough to reconstruct the optimal solution.

Can anyone advise me how to fit criteria #2 into my heuristic (f), or how else to tackle this problem?

CRITERIA 2 example: If the goal is (4,6) and the paths to (3,6) and (4,5) are of identical length, then the ideal solution should go through (3,6) because it approaches from the Y plane instead, of (4,5) which comes from the X plane. However if the length is not identical, then the shortest path must be favored regardless of what plane it approaches in.

Upvotes: 2

Views: 2558

Answers (2)

user1012037
user1012037

Reputation: 501

Answering my own question with somewhat of a HACK. Still interested in other answers, ideas, comments, if you know of a better way to solve this.

Hacked manhattan distance is calculated towards the nearest square in the Y plane, instead of the destination itself:

dy = min(absolute_value(dy), absolute_value(dy-1));

Then when constructing heuristic (f):

h = hacked_manhattan_distance();
if (h < 2)
   // we are beside close to the goal
   // switch back to real distance
    h = real_manhattan_distance();

Upvotes: 1

Fred Foo
Fred Foo

Reputation: 363517

You seem to be confusing the A* heuristic, what Russell & Norvig call h, with the partial path cost g. Together, these constitute the priority f = g + h.

The heuristic should be an optimistic estimate of how much it costs to reach the goal from the current point. Manhattan distance is appropriate for h if steps go up, down, left and right and take at least unit cost.

Your criterion 2, however, should go in the path cost g, not in h. I'm not sure what exactly you mean by "approaches the destination from the same y coordinate", but you can forbid/penalize entry into the goal node by giving all other approaches an infinite or very high path cost. There's strictly no need to modify the heuristic h.

The number of turns taken so far should also go in the partial path cost g. You may want to include in h an (optimistic) estimate of how many turns there are left to take, if you can compute such a figure cheaply.

Upvotes: 3

Related Questions