In the first post on A*, we explored the theory behind A*. Then we took A-star and put it into code. Now we will look at different heuristics for A* and how they affect the path.

The Manhattan Method

The Manhattan Heuristic produces this path.

This is the heuristic function we used in our implementation of A*. The Manhattan method will get you to the end cell in the least steps, but it doesn’t always guarantee the shortest path. It will usually give the shortest path, but it if doesn’t, the chosen path won’t be too much longer. The Manhattan heuristic overvalues the cost compared to G, so if you add penalties to the grid (extra cost to move through water, higher cost to climb a hill, etc.), they will have little to no affect on the resulting path. If you have no extra costs, this will work the best.

It is calculated like this:

H = Math.abs(currentCell.x-goalCell.x) + Math.abs(currentCell.y-goalCell.y);

Math.abs(x); is the absolute value.

The Diagonal Shortcut

The Diagonal Shortcut produces this path.

Unlike the Manhattan heuristic, this one balances H and G so it is ideal for finding paths on grids with costs for different terrains. However, this method is slower than the Manhattan one. To calculated the heuristic with the diagonal shortcut:

var xDist:int = Math.abs(currentCell.x-goalCell.x);
var yDist:int = Math.abs(currentCell.y-goalCell.y);
if(xDist > yDist){
   H = 1.4*yDist + (xDist-yDist);
} else {
   H = 1.4*xDist + (yDist-xDist);
}

This method would require some modification our implementation of A*. We set the cost for diagonal movement to 2 to exclude it. If we wanted to use the diagonal shortcut heuristic, we need to set the G cost for diagonal movement to √2 (1.414).

There are some other methods for calculating the heuristics like Euclidean distance, but that requires a square root calculation and not getting the square root of the distance will give a large H value.

You can play with this to create a grid and find paths using the Manhattan or Diagonal Shortcut heuristics.

Be Sociable, Share!