Soukup's Algorithm
The idea
Soukup's router alternates between two modes. In sprint mode it moves greedily: from the current cell, step to a free, unvisited neighbor that reduces the distance to the target, marking cells visited along the way. Sprinting costs one cell visit per cell of progress and requires no queue or labels. When no free improving neighbor exists, the router switches to escape mode, and escape mode is Lee's algorithm: the same breadth-first wave, expanding ring by ring, except that it starts from the set of all visited cells instead of a single source, and it is cut short at the first cell whose distance to the target is smaller than the stuck point's. The sprint resumes from that cell. Soukup is therefore Lee's algorithm used sparingly: full wave expansion only in the short stretches where greed fails.
The recipe
Step 1 (sprint). From the current cell, move straight toward the target (the neighbour that reduces distance), without a queue and without labels, as long as such a move is free.
Step 2 (escape on collision). When the sprint hits an obstacle, switch to a Lee-style breadth-first wave from the stall cell, expanding ring by ring until the wave reaches any cell from which a toward-the-target move is free again.
Step 3 (resume and repeat). Sprint again from that cell. Alternate the two modes until the target is reached, then backtrace. The escape waves guarantee completeness; the sprints forfeit the shortest-path guarantee.
Watch it work: sprint, stall, escape
Sprint moves are green, one frame each. Escapes step ring by ring: the amber cells are Lee's wave grown from the visited set, and each carries its Manhattan distance to the target. The stuck cell is red and shows the threshold. The wave stops at the first cell whose label is smaller than the threshold; that inequality, visible in the numbers, is the entire selection criterion.
Completeness without optimality
The escape wave is an exhaustive breadth-first search from the visited set, so if any path to the target exists, the escape finds a cell strictly closer to it. Each escape therefore decreases the minimum distance achieved, the loop terminates, and the router is complete. Optimality does not hold: sprint moves are committed without comparing path costs, so the concatenation of sprint segments and escape paths is in general longer than a shortest path. The maze lab quantifies the overhead on its presets: 200 versus Lee's 194 on the macro maze, 144 versus 114 on the shared channel.
Pros, cons, and the trade-off
Strengths
- Fast: the 1978 paper reports 10-50x speedups over Lee; open regions are traversed at one cell visit per cell of progress, with no search.
- Complete: the breadth-first escape is exhaustive, so a route is found whenever one exists.
- Minimal state: no frontier structure during sprints; memory stays small.
- Architecture-setting: inexpensive directed progress with an exact fallback became the standard organization of later routers.
Weaknesses
- Not shortest: sprint moves are committed without cost comparison; the measured overhead appears in the maze lab's congested presets.
- No quality bound: path shape depends on sprint order and obstacle geometry; the detour is not bounded.
- Uniform costs only: like the other pure-grid classics, via, bend, and congestion costs have no representation.
- Superseded as an engine: cost-weighted A* (A-star) with pattern-route front ends took its role.
The trade-off
Soukup removes exactly one of Lee's guarantees: optimality. Completeness is preserved by the escape wave, and runtime falls because open regions are traversed without search. Its lasting contribution is architectural: modern routers use the same structure, inexpensive directed attempts first, exhaustive search only on failure.
Is it actually used today?
The evidence separates the literal Soukup algorithm from its two-mode structure; the two have had different fates.
- Pattern routing uses the same structure: modern global and detailed routers attempt L-, Z-, and U-shaped connections directly and escalate to maze search only on failure.
- Its deployment era was real: printed-circuit-board and early gate-array routers of the 1980s shipped Soukup-style hybrids when Lee's runtime was unaffordable.
- Interactive: it runs in this site's maze lab; the congested presets show the wirelength cost of committing sprint moves without cost comparison.