app
AI Flow: Routing
Public Made by Adomby adom
The routing stage of AI Flow: routes a placed KiCad board connection by connection and reports what it made, what it could not and why. A guide, never a gate.
main
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147
//! The driver: routes the whole board in the designer's hierarchy (4.2), level by level, commits exact
//! copper, resolves conflicts by rip-up with memory, and post-processes each route.
use crate::board::*;
use crate::classify::*;
use crate::conn;
use crate::geom::*;
use crate::index::*;
use crate::rules::*;
use crate::search::*;
use std::collections::{HashMap, HashSet};
use crate::clock::Instant;
#[path = "repair.rs"]
pub(crate) mod repair;
/// How far a track may run inside a rail pour before a via round it is worth trying first.
/// A run through a pour its pad sits in, past which it counts as crossing rather than leaving. His own
/// J1 exit on benchmark B runs about 2.4 mm on F.Cu to get past the turn in the pair below it.
pub(crate) const POUR_RUN: f64 = 3.0 * NM;
/// How far a coupled run keeps straight past its fan-in, off a pad pair.
const PAIR_RUN_IN: f64 = 0.3 * NM;
/// Fine-pitch lane lengths past the pad, mm, one per run.
const LANES: [f64; 4] = [0.4, 0.5, 0.55, 0.45];
#[derive(Clone, Debug, PartialEq)]
pub struct Seg {
pub a: P,
pub b: P,
pub layer: usize,
pub width: i64,
}
#[derive(Clone, Debug)]
pub struct Route {
pub id: u32,
pub task: Task,
pub segs: Vec<Seg>,
pub vias: Vec<P>,
pub(crate) handles: Vec<(usize, u32)>,
pub(crate) via_handles: Vec<u32>,
}
pub struct Router<'a> {
pub board: &'a Board,
pub rules: Rules,
pub world: World,
pub routes: HashMap<u32, Route>,
next_id: u32,
pub history: History,
/// (ripper, victim) pad pairs and how often: Freerouting's rip-up memory, so two nets cannot
/// keep taking the same spot from each other.
memory: HashMap<((usize, usize), (usize, usize)), u32>,
pub(crate) rip_count: HashMap<(usize, usize), u32>,
pub log: Vec<String>,
pub rips: u32,
pub searches: u32,
pub nodes: u64,
pub notes: Vec<String>,
pub(crate) start: Instant,
trace: bool,
/// Each net's level and routable pads, for reading what is really open.
pub(crate) net_info: HashMap<NetId, (Level, Vec<usize>)>,
/// Why a task is still open, for handing it to the designer (Part 3 step 6).
why: HashMap<(usize, usize), String>,
pub splices: u32,
stalled: bool,
lane_len: f64,
/// This run's repair style. Loose: a rail victim takes any neck-width way back and a net may
/// come apart for a round, to be closed by the next. Tight: rails keep their shape and no move
/// may split a net. Neither wins everywhere (piprobe_v13: loose 96/96, tight 95/96), so runs
/// alternate and the best board is kept.
loose: bool,
/// Tasks with a pad no track can leave under the rules, for the designer's note.
boxed_pads: HashMap<(usize, usize), usize>,
/// Where a track starts on a pad whose centre sits too close to a neighbour for the rule.
pad_entry: HashMap<usize, P>,
/// Each fine-pitch pin's held lane: pad to (layer, shape, handle while it is on the board).
lanes: HashMap<usize, (usize, Shape, Option<u32>)>,
pub(crate) bus: crate::bus::BusPlan,
/// This go is running without the bus plan.
pub(crate) plain_go: bool,
/// Nets being moved off a pour they cut: a long run through it is no longer taken at all.
pub(crate) pour_strict: HashSet<NetId>,
/// The last-mile repair: the run is nearly out of time with a few joins open, so what is left
/// goes to deeper searches for those instead of a fresh run that could not finish.
pub(crate) deep: bool,
/// Rail taps that found no way, with the state they failed in (post.rs `rail_stamp`).
pub(crate) rail_walled: HashMap<(usize, usize), u64>,
/// How many times each rail tap's ladder has been run in this run (post.rs `try_rail`).
pub(crate) rail_tries: HashMap<(usize, usize), u32>,
/// Rails whose source and heavy loads share one connected pour: there the pour is the feed and
/// a track is only a tie-in to it. A rail with a few local patches is not one of these.
pour_fed: HashSet<NetId>,
/// Per rail pad: the current into its branch (current.rs branch_amps). Rails fed by their pour
/// have none: there each pad draws its own from the pour.
pub(crate) tap_amps: HashMap<usize, f64>,
/// The power stage's plan for the rated rails that are not fed by their pour (power.rs).
pub(crate) power: crate::power::PowerPlan,
/// The only nets this run may route, when it was asked for a few (a fixture). Repair finds its
/// work from every net left apart on the board, which without this is the whole board.
pub only: Option<HashSet<NetId>>,
/// Planned rail branches already laid once in this pass. Signals outrank power (4.2), so a signal
/// may move one, but it gives way by changing layer, never by thinning: laid again, it is tried
/// only at its planned width, with more layer changes allowed (the designer, 2026-11-10: "making that
/// rail via more often to protect signals"). If no full-width way exists the move is refused.
pub(crate) rail_laid: HashSet<(usize, usize)>,
/// Nets with a pour over much of an outer layer, and that layer: the board's plane in all but
/// name on a two-layer board. Each pad of the net on another layer gets its own via to it,
/// staked right after the pairs like an inner plane's (4.2), because after routing there is no
/// room left for them: on the wiki's two-layer boards a refill left 6 to 16 ground pads and
/// pour pieces cut off, where their designers have 100 to 300 vias (2026-11-10).
pub(crate) pour_plane: HashMap<NetId, usize>,
/// The pads those vias are for. One that finds no site is not a failed join: its pour may hold.
pub(crate) pour_pads: HashSet<usize>,
/// A connection being routed again at the width its current turned out to need.
pub(crate) rail_override: HashMap<(usize, usize), i64>,
/// Nets with a single-layer pad inside another net's big pour. They leave it his way, a short stub
/// and straight to another layer, rather than running through and splitting it on refill.
pub(crate) pour_exit: HashSet<NetId>,
/// The pads that make a net one of those.
pub(crate) pour_exit_pads: HashSet<usize>,
/// This attempt has been let off `pour_exit`: no exit was found, and an open join is worse.
pub(crate) pour_relax: bool,
/// The run through a pour allowed just now: `POUR_RUN`, or less when moving a net that cut one.
pub(crate) pour_limit: f64,
/// Planned exits: pads whose own route starts from a via laid with the group, and which tasks
/// were laid that way.
pub(crate) exit_via: HashMap<usize, P>,
pub(crate) exit_tasks: HashSet<(usize, usize)>,
}
#[derive(Default, Clone, Debug)]
pub struct Outcome {
pub failed: Vec<Task>,
pub seconds: f64,
}
fn poly_of(zone: &Zone, layer: usize) -> Vec<Vec<V>> {
let fills: Vec<Vec<V>> = zone.fills.iter().filter(|(l, _)| *l == layer).map(|(_, p)| p.clone()).collect();
if fills.is_empty() { vec![zone.outline.clone()] } else { fills }
}
/// A supply net whose pads all lie within this is local to one part and is routed with the first group.
const LOCAL_NET_MM: f64 = 6.0;
/// The most times one rail tap's search ladder is run in a run (three more in the last-mile repair).
pub(crate) const RAIL_TRIES: u32 = 6;
/// A supply pin's stub to its capacitor is laid with the first group when the two are this near.
const PIN_CAP_MM: f64 = 3.0;
pub fn build_world(board: &Board, rules: &Rules) -> World {
let bb = if board.edges.is_empty() {
let mut b = (f64::MAX, f64::MAX, f64::MIN, f64::MIN);
for p in &board.pads {
let s = p.shape.bbox();
b = (b.0.min(s.0), b.1.min(s.1), b.2.max(s.2), b.3.max(s.3));
}
b
} else {
board.bbox
};
let cell = 0.5 * NM;
let mut layers: Vec<Grid> = board.layers.iter().map(|_| Grid::new(bb, cell)).collect();
let mut holes = Grid::new(bb, cell);
let mut edge = Grid::new(bb, cell);
for (a, b) in &board.edges {
edge.add(Shape::Capsule { a: *a, b: *b, r: 0.0 }, NO_NET, Owner::Edge);
}
let n = board.layers.len();
for (i, p) in board.pads.iter().enumerate() {
if p.npth {
let r = p.drill.unwrap_or(p.size.0) / 2.0;
let s = Shape::Circle { c: p.center.into(), r };
for g in layers.iter_mut() {
g.add(s.clone(), NO_NET, Owner::Keepout);
}
holes.add(s, NO_NET, Owner::Pad(i as u32));
continue;
}
for &l in &p.layers {
layers[l].add(p.shape.clone(), p.net, Owner::Pad(i as u32));
}
if let Some(d) = p.drill {
holes.add(Shape::Circle { c: p.center.into(), r: d / 2.0 }, p.net, Owner::Pad(i as u32));
}
}
for t in &board.tracks {
layers[t.layer].add(Shape::Capsule { a: t.a.into(), b: t.b.into(), r: t.width as f64 / 2.0 }, t.net, Owner::Fixed);
}
for v in &board.vias {
for g in layers.iter_mut() {
g.add(Shape::Circle { c: v.at.into(), r: v.size as f64 / 2.0 }, v.net, Owner::Fixed);
}
holes.add(Shape::Circle { c: v.at.into(), r: v.drill as f64 / 2.0 }, v.net, Owner::Fixed);
}
let mut zones = Vec::new();
let pour_open: Vec<Vec<NetId>> = board
.zones
.iter()
.map(|z| {
let mut nets: Vec<NetId> = board.pads.iter().filter(|p| p.net != z.net && p.net != NO_NET && p.layers.iter().any(|l| z.layers.contains(l)) && in_poly(p.center.into(), &z.outline)).map(|p| p.net).collect();
nets.sort_unstable();
nets.dedup();
nets
})
.collect();
let plane_set = board.plane_layers();
for (zi, z) in board.zones.iter().enumerate() {
if z.keepout_tracks {
for &l in &z.layers {
layers[l].add(Shape::Poly { pts: z.outline.clone(), r: 0.0 }, NO_NET, Owner::Keepout);
}
}
if z.keepout_vias {
holes.add(Shape::Poly { pts: z.outline.clone(), r: 0.0 }, NO_NET, Owner::Keepout);
}
if z.keepout_tracks || z.keepout_vias || z.net == NO_NET {
continue;
}
for &l in &z.layers {
for poly in poly_of(z, l) {
zones.push((z.net, l, poly.clone()));
// A pour on a signal layer of a rail is deliberate copper: other nets stay out.
// A GND fill refills around tracks, so it blocks nothing.
let is_signal_layer = board.layers[l].signal;
// An inner plane is not such a pour, whatever its net: vias of every other net pass
// through it and KiCad cuts their antipads. KiCad types every layer "signal" unless
// told otherwise, so the layer type cannot tell the two apart; the plane test does.
// On a 4-layer switch board a +3.3V plane on In2.Cu refused all 49 GND vias.
if is_signal_layer && !plane_set.contains(&l) && !looks_ground(board.net_name(z.net)) && poly.len() >= 3 {
layers[l].add(Shape::Poly { pts: poly, r: 0.0 }, z.net, Owner::Zone(zi as u32));
}
}
}
}
let planes = board.plane_layers();
let mut route_layers: Vec<usize> = (0..n).filter(|&l| board.layers[l].signal && !planes.contains(&l)).collect();
if route_layers.is_empty() {
route_layers = vec![0, n - 1];
}
let mut escapes = Vec::new();
for (fi, f) in board.footprints.iter().enumerate() {
if crate::classify::is_fine_pitch(board, rules, fi) {
let mut b = (f64::MAX, f64::MAX, f64::MIN, f64::MIN);
for &p in &f.pads {
let s = board.pads[p].shape.bbox();
b = (b.0.min(s.0), b.1.min(s.1), b.2.max(s.2), b.3.max(s.3));
}
let m = rules.escape_margin;
escapes.push((b.0 - m, b.1 - m, b.2 + m, b.3 + m));
}
}
let rail_nets = rules.rails.keys().filter_map(|name| board.net_ids.iter().find(|(k, _)| k.eq_ignore_ascii_case(name)).map(|(_, v)| *v)).collect();
// Pads that reach their pour through thermal spokes (the same test as pour.rs makes).
let mut relief: Vec<Grid> = board.layers.iter().map(|_| Grid::new(bb, cell)).collect();
let mut relief_gap = vec![0.0f64; board.pads.len()];
let mut relief_reach = 0.0f64;
if std::env::var_os("ADOM_ROUTE_NO_RELIEF").is_none() {
for z in board.zones.iter().filter(|z| z.net != NO_NET && !z.keepout_tracks && z.outline.len() >= 3) {
let Some((gap, _)) = z.thermal else { continue };
for (i, p) in board.pads.iter().enumerate().filter(|(_, p)| p.net == z.net && !p.npth) {
let thermal = match p.zone_connect {
Some(2) | Some(0) => false,
Some(3) => p.drill.is_some(),
_ => !z.thermal_tht_only || p.drill.is_some(),
};
if !thermal || !in_poly(p.center.into(), &z.outline) {
continue;
}
for &l in p.layers.iter().filter(|l| z.layers.contains(l)) {
if relief_gap[i] == 0.0 {
relief[l].add(p.shape.clone(), p.net, Owner::Pad(i as u32));
}
}
relief_gap[i] = relief_gap[i].max(gap);
relief_reach = relief_reach.max(gap);
}
}
}
let mut partner = HashMap::new();
for pr in &rules.pairs {
let id = |name: &str| board.net_ids.iter().find(|(k, _)| k.eq_ignore_ascii_case(name)).map(|(_, v)| *v);
if let (Some(a), Some(b)) = (id(&pr.p), id(&pr.n)) {
partner.insert(a, b);
partner.insert(b, a);
}
}
World { relief, relief_gap, relief_reach, partner, pair_segs: Default::default(), rail_nets, follow: Default::default(), pour_avoid: HashMap::new(), pour_open, layers, holes, edge, route_layers, escapes, zones, guide: Default::default(), mask: if std::env::var_os("ADOM_ROUTE_NO_MASK_GUARD").is_some() { crate::mask::MaskMap::new(board, rules) } else { crate::mask::MaskMap::new(board, rules).guarded() }, pad_clearance: board.pads.iter().map(|p| p.local_clearance).collect(), max_local: board.pads.iter().map(|p| p.local_clearance).fold(0.0, f64::max) }
}
fn turn_of(a: P, b: P, c: P) -> Option<i32> {
let d1 = dir_of(a, b)?;
let d2 = dir_of(b, c)?;
Some(((d2 as i32 - d1 as i32).rem_euclid(8)).min((d1 as i32 - d2 as i32).rem_euclid(8)))
}
pub fn dir_of(a: P, b: P) -> Option<u8> {
let (dx, dy) = (b.0 - a.0, b.1 - a.1);
if dx == 0 && dy == 0 {
return None;
}
let tol = 2;
if dy.abs() <= tol && dx.abs() > tol {
return Some(if dx > 0 { 0 } else { 4 });
}
if dx.abs() <= tol && dy.abs() > tol {
return Some(if dy > 0 { 2 } else { 6 });
}
if (dx.abs() - dy.abs()).abs() <= tol {
return Some(match (dx > 0, dy > 0) {
(true, true) => 1,
(false, true) => 3,
(false, false) => 5,
(true, false) => 7,
});
}
None
}
/// Merge straight runs on one layer.
pub fn simplify(pts: &mut Vec<(P, usize)>) {
pts.dedup();
let mut i = 1;
while i + 1 < pts.len() {
let (a, b, c) = (pts[i - 1], pts[i], pts[i + 1]);
if a.1 == b.1 && b.1 == c.1 && dir_of(a.0, b.0) == dir_of(b.0, c.0) {
pts.remove(i);
if i > 1 {
i -= 1;
}
} else {
i += 1;
}
}
}
impl<'a> Router<'a> {
pub fn new(board: &'a Board, mut rules: Rules) -> Router<'a> {
// A board set up with a wider minimum than the standing neck is judged by its setup (2.2):
// Benchmark C's project says 0.2 mm, and 199 of KiCad's findings were 0.15 mm necks.
rules.neck = rules.neck.max(rules.min.track);
rules.track = rules.track.max(rules.neck);
let world = build_world(board, &rules);
let history = History::new(board.bbox);
let net_info = classify(board, &rules).into_iter().map(|i| (i.net, (i.level, i.pads))).collect();
Router { board, rules, world, routes: HashMap::new(), bus: Default::default(), plain_go: false, deep: false, rail_walled: HashMap::new(), rail_tries: HashMap::new(), pour_strict: Default::default(), pour_fed: Default::default(), tap_amps: HashMap::new(), power: Default::default(), only: None, rail_laid: HashSet::new(), pour_plane: HashMap::new(), pour_pads: HashSet::new(), rail_override: HashMap::new(), pour_exit: Default::default(), pour_exit_pads: Default::default(), pour_relax: false, pour_limit: POUR_RUN, exit_via: HashMap::new(), exit_tasks: HashSet::new(), next_id: 1, history, memory: HashMap::new(), rip_count: HashMap::new(), log: Vec::new(), rips: 0, searches: 0, nodes: 0, notes: Vec::new(), start: Instant::now(), trace: std::env::var_os("ADOM_ROUTE_TRACE").is_some(), net_info, why: HashMap::new(), splices: 0, stalled: false, loose: true, boxed_pads: HashMap::new(), lane_len: LANES[0] * NM, pad_entry: HashMap::new(), lanes: HashMap::new() }
}
pub(crate) fn pad_terminal(&self, i: usize) -> Terminal {
let p = &self.board.pads[i];
// A pad with a planned exit is reached at its via, from the layers its stub isn't on.
if let Some(&via) = self.exit_via.get(&i) {
return Terminal::Point { p: via, layers: self.world.route_layers.iter().copied().filter(|l| !p.layers.contains(l)).collect() };
}
Terminal::Point { p: self.pad_entry.get(&i).copied().unwrap_or(p.center), layers: p.layers.iter().copied().filter(|l| self.world.route_layers.contains(l)).collect() }
}
/// A rail's widths: the spec's wideNets (main run, branches, stubs), else a net class that sets
/// more than 4.2's floor, else the floor. A stub off a rail runs at the data width unless the spec
/// names one (4.2 gives branches no number of their own: check them against their current). A
/// branch without a figure stays at the main width, its current not being known.
pub(crate) fn widths_for(&self, t: &Task) -> (i64, i64) {
if let Some(&w) = self.rail_override.get(&(t.a, t.b)) {
return (w, self.rules.neck.min(w));
}
let r = &self.rules;
let name = self.board.net_name(t.net);
let class = r.track_for(t.net);
match t.level {
// An approved current: the main run carries the rail, a tap only what its pad draws, and
// a stub or tap is never asked to be narrower than the data band's neck (4.2).
Level::Power if r.rail(name).is_some() => {
let rail = r.rail(name).unwrap();
// A planned rail's tap has its width from the plan; into the pad it is no wider than the pad.
if let (true, Some(pp)) = (t.a == t.b, self.power.pads.get(&t.a)) {
let pad = &self.board.pads[t.a];
let at_pad = pad.size.0.min(pad.size.1) as i64;
return (pp.width, pp.width.min(at_pad).max(r.neck));
}
let own = crate::current::pad_load(self.board, r, t.a).unwrap_or(0.0);
// A tap carries its pad's whole branch, not only what the pad draws.
let through = self.tap_amps.get(&t.a).copied().unwrap_or(own).max(own);
let plain = if class > mm(0.3) { r.track } else { class };
let main = if self.pour_fed.contains(&t.net) { r.rail_width(own, false) } else { r.rail_width(rail.amps, true) }.max(plain);
// The drop limit on top of the chart (reference rule 2026-11-09), from the distance the copper
// has to cover: a tap from its pad to the nearest source at its branch's current, the
// trunk end to end at the rail's. The exact drop is rated from the laid copper after.
let oct = |p: P, q: P| -> f64 { let (dx, dy) = ((p.0 - q.0).abs() as f64, (p.1 - q.1).abs() as f64); dx.max(dy) + (SQRT2 - 1.0) * dx.min(dy) };
let drop_w = |amps: f64, len: f64| -> i64 { if self.pour_fed.contains(&t.net) { 0 } else { rail.volts.map(|v| r.drop_width(amps, len, v)).unwrap_or(0) } };
let to_source = self.board.pads.iter().filter(|p| p.net == t.net && rail.sources.iter().any(|s| *s == self.board.footprints[p.fp].reference)).map(|p| oct(p.center, self.board.pads[t.a].center)).fold(f64::INFINITY, f64::min);
let tap_drop = if to_source.is_finite() { drop_w(through, to_source) } else { 0 };
let main = if t.a != t.b { main.max(drop_w(rail.amps, oct(self.board.pads[t.a].center, self.board.pads[t.b].center))) } else { main };
// At the pad the track is no wider than the pad, unless the pad's own draw needs it.
let pad = &self.board.pads[t.a];
let at_pad = (pad.size.0.min(pad.size.1) as i64).max(r.rail_width(own, false));
let stub = r.rail_width(through, false).min(at_pad).max(r.neck);
match (t.zone == Some(RAIL_TAP), t.main) {
// One pad tapping toward its net's fill carries its own branch, like any tap:
// at the rail's full width, benchmark C's +5V_OUT pull-up R46 (0.5 mA) got 56 mm
// of 0.70 mm track (2026-11-09). Only the trunk between two clusters is the rail.
(true, true) if t.a == t.b && !self.pour_fed.contains(&t.net) => (r.rail_width(through, false).max(plain).max(tap_drop), stub),
(true, true) => (main, stub),
(true, false) => (r.rail_width(through, false).max(plain).max(tap_drop), stub),
_ => (stub.max(plain), r.neck.max(stub)),
}
}
Level::Power => {
// Net names differ in case between a spec and a board (+3v3, +3V3).
let w = r.wide.get(name).or_else(|| r.wide.iter().find(|(k, _)| k.eq_ignore_ascii_case(name)).map(|(_, v)| v));
// A class wider than 4.2's data band describes the copper that carries the current.
// Where the net has its own fill, that's the fill (benchmark B's +PS rails: classes of
// 4 to 10 mm, no track over 1 mm), and a track is only a tie-in to it.
let fed_by_fill = class > mm(0.3) && self.world.zones.iter().any(|(n, _, _)| *n == t.net);
let carried = if fed_by_fill { r.power_floor } else { class.max(r.power_floor) };
let main = w.and_then(|v| v.first().copied()).unwrap_or(carried);
let plain = if class > mm(0.3) { r.track } else { class };
let stub = w.filter(|v| v.len() >= 2).and_then(|v| v.last().copied()).unwrap_or(plain);
let stub = r.neck.max(stub);
let branch = w.filter(|v| v.len() >= 3).map(|v| v[1]).unwrap_or(main);
match (t.zone == Some(RAIL_TAP), t.main) {
(true, true) => (main, stub),
(true, false) => (branch, stub),
_ => (stub, r.neck),
}
}
Level::Kelvin => (mm(0.25), r.neck),
Level::Crystal => (r.neck, r.neck),
// A class wider than 4.2's data band holds a current width: that's not this net's run.
_ => (if class > mm(0.3) { r.track } else { class.max(r.neck) }, r.neck),
}
}
/// Every search attempt for one task, cheapest in vias first (RAPTOR-style rounds).
pub(crate) fn attempts(&self, t: &Task) -> Vec<Profile> {
let (w, n) = self.widths_for(t);
let c = self.rules.clearance_for(t.net, t.net);
let tgt = match t.level {
Level::Crystal | Level::Kelvin => c,
_ => (w * 2).max(c),
};
let mut out = Vec::new();
// A bus line stays on its bus's layer while it can: his benchmark B bus has no via in it.
let on_one_layer = !matches!(t.level, Level::Other) || self.bus.bands.iter().any(|(_, row)| row.contains(&(t.a, t.b)));
let mk = |width: i64, neck: i64, target_gap: i64, max_vias: u32, margin: f64| Profile { width, neck, clearance: c, target_gap, max_vias, margin, layer_bias: None };
if t.a == t.b && self.rail_laid.contains(&(t.a, t.b)) && self.power.pads.get(&t.a).map(|p| !p.anywhere).unwrap_or(false) {
return vec![mk(w, n, tgt, 2, 1.5 * NM), mk(w, n, tgt, 2, 5.0 * NM), mk(w, n, c, 4, 8.0 * NM), mk(w, n, c, 6, 40.0 * NM)];
}
if on_one_layer {
out.push(mk(w, n, tgt, 0, 1.5 * NM));
out.push(mk(w, n, tgt, 0, 5.0 * NM));
}
out.push(mk(w, n, tgt, 2, 1.5 * NM));
out.push(mk(w, n, tgt, 2, 5.0 * NM));
// Dense: drop to 2W spacing, then the neck everywhere (never below minimum clearance).
out.push(mk(w, n, c.max(w), 2, 5.0 * NM));
// A rail with an approved current keeps its width as far round as it takes before it is
// ever drawn at its neck: the neck is for the last stretch into a pad. Without these, a run
// that needed a detour of over 5 mm went down at the neck for its whole length (benchmark C's
// +5V to U10: 30 mm at 0.40 mm for 1.24 A, 2026-11-09).
if t.level == Level::Power && self.rules.rail(self.board.net_name(t.net)).is_some() && w > n {
out.push(mk(w, n, c, 2, 8.0 * NM));
out.push(mk(w, n, c, 4, 40.0 * NM));
// Then narrower by thirds, never under what the current alone needs (the chart): a run
// that can't be as wide as its drop limit asks is still as wide as fits, the stretches
// with room are widened after, and what is left over the limit is reported.
let rail = self.rules.rail(self.board.net_name(t.net)).unwrap();
let amps = if t.a != t.b { rail.amps } else { self.power.pads.get(&t.a).map(|p| p.amps).or_else(|| self.tap_amps.get(&t.a).copied()).or_else(|| crate::current::pad_load(self.board, &self.rules, t.a)).unwrap_or(0.0) };
let chart = self.rules.rail_width(amps, false).max(n);
let mut x = w;
while x > chart {
x = ((x * 2 / 3) / 10_000 * 10_000).max(chart);
out.push(mk(x, n, c, 2, 5.0 * NM));
out.push(mk(x, n, c, 4, 40.0 * NM));
}
}
out.push(mk(n, n, c, 2, 8.0 * NM));
out.push(mk(n, n, c, 4, 40.0 * NM));
out
}
pub(crate) fn seg_clear(&self, a: P, b: P, layer: usize, width: i64, net: NetId, also: NetId) -> bool {
let half = width as f64 / 2.0;
let (va, vb): (V, V) = (a.into(), b.into());
let reach = half + self.rules.max_clearance() as f64 + self.world.max_local + 1.0;
let bb = (va.0.min(vb.0) - reach, va.1.min(vb.1) - reach, va.0.max(vb.0) + reach, va.1.max(vb.1) + reach);
let mut ok = true;
self.world.layers[layer].visit(bb, |o| {
if (o.net == net && net != NO_NET) || (o.net == also && also != NO_NET) || self.world.crosses_pour(o, net) {
return true;
}
let local = if let Owner::Pad(i) = o.owner { self.world.pad_clearance[i as usize] } else { 0.0 };
let pad = if let Owner::Pad(i) = o.owner { Some(i) } else { None };
let need = half + (self.rules.clearance_at(net, o.net, pad) as f64).max(local) - DRC_TOL;
if o.dist_within(va, vb, need * 1.01) < need {
ok = false;
return false;
}
true
});
if !ok {
return false;
}
if self.world.mask.seg_hit_also(net, also, layer, va, vb, half).is_some() || !self.world.holes_clear_also(&self.rules, va, vb, half, net, also) {
return false;
}
let e = half + self.rules.edge as f64;
let bb = (va.0.min(vb.0) - e, va.1.min(vb.1) - e, va.0.max(vb.0) + e, va.1.max(vb.1) + e);
self.world.edge.visit(bb, |o| {
if o.shape.dist_seg(va, vb) < e {
ok = false;
return false;
}
true
});
ok
}
/// Tidy a path: straighten with fewer bends where copper allows ("as straight as possible,
/// with the fewest segments"), then cut every remaining 90-degree corner into two 135s.
pub(crate) fn finish_path(&self, path: &Path, net: NetId, also: NetId, neck: i64) -> Vec<(P, usize)> {
self.finish_path_on(path, net, also, &|_| neck)
}
/// `width_on` gives the width each layer's copper has to clear at: a rail's bus is wider than its
/// stubs, so a shortcut legal for one may not be for the other.
pub(crate) fn finish_path_on(&self, path: &Path, net: NetId, also: NetId, width_on: &dyn Fn(usize) -> i64) -> Vec<(P, usize)> {
let mut pts = path.pts.clone();
simplify(&mut pts);
// Pull tight: any stretch of a few segments on one layer that one bend can replace, longest
// first, so a route that wandered round something now gone straightens in one step.
for _ in 0..4 {
let mut changed = false;
let mut i = 0;
while i + 3 < pts.len() {
let mut done = false;
let reach = (pts.len() - 1 - i).min(8);
for span in (3..=reach).rev() {
let j = i + span;
if !pts[i..=j].iter().all(|x| x.1 == pts[i].1) {
continue;
}
let l = pts[i].1;
if let Some(q) = self.one_bend(pts[i].0, pts[j].0, l, net, also, width_on(l), if i > 0 { Some(pts[i - 1]) } else { None }, pts.get(j + 1).copied()) {
pts.splice(i + 1..j, q.into_iter().map(|x| (x, l)));
simplify(&mut pts);
changed = true;
done = true;
break;
}
}
if !done {
i += 1;
}
}
if !changed {
break;
}
}
collapse_jogs(&mut pts);
// Chamfer 90-degree corners: 135-degree angles are optimal, no 90-degree bends (4.2).
let mut i = 1;
while i + 1 < pts.len() {
let (a, b, c) = (pts[i - 1], pts[i], pts[i + 1]);
if a.1 == b.1 && b.1 == c.1 && turn_of(a.0, b.0, c.0) == Some(2) {
let la = (a.0 .0 - b.0 .0).abs().max((a.0 .1 - b.0 .1).abs());
let lc = (c.0 .0 - b.0 .0).abs().max((c.0 .1 - b.0 .1).abs());
let mut done = false;
for size in [0.5, 0.3, 0.2, 0.1, 0.05] {
let s = (size * NM) as i64;
let s = s.min(la).min(lc);
if s < 2_000 {
continue;
}
let s = s & !1;
let toward = |from: P, to: P| -> P {
let d = (to.0 - from.0, to.1 - from.1);
(from.0 + d.0.signum() * s, from.1 + d.1.signum() * s)
};
let (q1, q2) = (toward(b.0, a.0), toward(b.0, c.0));
if self.seg_clear(q1, q2, b.1, width_on(b.1), net, also) {
pts[i] = (q1, b.1);
pts.insert(i + 1, (q2, b.1));
i += 1;
done = true;
break;
}
}
let _ = done;
}
i += 1;
}
simplify(&mut pts);
pts
}
/// One bend between two points, if it is legal, shorter in bends, and doesn't make an acute
/// corner with what comes before or after.
#[allow(clippy::too_many_arguments)]
fn one_bend(&self, a: P, b: P, layer: usize, net: NetId, also: NetId, neck: i64, before: Option<(P, usize)>, after: Option<(P, usize)>) -> Option<Vec<P>> {
let (dx, dy) = (b.0 - a.0, b.1 - a.1);
let (adx, ady) = (dx.abs(), dy.abs());
let mut cands: Vec<Vec<P>> = Vec::new();
if dir_of(a, b).is_some() {
cands.push(Vec::new());
} else {
let d = adx.min(ady);
let (sx, sy) = (dx.signum(), dy.signum());
cands.push(vec![(a.0 + sx * d, a.1 + sy * d)]);
cands.push(vec![(b.0 - sx * d, b.1 - sy * d)]);
}
for c in cands {
let mut chain = vec![a];
chain.extend(c.iter().copied());
chain.push(b);
let clear = chain.windows(2).all(|w| self.seg_clear(w[0], w[1], layer, neck, net, also));
if !clear {
continue;
}
let mut ok = chain.windows(3).all(|w| turn_of(w[0], w[1], w[2]).map(|t| t <= 1).unwrap_or(false));
if let Some(p) = before {
if p.1 == layer {
ok &= turn_of(p.0, a, chain[1]).map(|t| t <= 1).unwrap_or(true);
}
}
if let Some(p) = after {
if p.1 == layer {
ok &= turn_of(chain[chain.len() - 2], b, p.0).map(|t| t <= 1).unwrap_or(true);
}
}
if ok {
return Some(c);
}
}
None
}
/// Commit a finished point list as copper, one width per straight run. A route that leaves a
/// fine-pitch part stays at the neck to the edge of that part's escape, then opens up if the run
/// is long enough to be worth a step (4.2: "leave the MCU at 0.15 mm and neck up for long runs").
/// Anywhere else a run takes its full width right up to the pad, unless copper beside it forbids
/// that for the whole run.
pub(crate) fn commit(&mut self, task: &Task, pts: &[(P, usize)], width: i64, neck: i64, also: NetId) -> u32 {
if task.zone == Some(RAIL_TAP) {
return self.commit_rail(task, pts, width, neck);
}
let id = self.fresh_id();
let fine = |pad: usize| crate::classify::is_fine_pitch(self.board, &self.rules, self.board.pads[pad].fp);
let leaves_fine = fine(task.a) || fine(task.b);
let mut segs = Vec::new();
let mut vias = Vec::new();
for w in pts.windows(2) {
let ((a, la), (b, lb)) = (w[0], w[1]);
if la != lb {
if a == b {
vias.push(a);
}
continue;
}
if a == b {
continue;
}
for (p, q, inside) in self.split_at_escape(a, b, leaves_fine && width > neck) {
let w = if inside || width <= neck || !self.seg_clear(p, q, la, width, task.net, also) { neck.min(width) } else { width };
segs.push(Seg { a: p, b: q, layer: la, width: w });
}
}
crate::post::smooth_widths(&mut segs, width, neck);
crate::post::merge_runs(&mut segs);
self.place(id, task.clone(), segs, vias);
id
}
pub(crate) fn fresh_id(&mut self) -> u32 {
self.next_id += 1;
self.next_id - 1
}
pub(crate) fn place(&mut self, id: u32, task: Task, segs: Vec<Seg>, vias: Vec<P>) {
let mut handles = Vec::new();
let mut via_handles = Vec::new();
for s in &segs {
let h = self.world.layers[s.layer].add(Shape::Capsule { a: s.a.into(), b: s.b.into(), r: s.width as f64 / 2.0 }, task.net, Owner::Conn(id));
handles.push((s.layer, h));
}
if self.world.partner.contains_key(&task.net) {
self.world.pair_segs.borrow_mut().entry(task.net).or_default().extend(segs.iter().map(|s| (id, s.layer, V::from(s.a), V::from(s.b))));
}
let (via_dia, via_drill) = self.rules.via_for(task.net);
let vr = via_dia as f64 / 2.0;
let dr = via_drill as f64 / 2.0;
for v in &vias {
for l in 0..self.world.layers.len() {
let h = self.world.layers[l].add(Shape::Circle { c: (*v).into(), r: vr }, task.net, Owner::Conn(id));
handles.push((l, h));
}
via_handles.push(self.world.holes.add(Shape::Circle { c: (*v).into(), r: dr }, task.net, Owner::Conn(id)));
}
self.lane_off(task.a);
self.lane_off(task.b);
self.routes.insert(id, Route { id, task, segs, vias, handles, via_handles });
}
/// Take a route's copper off the board without counting it as a conflict.
pub(crate) fn unplace(&mut self, id: u32) -> Option<Route> {
let r = self.routes.remove(&id)?;
if let Some(v) = self.world.pair_segs.borrow_mut().get_mut(&r.task.net) {
v.retain(|s| s.0 != id);
}
for (l, h) in &r.handles {
self.world.layers[*l].remove(*h);
}
for h in &r.via_handles {
self.world.holes.remove(*h);
}
Some(r)
}
pub fn rip(&mut self, id: u32) -> Option<Task> {
let r = self.unplace(id)?;
*self.rip_count.entry((r.task.a, r.task.b)).or_insert(0) += 1;
self.lane_on(r.task.a);
self.lane_on(r.task.b);
Some(r.task)
}
/// Time for a closing pass past the routing limit. Both clocks move: a search also checks the
/// whole-run limit, and left behind it stops every search here at its first look at the clock
/// (4096 nodes), which reads as no path.
pub(crate) fn grant_time(&mut self, secs: f64) {
self.rules.deadline = Some(Instant::now() + std::time::Duration::from_secs_f64(secs));
self.rules.time_limit = self.start.elapsed().as_secs_f64() + secs;
}
fn find_pour_exits(&mut self) {
// Working number from the reference boards: benchmark B's VBUS pour is 192 mm2 with a connector in it,
// and the largest such pours on piprobe_v13 and benchmark C are 35 and 73 mm2, local patches
// that signals may pass.
const BIG_POUR_MM2: f64 = 100.0;
self.pour_exit.clear();
self.pour_exit_pads.clear();
let mut avoid: HashMap<NetId, Vec<(usize, Vec<V>)>> = HashMap::new();
for (zi, z) in self.board.zones.iter().enumerate() {
if z.keepout_tracks || z.net == NO_NET || looks_ground(self.board.net_name(z.net)) || z.outline.len() < 3 {
continue;
}
let n = z.outline.len();
let area = (0..n).map(|k| z.outline[k].0 * z.outline[(k + 1) % n].1 - z.outline[(k + 1) % n].0 * z.outline[k].1).sum::<f64>().abs() / 2.0 / (NM * NM);
if area < BIG_POUR_MM2 {
continue;
}
for &net in self.world.pour_open.get(zi).map(|v| v.as_slice()).unwrap_or(&[]) {
let inside: Vec<usize> = self.board.pads.iter().enumerate().filter(|(_, p)| p.net == net && p.layers.len() == 1 && z.layers.contains(&p.layers[0]) && in_poly(p.center.into(), &z.outline)).map(|(i, _)| i).collect();
if !inside.is_empty() {
self.pour_exit.insert(net);
self.pour_exit_pads.extend(inside);
let (layers, outline) = (z.layers.clone(), z.outline.clone());
let list = avoid.entry(net).or_default();
list.extend(layers.into_iter().map(|l| (l, outline.clone())));
}
}
}
self.world.pour_avoid = avoid;
}
/// A load of at least this share of its rail has to be on the pour for the pour to be the feed.
fn find_pour_fed(&mut self) {
const HEAVY_SHARE: f64 = 0.1;
self.pour_fed.clear();
for (name, rail) in &self.rules.rails {
let Some(net) = self.board.net_ids.iter().find(|(k, _)| k.eq_ignore_ascii_case(name)).map(|(_, v)| *v) else { continue };
let refs_of = |group: &Vec<usize>| -> HashSet<&str> { group.iter().map(|&p| self.board.footprints[self.board.pads[p].fp].reference.as_str()).collect() };
let fed = crate::conn::net_groups(self.board, net, &[]).iter().any(|g| {
let refs = refs_of(g);
rail.sources.iter().any(|s| refs.contains(s.as_str())) && rail.loads.iter().filter(|(_, a)| **a >= HEAVY_SHARE * rail.amps).all(|(k, _)| refs.contains(k.as_str()))
});
if fed {
self.pour_fed.insert(net);
}
}
self.tap_amps.clear();
for (name, rail) in &self.rules.rails {
let Some(net) = self.board.net_ids.iter().find(|(k, _)| k.eq_ignore_ascii_case(name)).map(|(_, v)| *v) else { continue };
if !self.pour_fed.contains(&net) {
self.tap_amps.extend(crate::current::branch_amps(self.board, net, rail));
}
}
self.power = if std::env::var_os("ADOM_ROUTE_NO_POWER_PLAN").is_some() { Default::default() } else { crate::power::plan(self.board, &self.rules, &self.pour_fed) };
for n in self.power.notes.clone() {
self.log.push(n);
}
if self.trace {
let mut v: Vec<(String, f64)> = self.tap_amps.iter().map(|(p, a)| (format!("{} {}", self.board.net_name(self.board.pads[*p].net), self.board.pad_name(*p)), *a)).collect();
v.sort_by(|x, y| x.0.cmp(&y.0));
for (n, a) in v {
eprintln!(" branch {n}: {a:.4} A");
}
eprintln!(" pour-fed: {:?}", self.pour_fed.iter().map(|n| self.board.net_name(*n)).collect::<Vec<_>>());
}
}
/// See `pour_plane`. A pour counts when its outline's bounding box covers at least `SHARE` of
/// the board's; with one on each outer layer, the one opposite most of the net's pads.
fn find_pour_planes(&mut self) {
const SHARE: f64 = 0.4;
self.pour_plane.clear();
if std::env::var_os("ADOM_ROUTE_NO_POUR_PLANES").is_some() {
return;
}
let bb = self.board.bbox;
let board_area = ((bb.2 - bb.0) * (bb.3 - bb.1)).max(1.0);
let last = self.board.layers.len() - 1;
let inner = self.board.plane_nets();
let mut big: std::collections::BTreeMap<NetId, Vec<usize>> = Default::default();
for z in self.board.zones.iter().filter(|z| z.net != NO_NET && !z.keepout_tracks && z.outline.len() >= 3 && !inner.contains_key(&z.net)) {
let b = z.outline.iter().fold((f64::MAX, f64::MAX, f64::MIN, f64::MIN), |m, v| (m.0.min(v.0), m.1.min(v.1), m.2.max(v.0), m.3.max(v.1)));
if (b.2 - b.0) * (b.3 - b.1) >= SHARE * board_area {
for &l in z.layers.iter().filter(|&&l| l == 0 || l == last) {
let e = big.entry(z.net).or_default();
if !e.contains(&l) {
e.push(l);
}
}
}
}
for (net, layers) in big {
let on = |l: usize| self.board.pads.iter().filter(|p| p.net == net && p.drill.is_none() && p.layers.contains(&l)).count();
let layer = *layers.iter().min_by_key(|&&l| (on(l), std::cmp::Reverse(l))).unwrap();
self.pour_plane.insert(net, layer);
}
}
pub(crate) fn pour_fed_net(&self, name: &str) -> bool {
self.board.net_ids.iter().find(|(k, _)| k.eq_ignore_ascii_case(name)).map(|(_, v)| self.pour_fed.contains(v)).unwrap_or(false)
}
pub(crate) fn over_time(&self) -> bool {
self.start.elapsed().as_secs_f64() > self.rules.time_limit
}
/// What this bus member should look like: its routed neighbour's shape, carried over to each of
/// its own two pins. The two copies differ where the pin rows have different pitches, and the
/// search jogs between them.
fn bus_hint(&self, task: &Task, m: &crate::bus::Member) -> crate::global::Hint {
let mut lanes = Vec::new();
if let Some(((na, nb), swapped)) = m.follow {
if let Some(r) = self.routes.values().find(|r| r.task.a == na && r.task.b == nb) {
let (pa, pb) = if swapped { (nb, na) } else { (na, nb) };
let shift = |own: usize, theirs: usize| {
let (o, t) = (self.board.pads[own].center, self.board.pads[theirs].center);
(o.0 - t.0, o.1 - t.1)
};
for d in [shift(task.a, pa), shift(task.b, pb)] {
for s in &r.segs {
lanes.push((V((s.a.0 + d.0) as f64, (s.a.1 + d.1) as f64), V((s.b.0 + d.0) as f64, (s.b.1 + d.1) as f64), s.layer));
}
}
}
}
crate::global::Hint { net: task.net, lanes, layer: Some(m.layer) }
}
fn try_route(&mut self, task: &Task) -> bool {
let t0 = Instant::now();
let mut r = self.try_route_inner(task);
// No way off a big pour under the class: a local rule at the pad, for his review (reference choice
// for J1 on benchmark B). If there is still none, an open join is worse than a long run.
if !r && !self.pour_relax && self.pour_exit.contains(&task.net) {
if self.propose_exit_rule(task.a) || (task.b != task.a && self.propose_exit_rule(task.b)) {
r = self.try_route_inner(task);
}
if !r {
self.pour_relax = true;
r = self.try_route_inner(task);
self.pour_relax = false;
}
}
if self.trace {
eprintln!(" {:<7.2}s {} {} {} -> {} {}", t0.elapsed().as_secs_f64(), if r { "ok " } else { "FAIL" }, task.level.name(), self.board.pad_name(task.a), self.board.pad_name(task.b), self.board.net_name(task.net));
}
// Debug: the copper as it stood at the first failed connection, to see what walls it in.
if !r {
if let Some(path) = std::env::var_os("ADOM_ROUTE_SNAP_FAIL") {
let want = std::env::var("ADOM_ROUTE_SNAP_PAD").ok();
let hit = want.as_ref().map_or(true, |w| *w == self.board.pad_name(task.a) || *w == self.board.pad_name(task.b));
if hit && !std::path::Path::new(&path).exists() {
let mut routes: Vec<&Route> = self.routes.values().collect();
routes.sort_by_key(|r| r.id);
let _ = std::fs::write(&path, crate::write::render(self.board, &routes, &self.rules));
eprintln!(" snapshot at the first failure ({} -> {}) written", self.board.pad_name(task.a), self.board.pad_name(task.b));
}
}
}
r
}
pub(crate) fn targets_of(&self, task: &Task) -> Vec<Terminal> {
match task.zone {
Some(RAIL_TAP) => self.rail_targets(task, 0.0),
Some(z) => {
let (_, layer, poly) = &self.world.zones[z];
vec![Terminal::Zone { layer: *layer, poly: poly.clone() }]
}
None if self.joins_copper(task) => self.join_targets(task),
None => vec![self.pad_terminal(task.b)],
}
}
fn try_route_inner(&mut self, task: &Task) -> bool {
if task.zone == Some(RAIL_TAP) {
return self.try_rail(task);
}
let sources = [self.pad_terminal(task.a)];
let targets = self.targets_of(task);
let mut profiles = self.attempts(task);
// A net being moved off a pour leaves the plan's layer behind: that layer is what cut it.
let member = if self.pour_strict.contains(&task.net) { None } else { self.bus.members.get(&(task.a, task.b)).cloned() };
self.world.guide.borrow_mut().hint = member.as_ref().map(|m| self.bus_hint(task, m));
// A bus runs at 2W from the first try (4.2: non-high-speed signals may drop to 2W in dense
// areas, and a bus is what makes the area dense).
if member.is_some() {
for pf in &mut profiles {
pf.target_gap = pf.target_gap.min(pf.width.max(pf.clearance));
}
}
// First tries on the layer the bus plan chose, where that costs no via: the line that would
// cross the rest takes the other layer on purpose rather than by finding out.
let held_sources: Vec<Terminal> = match &member {
Some(m) if m.free => vec![Terminal::Point { p: self.board.pads[task.a].center, layers: vec![m.layer] }],
_ => Vec::new(),
};
let held_targets: Vec<Terminal> = match &member {
Some(m) if m.free => vec![Terminal::Point { p: self.board.pads[task.b].center, layers: vec![m.layer] }],
_ => Vec::new(),
};
// Past a third of the time a first try turns cheap, so one hard connection can't spend what
// the tasks behind it need (benchmark B: 31 failures took 79 of 120 s, and the last 43
// tasks never got a try). Early on it keeps the full budget: capping it from the start
// cost piprobe_v13 five joins (91 against 86 of 92).
let mut rules = self.rules.clone();
// A move off a pour runs last and has its own clock: nothing is waiting behind it.
if self.start.elapsed().as_secs_f64() > self.rules.time_limit / 3.0 && !self.pour_strict.contains(&task.net) && !self.pour_exit.contains(&task.net) {
rules.node_limit = rules.node_limit.min(100_000);
}
// Bus members get a real effort on the layer the plan chose first: a member that gives up its
// layer here crosses the rest later (bus.rs). Nesting round a neighbour's pin on its own layer
// is the plan working: benchmark B's bottom row does this, at up to 1.7 times the straight
// distance; beyond 2 it falls through to the weighed attempts.
if !held_sources.is_empty() {
let (w, n) = self.widths_for(task);
let c = self.rules.clearance_for(task.net, task.net);
let straight = hypot(sub(self.board.pads[task.a].center.into(), self.board.pads[task.b].center.into()));
for (width, neck, gap, margin) in [(w, n, w.max(c), 1.5 * NM), (w, n, w.max(c), 5.0 * NM), (n, n, c, 8.0 * NM)] {
let pf = Profile { width, neck, clearance: c, target_gap: gap, max_vias: 0, margin, layer_bias: None };
self.searches += 1;
let q = Query { net: task.net, also: None, sources: &held_sources, targets: &held_targets, profile: pf, rules: &rules, soft: None, via_in: None, history: Some(&self.history), free: &[], arrive: None };
if let Some(path) = search(&self.world, &q) {
self.nodes += path.nodes as u64;
let len: f64 = path.pts.windows(2).map(|w| hypot(sub(w[0].0.into(), w[1].0.into()))).sum();
if len <= 2.0 * straight {
let pts = self.finish_path(&path, task.net, NO_NET, pf.neck);
self.commit(task, &pts, pf.width, pf.neck, NO_NET);
return true;
}
}
}
}
let Some((path, pf)) = self.weigh(task, &sources, &targets, &profiles, &rules) else { return false };
let pts = self.finish_path(&path, task.net, NO_NET, pf.neck);
self.commit(task, &pts, pf.width, pf.neck, NO_NET);
true
}
/// Plane nets: each pad gets its own via just clear of the pad, on a short stub (4.2, 4.4).
fn fan_out_pad(&mut self, pad: usize, task: &Task) -> bool {
// In a big pour a via beside a connector's pad walls off the pads next to it. He ties such a pad
// straight to its part's own through-hole pad of the net (J1's A1 and B12 to the shell), which
// reaches the plane already.
if self.pour_exit_pads.contains(&pad) && self.tie_to_sibling(pad, task) {
return true;
}
let p = &self.board.pads[pad];
let f = &self.board.footprints[p.fp];
let exposed = f.pads.len() > 4 && p.size.0 >= 1.0 * NM && p.size.1 >= 1.0 * NM;
let center = p.center;
let net = p.net;
let layer = p.layers.iter().copied().find(|l| self.world.route_layers.contains(l));
let Some(layer) = layer else { return true };
if exposed {
// Thermal vias are placed in the pad; the count must be confirmed for the part's heat.
let mut placed = Vec::new();
let (w, h) = (p.size.0, p.size.1);
let step = 1.0 * NM;
let nx = ((w - self.rules.via as f64) / step).floor().max(0.0) as i64;
let ny = ((h - self.rules.via as f64) / step).floor().max(0.0) as i64;
for j in 0..=ny {
for i in 0..=nx {
let v = snap((center.0 + ((i as f64 - nx as f64 / 2.0) * step) as i64, center.1 + ((j as f64 - ny as f64 / 2.0) * step) as i64));
let q = Query { net, also: None, sources: &[], targets: &[], profile: Profile { width: 0, neck: 0, clearance: self.rules.clearance, target_gap: 0, max_vias: 0, margin: 0.0, layer_bias: None }, rules: &self.rules, soft: None, via_in: Some(pad), history: None, free: &[], arrive: None };
let (mut b, mut c) = (Vec::new(), 0.0);
if self.world.via_ok(v, &q, None, &mut b, &mut c) {
placed.push(v);
}
}
}
if placed.is_empty() {
return false;
}
self.notes.push(format!("{}: {} thermal vias in the exposed pad; confirm the count against the part's heat (4.4)", self.board.pad_name(pad), placed.len()));
let id = self.next_id;
self.next_id += 1;
self.place(id, task.clone(), Vec::new(), placed);
return true;
}
let vr = self.rules.via as f64 / 2.0;
let gap = self.rules.pad_via_gap as f64;
let mut best: Option<(f64, P, i64)> = None;
let widths = [self.rules.track, self.rules.neck];
for d in 0..8usize {
let (dx, dy) = DIRS[d];
let unit = if dx != 0 && dy != 0 { SQRT2 } else { 1.0 };
// Walk outward along this direction until the via clears the pad.
let mut t = 0.0f64;
while t < 3.0 * NM {
t += 0.02 * NM;
let v = snap((center.0 + (dx as f64 * t / unit) as i64, center.1 + (dy as f64 * t / unit) as i64));
if p.shape.dist_pt(v.into()) < vr + gap {
continue;
}
let q = Query { net, also: None, sources: &[], targets: &[], profile: Profile { width: 0, neck: 0, clearance: self.rules.clearance, target_gap: 0, max_vias: 0, margin: 0.0, layer_bias: None }, rules: &self.rules, soft: None, via_in: None, history: None, free: &[], arrive: None };
let (mut b, mut c) = (Vec::new(), 0.0);
if !self.world.via_ok(v, &q, None, &mut b, &mut c) {
continue;
}
let mut w_ok = None;
for w in widths {
if self.seg_clear(center, v, layer, w, net, NO_NET) {
w_ok = Some(w);
break;
}
}
if let Some(w) = w_ok {
let score = t + if w == self.rules.neck { 0.05 * NM } else { 0.0 };
if best.map(|x| score < x.0).unwrap_or(true) {
best = Some((score, v, w));
}
}
break;
}
}
let Some((_, v, w)) = best else { return false };
let id = self.next_id;
self.next_id += 1;
let segs = vec![Seg { a: snap(center), b: v, layer, width: w }];
self.place(id, task.clone(), segs, vec![v]);
true
}
/// A pad with nowhere to put its via: the nearest site whose only blockers can move.
fn fan_out_site(&self, pad: usize, prices: &HashMap<u32, f64>) -> Option<(P, usize, Vec<u32>)> {
let p = &self.board.pads[pad];
let (center, net, shape) = (p.center, p.net, p.shape.clone());
let layer = p.layers.iter().copied().find(|l| self.world.route_layers.contains(l))?;
let vr = self.rules.via as f64 / 2.0;
let gap = self.rules.pad_via_gap as f64;
let price = |c: u32| prices.get(&c).copied().unwrap_or(f64::INFINITY);
let neck = self.rules.neck;
let mut best: Option<(f64, P, Vec<u32>)> = None;
for d in 0..8usize {
let (dx, dy) = DIRS[d];
let unit = if dx != 0 && dy != 0 { SQRT2 } else { 1.0 };
let mut t = 0.0f64;
while t < 2.0 * NM {
t += 0.02 * NM;
let v = snap((center.0 + (dx as f64 * t / unit) as i64, center.1 + (dy as f64 * t / unit) as i64));
if shape.dist_pt(v.into()) < vr + gap {
continue;
}
let q = Query { net, also: None, sources: &[], targets: &[], profile: Profile { width: 0, neck: 0, clearance: self.rules.clearance, target_gap: 0, max_vias: 0, margin: 0.0, layer_bias: None }, rules: &self.rules, soft: None, via_in: None, history: None, free: &[], arrive: None };
let (mut blockers, mut c) = (Vec::new(), 0.0);
if self.world.via_ok(v, &q, Some(&price), &mut blockers, &mut c) && self.stub_clear_soft(center, v, layer, neck, net, &price, &mut blockers) {
if !blockers.is_empty() {
let score = t + blockers.len() as f64 * NM;
if best.as_ref().map(|x| score < x.0).unwrap_or(true) {
best = Some((score, v, blockers));
}
}
break;
}
}
}
best.map(|(_, v, b)| (v, layer, b))
}
#[allow(clippy::too_many_arguments)]
fn stub_clear_soft(&self, a: P, b: P, layer: usize, width: i64, net: NetId, price: &dyn Fn(u32) -> f64, blockers: &mut Vec<u32>) -> bool {
let (va, vb): (V, V) = (a.into(), b.into());
let half = width as f64 / 2.0;
let need = half + self.rules.max_clearance() as f64;
let bb = (va.0.min(vb.0) - need, va.1.min(vb.1) - need, va.0.max(vb.0) + need, va.1.max(vb.1) + need);
let mut ok = true;
self.world.layers[layer].visit(bb, |o| {
if o.net == net {
return true;
}
if o.shape.dist_seg(va, vb) < half + self.rules.clearance_for(net, o.net) as f64 {
if let Owner::Conn(c) = o.owner {
if price(c).is_finite() {
if !blockers.contains(&c) {
blockers.push(c);
}
return true;
}
}
ok = false;
return false;
}
true
});
ok
}
/// A pair: route one thick centreline, then split it into two parallel tracks at the pair's
/// width and gap (4.2). The fan-in is only as long as the pads' spread needs, so the coupled run
/// covers all it can; each end runs straight into its pad's side where the line meets the pad,
/// which is how a pair keeps its spacing on entry, and otherwise takes a short stub. Falls back
/// to two separate routes, and says so.
fn route_pair(&mut self, pn: NetId, nn: NetId, width: i64, gap: i64) -> Vec<Task> {
let pads_of = |net: NetId| -> Vec<usize> { self.board.pads.iter().enumerate().filter(|(_, p)| p.net == net && !p.layers.is_empty()).map(|(i, _)| i).collect() };
let (pp, np) = (pads_of(pn), pads_of(nn));
let mk = |net, a, b| Task { net, level: Level::Pair, a, b, main: false, zone: None };
if pp.len() < 2 || np.len() < 2 {
return Vec::new();
}
let d = |a: usize, b: usize| hypot(sub(self.board.pads[a].center.into(), self.board.pads[b].center.into()));
// A net with more pads than two ends (a USB-C connector's two rows, a protection part): the
// coupled run goes between the pads farthest apart, and the rest join it afterwards.
let far = |pads: &[usize]| -> (usize, usize) {
let mut best = (pads[0], pads[1], -1.0);
for (i, &a) in pads.iter().enumerate() {
for &b in &pads[i + 1..] {
if d(a, b) > best.2 {
best = (a, b, d(a, b));
}
}
}
(best.0, best.1)
};
let (p1, p2) = far(&pp);
let nearest = |to: usize| -> usize { np.iter().copied().min_by(|&x, &y| d(to, x).total_cmp(&d(to, y))).unwrap() };
let (n1, n2) = (nearest(p1), nearest(p2));
if n1 == n2 {
let mut out = Vec::new();
for (net, pads) in [(pn, &pp), (nn, &np)] {
for w in chain_pads(self.board, pads).windows(2) {
out.push(mk(net, w[1], w[0]));
}
}
return out;
}
// Side pads, each to the end nearest it; `targets_of` lets it land on the run instead (4.2).
let mut rest = Vec::new();
for (net, pads, e1, e2) in [(pn, &pp, p1, p2), (nn, &np, n1, n2)] {
for &o in pads.iter().filter(|&&o| o != e1 && o != e2) {
rest.push(mk(net, o, if d(o, e1) <= d(o, e2) { e1 } else { e2 }));
}
}
let names = format!("{}/{}", self.board.net_name(pn), self.board.net_name(nn));
// A pair that could not be coupled is two plain long tracks. They keep their place at the head
// of the queue but lose the pair's protection: repair may move them like any data line. Held
// as a pair on adom/carrier-fc-rp2350a-mini they sealed a module's pad column and nothing was
// allowed to push them aside.
let loose = |t: Task| Task { level: Level::Data, ..t };
let mut fallback = vec![loose(mk(pn, p1, p2)), loose(mk(nn, n1, n2))];
fallback.extend(rest.iter().cloned().map(loose));
// Every layer both far ends reach, those clear of another net's pour first: on benchmark B
// both ends are through-hole, F.Cu holds the VBUS pour round the connector, and his own pair
// runs coupled on B.Cu. Taking only the first shared layer gave up with "no room".
let mut layers: Vec<usize> = self.world.route_layers.iter().copied().filter(|l| self.board.pads[p1].layers.contains(l) && self.board.pads[p2].layers.contains(l)).collect();
if layers.is_empty() {
return fallback;
}
let in_pour = |l: usize, at: P, zones: &[(NetId, usize, Vec<V>)]| zones.iter().any(|(n, zl, poly)| *zl == l && *n != pn && *n != nn && in_poly(at.into(), poly));
let (e1, e2) = (self.board.pads[p1].center, self.board.pads[p2].center);
layers.sort_by_key(|&l| in_pour(l, e1, &self.world.zones) as u8 + in_pour(l, e2, &self.world.zones) as u8);
// Tracks at pitch need (spread - pitch) / 2 of 45-degree run to come together, plus a little.
let pitch = (width + gap) as f64;
let fan = |s: f64| (s - pitch).max(0.0) / 2.0 + 0.3 * NM;
let (f1, f2) = (fan(d(p1, n1)), fan(d(p2, n2)));
// Each end opens on its own: a pair's width often only breaks clearance at one fine-pitch end,
// and growing both would use up a short pair (PCB_Troubleshooting: necked for the last 0.66 mm
// at 0.4 mm pins). The least fan-in that works wins, keeping the most coupled.
let mut why: Vec<String> = Vec::new();
let mut grow: Vec<(f64, f64)> = Vec::new();
for x in [0.0, 0.2, 0.4, 0.66, 0.9] {
for y in [0.0, 0.2, 0.4, 0.66, 0.9] {
grow.push((x, y));
}
}
grow.sort_by(|a, b| (a.0 + a.1).total_cmp(&(b.0 + b.1)));
for &layer in &layers {
for &(x, y) in &grow {
let (r1, r2) = (f1 + x * NM, f2 + y * NM);
// Straight out from each pad pair first, as he leaves them, in the directions that
// keep polarity without a crossing. The free search stays as the last try.
let mut tries: Vec<Option<(P, P)>> = self.pair_run_ins([p1, n1, p2, n2], r1, r2).into_iter().map(Some).collect();
tries.push(None);
// Through the connector its side pads belong to first, as he runs it, with all of its
// exits planned as one group. His own run stands about 0.35 mm off the connector's
// centre, which is what makes room for the vias, so a few offsets are tried; the
// first where every exit fits wins. If none does, the plain run below still stands.
for &offset in &[0i64, -350_000, 350_000, -175_000, 175_000, -525_000, 525_000] {
let Some((fp, stops)) = self.pair_through([p1, n1, p2, n2], [pn, nn], layer, offset) else { break };
for ends in &tries {
match self.try_pair([p1, n1, p2, n2], [pn, nn], layer, width, gap, r1, r2, *ends, &stops) {
Ok(note) => {
if self.plan_exits(fp, [pn, nn], layer) {
// The way out is laid: from here on nothing needs more than a stub in the pour.
self.pour_limit = crate::router::repair::STUB_RUN;
self.notes.push(format!("{names}: on {} through its connector with planned exits, {note}", self.board.layers[layer].name));
return rest;
}
let ids: Vec<u32> = self.routes.values().filter(|r| r.task.net == pn || r.task.net == nn).map(|r| r.id).collect();
for id in ids {
self.unplace(id);
}
break;
}
Err(w) => {
if !why.contains(&w) {
why.push(w);
}
}
}
}
}
for ends in &tries {
match self.try_pair([p1, n1, p2, n2], [pn, nn], layer, width, gap, r1, r2, *ends, &[]) {
Ok(note) => {
self.notes.push(format!("{names}: on {}, {note}", self.board.layers[layer].name));
return rest;
}
Err(w) => {
if !why.contains(&w) {
why.push(w);
}
}
}
}
}
}
self.notes.push(format!("{names}: {}; routed as two separate tracks, so check impedance and skew", why.join(", then ")));
fallback
}
/// One attempt at a pair with the given fan-in radius at each end.
#[allow(clippy::too_many_arguments)]
/// Stops that carry a run straight through a connector holding side pads of both nets, on a layer
/// those pads don't use. A part with two rows of them (a USB-C receptacle's A and B rows) qualifies.
/// The run crosses the rows square, a little past each. Nearest the run's start first.
fn pair_through(&self, pads: [usize; 4], nets: [NetId; 2], layer: usize, offset: i64) -> Option<(usize, Vec<P>)> {
let [p1, n1, ..] = pads;
let start = self.board.pads[p1].center;
let start2 = self.board.pads[n1].center;
let mid = ((start.0 + start2.0) / 2, (start.1 + start2.1) / 2);
for (fi, f) in self.board.footprints.iter().enumerate() {
let mine: Vec<&Pad> = f.pads.iter().map(|&i| &self.board.pads[i]).filter(|p| (p.net == nets[0] || p.net == nets[1]) && !p.layers.contains(&layer)).collect();
if mine.len() < 4 || !nets.iter().all(|n| mine.iter().any(|p| p.net == *n)) || pads.iter().any(|&i| f.pads.contains(&i)) {
continue;
}
let same = |a: i64, b: i64| (a - b).abs() < 100_000;
let rows_along_x = mine.iter().any(|p| mine.iter().any(|q| !std::ptr::eq(*p, *q) && same(p.center.1, q.center.1)));
let b = mine.iter().fold((i64::MAX, i64::MAX, i64::MIN, i64::MIN), |m, p| (m.0.min(p.center.0), m.1.min(p.center.1), m.2.max(p.center.0), m.3.max(p.center.1)));
let c = ((b.0 + b.2) / 2, (b.1 + b.3) / 2);
const PAST_THE_ROW: i64 = 2_000_000;
let (a1, a2) = if rows_along_x { ((c.0 + offset, b.1 - PAST_THE_ROW), (c.0 + offset, b.3 + PAST_THE_ROW)) } else { ((b.0 - PAST_THE_ROW, c.1 + offset), (b.2 + PAST_THE_ROW, c.1 + offset)) };
let d = |q: P| hypot(sub(q.into(), mid.into()));
return Some((fi, if d(a1) <= d(a2) { vec![snap(a1), snap(a2)] } else { vec![snap(a2), snap(a1)] }));
}
None
}
/// A bus as he routes one: its lines in bands of up to `BAND_MAX` neighbours, each band one shared
/// path at 3W pitch, every line an offset copy of it with a short fan-in to its pins at each end.
/// A band that doesn't fit whole is taken up again and its lines go one at a time as before.
/// A bus line's neighbours in its row that are already down, on the bus's layer, for the search
/// to run beside (search.rs FOLLOW_COST). Cleared for anything not in a bus.
/// Whether this connection is a line of a planned bus row.
pub(crate) fn in_bus_row(&self, task: &Task) -> bool {
std::env::var_os("ADOM_ROUTE_NO_BANDS").is_none() && self.bus.bands.iter().any(|(_, row)| row.contains(&(task.a, task.b)))
}
pub(crate) fn set_follow(&self, task: &Task) {
*self.world.follow.borrow_mut() = None;
if std::env::var_os("ADOM_ROUTE_NO_BANDS").is_some() {
return;
}
let key = (task.a, task.b);
let Some((layer, row)) = self.bus.bands.iter().find(|(_, row)| row.contains(&key)) else { return };
let k = row.iter().position(|x| *x == key).unwrap();
let near: Vec<(usize, usize)> = [k.checked_sub(1), Some(k + 1)].into_iter().flatten().filter_map(|i| row.get(i).copied()).collect();
let segs: Vec<(V, V)> = self.routes.values().filter(|r| near.contains(&(r.task.a, r.task.b))).flat_map(|r| r.segs.iter().filter(|s| s.layer == *layer).map(|s| (V::from(s.a), V::from(s.b)))).collect();
if segs.is_empty() {
return;
}
// Routing packs the row at the pitch so it fits; spread() gives it its room once all is down.
let w = self.widths_for(task).0;
let pitch = (3 * w).max(w + self.rules.clearance_for(task.net, task.net)) as f64;
*self.world.follow.borrow_mut() = Some((*layer, segs, pitch));
}
/// Where a coupled run may start and end so it leaves each pad pair square to the pads' axis,
/// keeping the same net on the same side. Empty if a pair's pads don't line up on the 45-degree
/// grid, or no combination keeps polarity.
fn pair_run_ins(&self, pads: [usize; 4], r1: f64, r2: f64) -> Vec<(P, P)> {
let [p1, n1, p2, n2] = pads;
let c = |i: usize| self.board.pads[i].center;
let square = |a: P, b: P, r: f64| -> Vec<(P, (f64, f64))> {
let Some(d) = dir_of(a, b) else { return Vec::new() };
let m = ((a.0 + b.0) / 2, (a.1 + b.1) / 2);
let mut out = Vec::new();
for k in [2u8, 6] {
let (dx, dy) = DIRS[((d + k) % 8) as usize];
let n = if dx != 0 && dy != 0 { (r + PAIR_RUN_IN) / SQRT2 } else { r + PAIR_RUN_IN } as i64;
out.push((snap((m.0 + dx * n, m.1 + dy * n)), (dx as f64, dy as f64)));
}
out
};
let side = |h: (f64, f64), m: P, pad: P| h.0 * (pad.1 - m.1) as f64 - h.1 * (pad.0 - m.0) as f64;
let (m1, m2) = (((c(p1).0 + c(n1).0) / 2, (c(p1).1 + c(n1).1) / 2), ((c(p2).0 + c(n2).0) / 2, (c(p2).1 + c(n2).1) / 2));
let mut out = Vec::new();
for (s, h1) in square(c(p1), c(n1), r1) {
for (e, h2) in square(c(p2), c(n2), r2) {
// h2 points away from the end; arriving, the run heads the other way.
if side(h1, m1, c(p1)) * side((-h2.0, -h2.1), m2, c(p2)) > 0.0 {
out.push((s, e));
}
}
}
// The shorter way first: the two ends facing each other.
out.sort_by(|a, b| hypot(sub(a.0.into(), a.1.into())).total_cmp(&hypot(sub(b.0.into(), b.1.into()))));
out
}
#[allow(clippy::too_many_arguments)]
fn try_pair(&mut self, pads: [usize; 4], nets: [NetId; 2], layer: usize, width: i64, gap: i64, r1: f64, r2: f64, ends: Option<(P, P)>, through: &[P]) -> Result<String, String> {
let [p1, n1, p2, n2] = pads;
let [pn, nn] = nets;
let mid = |a: usize, b: usize| {
let (x, y) = (self.board.pads[a].center, self.board.pads[b].center);
snap(((x.0 + y.0) / 2, (x.1 + y.1) / 2))
};
let (m1, m2) = (mid(p1, n1), mid(p2, n2));
let total = width * 2 + gap;
let (from, to) = ends.unwrap_or((m1, m2));
let pf = Profile { width: total, neck: total, clearance: self.rules.clearance, target_gap: self.rules.clearance, max_vias: 0, margin: 4.0 * NM, layer_bias: None };
let free_zones = [(m1, r1 + PAIR_RUN_IN + 10_000.0), (m2, r2 + PAIR_RUN_IN + 10_000.0)];
let mut stops = vec![from];
stops.extend_from_slice(through);
stops.push(to);
let mut line: Vec<P> = Vec::new();
for w in stops.windows(2) {
let sources = [Terminal::Point { p: w[0], layers: vec![layer] }];
let targets = [Terminal::Point { p: w[1], layers: vec![layer] }];
let q = Query { net: pn, also: Some(nn), sources: &sources, targets: &targets, profile: pf, rules: &self.rules, soft: None, via_in: None, history: None, free: &free_zones, arrive: None };
let path = search(&self.world, &q).ok_or("no room for a coupled run")?;
let pts = self.finish_path(&path, pn, nn, total);
line.extend(pts.iter().map(|x| x.0));
}
line.dedup();
// Run in from the pad pair straight, so the body keeps that direction past the fan-in.
if ends.is_some() {
line.insert(0, m1);
line.push(m2);
line.dedup();
}
let center = trim_each(&line, r1, r2);
if center.len() < 2 {
return Err("the two ends are too close for a coupled run".to_string());
}
let off = (width + gap) as f64 / 2.0;
let side_at = |a: P, b: P, c: P| -> f64 {
let (ax, ay) = ((b.0 - a.0) as f64, (b.1 - a.1) as f64);
let (bx, by) = ((c.0 - a.0) as f64, (c.1 - a.1) as f64);
ax * by - ay * bx
};
let last = center.len() - 1;
let side = if side_at(center[0], center[1], self.board.pads[p1].center) >= 0.0 { 1.0 } else { -1.0 };
if (side_at(center[last - 1], center[last], self.board.pads[p2].center) >= 0.0) != (side > 0.0) {
return Err("the pair would have to cross. Consider swapping polarity if the part allows it".to_string());
}
let body_p = offset_polyline(¢er, side * off);
let body_n = offset_polyline(¢er, -side * off);
for b in [&body_p, &body_n] {
for w in b.windows(2) {
if !self.seg_clear(w[0], w[1], layer, width, pn, nn) {
return Err("the split pair fails clearance".to_string());
}
}
}
// Searched as one, each track still answers for itself: D+ across D-'s mask opening is a
// bridge, whichever net the search was carrying.
for (net, b) in [(pn, &body_p), (nn, &body_n)] {
for w in b.windows(2) {
let (va, vb): (V, V) = (w[0].into(), w[1].into());
if self.world.mask.seg_hit(net, layer, va, vb, width as f64 / 2.0).is_some() || !self.world.holes_clear(&self.rules, va, vb, width as f64 / 2.0, net) {
return Err("a split track crosses its partner's mask opening or hole".to_string());
}
}
}
let mut placed: Vec<u32> = Vec::new();
let mut lens = [0.0f64; 2];
let mut stubs: [Vec<u32>; 2] = [Vec::new(), Vec::new()];
let len_of = |b: &[P]| -> f64 { b.windows(2).map(|w| hypot(sub(w[0].into(), w[1].into()))).sum() };
let bodies: [(NetId, &Vec<P>, usize, usize); 2] = [(pn, &body_p, p1, p2), (nn, &body_n, n1, n2)];
for (k, (net, body, a, b)) in bodies.into_iter().enumerate() {
let task = Task { net, level: Level::Pair, a, b, main: false, zone: None };
let id = self.fresh_id();
let segs: Vec<Seg> = body.windows(2).map(|w| Seg { a: w[0], b: w[1], layer, width }).collect();
lens[k] += len_of(body);
self.place(id, task.clone(), segs, Vec::new());
placed.push(id);
let n = body.len();
let partner = |pad: usize| -> usize { if pad == a { if k == 0 { n1 } else { p1 } } else if k == 0 { n2 } else { p2 } };
for (pad, end, next) in [(a, body[0], body[1]), (b, body[n - 1], body[n - 2])] {
let other = nets[1 - k];
match self.pair_entry(&task, pad, partner(pad), end, next, layer, width, other) {
Some((sid, l)) => {
placed.push(sid);
stubs[k].push(sid);
lens[k] += l;
}
None => {
for id in placed {
self.unplace(id);
}
return Err("fan-in failed".to_string());
}
}
}
}
// The two tracks answer to each other as well. Each was searched with its partner's copper as
// its own, so nothing above has measured one against the other: where the run leaves the
// pads away from the way the body goes, a pad entry doubles back beside its partner's (the designer's
// drone-motor-carrier, 2026-11-10: D+ 0.078 mm from D-, where KiCad wants 0.2).
{
let floor = (gap.min(self.rules.clearance_for(pn, nn)) + width) as f64 - 2_000.0;
let of = |net: NetId| -> Vec<Seg> { placed.iter().filter_map(|id| self.routes.get(id)).filter(|r| r.task.net == net).flat_map(|r| r.segs.iter().cloned()).collect() };
let (ps, ns) = (of(pn), of(nn));
let close = ps.iter().any(|a| ns.iter().any(|b| a.layer == b.layer && seg_seg(a.a.into(), a.b.into(), b.a.into(), b.b.into()) < floor));
if close {
for id in placed {
self.unplace(id);
}
return Err("its two tracks come closer than their gap at a pad entry".to_string());
}
// Nor has either track been measured against its partner's PADS: a part sitting on the pair
// (a protection diode with one pad on each line) lies in the coupled run's way, and the
// partner's track went straight through its pad, a short (a large Ethernet switch board,
// D301.2, 2026-11-10). Full clearance to every pad of the other net.
let clr = self.rules.clearance_for(pn, nn) as f64 - 2_000.0;
let hits = |segs: &[Seg], other: NetId| -> bool {
self.board.pads.iter().filter(|p| p.net == other && !p.layers.is_empty()).any(|p| segs.iter().any(|s| p.layers.contains(&s.layer) && p.shape.dist_seg(s.a.into(), s.b.into()) - s.width as f64 / 2.0 < clr))
};
if hits(&ps, nn) || hits(&ns, pn) {
for id in placed {
self.unplace(id);
}
return Err("one track would touch a pad of its partner's net".to_string());
}
}
// Skew: report it, and make up a real difference with a 45-degree dip on the short net before
// the coupled run (PCB_Troubleshooting, "A USB pair fails"; 0.5 mm is the limit noted there).
let mut skew = (lens[0] - lens[1]).abs();
let mut dip = String::new();
if skew > 0.5 * NM {
let short = if lens[0] < lens[1] { 0 } else { 1 };
if self.skew_dip(&stubs[short], skew) {
dip = format!("; {:.2} mm made up with a 45-degree dip", skew / NM);
skew = 0.0;
} else {
dip = "; no straight stub long enough to dip, so the skew stands".to_string();
}
}
// Measured on what was laid, pad entries included, not just the body.
let segs_of = |net: NetId| -> Vec<Seg> { placed.iter().filter_map(|id| self.routes.get(id)).filter(|r| r.task.net == net).flat_map(|r| r.segs.iter().cloned()).collect() };
let total = crate::post::coupled_len(&segs_of(pn), &segs_of(nn), (width + gap) as f64 + 2_000.0);
Ok(format!("coupled {:.2} of {:.2} mm at {:.3}/{:.3} mm; skew {:.3} mm{dip}", total / NM, lens[0] / NM, width as f64 / NM, gap as f64 / NM, skew / NM))
}
/// Join a pair's body end to its pad. Straight into the pad's side when the body's own line meets
/// it: that keeps the spacing right up to the pad (4.2 pad entry). Otherwise a short search to
/// the side of the pad nearest the partner, then to its centre. At the pair's width if it clears,
/// else necked (at 0.4 mm pins the pair width breaks clearance to the next pin).
#[allow(clippy::too_many_arguments)]
fn pair_entry(&mut self, task: &Task, pad: usize, partner: usize, end: P, next: P, layer: usize, width: i64, other: NetId) -> Option<(u32, f64)> {
let neck = self.rules.neck;
let shape = self.board.pads[pad].shape.clone();
let center = self.board.pads[pad].center;
if shape.dist_pt(end.into()) <= 0.0 {
let id = self.fresh_id();
self.place(id, task.clone(), Vec::new(), Vec::new());
return Some((id, 0.0));
}
if let Some(dir) = dir_of(next, end) {
let (dx, dy) = DIRS[dir as usize];
let mut t = 0i64;
while (t as f64) < 1.5 * NM {
t += 20_000;
let q = (end.0 + dx * t, end.1 + dy * t);
if shape.dist_pt(q.into()) > 0.0 {
continue;
}
// Well inside the pad, so the track's end is covered by it.
let q = (q.0 + dx * 20_000, q.1 + dy * 20_000);
let q = if shape.dist_pt(q.into()) <= 0.0 { snap(q) } else { snap((q.0 - dx * 20_000, q.1 - dy * 20_000)) };
for w in [width, neck] {
if self.seg_clear(end, q, layer, w, task.net, other) {
let id = self.fresh_id();
let l = hypot(sub(end.into(), q.into()));
self.place(id, task.clone(), vec![Seg { a: end, b: q, layer, width: w }], Vec::new());
return Some((id, l));
}
}
break;
}
}
// Toward the partner by as much as the pad allows: the side of the pad.
let u = sub(self.board.pads[partner].center.into(), center.into());
let ul = hypot(u).max(1.0);
let (ux, uy) = (u.0 / ul, u.1 / ul);
let c: V = center.into();
let reach = (shape.support(ux, uy) - (c.0 * ux + c.1 * uy) - neck as f64 / 2.0).max(0.0);
let side = snap(((c.0 + ux * reach) as i64, (c.1 + uy * reach) as i64));
for from in [side, center] {
if shape.dist_pt(from.into()) > 0.0 {
continue;
}
let layers: Vec<usize> = vec![layer];
let s = [Terminal::Point { p: from, layers: layers.clone() }];
let t = [Terminal::Point { p: end, layers }];
for w in [width.min(mm(0.3)), neck] {
let pf = Profile { width: w, neck: w, clearance: self.rules.clearance, target_gap: self.rules.clearance, max_vias: 0, margin: 1.5 * NM, layer_bias: None };
let q = Query { net: task.net, also: None, sources: &s, targets: &t, profile: pf, rules: &self.rules, soft: None, via_in: None, history: None, free: &[], arrive: dir_of(end, next) };
if let Some(path) = search(&self.world, &q) {
let pts = self.finish_path(&path, task.net, NO_NET, w);
let segs: Vec<Seg> = pts.windows(2).filter(|w2| w2[0].1 == w2[1].1 && w2[0].0 != w2[1].0).map(|w2| Seg { a: w2[0].0, b: w2[1].0, layer, width: w }).collect();
let l = segs.iter().map(|s| hypot(sub(s.a.into(), s.b.into()))).sum();
let id = self.fresh_id();
self.place(id, task.clone(), segs, Vec::new());
return Some((id, l));
}
}
}
None
}
/// A 45-degree dip on one of these stub routes, deep enough to add `need` of length: down, along
/// and back adds 2 d (sqrt 2 - 1). Wherever a straight run is long enough and copper allows.
fn skew_dip(&mut self, stubs: &[u32], need: f64) -> bool {
let depth = ((need / (2.0 * (SQRT2 - 1.0))) as i64 + 2_000) & !1;
for &id in stubs {
let Some(r) = self.routes.get(&id) else { continue };
let (task, segs) = (r.task.clone(), r.segs.clone());
for (i, s) in segs.iter().enumerate() {
let Some(d) = dir_of(s.a, s.b) else { continue };
let len = (s.a.0 - s.b.0).abs().max((s.a.1 - s.b.1).abs());
if len < depth * 2 + 2_000 {
continue;
}
let (dx, dy) = DIRS[d as usize];
let mid = len / 2;
for turn in [2i32, -2] {
// The two legs turn off the run by 45 degrees toward this side.
let down = DIRS[((d as i32 + turn / 2).rem_euclid(8)) as usize];
let up = DIRS[((d as i32 - turn / 2).rem_euclid(8)) as usize];
let start = (s.a.0 + dx * (mid - depth), s.a.1 + dy * (mid - depth));
let q1 = (start.0 + down.0 * depth, start.1 + down.1 * depth);
let q2 = (q1.0 + up.0 * depth, q1.1 + up.1 * depth);
let chain = [s.a, start, q1, q2, s.b];
let clear = chain.windows(2).all(|w| self.seg_clear(w[0], w[1], s.layer, s.width, task.net, NO_NET));
if clear && dir_of(q2, s.b) == Some(d) {
let mut out = segs.clone();
let repl: Vec<Seg> = chain.windows(2).filter(|w| w[0] != w[1]).map(|w| Seg { a: w[0], b: w[1], layer: s.layer, width: s.width }).collect();
out.splice(i..=i, repl);
let vias = self.routes.get(&id).map(|r| r.vias.clone()).unwrap_or_default();
self.unplace(id);
self.place(id, task, out, vias);
return true;
}
}
}
}
false
}
/// Route the whole board in the hierarchy, repair what's left, and go again with the failures
/// first while that keeps finding something new. Always returns the fullest result seen, and of
/// those the cleanest. `tasks` order is level, then listed priority, then shortest first, with
/// earlier runs' failures first inside their level.
pub fn run(&mut self, plan: &Plan) -> Outcome {
let wall0 = std::time::Instant::now();
let t0 = Instant::now();
self.start = t0;
// Part 3 step 8 is part of the job: routing gets three quarters of the limit, and whatever it
// doesn't use goes to the optimisation pass.
let total = self.rules.time_limit;
self.rules.time_limit = total * 0.75;
self.rules.deadline = Some(t0 + std::time::Duration::from_secs_f64(self.rules.time_limit));
self.bus = crate::bus::plan(self.board, &self.world, &self.rules, plan);
self.log.extend(self.bus.notes.iter().cloned());
self.find_pour_fed();
self.find_pour_planes();
self.find_pour_exits();
self.find_pad_entries(plan);
self.lay_lanes(plan);
let mut failed_first: HashSet<(usize, usize)> = HashSet::new();
let mut best: Option<repair::Best> = None;
let mut seen: Vec<Vec<(usize, usize)>> = Vec::new();
for attempt in 0..8 {
if attempt > 0 && self.over_time() {
break;
}
let run_start = t0.elapsed().as_secs_f64();
if attempt > 0 {
let ids: Vec<u32> = self.routes.keys().copied().collect();
for id in ids {
self.rip(id);
}
self.notes.clear();
self.history.decay();
// Rerunning the same plan with the failures first has never beaten the first run
// here (piprobe_v13: 6 then 6, 4 then 5). A different lane length gives a different
// board: 0.4 mm and 0.5 mm leave different holes, so try the other one.
self.lane_len = LANES[if attempt == 1 { 0 } else { attempt % LANES.len() }] * NM;
// Loose first, on both the bus run and the plain run: it closed piprobe_v13 where tight didn't.
self.loose = attempt % 3 != 2;
self.lay_lanes(plan);
// The bus plan makes the better board, but it can hold a line to a layer that leaves
// another pin shut (piprobe_v13: 95 of 96 with it at 324 mm, 96 of 96 without at 339
// mm, his own 330 mm). So the second go is the plain one, with nothing else changed,
// and `Best` prefers the fullest board.
self.plain_go = attempt == 1;
self.bus = if attempt == 1 { Default::default() } else { crate::bus::plan(self.board, &self.world, &self.rules, plan) };
if attempt == 1 {
// Nothing carried over either, or it isn't the plain one.
failed_first.clear();
self.history = History::new(self.board.bbox);
self.memory.clear();
self.rip_count.clear();
}
}
let failed = self.pass(plan, &failed_first);
let first = failed.len();
let open = self.repair(failed, &mut best);
self.log.push(format!("run {}: {} open after the pass, {} after repair, {} rips ({} splices), {:.1} s so far", attempt + 1, first, open.len(), self.rips, self.splices, t0.elapsed().as_secs_f64()));
if open.is_empty() {
break;
}
// Not enough time left for another whole run to get as far as this one did: a fresh run
// would be cut short and thrown away (a motor-controller board: run 1 took 524 s and left 3
// open, run 2 had 65 s and left 24). The time goes to the best board's open joins
// instead, searched deeper than a normal repair allows.
let run_secs = t0.elapsed().as_secs_f64() - run_start;
let left = self.rules.time_limit - self.start.elapsed().as_secs_f64();
if left > 1.0 && left < 0.5 * run_secs && std::env::var_os("ADOM_ROUTE_NO_LAST_MILE").is_none() {
if let Some(b) = best.as_ref() {
let (routes, failed, notes): (Vec<Route>, Vec<Task>, Vec<String>) = (b.routes.values().cloned().collect(), b.failed.clone(), b.notes.clone());
let ids: Vec<u32> = self.routes.keys().copied().collect();
for id in ids {
self.rip(id);
}
let mut routes = routes;
routes.sort_by_key(|r| r.id);
for r in routes {
self.place(r.id, r.task, r.segs, r.vias);
}
self.rebuild_exit_vias();
self.notes = notes;
let before = failed.len();
self.deep = true;
let after = self.repair(failed, &mut best);
self.deep = false;
self.log.push(format!("last mile: {before} open on the best board, {} after deeper searches, {:.1} s so far", after.len(), t0.elapsed().as_secs_f64()));
}
break;
}
// The same holes twice means this order has nothing more to give: stop, don't spin.
let mut key: Vec<(usize, usize)> = open.iter().map(|t| (t.a, t.b)).collect();
key.sort();
if seen.contains(&key) {
break;
}
seen.push(key);
failed_first.extend(open.iter().map(|t| (t.a, t.b)));
}
let best = best.expect("repair always records a state");
let ids: Vec<u32> = self.routes.keys().copied().collect();
for id in ids {
self.rip(id);
}
for r in best.routes.into_values() {
self.place(r.id, r.task, r.segs, r.vias);
}
self.rebuild_exit_vias();
self.notes = best.notes;
self.rules.time_limit = total;
self.rules.deadline = Some(t0 + std::time::Duration::from_secs_f64(total));
let count = |t: &Self| -> usize { t.net_info.keys().map(|&n| t.islands(n).len().saturating_sub(1)).sum() };
let c0 = count(self);
self.optimize();
let c1 = count(self);
self.trim_overlaps();
let c2 = count(self);
self.second_vias();
let c3 = count(self);
self.log.push(format!("islands: {c0} before optimise, {c1} after, {c2} after trim, {c3} after second vias"));
self.widen_rails();
self.heal_pours();
if std::env::var_os("ADOM_ROUTE_NO_STITCH").is_none() {
self.grant_time(20.0);
self.stitch_pours();
// A join laid by stitching can run over the stub that used to end in the pour.
self.trim_overlaps();
}
self.settle_pad_rules();
// Tidying re-routes things, and a re-route can lose a chamfer to its new neighbours. These
// run past the routing deadline on a short one of their own: an unfinished corner or a
// starved fill is worse than 15 s.
self.grant_time(15.0);
self.fix_square_corners();
// Breathing room last among the moves: everything is joined, rails are at width.
if std::env::var_os("ADOM_ROUTE_NO_SPREAD").is_none() {
self.grant_time(20.0);
self.spread();
}
self.stitch_fill_pads();
self.fix_teardrops();
self.return_vias();
// The passes since the rails were sized (spacing, corners, vias) move copper a little, and a
// rail right at its drop limit can end a hair over it: size once more, as the last thing.
self.rate_rails_last();
self.rail_notes();
self.drop_shorts();
for t in &best.failed {
let why = match self.boxed_pads.get(&(t.a, t.b)) {
Some(&p) => format!("no track can leave {} under the rules: its pad sits closer to a neighbour than the clearance the net classes ask for", self.board.pad_name(p)),
None => self.why.get(&(t.a, t.b)).cloned().unwrap_or_else(|| "no legal path found within the time limit".to_string()),
};
self.notes.push(format!("for the designer: {} {} to {}: {}", self.board.net_name(t.net), self.board.pad_name(t.a), self.board.pad_name(t.b), why));
}
self.log.push(format!("clock: {} work units, {:.1} s of the work budget", crate::clock::units(), t0.elapsed().as_secs_f64()));
// The seconds reported are real ones; budgets run on the work clock (clock.rs).
Outcome { failed: best.failed, seconds: wall0.elapsed().as_secs_f64() }
}
fn pass(&mut self, plan: &Plan, failed_first: &HashSet<(usize, usize)>) -> Vec<Task> {
let mut queue: Vec<Task> = Vec::new();
self.exit_via.clear();
self.exit_tasks.clear();
self.pour_limit = POUR_RUN;
self.rail_override.clear();
self.rail_laid.clear();
self.rail_tries.clear();
for (pn, nn, w, g) in &plan.pairs {
// make_plan holds the gap to what DRC allows between these two nets (2.2).
let rest = self.route_pair(*pn, *nn, *w, *g);
queue.extend(rest);
}
queue.extend(plan.tasks.iter().cloned());
// The power stage's rails: its taps in its order, in place of the classifier's trunk and taps.
// Only for rails this run was asked to route (a fixture routes a few nets and no others).
let asked: HashSet<NetId> = queue.iter().map(|t| t.net).collect();
// A via for each pad of a poured net that is not on the pour's layer (`pour_plane`).
self.pour_pads.clear();
let mut planes: Vec<(NetId, usize)> = self.pour_plane.iter().map(|(n, l)| (*n, *l)).filter(|(n, _)| asked.contains(n)).collect();
planes.sort_unstable();
for (net, layer) in planes {
for (i, p) in self.board.pads.iter().enumerate().filter(|(_, p)| p.net == net && !p.layers.is_empty() && p.drill.is_none() && !p.layers.contains(&layer)) {
let _ = p;
queue.push(Task { net, level: Level::PlaneFanout, a: i, b: i, main: false, zone: None });
self.pour_pads.insert(i);
}
}
let planned: HashSet<NetId> = self.power.order.iter().map(|(n, _)| *n).filter(|n| asked.contains(n)).collect();
if !planned.is_empty() {
queue.retain(|t| !planned.contains(&t.net));
for (net, taps) in self.power.order.iter().filter(|(n, _)| planned.contains(n)) {
queue.extend(taps.iter().map(|&p| Task { net: *net, level: Level::Power, a: p, b: p, main: false, zone: Some(RAIL_TAP) }));
}
}
let priority = &self.rules.priority;
let rank = |t: &Task| -> usize { priority.iter().position(|n| n == self.board.net_name(t.net)).unwrap_or(usize::MAX) };
// Chains and rails keep the plan's order inside their net: a pad joins what is already laid.
let mut net_len: HashMap<NetId, i64> = HashMap::new();
for t in queue.iter().filter(|t| t.a != t.b) {
let (a, b) = (self.board.pads[t.a].center, self.board.pads[t.b].center);
net_len.entry(t.net).or_insert((a.0 - b.0).abs().max((a.1 - b.1).abs()));
}
let ln = |t: &Task| -> i64 {
// Rail tasks go after the shorter connections of their level: trunk, then nearest first.
if t.zone == Some(RAIL_TAP) { return i64::MAX; }
net_len.get(&t.net).copied().unwrap_or(0)
};
// GND via sites are staked out right after the pairs, so a pad doesn't get walled in, but
// they stay the lowest priority: any route may take one back and it moves (4.4).
// Rails that need 0.6 mm or more go straight after the pairs: laid after data they have no room
// (reference choice 2026-11-06, on benchmark C: 301 of 302 and 33.6 mm under width, against 299 and
// 61.8 mm). Everything else keeps 4.2's order. ADOM_ROUTE_RAILS_LAST restores it, to compare.
let heavy_first = std::env::var_os("ADOM_ROUTE_RAILS_LAST").is_none();
let heavy = |t: &Task| heavy_first && t.level == Level::Power && !self.pour_fed.contains(&t.net) && (self.power.pads.contains_key(&t.a) || self.rules.rail(self.board.net_name(t.net)).map(|r| self.rules.rail_width(r.amps, true) >= mm(0.6) || self.widths_for(t).0 >= mm(0.4)).unwrap_or(false));
// A supply net that lives within a few millimetres (an MCU's VCAP pin and its capacitor, VDDA
// behind its ferrite) is laid with the first group too: it needs almost no room, its place is
// fixed by the parts, and laid after the data lines it is walled in. a flight controller board:
// U1.31 to its VCAP capacitor, 1 mm apart, was one of nine such joins left open.
let mut extent: HashMap<NetId, (i64, i64, i64, i64)> = HashMap::new();
for p in self.board.pads.iter().filter(|p| p.net != NO_NET && !p.layers.is_empty()) {
let e = extent.entry(p.net).or_insert((p.center.0, p.center.1, p.center.0, p.center.1));
*e = (e.0.min(p.center.0), e.1.min(p.center.1), e.2.max(p.center.0), e.3.max(p.center.1));
}
// And on any rail, a supply pin's stub to its own capacitor (the classifier's cap-first task,
// 4.2): a millimetre or two beside the pin, laid before the pin's neighbours fan out past it.
// adom/rp2350a-ads1220: the RP2350's three 1.1 V pins were walled in by the data lines.
let pin_cap = |t: &Task| t.zone == Some(RAIL_TAP) && t.a != t.b && !t.main && {
let (a, b) = (self.board.pads[t.a].center, self.board.pads[t.b].center);
(a.0 - b.0).abs().max((a.1 - b.1).abs()) <= mm(PIN_CAP_MM)
};
let local = |t: &Task| std::env::var_os("ADOM_ROUTE_NO_LOCAL_FIRST").is_none() && t.level == Level::Power && (pin_cap(t) || extent.get(&t.net).map_or(false, |e| (e.2 - e.0).max(e.3 - e.1) <= mm(LOCAL_NET_MM)));
let order = |t: &Task| -> Level { if t.level == Level::PlaneFanout || heavy(t) || local(t) { Level::Pair } else { t.level } };
// The whole-board plan only guides: level order is fixed by the hierarchy (4.2).
let bus = &self.bus;
let held_to = |t: &Task| bus.members.get(&(t.a, t.b)).filter(|m| m.free).map(|m| m.layer);
let global = crate::global::plan(&self.world, &self.rules, self.board, &queue, &held_to);
queue.sort_by_key(|t| (order(t), !failed_first.contains(&(t.a, t.b)), rank(t), self.bus.order_of(t), ln(t)));
// Where the rails laid first end: the first task that is neither a pair, a plane fan-out nor one of them.
let early: HashSet<(usize, usize)> = queue.iter().filter(|t| heavy(t) || local(t) || matches!(t.level, Level::Pair | Level::PlaneFanout)).map(|t| (t.a, t.b)).collect();
let mut rails_rated = !queue.iter().any(|t| heavy(t));
self.log.push(global.note.clone());
let mut failed: Vec<Task> = Vec::new();
let patience = self.rules.time_limit * 0.5;
// A bus goes down line after line when its first line's turn comes, each following the one
// before at the bus pitch: parallel lines, as his benchmark B bus is drawn.
let follow_on = std::env::var_os("ADOM_ROUTE_NO_BANDS").is_none();
let bands = self.bus.bands.clone();
let band_of: HashMap<(usize, usize), (usize, usize)> = bands.iter().enumerate().flat_map(|(i, (_, row))| row.iter().enumerate().map(move |(k, key)| (*key, (i, k)))).collect();
if follow_on {
let by_key: HashMap<(usize, usize), Task> = queue.iter().map(|t| ((t.a, t.b), t.clone())).collect();
let mut emitted: HashSet<usize> = HashSet::new();
let mut grouped: Vec<Task> = Vec::with_capacity(queue.len());
for t in queue.drain(..) {
match band_of.get(&(t.a, t.b)) {
Some(&(bi, _)) => {
if emitted.insert(bi) {
grouped.extend(bands[bi].1.iter().filter_map(|k| by_key.get(k).cloned()));
}
}
None => grouped.push(t),
}
}
queue = grouped;
}
let queued = queue.len();
for (turn_no, task) in queue.into_iter().enumerate() {
if !rails_rated && !early.contains(&(task.a, task.b)) {
rails_rated = true;
self.rate_rails_now();
}
self.set_follow(&task);
if task.level == Level::PlaneFanout && task.a == task.b && task.zone.is_none() {
if !self.fan_out_pad(task.a, &task) && !self.pour_pads.contains(&task.a) {
failed.push(task);
}
continue;
}
if self.over_time() {
// Out of time, but a join that was never tried is not given up unseen: one short
// try each (half a second of work, a small search). On adom/esc-g431 21 joins ended
// as "no legal path found within the time limit" without one search, among them an
// LED to its resistor.
let (full, limit, deadline) = (self.rules.node_limit, self.rules.time_limit, self.rules.deadline);
self.rules.node_limit = full.min(30_000);
self.rules.time_limit = self.start.elapsed().as_secs_f64() + 0.5;
self.rules.deadline = Some(Instant::now() + std::time::Duration::from_secs_f64(0.5));
let done = self.joined(&task) || self.try_route(&task);
self.rules.node_limit = full;
self.rules.time_limit = limit;
self.rules.deadline = deadline;
if !done {
failed.push(task);
}
continue;
}
// Past a third of the time, first tries turn cheap, rails included (try_route_inner says
// why): on benchmark C rails alone took 196 of 240 s and repair never got a turn.
let full = self.rules.node_limit;
if self.start.elapsed().as_secs_f64() > self.rules.time_limit / 3.0 {
self.rules.node_limit = full.min(100_000);
}
// One first try may not take much of the run either: on benchmark B a USB line in its
// connector took 100 of 240 s to fail, and the last tasks never had a turn.
// Nor may the hard ones together: each turn gets a share of what is left, four times the
// even split, so easy tasks leave their time to the hard ones but the last tasks always
// have a turn. a flight controller board: a dozen stuck data lines took the whole pass, and
// nine joins of a millimetre or two (an MCU's VCAP pin to its capacitor) were never tried.
let left = (self.rules.time_limit - self.start.elapsed().as_secs_f64()).max(0.0);
// OFF unless ADOM_ROUTE_SHARE is set. Measured 2026-11-10: on benchmark C the share cut the
// in-level repairs short and the run ended at 293 of 302 instead of 300, and on the
// flight controller it changed nothing (its time went to rail taps, fixed in post.rs).
let share = if std::env::var_os("ADOM_ROUTE_SHARE").is_none() { f64::INFINITY } else { (left / (queued - turn_no).max(1) as f64 * 4.0).max(1.0) };
let deadline = self.rules.deadline;
let turn = Instant::now() + std::time::Duration::from_secs_f64((self.rules.time_limit / 30.0).min(share));
self.rules.deadline = deadline.map(|d| d.min(turn));
let done = self.joined(&task) || self.try_route(&task);
self.rules.node_limit = full;
self.rules.deadline = deadline;
if done {
continue;
}
// Repair inside the level, so the hierarchy still decides who gets the room: only
// equal or lower priority may move here. Everything else waits for the final rounds,
// and past half the time so does this: every task gets its first try before any task
// gets a second.
if self.start.elapsed().as_secs_f64() > patience {
failed.push(task);
continue;
}
let turn = Instant::now() + std::time::Duration::from_secs_f64((self.rules.time_limit / 10.0).min(share));
self.rules.deadline = deadline.map(|d| d.min(turn));
let r = self.repair_one(&task, repair::Mode { escalate: false, swap: false });
self.rules.deadline = deadline;
match r {
repair::Repair::Fixed => {}
_ => failed.push(task),
}
}
*self.world.follow.borrow_mut() = None;
self.repair_rails(plan, failed)
}
}
/// A segment of a few microns between two others is a square corner in disguise, too small to be seen
/// as a chamfer or to be one. Put the real corner back, so the chamfer below can do its job.
fn collapse_jogs(pts: &mut Vec<(P, usize)>) {
let jog = (0.03 * NM) as i64;
let mut i = 1;
while i + 2 < pts.len() {
let (a, b, c, d) = (pts[i - 1], pts[i], pts[i + 1], pts[i + 2]);
let short = (b.0 .0 - c.0 .0).abs().max((b.0 .1 - c.0 .1).abs()) < jog;
if short && a.1 == b.1 && b.1 == c.1 && c.1 == d.1 && b.0 != c.0 {
if let (Some(d1), Some(d2)) = (dir_of(a.0, b.0), dir_of(c.0, d.0)) {
if let Some(x) = line_meet(b.0, d1, c.0, d2) {
pts[i] = (x, b.1);
pts.remove(i + 1);
continue;
}
}
}
i += 1;
}
}
/// Where the octilinear line through `p` in direction `dp` meets the one through `q` in direction `dq`.
fn line_meet(p: P, dp: u8, q: P, dq: u8) -> Option<P> {
let (ax, ay) = DIRS[dp as usize];
let (bx, by) = DIRS[dq as usize];
let det = ax * by - ay * bx;
if det == 0 {
return None;
}
let t = ((q.0 - p.0) * by - (q.1 - p.1) * bx) / det;
Some((p.0 + ax * t, p.1 + ay * t))
}
fn chain_pads(board: &Board, pads: &[usize]) -> Vec<usize> {
let mut left: Vec<usize> = pads.to_vec();
let Some(first) = left.pop() else { return Vec::new() };
let mut seq = vec![first];
while !left.is_empty() {
let c: V = board.pads[*seq.last().unwrap()].center.into();
let (i, _) = left.iter().enumerate().map(|(i, &p)| (i, hypot(sub(c, board.pads[p].center.into())))).min_by(|a, b| a.1.total_cmp(&b.1)).unwrap();
seq.push(left.swap_remove(i));
}
seq
}
/// Remove a length from each end of a polyline.
fn trim_each(pts: &[P], from_start: f64, from_end: f64) -> Vec<P> {
let cut = |v: Vec<P>, amount: f64| -> Vec<P> {
let mut left = amount;
let mut out = v;
while out.len() >= 2 {
let l = hypot(sub(out[0].into(), out[1].into()));
if l <= left {
left -= l;
out.remove(0);
} else {
let t = left / l;
let a = out[0];
out[0] = snap(((a.0 as f64 + (out[1].0 - a.0) as f64 * t) as i64, (a.1 as f64 + (out[1].1 - a.1) as f64 * t) as i64));
break;
}
}
out
};
let mut f = cut(pts.to_vec(), from_start);
f.reverse();
let mut g = cut(f, from_end);
g.reverse();
g
}
/// Parallel copy of a polyline at a signed distance, mitred at each bend.
fn offset_polyline(pts: &[P], d: f64) -> Vec<P> {
let n = pts.len();
let mut out = Vec::with_capacity(n);
let normal = |a: P, b: P| -> V {
let (x, y) = ((b.0 - a.0) as f64, (b.1 - a.1) as f64);
let l = (x * x + y * y).sqrt().max(1.0);
V(-y / l, x / l)
};
for i in 0..n {
let p: V = pts[i].into();
let q = if i == 0 {
let m = normal(pts[0], pts[1]);
V(p.0 + m.0 * d, p.1 + m.1 * d)
} else if i == n - 1 {
let m = normal(pts[n - 2], pts[n - 1]);
V(p.0 + m.0 * d, p.1 + m.1 * d)
} else {
let (m1, m2) = (normal(pts[i - 1], pts[i]), normal(pts[i], pts[i + 1]));
let bis = V(m1.0 + m2.0, m1.1 + m2.1);
let l = hypot(bis).max(1e-9);
let u = V(bis.0 / l, bis.1 / l);
let scale = d / dot(u, m1).max(0.2);
V(p.0 + u.0 * scale, p.1 + u.1 * scale)
};
out.push(snap(to_p(q)));
}
out
}
/// Whether a straight stub from a pad to the nearest point of its own fill meets no other net.
fn zone_stub_clear(board: &Board, rules: &Rules, world: &World, pad: usize, z: usize) -> bool {
let p = &board.pads[pad];
let (net, layer, poly) = (p.net, world.zones[z].1, &world.zones[z].2);
let c: V = p.center.into();
let n = poly.len();
let mut near = (f64::INFINITY, c);
for i in 0..n {
let (a, b) = (poly[i], poly[(i + 1) % n]);
let ab = sub(b, a);
let t = (dot(sub(c, a), ab) / dot(ab, ab).max(1.0)).clamp(0.0, 1.0);
let q = V(a.0 + ab.0 * t, a.1 + ab.1 * t);
let d = hypot(sub(c, q));
if d < near.0 {
near = (d, q);
}
}
let need = rules.neck as f64 / 2.0 + rules.clearance as f64;
let bb = (c.0.min(near.1 .0) - need, c.1.min(near.1 .1) - need, c.0.max(near.1 .0) + need, c.1.max(near.1 .1) + need);
let mut clear = true;
world.layers[layer].visit(bb, |o| {
if o.net != net && o.shape.dist_seg(c, near.1) < need {
clear = false;
}
clear
});
clear
}
pub struct Plan {
pub tasks: Vec<Task>,
pub pairs: Vec<(NetId, NetId, i64, i64)>,
pub skipped_pads: usize,
}
/// Turn the board into a list of work: what the copper already joins is not routed again.
pub fn make_plan(board: &Board, rules: &Rules) -> Plan {
let groups = conn::pad_groups(board, &[]);
let infos = classify(board, rules);
let world = build_world(board, rules);
let mut tasks = Vec::new();
let mut pairs = Vec::new();
let planes = board.plane_nets();
let mut skipped = 0;
for pr in &rules.pairs {
let (Some(&p), Some(&n)) = (board.net_ids.get(&pr.p), board.net_ids.get(&pr.n)) else { continue };
let open = |net: NetId| groups.get(&net).map(|g| g.len() > 1).unwrap_or(false);
if open(p) && open(n) {
// A pair is never tighter than DRC allows between its own two nets.
pairs.push((p, n, pr.width, pr.gap.max(rules.clearance_for(p, n))));
}
}
let in_pair: HashSet<NetId> = pairs.iter().flat_map(|x| [x.0, x.1]).collect();
for info in &infos {
if in_pair.contains(&info.net) {
continue;
}
let g = groups.get(&info.net).cloned().unwrap_or_default();
if info.level == Level::PlaneFanout && planes.contains_key(&info.net) {
// Pads the plane doesn't already reach each get their own via.
let plane_layers = &planes[&info.net];
for &pad in &info.pads {
let p = &board.pads[pad];
if p.layers.iter().any(|l| plane_layers.contains(l)) {
continue;
}
let joined_to_plane = g.iter().any(|grp| grp.contains(&pad) && grp.iter().any(|&o| board.pads[o].layers.iter().any(|l| plane_layers.contains(l))));
if joined_to_plane {
skipped += 1;
continue;
}
tasks.push(Task { net: info.net, level: Level::PlaneFanout, a: pad, b: pad, main: false, zone: None });
}
continue;
}
// A Kelvin tap is its own dedicated copper, routed first (4.2); the rest of the net is
// planned without the amplifier's pins, so nothing else can land on them.
let sense: HashSet<usize> = info.taps.iter().flat_map(|t| t[..t.len() - 1].iter().copied()).collect();
for t in &info.taps {
tasks.extend(t.windows(2).map(|w| Task { net: info.net, level: Level::Kelvin, a: w[0], b: w[1], main: false, zone: None }));
}
let rest = NetInfo { net: info.net, level: info.level, pads: info.pads.iter().copied().filter(|p| !sense.contains(p)).collect(), why: String::new(), switching: info.switching, taps: Vec::new() };
let info = &rest;
let planned = if info.level == Level::Power {
let zones: Vec<(usize, usize, &Vec<V>)> = (0..world.zones.len()).filter(|&z| world.zones[z].0 == info.net && world.route_layers.contains(&world.zones[z].1)).map(|z| (z, world.zones[z].1, &world.zones[z].2)).collect();
let live: Vec<Vec<usize>> = g.iter().map(|grp| grp.iter().copied().filter(|p| info.pads.contains(p)).collect::<Vec<_>>()).filter(|grp: &Vec<usize>| !grp.is_empty()).collect();
if live.len() < 2 && zones.is_empty() { Vec::new() } else { plan_rail(board, info, &live, &zones, &|pad, z| zone_stub_clear(board, rules, &world, pad, z), crate::post::cap_reach(rules)) }
} else {
plan_net(board, info, &g)
};
tasks.extend(planned);
}
Plan { tasks, pairs, skipped_pads: skipped }
}
#[cfg(test)]
mod finish_tests {
use super::*;
#[test]
fn a_micron_jog_is_a_square_corner_again() {
let n = |x: f64, y: f64| (mm(x), mm(y));
let mut pts = vec![(n(0.0, 0.0), 0), (n(1.0, 0.0), 0), (n(1.01, 0.01), 0), (n(1.01, 1.0), 0)];
collapse_jogs(&mut pts);
assert_eq!(pts, vec![(n(0.0, 0.0), 0), (n(1.01, 0.0), 0), (n(1.01, 1.0), 0)]);
}
}