The idea is that if we already have the path from B→L, we also get the shortest path to any along the way:
L
path from B to L includes X path from B to X path from X to L
Think of the landmark as something far in the distance. Your friend tells you “from your house B, walk towards the Eiffel Tower L until you get to Daniel’s house ”. The goal is not to reach the landmark. The landmark tells us a direction to go in. The goal, Daniel’s house, is on the way.
Most goals aren’t on the path B→L but sometimes they are close to that path:
path from B to L path from B to X path from X to L
But what does it mean to be “close”? We can use the path length, cost(B, L). When the paths are almost the same, cost(B, L) is close to cost(B, X) + cost(X, L).
In A*, we use the heuristic function as a lower bound for the path length cost(B, X). 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). To calculate a lower bound, 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 .
Some of the academic research papers refer to this as a heuristic based on the triangle inequality. Other papers call this the “differential heuristic” because it takes the difference between already computed distances.
How often is this triangle inequality useful?
cost(B, X) cost(X, L) cost(B, L) ≤ cost(B, X) + cost(X, L)
It depends on where L is relative to the path B→:
only in undirected graphs
middle
B L
no
after
B L
yes
Move the start B and goal around to see where a landmark would help:
Try moving the landmark L outside the green shaded region, and see that the heuristic and path don’t always match.
Since a landmark needs to be “after” the goal , a single landmark won’t be useful for all paths. 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 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 start point B to see how the shaded area also depends on where the start is.
The best landmark position depends on the start point B and goal . We want the landmark to be “after” the goal , but what’s “after” depends on where the start point B and goal are.
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 B, goal , and landmark L on this map:
The purple shaded areas show the goal positions that the landmark helsp. It looks like the landmark can cover the main corridors but not the side rooms. We need many more landmarks:
Much more of the map is covered in purple now. Picking the number and placement of landmarks is project specific. Consider:
Fortunately, even if a landmark isn’t optimal, it might still help somewhat, and it’s still no worse than if we use the regular A* heuristic.
Although the best landmark positions will be project specific, one algorithm to place landmarks in a project-agnostic way is to keep track of which locations are good for many randomly chosen paths. Try it here to find a landmark position:
It usually but not always picks a spot in the upper left. It matches our intuition that landmarks should go on the outer edges of the map.
The second landmark should be away from the first landmark. The third landmark should be away from the first and second landmark. Each subsequent landmark should be evaluated based on what it adds. This is what it looks like with two existing landmarks:
It picks a third away from the first two, but not always in the same place.
The change described on this page is to the heuristic function given to A*. We don’t need to change A* itself.
We need to pick landmarks. If the maps are known ahead of time, landmarks can be placed in a map designer tool. If the maps are procedurally generated, try the randomized map analysis earlier on this page. Some of the papers linked at the end have more sophisticated placement algorithms.
Then we need to analyze the map. Allocate a 2D array of numbers, cost[nodeId][landmarkId].
For each landmark, we run Dijkstra’s Algorithm. It’s a “single source shortest path” algorithm but we want a single goal instead of a single source. In a directed graph, we need to reverse all the edges. In an undirected graph, we can use the edges as is. We set cost[nodeId][landmarkId] to the cost of the shortest path from node nodeId to node landmarkId. If the weights are all 1, we can use Breadth First Search instead of Dijkstra’s Algorithm.
This is approximately what I’m running for the demos on this page (undirected graphs):
const L = [ /* array of landmark locations */ ]; let L_cost = [ /* array[nodeId] of arrays[landmarkId] */ ]; for (let landmarkId = 0; landmarkId < L.length; landmarkId++) { let output = dijkstraSearch(L[landmarkId]); for (let nodeId = 0; nodeId < graph.num_nodes; nodeId++) { L_cost[nodeId][landmarkId] = output.cost_so_far[nodeId]; } }
Note that it’s not much code. It’s running our existing algorithm (Dijkstra’s, A*, or BFS) and storing the results in an array. It could run in a background thread.
Then we need to modify the heuristic function. Previously the heuristic was distance(B, X). For example:
function heuristicManhattan(a, z) { return Math.abs(a.x - z.x) + Math.abs(a.y - z.y); }
Each landmark Li gives us a lower bound cost(Lᵢ, X) - cost(Lᵢ, B). We want to take the highest of these:
function heuristicLandmark(B, X) { let h = heuristicManhattan(B, X); // or any base heuristic for (let i = 0; i < L.length; i++) { let lowerBound = L_cost[B][i] - L_cost[X][i]; lowerBound = Math.abs(lowerBound); // if undirected if (lowerBound > h) { h = lowerBound; } } return h; }
Note that it’s not much code. It’s running the existing heuristic (typically Manhattan, Chebyshev, or Euclidean distance) and sometimes increasing it if the landmarks form a good triangle.
There are lots of techniques for making A* run faster. I like this one because it’s very little code.
I tried the differential heuristic on some maps from Dragon Age (provided by movingai.com[3]), a maze (also provided by movingai.com), and Cogmind[4] (maps provided by Josh Ge). All of these maps are undirected graphs (edges are bidirectional) so I’ve used that version of the differential heuristic.
to see the performance on different paths.
8.1 Dragon Age, The Circle Tower#
The landmark is badly placed for the initial B→ path. Try moving it.
In the next demo the landmarks L are in places that don’t help. Move them around to improve search.
The blue area are the nodes we no longer have to search. More blue is better.