Heuristics

When using a heuristic-based algorithm like A*, you may wonder what kind of heuristic you should use. In this section I will cover mostly ideas for grid maps. If you use A* on a polygonal map, you may want different heuristics. The heuristic should be a continuous function; jumps in the heuristic from one map space to its neighbor may cause A* to behave strangely.

A* does best (i.e., finds an optimal path in the least time) when the distance is close to the minimal path cost from the current node to the goal. However, we may want some modifications to the heuristic to give us better behavior, depending on what we really need. For example, we may not need the optimal path, or perhaps we want different characteristics for the beginning of the path and the end of the path.

Manhattan distance

The standard heuristic is the Manhattan distance. Look at your cost function and see what the least cost is for moving from one space to another. In my game, it is 10. Therefore, the heuristic in my game should be 10 times the Manhattan distance:

h(A) = 10 * (abs(A.x-goal.x) + abs(A.y-goal.y))

You should use the scale that matches your cost function.

Diagonal distance

If on your map you allow diagonal movement, then you need a different heuristic. The Manhattan distance for (4 east, 4 north) will be 8. However, you could simply move (4 northeast) instead, so the heuristic should be 4. This function handles diagonals:

h(A) = max(abs(A.x-goal.x), abs(A.y-goal.y))

Straight line distance

If your units can move at any angle (instead of grid directions), then you should probably use a straight line distance:

h(A) = sqrt((A.x-goal.x)^2 + (A.y-goal.y)^2)

Guessing path quality

Instead of assuming the path is the best possible, you could check for obvious obstacles, and increase your path cost if you find some. To do this, construct a polygonal estimate of the map (make polygons for impassable areas, but ignore passable terrain, no matter how difficult it is to traverse). Then when you are looking at the distance from the current position to the goal, you can scan for simple obstacles and draw a line around them. The length of that line can be your heuristic.

Breaking ties

One thing that can lead to poor performance is ties in the heuristic. When several paths have the same f value, they are all explored, even though we only need to explore one of them. To solve this problem, we can add a small tie-breaker to the heuristic. This tie breaker also can give us nicer looking paths:

double dx1 = currentX - goalX;
double dy1 = currentY - goalY;
double dx2 = startX - goalX;
double dy2 = startY - goalY;
cross = dx1*dy2 - dx2*dy1;
if( cross<0 ) cross = -cross;
... add cross*0.001 to the heuristic ...

This code computes the vector cross-product between the start to goal vector and the current point to goal vector. When these vectors don't line up, the cross product will be larger. The result is that this code will give some slight preference to a path that lies along the straight line path from the start to the goal. It can significantly improve the speed of path-finding when there are few obstacles around.

To see a demonstration of the improvement from this fudge factor, see James Macgill's A* applet. Use "Clear" to clear the map, and choose two points on opposite corners of the map. When you use the "Classic A*" method, you will see the effect of ties. When you use the "Fudge" method, you will see the effect of the above cross product added to the heuristic.

Searching for an area

If you want to search for any spot near some goal, instead of one particular space, you could construct a heuristic h'(x) that is the minimum of h1(x), h2(x), h3(x), ... where h1, h2, h3 are heuristics to each of the nearby spots. However, a faster way is to just let A* search for the center of the goal area. Once you pull any nearby space from the OPEN set, you can stop and construct a path.


Last modified: Sun Nov 18 11:32:17 2001
From Amit's Game Programming Site
Copyright (C) 2000, Amit J. Patel