Hadlock's Algorithm

The idea

On an obstacle-free grid, the shortest path length equals the Manhattan distance M between the pins. Obstacles force detours: moves that increase the distance to the target. For any path with d detour moves,

• M Manhattan distance between the two pins
• d number of detour moves: steps that increase the distance to the target

because each step away from the target must be compensated by one additional step toward it. Minimizing path length is therefore equivalent to minimizing detour count. Hadlock's algorithm expands cells in order of detour count: all cells reachable with zero detours first, then one, then two. The implementation is a zero-one breadth-first search over a double-ended queue (deque): moves that reduce the distance to the target join the front (cost 0, current detour level), moves that increase it join the back (cost 1, next level). The deque therefore stays sorted by detour count without a priority queue, holding at most two consecutive detour values at any moment.

The recipe

Step 1 (label by detour). Give the source detour number d = 0. A cell's detour number is how many of the moves on its best path so far led away from the target (Manhattan distance to the target increased).

Step 2 (expand cheapest first, with a deque). Take the cell with the smallest d. For each free neighbour: if the move goes toward the target, the neighbour keeps the same d and goes to the front of the deque (double-ended queue); if it goes away, the neighbour gets d + 1 and goes to the back. The front of the deque therefore always holds the current detour level.

Step 3 (stop at the target). The first time the target is reached, its path has the minimum detour count, and by the identity length = M + 2d (M the Manhattan distance) it is a shortest path. Backtrace as in Lee.

Watch it work: the deque in action

The scenario matches the A* page's queue diagram, so the two data structures can be compared directly. The right panel shows the deque itself, front at the top. Pops always occur at the front. A neighbor that reduces the distance to the target enters at the front with an unchanged detour count (cost 0); a neighbor that increases it enters at the back with detour count + 1 (cost 1). The panel shows the resulting invariant directly: at any moment the deque holds at most two consecutive detour values, front to back, which is why no priority queue is needed.

Exploration cost, and the exact relation to A*

Cells with detour count zero form a staircase-shaped corridor between the pins; the search expands outside it only where obstacles impose a higher detour count. On this site's macro-maze benchmark, Hadlock settles 769 cells versus 2,843 for Lee at equal path length.

The relation to A* (A-star) is an identity, not an analogy. A path reaching cell n with t toward-moves and a away-moves has g(n) = t + a and h(n) = M − t + a, so

• f, g, h the A* quantities: priority, cost so far, Manhattan estimate
• d(n) detour count of the best known path to cell n

Expansion by detour count is therefore the same ordering as A* under the Manhattan estimate. The count difference (769 versus 1,208 on the macro maze) comes only from how ties are broken among cells with equal f:

• Cells with equal f can be expanded in any order without affecting the path length. Only the settled-cell count changes.
• Both algorithms must settle every cell with f below the final path length. The difference comes from the last f level, where the search stops as soon as the target is settled.
• Within that level, Hadlock expands the most recently discovered cell first (the deque is last-in-first-out for toward-moves), so it runs down one corridor straight to the target.
• A* breaks ties by smaller h, which spreads work across several frontier branches and settles more cells before reaching the target.

Pros, cons, and the trade-off

Is it actually used today?

The evidence on Hadlock's algorithm covers open-source tools, commercial documentation, and the teaching literature.

• Why not: production routing graphs are cost-weighted (vias, layer direction, congestion), and detour counting measures only uniform steps. Production point-to-point search uses cost-general Dijkstra and A* (A-star) engines.
• Where it appears: teaching, where it isolates the effect of search ordering from cost modeling; specialized uniform-cost grid problems; and analysis, since on unit grids it is A* with the Manhattan estimate plus a specific tie-breaking rule.
• Interactive: it runs in this site's maze lab; its settled-cell counts on the bundled presets are the lowest of the four algorithms.