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 🟢. Can we reuse it for another goal X? These are the tiles where the perfect heuristic helps us:

Suppose we’re finding the shortest path from A to Z. A* needs a heuristic function giving an estimated cost from n to Z, for many different nodes n, but always to the destination Z. Let’s suppose for this particular Z we have precalculated cost(n, Z) for all nodes n. What would happen? We could use this as our heuristic, and A* would run fast! But we could only use it when finding a path to Z.

What if there’s some other node L where we have precalculated the cost(n, L) from all other nodes n? Can we use that to find the shortest path from A to Z? Yes, but only when Z is on the path from A to L:

In this case we know cost(A, L) and cost(Z, L) because we have precalculated cost(*, L), but we need to know cost(A, Z). If Z is on the shortest path from A to L, then we can calculate cost(A, Z) = cost(A, L) - cost(Z, L).

Can we handle more cases? What if Z is near the shortest path from A→L?

We can’t exactly calculate cost(A, Z) in this situation. However, the triangle inequality^[1] adapted for directed graphs, we can construct both lower and upper bounds:

cost(A, L) - cost(Z, L) ≤ cost(A, Z) ≤ cost(A, L) + cost(Z, 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!

{{ Heuristic is a lower bound so we normally only care about cost(A, Z) ≥ cost(A, L) - cost(Z, L), but see references — one paper found the upper bound to be useful too }}

{{ if the graph is directed we can only say this, but if it’s not directed we can use abs(cost(A, L) - cost(Z, L)) which allows for the landmark to be on the other side too }}

4 Triangle geometry#

How often is this triangle inequality useful?

It depends on where L is in relation to A and Z. We need L to be “behind” Z when coming from A.

Since we want to find paths for any A and any Z, there’s not going to be a single L that is always “behind” Z. That means we need to have multiple nodes 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(A, Z) = max(
    distance(A, Z),
    cost(Z, L₁) - cost(A, L₁),
    cost(Z, L₂) - cost(A, L₂),
    cost(Z, L₃) - cost(A, L₃),
    …
    cost(Z, Lₙ) - cost(A, Lₙ)
)

If your graph is undirected, then we can also use the triangle with the edges reversed. In practice this means taking abs() of each of the lower bounds:

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

{{ TODO demo: one goal, one landmark, reader moves N to see triangle, costs of each of the three sides, calculated lower bound, and distance heuristic }}

5 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[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(A, Z), because that was the only lower bound I had. Now I have an additional lower bound for each landmark L_i, cost(L_i, Z) - cost(L_i, A), stored as L_cost[Z][landmarkId] - L_cost[A][landmarkId]. Here’s what the code looks like before landmarks:

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 might increase the heuristic:

function landmark_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!

If movement is symmetric (graph is undirected), then cost(a, z) == cost(z, a) so we can reuse the landmark in the reverse direction by setting lower_bound = abs(L_cost[a][landmarkId] - L_cost[z][landmarkId]).

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.

6 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 Z, one P, 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 }}

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

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 pivot points control the differential heuristic.

Dragon Age and maze maps provided by movingai.com. Cogmind maps provided by Josh Ge.