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 position and wall configuration. Try moving the goal or editing the walls to see the heuristic change.

If the goal position and walls stay the same, then we can use flow field pathfinding. But usually the goal position 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 goal positions.

{TODO: should I simplify by assuming walls can’t be edited? I can put that into a later section}

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 goal locations 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, we can use that to estimate the cost to a different location.

4 Triangle geometry#

How often is this triangle inequality useful?

It depends on where landmark L is in relation to start B and goal X. We need L to be “behind” X when coming from B. Move the start blob and purple goal X 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.

5 Multiple landmarks#

No single landmark L is always “behind” goal X. 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.

{{ TODO to build intuition, show a larger map like the one from the top of the page, with multiple heuristics, maybe differently colored, maybe shaded with different angled stripes }}

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. {{ save for IMPL? }} 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 Placement of landmarks#

If we have just one landmark, where should we place it? A landmark’s location will help some goal locations but not all. Let’s explore this to build up some sense of what landmark locations are most useful. Move the landmark around to see which goal locations are helped:

{{ TODO demo: one X, one L, all N: show how much the landmark improves the heuristic }}

{{ offline calculation: lots of starts, lots of goals, improvement for each landmark candidate site; no interaction here because there are no free variables anymore }}

{{ conclusion on placement to be written after I have the demo implemented }}

Another idea: do we need complete data? No, we don’t! That means we could use the cost_so_far from the previous few A* runs. They’re already computed, so it’s almost free to keep that around. If we’re finding a lot of paths in the same areas, that data would probably help a lot.

{{ which landmarks help the most? the LPI paper suggests picking the landmarks closest to the start or goal nodes }}

Another idea: place the landmark near the centroid of the last N destinations

{{ TODO: distance heuristic ≤ landmark heuristic ≤ true distance so that gives me a number I can put on a gradient color visualization }}

9 Appendix: Map changes#

We need to precalculate cost(__, L) from all other points to L, but what if the map changes? This is not that expensive to calculate occasionally. It’s Dijsktra’s Algorithm starting at L with edges reversed. If the graph is undirected, you don’t need to reverse edges. And if all your movement costs are 1, you can use the much faster Breadth First Search. And either way you can spread this out over multiple frames.

There are two problems that happen if you use an outdated cost(__, L) after the map changes:

The new cost is lower than the old cost (you broke a wall). The heuristic will overestimate sometimes, and A* will return a non-shortest path until you’ve updated the cost table. Think of it this way: you broke a wall but the unit doesn’t know right away to take that into account.
The new cost is higher than the old cost (you added a wall). The heuristic will be lower than desired, and A* will take a little longer to run until you’ve updated the cost table. It will still be faster than if you weren’t using landmarks. Think of it this way: you added a wall so the unit might think that area’s safe to walk through but will soon find a path around it.

10 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. Cogmind maps provided by Josh Ge.