A technical guide from Red Blob Games explains how landmark nodes can improve A* pathfinding by giving its heuristic information about a map's actual structure. The method, often called a differential heuristic, precomputes distances to selected locations and reuses them as lower bounds during later searches.
A* relies on a heuristic to estimate the remaining cost from a node to the goal. A common distance formula works well in open space but does not understand walls, corridors or other constraints. It can therefore guide the search toward a goal geometrically even when the shortest available route initially travels in another direction. The algorithm still finds the route, but it may inspect more nodes than necessary.
A perfect heuristic could store the true shortest cost from every location to a particular goal. That would make search efficient, but recalculating or storing such information for every possible goal is usually impractical. A landmark offers a reusable compromise. The system computes exact distances from map nodes to one chosen location ahead of time, then derives information about other start-and-goal pairs from those values.
The mathematical basis is the triangle inequality. If the cost from node B to landmark L and the cost from node X to L are already known, their difference can provide a lower bound on the cost from B to X. A* can use that bound without sacrificing correctness. The guide notes that the technique applies to graphs generally, not only the grids used in its interactive demonstrations.
One landmark will not help equally across an entire map. Its value depends on where it sits relative to the start, goal and available paths. The guide therefore recommends multiple landmarks and taking the maximum lower bound they produce. Locations near outer edges or beyond major corridors can be useful, but the best number and placement remain specific to each project. New landmarks should be assessed for what they add beyond the existing set.
Preparing the data requires a shortest-path pass for each landmark. For a directed graph, the guide says edges should be reversed so the stored value represents the cost from each node to the landmark. Dijkstra's algorithm handles weighted graphs, while breadth-first search is sufficient when every edge has the same weight. The resulting values can be stored by node and landmark.
The optimization changes the heuristic supplied to A*, not A* itself, and can be combined with other improvements. Its cost is additional preprocessing and memory. For fixed game maps, designers can place landmarks during authoring. Procedurally generated maps can instead use automated sampling to identify locations that improve many representative routes. Even imperfect landmarks can preserve the ordinary heuristic as a fallback while improving searches where their precomputed distances provide a tighter bound.
