Improving Heuristics

19 May 2015

I had put this on hold in 2015 and revisited it in late 2016, and then again in 2018 and 2019 and 2022 and 2024 and 2026. Consider it an early draft that needs a lot of work. This is how I often work — I have a jumbled mess of ideas, put them into an outline, find the flow or explanations don’t work, and then rewrite it. And then rewrite it again and again until I make an explanation I really like. It can take a long time.

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 red blob (start) and purple X (goal) to see A* in action:

Now try moving the green circle to be near the purple X. As the heuristic value gets closer to the true distance , the number of nodes A* has to explore decreases from to .

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. Try moving the goal to see the heuristic change. Try moving the start to see the heuristic not change.

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 🟢. Can we reuse it for another goal X? Yes, sometimes! Move the red start point and the green landmark 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 X along the way:

And we almost have the path if the goal X is near the path 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 X.

4 Multiple landmarks#

How often is this triangle inequality useful?

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

Try moving the green landmark 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 X, 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 X 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 blob start point 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 X. We want the landmark to be “behind” goal X, but what’s “behind” depends on both where the start point B is and where the goal X is.

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:

But where should we place them? One way to pick is to randomly generate paths and keep track of which locations are good for many different paths.

This gives us a sense of where the landmarks should go, and it matches our intuition that they should go on the outer edges of the map. We can place the first landmark using this guide. To place the second landmark, we need to re-run this evaluation to see which locations add information beyond what the first landmark already gives us. To place the third landmark, we need to re-run to see which locations add information beyond the first and second, and so on.

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 forest and a mine.
All all paths equally valuable to optimize? For example if pathfinding is limiting the frame rate, we might want to focus on long paths that are slower to compute and not on short paths.
Is the map static or does it change over time? If static, we might want to spend a lot of time in the map designer tool to precalculate optimal landmarks. But if dynamic, we might want to use the last few goal locations to decide new landmark positions. The new landmarks can be computed in a background thread.
- If the change reduces an edge cost is lower than the old cost, the heuristic will overestimate sometimes, and A* will return a non-shortest path until you’ve updated the cost table. Pathfinding is optimized but nonoptimal. Example: the player broke a wall but the unit won’t look for the shorter path right away.
- If the change increases an edge cost, the heuristic will be lower than desired, and A* will take a little longer to run until you’ve updated the cost table. Pathfinding is optimal but not optimized. Example: the player added a wall so the unit might think that area’s safe to walk through but will have to find a path around it.
Are the maps open world or constrained? A real time strategy game may have different needs than a room+corridor dungeon crawler.
Fortunately, even if a landmark doesn’t greatly speed up finding a specific (start, goal) path, it might help a little, and it’s still no worse than if we use the regular A* heuristic.

6 Undirected graphs#

In many maps, you can move from B→X and also X→B with the same movement cost. When cost(B, X) = cost(X, B) we can consider both directions with abs() in the heuristic:

heuristic(B, X) = max(
    distance(B, X),
    abs(cost(X, L₁) - cost(B, L₁)),
    abs(cost(X, L₂) - cost(B, L₂)),
    abs(cost(X, L₃) - cost(B, L₃)),
    …
    abs(cost(X, Lₙ) - cost(B, Lₙ))
)

In the demo at the top the green landmark point helps near the goal. But in an undirected graph, the landmark point also helps near the start.

{{ TODO: add demo with a checkbox for whether it’s treated as directed or undirected, and show a heat map so we can see where the landmarks actually help, or maybe which goal nodes are helped }}

7 Implementation#

As the name “differential heuristics” suggests, this is a change to the heuristic given to A*, but not a change to the A* algorithm itself.

I wrote cost(n, Lᵢ) in the previous section but for implementation we can store it in a 2D array, cost[nodeId][landmarkId]. {{ save for IMPL? }} The heuristic is looking at all the landmarkId values, so we’ll get better cache behavior with cost[nodeId][landmarkId] than with cost[landmarkId][nodeId].

To calculate the cost[nodeId][landmarkId] array, we need to add a map analysis step. My article on A* and Dijkstra’s Algorithm shows how to calculate cost[…][landmarkId] with Dijkstra’s Algorithm for a single landmark. Dijkstra’s is “single source shortest path” but we want a single goal instead of a single source. In a directed graph, we need to reverse all the edges.

function zero_heuristic(a, b) { return 0; }

const L = [ /* array of landmark locations */ ];
let L_cost = [ /* array[nodeId] of arrays[landmarkId] */ ];
for (let landmarkId = 0; landmarkId < L.length; landmarkId++) {
    let output = reverse_dijsktra_search(L[landmarkId]);
    for (let nodeId = 0; nodeId < graph.num_nodes; nodeId++) {
      L_cost[nodeId][landmarkId] = output.cost_so_far[nodeId];
    }
}

What changes with the A* code? Nothing. We only have to change the heuristic function. Previously I set the heuristic to be distance(B, X), because that was the only lower bound I had. Now I have an additional lower bound for each landmark L_i, cost(Lᵢ, X) - cost(Lᵢ, B), stored as L_cost[X][landmarkId] - L_cost[B][landmarkId]. Here’s what the code looks like before:

function distance_heuristic(a, z) { // Manhattan distance
    return Math.abs(a.x - z.x) + Math.abs(a.y - z.y);
}

Each landmark serves as a lower bound, so it can increase the heuristic:

function differential_heuristic(a, z) {
    let h = distance_heuristic(a, z);
    for (let landmarkId = 0; landmarkId < L.length; landmarkId++) {
        let lower_bound = L_cost[a][landmarkId] - L_cost[z][landmarkId];
        if (lower_bound > h) { h = lower_bound; }
    }
    return h;
}

That’s all!

The idea is extremely simple to implement compared to just about any other technique that gives such a nice speedup. Bonus: these distance fields can be updated in a background thread.

8 Appendix: more demos#

In these demos, the light blue is the area searched by A* with the regular (manhattan) heuristic. The dark blue is the area searched by A* with the new (differential) heuristic. The red and purple points are the endpoints of the path. The green landmark points control the differential heuristic.

Dragon Age and maze maps provided by movingai.com^[2]. Cogmind maps provided by Josh Ge.