Where parts are placed and where tracks and vias run on a board, with the wire length reported.
How the precision is kept
Placement is simulated annealing and routing is a grid search: both are heuristics whose result depends on the seed, the iteration count and the grid pitch, not on rounding. Final part positions are rounded to 0.001 mm. Track corners lie on grid points computed in 64-bit; the search keeps its path costs in a 32-bit array, which decides between paths but is not part of any coordinate.
Open item. Keep the router's path costs in a Float64Array.
Calculations under this policy
8 calculations in 2 source files. The code is read from the released app when this page loads. It is the calculation people run, not a copy kept for this page.
place.jsShared shell, every app64-bit4 calculationsReviewed
The estimate of total connection length reported before and after placement.
Σ over nets of (x_max − x_min) + (y_max − y_min)
A plain 64-bit sum over the nets of the bounding boxes of their pads.
place.js
lines 12 to 17
/** Half-perimeter wire length of every net at the current positions (mm). */
export function hpwl(board) {
const nets = new Map();
for (const p of board.parts) for (const pad of p.pads) { const n = p.padNets[pad.num]; if (!n) continue; const w = board.padWorld(p, pad); if (!nets.has(n)) nets.set(n, []); nets.get(n).push([w.x, w.y]); }
let t = 0; for (const pts of nets.values()) if (pts.length > 1) { const b = bbox(pts); t += (b[2] - b[0]) + (b[3] - b[1]); } return t;
}
Overlap and outline penalties
64-bit
The cost added when courtyards overlap or reach outside the board.
cost = 50 × (overlap area + area outside the margin)
Courtyard boxes are axis-aligned bounding boxes grown by half the gap. The weight 50 is a fixed number; the penalties steer the search and are not reported.
How the search cools from large moves to small ones.
T₀ = max(1, 0.15 (W + H)); T_end = 0.002 (W + H); T ← T × (T_end ÷ T₀)^(1 ÷ iterations)
The temperature is multiplied by a constant factor each iteration. A move is accepted when it lowers the cost, or with probability e^(−Δ ÷ T) drawn from a seeded 32-bit generator, so the same seed gives the same board.
place.js
lines 48 to 49
let T = Math.max(1, (W + H) * 0.15) * 1, cur = wl + pen; const Tend = 0.002 * (W + H);
const decay = Math.pow(Tend / T, 1 / Math.max(1, iterations));
Final part positions
64-bit
The positions stored on the board when placement ends.
x, y = round(value × 1000) ÷ 1000
After the search every part position, locked parts included, is rounded to 0.001 mm and stored. The wire length reported as after is computed from the rounded positions.
pitch = (track width + clearance) ÷ 2 by default; x = ox + i × pitch
Grid coordinates are computed from the index in 64-bit. The origin is the outline's corner less one pitch, so grid points do not in general fall on pad centers.
Which grid points a track or a via of another net may not use.
blocked when distance to copper < clearance + track width ÷ 2 + 0.25 × pitch
Each grid point's distance to each copper shape is computed in 64-bit and compared with the grown clearance. The quarter-pitch slack covers the straight segments between grid points, so the map keeps more distance than the rule asks by that amount.
route.js
lines 31 to 37
const raster = (it) => { // copper with no net blocks everyone (owner -2)
const n = it.net ? nid(it.net) : -2, box = primBox(it.prim);
for (const [arr, extra] of [[blk, R.clearance + R.trackWidth / 2 + slack], [blkVia, R.clearance + R.viaDia / 2 + slack]]) {
const r = extra, x0 = Math.max(0, Math.floor((box[0] - r - ox) / pitch)), x1 = Math.min(Wc - 1, Math.ceil((box[2] + r - ox) / pitch)), y0 = Math.max(0, Math.floor((box[1] - r - oy) / pitch)), y1 = Math.min(Hc - 1, Math.ceil((box[3] + r - oy) / pitch));
for (const l of it.layers) { const li = board.layers.indexOf(l); if (li < 0) continue; for (let y = y0; y <= y1; y++) for (let x = x0; x <= x1; x++) if (pointPrimDist([cx(x), cy(y)], it.prim) < r) claim(arr[li], y * Wc + x, n); }
}
};
Path search
64-bit
The cheapest path on the grid from a pad to the copper already routed for its net.
step cost 1, diagonal 1.4142, against the layer's direction × 1.4, via 14 per layer
Path costs are stored in and read back from a Float32Array, so paths are compared on 32-bit sums; the cost only decides which grid cells the track uses and is not returned. The track's coordinates are grid points in 64-bit. The diagonal cost is 1.4142, a rounded √2.
route.js
lines 111 to 130
function search(tgt, tree, n) {
const dist = new Float32Array(L * N).fill(Infinity), prev = new Int32Array(L * N).fill(-1), heap = new Heap();
for (const [li, x, y] of tgt.cells) { const s = li * N + y * Wc + x; dist[s] = 0; heap.push(0, s); }
const dirs = [[1, 0, 1], [-1, 0, 1], [0, 1, 1], [0, -1, 1], [1, 1, 1.4142], [1, -1, 1.4142], [-1, 1, 1.4142], [-1, -1, 1.4142]];
let exp = 0;
while (heap.size) {
const s = heap.pop(), li = Math.floor(s / N), r = s - li * N, y = Math.floor(r / Wc), x = r - y * Wc, d = dist[s];
if (tree[s]) { const path = []; let c = s; while (c !== -1) { const l = Math.floor(c / N), rr = c - l * N, yy = Math.floor(rr / Wc); path.push([l, rr - yy * Wc, yy]); c = prev[c]; } stats.expansions += exp; return path.reverse(); }
if (++exp > budget) { stats.expansions += exp; return null; }
for (const [dx, dy, c0] of dirs) {
const nx = x + dx, ny = y + dy; if (nx < 1 || ny < 1 || nx >= Wc - 1 || ny >= Hc - 1) continue; const ni = ny * Wc + nx;
if (!free(blk, li, ni, n)) continue;
if (dx && dy && (!free(blk, li, y * Wc + nx, n) || !free(blk, li, ny * Wc + x, n))) continue;
let c = c0; if (opts.preferDirections !== false && L > 1) { const horiz = li % 2 === 0; if ((dy && !dx && horiz) || (dx && !dy && !horiz)) c *= 1.4; }
const ns = li * N + ni, nd = d + c; if (nd < dist[ns]) { dist[ns] = nd; prev[ns] = s; heap.push(nd, ns); }
}
for (let l2 = 0; l2 < L; l2++) { if (l2 === li) continue; const i = y * Wc + x; if (!free(blkVia, l2, i, n) || !free(blkVia, li, i, n) || !free(blk, l2, i, n)) continue; const ns = l2 * N + i, nd = d + viaCost * Math.abs(l2 - li); if (nd < dist[ns]) { dist[ns] = nd; prev[ns] = s; heap.push(nd, ns); } }
}
stats.expansions += exp; return null;
}
Track points
64-bit
The corner points of a routed track.
drop a point when |(b − a) × (c − b)| ≤ 1e-9
Grid points on a straight run are removed with an absolute test on the cross product. A track that starts outside its pad gets one extra segment from the pad center to the first grid point.
route.js
lines 94 to 97
const pts = sg.map(([, x, y]) => [cx(x), cy(y)]); const simp = [pts[0]];
for (let k = 1; k + 1 < pts.length; k++) { const a = simp[simp.length - 1], b = pts[k], c = pts[k + 1]; if (Math.abs((b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0])) > 1e-9) simp.push(b); }
if (pts.length > 1) simp.push(pts[pts.length - 1]);
if (si === 0 && pointPrimDist(simp[0], tgt.p.prim) > 0) simp.unshift([tgt.p.pad.x, tgt.p.pad.y]); // only a start outside the pad needs a stub in
In detail
Method
Simulated annealing on half-perimeter wire length plus overlap and outline penalties (the file cites Kirkpatrick et al. 1983); wave routing on a multi-layer grid with 45° moves and vias (the file cites Lee 1961 and Hart, Nilsson and Raphael 1968).
Number types
64-bit numbers for positions and costs in placement; Int32Array obstacle maps, a Float32Array of path costs and Int32Array back-pointers in routing.
Tolerances
Overlap and outside counts use 1e-9. Collinear track points are dropped when the cross product is at most 1e-9. Diagonal step cost 1.4142.
Checked by
The engines test runs a three-part example and checks that all three nets are routed and the design rule check is clean.
Limits
Grid pitch defaults to (track width + clearance) ÷ 2; obstacles are grown by a quarter pitch of slack. Tracks start on the grid, with a stub from the pad center when the first grid point is outside the pad.
Approach: 64-bit, stated limit
The arithmetic is 64-bit, but the method or the data sets the accuracy: a solver tolerance, a mesh, a step size, a datum shift, a table. The limit is stated where the result is shown.