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.
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.
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))
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)
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.
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.
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.
Back: Goals | Up: Home | Next: Movement Costs |
Last modified: Sun Nov 18 11:32:17 2001 From Amit's Game Programming Site | Copyright (C) 2000, Amit J. Patel |