Improving Heuristics

from Red Blob Games
DRAFT
19 May 2015

Table of Contents

For optimizing A* we usually look at the priority queue or the map representation. Often overlooked is improving the heuristic function.

A* uses a heuristic function to get an estimate of the cost of moving from one place to another (also called “geodesic distance”). All other things being equal, the better the estimate, the faster A* runs. Normally in game maps we use straight line distance as the heuristic. This is a great estimate in wide open maps with few obstacles. Here’s a × map of Denerim (Bloodmage HQ) from Dragon Age:Origins with walkable tiles. The straight line distance is but the actual path is . The mismatch means A* has to explore nodes:

{{ the demo here should use a non-grid, maybe with delaunay where nodes are circles and edges are line segments }}

{{ add arrowhead to path, as well as blob & X for start/end, maybe green Δ for landmarks }}

What if we could improve the heuristic from to ? (The best would be the actual graph distance of .) Instead of exploring nodes, A* would explore only nodes:

These are interactive diagrams. You can move the blue and red points around. What are the green nodes?

#Precalculated costs

Suppose we’re finding the shortest path from A→Z. A* will ask for heuristic(n, Z) for many different nodes n, but always to the destination Z. The best heuristic (as explained on the main page) is the exact cost from n to Z. In practice, we can’t use the best heuristic but instead use a distance function.

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 we had precalculated the cost(n, L) for some other point L? 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:

AZLcost(A, Z)cost(Z, L)cost(A, L) = cost(A, Z) + cost(Z, 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?

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

#Triangle geometry

Let’s generalize this. Instead of having all costs cost(, Z) let’s say there’s a third point L where we have cost(_, L). Point L is called a landmark. If you’re at A and want to get to Z, a friend could say “walk towards L, and you’ll see Z on the way — you can’t miss it!”.

{{ I already generalized in the previous section, so reword this }}

AZLcost(A, Z)cost(Z, L)cost(A, L)

We have cost(*, L) precalculated. We are trying to find a path A→Z, and need to estimate cost(N, Z). We can estimate cost(N, Z) ≥ cost(N, L) - cost(Z, L). This works for any N and any Z, and any L for which we have precalculated cost(_, L).

— EDIT —

This only works when L is behind the route A→Z*. To make it work for many different paths, we need to have multiple landmarks L placed around the map. Then we calculate final heuristic as:

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

Although I write it as cost(Lᵢ, __), it’s really stored as a precalculated array cost[i][__]. Since distance() is fast and cost[] is precalculated for each of the L points, this heuristic is fairly fast to calculate.

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

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

To use our landmark L, we need to add a map analysis step and modify the heuristic function.

The map analysis, run once per map, is to calculate cost(L, __) for all locations and save those costs in a data structure. My article on A* and Dijkstra’s Algorithm[2] shows how to calculate these with Dijkstra’s Algorithm, and save it in a variable cost_so_far[]. For the landmark L, I’m going to copy that to L_cost[]. This is roughly what we have to do:

const output = astar_search(L, null, function(a, b) { /* heuristic */ return 0; });
const L_cost = output.cost_so_far;

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, cost(L, Z) - cost(L, A), which has been calculated during the map analysis and saved to L_cost[Z] - L_cost[A]. I need the heuristic to pick the better lower bound. Here’s what the code looks like before landmarks:

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

Here’s what we do with one landmark:

function landmark_heuristic(a, z) {
    return Math.max(distance_heuristic(a, z), L_cost[z] - L_cost[a]);
}

That’s all!

Note that if your edge costs are symmetric, then cost(a, z) == cost(z, a) so we can reuse the landmark in the reverse direction:

function landmark_heuristic(a, z) {
    return Math.max(distance_heuristic(a, z), Math.abs(L_cost[z] - L_cost[a]));
}

If your edge costs are asymmetric, then you can’t reuse the landmark.

To handle multiple landmarks, we’ll loop over them in the heuristic function:

function landmark_heuristic(a, z) {
    // Assume landmarks are in array L_costs[]
    let d = distance_heuristic(a, z);
    for (let i = 0; i < L_costs.length; i++) {
        d = Math.max(d, L_costs[i][z] - L_costs[i][a]);
    }
    return d;
}

The idea is extremely simple to implement compared to just about any other technique that gives such a nice speedup.

#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:

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

#Appendix: Map changes

We need to precalculate cost(L, __) to all other points, but what if the map changes? This is not that expensive to calculate occasionally. It’s Dijsktra’s Algorithm starting at L. 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:

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

If you need to recalculate often, consider Breadth First Search instead of Dijkstra’s Algorithm. It runs much faster but will produce worse distance values (but still better than straight line distance). In many maps this will be a good tradeoff.

#Appendix: more demos

Demo #2 - Dragon Age, The Circle Tower
Demo #3 - maze
Demo #4 - Dragon Age, Lothering
Demo - Cogmind level - Research 2
Demo - Cogmind level - Factory 4

The next demo shows how placing the green points in a bad location doesn’t help pathfinding at all. Try moving the green points around to see if you can find the best spots.

Demo - Cogmind level - Factory 5

As before, the light area is A* with a (manhattan) distance heuristic, and the dark area is A* with the landmark heuristic.

#More reading

Terminology isn’t consistent.

This is the paper I found first http://research.microsoft.com/pubs/64511/tr-2004-24.pdf[3] (“landmarks”) but this paper had it earlier: https://www.cs.rice.edu/~eugeneng/papers/INFOCOM02.pdf[4] (“landmarks”, “base nodes”, “triangulated heuristic”). The latter paper also suggests using the upper bound; that’s something I should investigate for game maps. There are also papers from Sturvetant that use “pivot points” and “differential heuristic”.

http://www.cc.gatech.edu/~thad/6601-gradAI-fall2014/02-search-01-Astart-ALT-Reach.pdf[5]

There’s a different approach in pathfinding also called “landmarks” (e.g. https://pdfs.semanticscholar.org/f918/5ed02848c1cd3e0ccdda16fa7a32f7428a8a.pdf[6]) which is not the same how these points are used. Those landmarks need to be between the start and end points, whereas the landmarks on this page are used on the edges of the map. “If you want to walk to Z, walk to L, and then to Z” vs “If you want to walk to Z, walk to L, and Z is on the way”.

TODO: also try breadth first search with the two-insertonly-queue trick on these large maps. Breadth first search is faster than A* but I’d be scanning the entire map instead of just part of it; I’m not sure which will win overall. Mazes are probably faster with breadth first search, and big open areas might be too.

http://webdocs.cs.ualberta.ca/~bowling/papers/11aaai-heuristicopt.pdf[7]

http://www.cs.du.edu/~sturtevant/papers/GPPC-2014.pdf[8]

Pieeter Geerkens has this implemented in his hex grid pathfinding lib: https://gamedev.stackexchange.com/a/93849[9]

Andrei Kashcha has landmarks and the rest of ALT implemented in his graph pathfinding lib https://github.com/anvaka/ngraph.path[10]