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.

The rest of the page is incomplete; skip ahead to the demos!!

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 heuristic pushes us east, but the shortest path is to the west:

A* runs faster when the heuristic guides us in the right direction. It wastes time when the heuristic guides us in the wrong direction.

The rest of the page is incomplete; skip ahead to the demos!!

2 Perfect heuristic#

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

Can we do that? Yes!

However, calculating that heuristic takes more time than we save by giving an improved heuristic to A*, so it makes the overall process slower.

It’d be nice if we can calculate the heuristic once and reuse it for multiple A* calls.

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. However, using the triangle inequality^[1] adapted for directed graphs, we can construct both lower and upper bounds:

cost(B, L) - cost(X, L) ≤ 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 help us estimate other costs that don’t involve that 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:

Since we want to find paths for any B and any X, there’s not going to be a single landmark L that is always “behind” goal X. That means we need to have multiple landmarks L₁, L₂, L₃, etc. Each one gives us some lower bound for the heuristic. The heuristic value will then be the highest of these values:

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

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

5 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.

6 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]. 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.

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++) {
    /* use dijkstra's algorithm if available, otherwise use a_star with the zero heuristic */
    let output = astar_search(L[landmarkId], null, zero_heuristic);
    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_i, X) - cost(L_i, 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.

7 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 }}

8 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.

9 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.