PDA

View Full Version : A* and 15 puzzles



joebanana
May 6th, 2008, 11:32 AM
I am working on algorithm for 15 puzzles. I am trying to implement A* and I just cant figure out how the formula is for evaluating h in heuristic function. I am following this tutorial. A* (http://www.geocities.com/jheyesjones/astar.html)
It includes explanation for h but maybe it's just that my English is so bad and I can't see it from the picture. :) Thx for help.

mike_g
May 6th, 2008, 12:34 PM
Theres various ways to get the heuristic, but to find the shortest path you must never overestimate the minimum possible move cost to the target.

The way I did it in the past was to use Pytharoras to get a striaght line distance based on the minimum move cost. In pseudo code for a 2d grid:

dx = pos_x - target_x;
dy = pos_y - target_y;
distance = square_root_of( (dx*dx)+(dy*dy) );
heuristic = distance * base_move_cost;

This can be expensive tho if you are doing realtime pathfinding in a game or something. So if you want something quick, that does not necessarily get the shortest path you could just do:

heuristic = (dx + dy) * base_move_cost;

joebanana
May 7th, 2008, 10:20 AM
So you used an euclidian distance. I found a number of suggestion that with 15 puzzles it's good to follow Manhattan distance(which is almost the same except diagonal movement). In the case of a 8 puzzles which goal is:


A B C
H D
G F E

I found a Nelson sequence(on the above link) which converges quickly. Does anybody know a heuristic similar function for 15-puzzles in the shape:


1 2 3 4
5 6 7 8
9 10 11 12
13 14 15

that converges faster than minimum Manhattan distance? (If there is any other criteria.)

Lster
May 7th, 2008, 11:01 AM
You may be interested in this link:

http://www.policyalmanac.org/games/aStarTutorial.htm

This is what I used when learning A* searching. I found the section, "Summary of the A* Method", to be especially useful. :)