Improving Heuristics

19 May 2015

For optimizing A* we usually look at the priority queue or the map representation. Often overlooked is improving the heuristic function . Here’s an example from the town of Denerim in Dragon Age Origins. Try moving the start B and goal to see A* in action:

Now try moving the green L to be near the purple . As the heuristic value gets closer to the true distance , the number of nodes A* has to explore decreases from to . The blue area is the savings.

On this page I’ll show a way to improve the heuristic to speed up A*. At the end of the page I show this technique with maps from real games.

1  A*’s use of the heuristic#

A* uses a heuristic to guide it towards the goal. We can think of it like wind pushing us in the right direction. Here, the heuristic pushes us east, and the shortest path goes east:

But sometimes it pushes us in the wrong direction. Here, the shortest path is to the west but the heuristic pushes us east:

A* runs faster when the heuristic guides us in the right direction. It wastes time when the heuristic guides us in the wrong direction. But why is it in the wrong direction? It’s because the usual distance-based heuristic doesn’t know about the walls.

2  Perfect heuristic#

Ideally, we’d find a heuristic that knows about walls and never points in the wrong direction:

Can we calculate this “perfect” heuristic? Yes!

But the perfect heuristic is different for every goal and wall configuration. Move the goal and you’ll see the heuristic changes. Move the start B and you’ll see it doesn’t.

If the goal and walls stay the same, then we can use flow field pathfinding. But usually the goal isn’t the same, so we need to construct a brand new perfect heuristic for each goal. That is impractically slow to calculate every time we run A*, and it’s also impractically too large to store if we want to compute it ahead of time.

It’d be nice if we could calculate the heuristic once and then reuse it for multiple A* runs with different goals.

3  Reusing a perfect heuristic#

Let’s calculate a perfect heuristic to the green landmark L. Can we reuse it for another goal ? Yes , sometimes! Move the start point B and the landmark L around to see which purple goals are helped:

The idea is that if we already have the path from B→L, we also get the shortest path to any along the way:

cost(B, X)<br>cost(X, L)<br>cost(B, L) = cost(B, X) + cost(X, L)

And we almost have the path if the goal is near the path B→L:

cost(B, X)<br>cost(X, L)<br>cost(B, L)

We can’t exactly calculate cost(B, X) in this situation. But the triangle inequality[1] says that the sum of two sides of a triangle is at least as long as the third side. Adapted for directed graphs, we can say cost(B, X) + cost(X, L) ≥ cost(B, L). For a heuristic we want a lower bound on cost(B, X) so we rewrite this inequality as cost(B, X) ≥ cost(B, L) - cost(X, L).

That’s the key idea here . It’s impractical to precalculate all costs to all locations, but if we’ve precalculated the costs to a specific location L, we can use that to estimate the cost to a different location .

4  Multiple landmarks#

How often is this triangle inequality useful?

cost(B, X)<br>cost(X, L)<br>cost(B, L)

It depends on where landmark L is in relation to start point B and goal . We need L to be “behind” when coming from B. Move the start B and goal around to see where a landmark would help:

Try moving the landmark L outside the green shaded region, and see that the heuristic and path don’t always match.

Since a landmark needs to be “behind” the goal , a landmark won’t be useful for all goals. We need multiple landmarks L₁, L₂, L₃, etc. Each one gives us some lower bound for the heuristic:

cost(B, X) ≥ cost(B, L₁) - cost(X, L₁)<br>cost(B, X) ≥ cost(B, L₂) - cost(X, L₂)<br>cost(B, X) ≥ cost(B, L₃) - cost(X, L₃)<br>cost(B, X) ≥ cost(B, Lₙ) - cost(X, Lₙ)

We can take the max() of these to pick the highest bound. In this diagram, try moving the goal to one of the purple shaded areas to see how those areas are improved by the landmarks. Then try moving it to one of the unshaded areas to see how A* isn’t any faster there. Also try moving the start point B to see how the shaded area also depends on where the start is.

5  Placement of landmarks#

The best landmark position depends on the start point B and goal . We want the landmark to be “behind” goal , but what’s “behind” depends on both where the start point B is and where the goal are.

We want to use landmarks to improve as many (start, goal) pairs as possible.

Let’s start with a single landmark. Try moving the start point, goal, and landmark around in this map:

It looks like the landmark can cover the main corridors but not the side rooms. We need many more landmarks:

Picking the number and placement of landmarks is project specific. Consider:

Are all paths equally likely? For example in a colony builder game like Dwarf Fortress, we may care a lot more about paths to/from the main base, and not paths between a...