"""
PCB Drilling Routing Algorithms
================================
Extracted from pcb_drilling_astar.html and ported to Python.
Three tour-construction strategies for ordering holes on a PCB:
1. A* — greedy with a 1-step lookahead heuristic (cost-to-go estimated
by a nearest-neighbor MST surrogate).
2. Nearest Neighbor — pick the closest undrilled hole each step.
3. Optimal TSP — exhaustive permutation search for the remaining tour
(only enabled when |remaining| <= max_optimal_n, default 10).
The original HTML also exposed `findPathAStar` between two points, but it
collapsed to straight-line interpolation (no obstacles in the demo), so it is
kept here only as a utility for visualization/animation. The real routing
logic is the *order* in which holes are visited.
Coordinates are 2-D Euclidean.
"""
from __future__ import annotations
import math
from dataclasses import dataclass, field
from itertools import permutations
from typing import Iterable, Sequence
# ---------------------------------------------------------------------------
# Geometry primitives
# ---------------------------------------------------------------------------
@dataclass(frozen=True)
class Point:
x: float
y: float
def distance(self, other: "Point") -> float:
return math.hypot(self.x - other.x, self.y - other.y)
@dataclass
class Hole:
x: float
y: float
diameter: float = 1.0
type: str = "via"
drilled: bool = False
def point(self) -> Point:
return Point(self.x, self.y)
# ---------------------------------------------------------------------------
# Heuristic: MST-style nearest-neighbor lower bound for the remaining tour
# ---------------------------------------------------------------------------
def estimate_remaining_distance(start: Point, remaining: Sequence[Hole]) -> float:
"""
Approximate the cost of visiting every hole in `remaining` starting from
`start`, using a greedy nearest-neighbor walk. This is the heuristic h(n)
used by the A*-style selector below.
Not admissible in the strict A* sense (NN can overestimate), but cheap and
informative for tour ordering on PCB drilling workloads.
"""
if not remaining:
return 0.0
unvisited = list(remaining)
current = start
total = 0.0
while unvisited:
nearest_idx = min(
range(len(unvisited)),
key=lambda i: current.distance(unvisited[i].point()),
)
nearest = unvisited.pop(nearest_idx)
total += current.distance(nearest.point())
current = nearest.point()
return total
# ---------------------------------------------------------------------------
# Strategy 1: A*-style next-hole selection
# ---------------------------------------------------------------------------
@dataclass
class AStarStats:
nodes_explored: int = 0
def find_next_hole_astar(
current: Point,
undrilled: Sequence[Hole],
stats: AStarStats | None = None,
) -> Hole | None:
"""
Pick the next hole to drill by minimizing f(n) = g(n) + h(n), where:
g(n) = distance from `current` to candidate hole n
h(n) = estimate_remaining_distance(n, all other undrilled)
This is the per-step decision used as `astar` mode in the original demo.
"""
if not undrilled:
return None
best_hole: Hole | None = None
best_cost = math.inf
for candidate in undrilled:
g = current.distance(candidate.point())
others = [h for h in undrilled if h is not candidate]
h = estimate_remaining_distance(candidate.point(), others)
f = g + h
if stats is not None:
stats.nodes_explored += 1
if f < best_cost:
best_cost = f
best_hole = candidate
return best_hole
# ---------------------------------------------------------------------------
# Strategy 2: Nearest Neighbor
# ---------------------------------------------------------------------------
def find_nearest_hole(current: Point, undrilled: Sequence[Hole]) -> Hole | None:
"""Classic greedy nearest neighbor — pick the closest undrilled hole."""
if not undrilled:
return None
return min(undrilled, key=lambda h: current.distance(h.point()))
# ---------------------------------------------------------------------------
# Strategy 3: Optimal TSP (only viable for small remaining sets)
# ---------------------------------------------------------------------------
def find_optimal_next(
current: Point,
undrilled: Sequence[Hole],
max_n: int = 10,
) -> Hole | None:
"""
For small `undrilled` sets, enumerate all visit orderings and return the
first hole of the cheapest complete tour. Falls back to nearest neighbor
when |undrilled| > max_n (factorial blow-up).
The original HTML used max_n=10 with a brute-force fallback inside
`findOptimalNext`; we keep the same behavior here, but the inner search
is now a true TSP rather than the nearest-neighbor surrogate used in JS.
"""
if not undrilled:
return None
if len(undrilled) > max_n:
return find_nearest_hole(current, undrilled)
best_first: Hole | None = None
best_total = math.inf
for perm in permutations(undrilled):
total = 0.0
prev = current
for hole in perm:
total += prev.distance(hole.point())
if total >= best_total:
break # prune
prev = hole.point()
if total < best_total:
best_total = total
best_first = perm[0]
return best_first
# ---------------------------------------------------------------------------
# Tour driver: run any of the strategies end-to-end
# ---------------------------------------------------------------------------
@dataclass
class TourResult:
order: list[Hole] = field(default_factory=list)
total_distance: float = 0.0
nodes_explored: int = 0
def build_tour(
holes: Iterable[Hole],
start: Point = Point(50.0, 50.0),
strategy: str = "astar",
max_optimal_n: int = 10,
) -> TourResult:
"""
Drive a complete drilling tour using one of the three strategies.
Parameters
----------
holes : iterable of Hole
All holes to drill (will be marked .drilled=True in-place).
start : Point
Drill head starting position (default matches the HTML's (50, 50)).
strategy : {"astar", "nearest", "optimal"}
max_optimal_n : int
TSP brute-force ceiling for the "optimal" strategy.
Returns
-------
TourResult with visit order, accumulated travel distance, and (for A*)
the number of candidate evaluations performed.
"""
pool = [h for h in holes if not h.drilled]
result = TourResult()
current = start
stats = AStarStats()
while pool:
if strategy == "astar":
nxt = find_next_hole_astar(current, pool, stats)
elif strategy == "nearest":
nxt = find_nearest_hole(current, pool)
elif strategy == "optimal":
nxt = find_optimal_next(current, pool, max_n=max_optimal_n)
else:
raise ValueError(f"Unknown strategy: {strategy!r}")
if nxt is None:
break
result.total_distance += current.distance(nxt.point())
nxt.drilled = True
result.order.append(nxt)
current = nxt.point()
pool.remove(nxt)
result.nodes_explored = stats.nodes_explored
return result
# ---------------------------------------------------------------------------
# Demo — only runs when executed directly
# ---------------------------------------------------------------------------
if __name__ == "__main__":
import random
random.seed(0)
sample = [
Hole(x=50 + random.random() * 700,
y=50 + random.random() * 500)
for _ in range(50)
]
for strat in ("nearest", "astar", "optimal"):
# Re-clone so strategies don't see each other's drilled flags
holes = [Hole(h.x, h.y, h.diameter, h.type) for h in sample]
res = build_tour(holes, strategy=strat)
print(
f"{strat:>8s}: distance = {res.total_distance:8.1f} "
f"nodes_explored = {res.nodes_explored}"
)