Speed Up A* by Fixing the Heuristic, Not the Queue

Most A* optimization effort goes into the priority queue or map representation, but the heuristic function is where the biggest wins often hide. The standard straight-line distance estimate is blind to walls, so it can steer the search away from the true shortest path and force A* to explore far more nodes than necessary. A ‘perfect’ heuristic that accounts for obstacles exists, but it has to be recomputed for every goal, which is too slow to run on demand and too large to precompute and store for all destinations.

The differential heuristic sidesteps that cost by precomputing exact distances to a small set of fixed reference nodes called landmarks. The triangle inequality then yields a valid lower bound for any goal: cost(start, goal) is at least cost(start, landmark) minus cost(goal, landmark). Because this bound reuses one precomputed distance field across many different goals, it captures wall-aware guidance without per-query recomputation. A single landmark only helps goals that lie roughly ‘on the way’ to it, so multiple landmarks are used and A* takes the maximum of their bounds, tightening the estimate wherever any landmark applies.

Landmark placement is the practical lever. Corners and outer edges tend to cover the most start–goal pairs, and an automated strategy is to score candidate spots against many random paths, then spread each new landmark away from the previous ones. Placement choices are project-specific—weighing which paths matter most, whether the map is static or dynamic, and how edge-cost changes affect optimality (a removed wall can leave paths non-optimal until distances are refreshed; an added wall just slows the search). The appeal is that a suboptimal landmark never makes things worse than plain A*, and the whole technique changes only the heuristic function—A* itself is untouched.