Improving Heuristics for A* Pathfinding

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.

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.

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.

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:

L cost(B, X) cost(X, L) 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) cost(X, L) cost(B, L) < cost(B, X) + cost(X, 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 .

How often is this triangle inequality useful?

cost(B, X) cost(X, L) 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₁) cost(B, X) ≥ cost(B, L₂) - cost(X, L₂) cost(B, X) ≥ cost(B, L₃) - cost(X, L₃) … 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.

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:

Fortunately, even if a landmark isn’t optimal, it might still help somewhat, and it’s still no worse than if we use the regular A* heuristic.

One algorithm to place landmarks is to randomly generate paths and keep track of which locations are good for many different paths.

It usually but not always picks a spot in the upper left. It matches our intuition that landmarks should go on the outer edges of the map.

The second landmark should be away from the first landmark. The third landmark should be away from the first and second landmark. Each subsequent landmark should be evaluated based on what it adds. This is what it looks like with two existing landmarks:

It picks a third away from the first two, but not always in the same place.

As the name “differential heuristics” suggests, this is a change to the heuristic given to A*. We don’t need to change A* itself.

We need to pick landmarks . If the maps are known ahead of time, landmarks can be placed in a map designer tool. If the maps are procedurally generated, try the randomized map analysis earlier on this page. Some of the papers linked at the end have more sophisticated placement algorithms.

Then we need to analyze the map . Allocate a 2D array of numbers, cost[nodeId][landmarkId] .

For each landmark, we run Dijkstra’s Algorithm . It’s a “single source shortest path” algorithm but we want a single goal instead of a single source. In a directed graph, we need to reverse all the edges. In an undirected graph, we can use the edges as is. We set cost[nodeId][landmarkId] to the cost of the shortest path from node nodeId to node landmarkId . If the weights are all 1, we can use Breadth First Search instead of Dijkstra’s Algorithm.

This is essentially what I’m running for the demos on this page (undirected graphs):

const L = [ /* array of landmark locations */ ]; let L_cost = [ /* array[nodeId] of arrays[landmarkId] */ ]; for ( let landmarkId = 0; landmarkId < L.length; landmarkId++) { let output = dijkstraSearch(L[landmarkId]); for ( let nodeId = 0; nodeId < graph.num_nodes; nodeId++) { L_cost[nodeId][landmarkId] = output.cost_so_far[nodeId]; } } Note that it’s not much code . It’s running our existing algorithm (Dijkstra’s, A*, or BFS) and storing the results in an array. It could run in a background thread.

Then we need to modify the heuristic function . Previously the heuristic was distance(B, X) . For example:

function heuristicManhattanDistance ( a , z ) { return Math.abs(a.x - z.x) + Math.abs(a.y - z.y); } Each landmark L i gives us a lower bound cost(Lᵢ, X) - cost(Lᵢ, B) . We want to take the highest of these:

function heuristicLandmark ( B , X ) { let h = heuristicManhattanDistance(B, X); // or any other distance heuristic for ( let landmarkId = 0; landmarkId < L.length; landmarkId++) { let lowerBound = L_cost[B][landmarkId] - L_cost[X][landmarkId]; // if the graph is undirected, use lowerBound = Math.abs(lowerBound) if (lowerBound > h) { h = lowerBound; } } return h; } Note that it’s not much code . It’s running the existing heuristic (typically Manhattan, Chebyshev, or Euclidean distance) and sometimes increasing it if the landmarks form a good triangle.

What changes with the A* code? Nothing .

There are lots of techniques for making A* run faster. I like this one because it’s very little code.

I tried the differential heuristic on some maps from Dragon Age ( provided by movingai.com [3] ), a maze (also provided by movingai.com), and Cogmind [4] (maps provided by Josh Ge). All of these maps have bidirectional edges so I’ve used that version of the differential heuristic.

to see the performance on different paths. 8.1 Dragon Age, The Circle Tower # The landmark is badly placed for the initial B → path. Try moving it.

In the next demo the landmarks L are in places that don’t help. Move them around to improve search.

The blue area are the nodes we no longer have to search. More blue is better.

The landmark L points help more when closer to the start point B than the goal . They help more when they’re “past” the goal point. Move the start B and goal around and see that there’s a big improvement no matter which path you want to find:

However, it took a lot of landmarks to get that improvement. We can do better by using the random path map analysis to pick fewer landmarks but in smarter locations:

A* with a distance heuristic behaves particularly badly with mazes, but in this one, just four landmarks make a big difference! Then Try dragging the start B and goal to see how much the landmarks help . The blue areas are the areas we didn’t have to search by using the landmarks. Also toggle the bidirectional flag to see how much of a difference that makes.

This map has large open areas, and it seems to work well with the landmarks.

This page is about using Cartesian coordinates in a game map to construct a graph-based heuristic based on “landmark” nodes (sometimes called “pivots” or “beacons”). I’ve collected some references but haven’t read all of them so I may have some of this wrong.

It’s also possible to go in reverse. Many graphs do not have natural Cartesian coordinates, and even the ones that do may not have good results from a distance-based heuristic.

Storing the landmark data requires one number per node. In a typical game map, those numbers may be very similar from one grid space to the next. Just as image compression takes advantage of nearby pixels having similar values, we might want to compress the landmark data because nearby graph nodes have similar values:

The landmarks L used on this page are placed beyond the end of the path B→X, so the layout is B→X→L. There are also algorithms that place landmarks along the path, B→L→L→L→X. I am not covering that topic here, but if you’re interested, see:

Email me redblobgames@gmail.com , or comment here: