Explore / Methods & Algorithms / Routing / Hightower's Algorithm

Hightower's Algorithm

Routing foundational detailed routing 1969 Hightower can miss existing paths very fast and lean

The idea

Mikami-Tabuchi's completeness comes from brute breadth: perpendiculars from every point of every line. Hightower kept the bidirectional line-probing skeleton but probes only from escape points: for each blocked line, choose the point just past the edge of the obstacle that blocked it, and shoot the single perpendicular there that escapes the blockage. One or two new lines per iteration instead of hundreds; the data structure stays tiny and the router runs blisteringly fast on the sparse boards of its era.

The recipe

Step 1 (escape lines). Through the source and through the target, draw the maximal free horizontal and vertical lines, as in Mikami-Tabuchi, and test for a crossing between the two families.

Step 2 (escape points, not every point). If they do not cross, pick a single escape point per line: a point just past the edge of the obstacle that blocked the line, chosen so a perpendicular line through it can clear that obstacle. Draw the perpendicular through that one point only.

Step 3 (iterate, without a guarantee). Repeat from the new lines. Memory stays tiny because only one point per line spawns a probe, but the heuristic choice can skip the very point a path needs: unlike Mikami-Tabuchi, the search can fail on a routable net.

Watch it work: escape points only

The frames follow the Mikami-Tabuchi walkthrough's progression on the same scenario: level-0 trial lines, probes, the first inter-family intersection, and the joined path. The difference is the probe rule: one chosen escape point per blocked line instead of every point.

Pros, cons, and the trade-off

Strengths

  • Very fast: constant new segments per iteration; the leanest of all the classics.
  • Minimal memory: even fewer segments than Mikami-Tabuchi.
  • Effective on sparse boards: on the low-obstacle problems of its era, it almost always connected.
  • Architecturally influential: prune hard, keep an exact fallback: the layered structure every later router adopted.

Weaknesses

  • Incomplete: staggered-baffle configurations exist where the only escape passes through points the heuristic never probes; it reports failure on routable pins.
  • Needs a safety net: practical deployments backed it with a maze router for the misses.
  • Fragile heuristic: escape-point choice determines the outcome, and no choice rule is safe.
  • Same cost-model limits as all line search: no weighted edges, no via pricing.

The trade-off

Hightower stands one sacrifice beyond Soukup in the taxonomy: Soukup gave up shortest paths, Hightower gives up finding paths at all. In exchange it was the fastest thing of its decade, and its real bequest is the pattern of a fast unsafe method guarded by a slow safe one.

Is it actually used today?

The evidence for Hightower's algorithm is historical and pedagogical rather than from shipping tools.

  • Its niche closed: incompleteness is disqualifying for silicon sign-off, and the boards sparse enough for it to shine stopped being the hard problem.
  • Its pattern shipped everywhere: try-cheap-first with an exact fallback is the standing architecture of modern routing (pattern route, then windowed search, then full maze).
  • Its role now: the cautionary example in every routing lecture, paired with Mikami-Tabuchi to show exactly what completeness costs and buys.

References and further reading