/**
* Orthogonal edge routing — wires that behave like circuitry.
*
* Edges used to be bezier curves drawn straight from A to B, so they ran BEHIND
* whatever sat between them. At 105 edges on the system level that is a wall of
* spaghetti that hides the layout underneath it.
*
* These routes are axis-aligned and obstacle-aware: they leave a node's right
* edge, run in the free channel between columns, and enter the target's left
* edge. A route never crosses a node it does not belong to, which is the
* invariant the tests check.
*
* Edges leaving the SAME node share a trunk, and where a branch turns off the
* trunk there is a JUNCTION — one wire with taps, rather than several wires
* drawn on top of each other.
*
* Pure: geometry in, geometry out. No DOM.
*/
const DEFAULTS = {
// Routing resolution, and the minimum clearance around a node.
//
// Left undefined it is CHOSEN from the work the board actually needs: cost is
// edges x cells, and cells is area/grid^2, so a big board routes coarsely
// rather than not at all. Measured before this existed, one 226-node module
// took 55 SECONDS at a fixed grid of 40 — a frozen tab, not a slow render.
grid: undefined,
targetVisits: 700000, // the work to aim for when choosing a grid
clearance: 10, // how far a route stays off a node's edge
turnCost: 6, // a turn costs this many grid steps, so paths stay straight
// What it costs to run down a lane another wire is already using.
//
// Without this every wire takes the same shortest channel and they stack
// exactly on top of each other, which reads as one wire — or as a short
// between two circuits that are not connected at all. Siblings are exempt:
// wires from one source SHOULD share a trunk, that is what makes a junction.
laneCost: 9,
maxCells: 400000, // refuse to search a board this big rather than hang the tab
// The work budget, in cell-visits across ALL edges.
//
// Cost is edges x search area, and it runs away: measured on a real scan,
// 108 edges over 3k cells took 0.8s but 316 edges over 22k cells took 55
// SECONDS, which is not a slow render, it is a frozen tab. Past this budget
// the caller is told to draw curves instead.
budget: 4000000
}
/**
* @param {Array} nodes [{ id, x, y, w, h }]
* @param {Array} links [{ from, to }]
* @returns {object} { routes: [{ from, to, points: [{x,y}] }], failed }
*/
export function routeEdges (nodes, links, opts = {}) {
const O = { ...DEFAULTS, ...opts }
const byId = new Map(nodes.map(n => [n.id, n]))
if (O.grid === undefined) O.grid = chooseGrid(nodes, links, O)
const valid = links.filter(l => byId.has(l.from) && byId.has(l.to))
if (valid.length === 0) return { routes: [], failed: 0 }
// --- the board: a grid where a cell is blocked if a node covers it.
let minX = Infinity; let minY = Infinity; let maxX = -Infinity; let maxY = -Infinity
for (const n of nodes) {
minX = Math.min(minX, n.x)
minY = Math.min(minY, n.y)
maxX = Math.max(maxX, n.x + n.w)
maxY = Math.max(maxY, n.y + n.h)
}
// Margin so a route can always go around the outside.
const pad = O.grid * 6
minX -= pad; minY -= pad; maxX += pad; maxY += pad
const cols = Math.ceil((maxX - minX) / O.grid) + 1
const rows = Math.ceil((maxY - minY) / O.grid) + 1
if (cols * rows > O.maxCells) {
// Too big to search: say so rather than hang, and let the caller fall back.
return { routes: [], failed: valid.length, tooLarge: true }
}
// Refuse the job rather than freeze: the caller falls back to curves.
if (valid.length * cols * rows > O.budget) {
return { routes: [], failed: valid.length, overBudget: true }
}
const blocked = new Uint8Array(cols * rows)
const owner = new Int32Array(cols * rows).fill(-1)
const idx = (cx, cy) => cy * cols + cx
const toCellX = (x) => Math.round((x - minX) / O.grid)
const toCellY = (y) => Math.round((y - minY) / O.grid)
nodes.forEach((n, i) => {
const x0 = toCellX(n.x - O.clearance)
const x1 = toCellX(n.x + n.w + O.clearance)
const y0 = toCellY(n.y - O.clearance)
const y1 = toCellY(n.y + n.h + O.clearance)
for (let cy = Math.max(0, y0); cy <= Math.min(rows - 1, y1); cy++) {
for (let cx = Math.max(0, x0); cx <= Math.min(cols - 1, x1); cx++) {
blocked[idx(cx, cy)] = 1
owner[idx(cx, cy)] = i
}
}
})
// Edges from one source share a trunk: the channel just right of that node.
const trunkOf = new Map()
for (const l of valid) {
if (trunkOf.has(l.from)) continue
const n = byId.get(l.from)
trunkOf.set(l.from, n.x + n.w + O.grid * 2)
}
// Which source last claimed each cell, so a later route can tell "my own
// trunk" from "somebody else's lane".
const laneOwner = new Map()
const routes = []
let failed = 0
for (const l of valid) {
const a = byId.get(l.from)
const b = byId.get(l.to)
const path = routeOne(a, b, trunkOf.get(l.from), l.fromPoint, l.toPoint, l.from)
if (path) {
routes.push({ from: l.from, to: l.to, points: path })
claimLanes(path, l.from)
} else failed++
}
// All or nothing: a board where many edges could not be routed looks worse
// half-orthogonal than it does as plain curves.
if (failed > routes.length * 0.15) {
return { routes: [], failed: valid.length, mixedRefused: true }
}
return { routes, failed }
// Mark every cell a finished route runs through, so the next one prefers a
// free lane beside it rather than the same one.
function claimLanes (points, source) {
for (let i = 1; i < points.length; i++) {
const from = points[i - 1]
const to = points[i]
const steps = Math.max(
Math.abs(toCellX(to.x) - toCellX(from.x)),
Math.abs(toCellY(to.y) - toCellY(from.y))
)
for (let step = 0; step <= steps; step++) {
const t = steps === 0 ? 0 : step / steps
const cx = clampCell(toCellX(from.x + (to.x - from.x) * t), cols)
const cy = clampCell(toCellY(from.y + (to.y - from.y) * t), rows)
laneOwner.set(cy * cols + cx, source)
}
}
}
// --- one route, as grid cells, then simplified back into world points.
function routeOne (a, b, trunkX, fromPoint, toPoint, source) {
// A caller with real SOCKETS supplies the exact points the wire must meet;
// otherwise the ports sit where a header socket would be. Either way the
// first ROUTABLE cell is a full grid step clear of the node, outside its
// blocked halo.
const startY = fromPoint ? fromPoint.y : a.y + Math.min(a.h / 2, 10)
const endY = toPoint ? toPoint.y : b.y + Math.min(b.h / 2, 10)
const startWorld = { x: a.x + a.w + O.grid * 2, y: startY }
const endWorld = { x: b.x - O.grid * 2, y: endY }
const start = { cx: clampX(toCellX(startWorld.x)), cy: clampY(toCellY(startWorld.y)) }
const goal = { cx: clampX(toCellX(endWorld.x)), cy: clampY(toCellY(endWorld.y)) }
const aIdx = nodes.indexOf(a)
const bIdx = nodes.indexOf(b)
// Nothing is passable, not even the route's own endpoints: letting a route
// cross its own source is how a backward edge ended up running straight
// back THROUGH the node it came from.
const strict = (cx, cy) => !blocked[idx(cx, cy)]
// Only if that fails — a node boxed in on every side — allow the route to
// pass through its own endpoints rather than dropping the edge.
const permissive = (cx, cy) => {
const i = idx(cx, cy)
return !blocked[i] || owner[i] === aIdx || owner[i] === bIdx
}
const trunkCell = trunkX === undefined ? null : clampX(toCellX(trunkX))
const cells = astar(start, goal, strict, trunkCell, source) ||
astar(start, goal, permissive, trunkCell, source)
if (!cells) return null
const points = cells.map(c => ({ x: minX + c.cx * O.grid, y: minY + c.cy * O.grid }))
// Meet the exact socket, without ever drawing a diagonal: step out
// horizontally from the socket, then take the grid's y in the free channel.
const exitX = points[0].x
const entryX = points[points.length - 1].x
const head = fromPoint
? [{ x: fromPoint.x, y: fromPoint.y }, { x: exitX, y: fromPoint.y }]
: [{ x: a.x + a.w, y: points[0].y }]
const tail = toPoint
? [{ x: entryX, y: toPoint.y }, { x: toPoint.x, y: toPoint.y }]
: [{ x: b.x, y: points[points.length - 1].y }]
return simplify([...head, ...points, ...tail])
}
function clampCell (v, limit) { return Math.max(0, Math.min(limit - 1, v)) }
function clampX (cx) { return Math.max(0, Math.min(cols - 1, cx)) }
function clampY (cy) { return Math.max(0, Math.min(rows - 1, cy)) }
/**
* A* with a TURN COST, which is what makes the result look like circuitry
* rather than a staircase: going straight is free, changing direction is not.
* A small bonus for running along the source's trunk keeps sibling edges
* together so they can share it.
*/
function astar (start, goal, passable, trunkCx, source) {
const startKey = start.cy * cols + start.cx
const goalKey = goal.cy * cols + goal.cx
// State is (cell, direction), keyed as a NUMBER rather than a string: the
// string concatenation was allocating once per expansion, and the open list
// was scanned linearly for its minimum, which is O(n) per pop. Between them
// they were most of the 55 seconds a big level used to take.
const stateOf = (cellKey, dir) => cellKey * 5 + dir
const gScore = new Map([[stateOf(startKey, 0), 0]])
const came = new Map()
const open = new MinHeap()
open.push(heuristic(start), { key: startKey, dir: 0, cx: start.cx, cy: start.cy })
const DIRS = [
{ dx: 1, dy: 0, id: 1 }, { dx: -1, dy: 0, id: 2 },
{ dx: 0, dy: 1, id: 3 }, { dx: 0, dy: -1, id: 4 }
]
let guard = 0
while (open.size > 0) {
if (++guard > O.maxCells) return null
const current = open.pop()
if (current.key === goalKey) return reconstruct(current)
for (const d of DIRS) {
const nx = current.cx + d.dx
const ny = current.cy + d.dy
if (nx < 0 || ny < 0 || nx >= cols || ny >= rows) continue
if (!passable(nx, ny)) continue
const turn = current.dir !== 0 && current.dir !== d.id ? O.turnCost : 0
const trunkBonus = trunkCx !== null && nx === trunkCx ? -0.4 : 0
// Somebody else's lane costs extra; my own source's trunk does not,
// because sharing it is the point.
const claimed = laneOwner.get(ny * cols + nx)
const lane = claimed !== undefined && claimed !== source ? O.laneCost : 0
const tentative = (gScore.get(stateOf(current.key, current.dir)) || 0) +
1 + turn + trunkBonus + lane
const nKey = ny * cols + nx
const stateKey = stateOf(nKey, d.id)
if (gScore.has(stateKey) && gScore.get(stateKey) <= tentative) continue
gScore.set(stateKey, tentative)
came.set(stateKey, { key: current.key, dir: current.dir, cx: current.cx, cy: current.cy })
open.push(tentative + heuristic({ cx: nx, cy: ny }), { key: nKey, dir: d.id, cx: nx, cy: ny })
}
}
return null
function heuristic (c) {
return Math.abs(c.cx - goal.cx) + Math.abs(c.cy - goal.cy)
}
function reconstruct (end) {
const out = [{ cx: end.cx, cy: end.cy }]
let cursor = { key: end.key, dir: end.dir, cx: end.cx, cy: end.cy }
let steps = 0
while (came.has(stateOf(cursor.key, cursor.dir))) {
if (++steps > O.maxCells) break
cursor = came.get(stateOf(cursor.key, cursor.dir))
out.push({ cx: cursor.cx, cy: cursor.cy })
}
return out.reverse()
}
}
}
/**
* Pick a routing resolution from the work the board needs.
*
* Cost is (edges x cells) and cells is area/grid^2, so grid ~ sqrt(edges x area
* / target). A small board gets a fine grid and tight clearance; a large one
* gets a coarse grid and still gets routed, which beats falling back to curves.
*/
function chooseGrid (nodes, links, O) {
if (nodes.length === 0 || links.length === 0) return 20
let minX = Infinity; let minY = Infinity; let maxX = -Infinity; let maxY = -Infinity
for (const n of nodes) {
minX = Math.min(minX, n.x); minY = Math.min(minY, n.y)
maxX = Math.max(maxX, n.x + n.w); maxY = Math.max(maxY, n.y + n.h)
}
const area = Math.max(1, (maxX - minX) * (maxY - minY))
// Capped at 45 on purpose. A coarser grid is faster but the clearance halo
// around each node is measured in CELLS, so past roughly the row gap it
// swallows the channels between stacked nodes and A* can find no path at all.
// Measured at grid ~120: favela-web routed 84 of 189 edges and the rest fell
// back to curves, which looks worse than either choice made consistently.
// Past what a routable grid can afford, the budget refuses the whole job.
const grid = Math.sqrt(links.length * area / Math.max(1, O.targetVisits))
return Math.max(20, Math.min(45, Math.round(grid / 5) * 5))
}
/** A binary min-heap: A* pops the cheapest state once per expansion. */
class MinHeap {
constructor () {
this.keys = []
this.values = []
}
get size () { return this.keys.length }
push (priority, value) {
this.keys.push(priority)
this.values.push(value)
let i = this.keys.length - 1
while (i > 0) {
const parent = (i - 1) >> 1
if (this.keys[parent] <= this.keys[i]) break
this.swap(parent, i)
i = parent
}
}
pop () {
const top = this.values[0]
const lastKey = this.keys.pop()
const lastValue = this.values.pop()
if (this.keys.length > 0) {
this.keys[0] = lastKey
this.values[0] = lastValue
let i = 0
for (;;) {
const l = i * 2 + 1
const r = l + 1
let small = i
if (l < this.keys.length && this.keys[l] < this.keys[small]) small = l
if (r < this.keys.length && this.keys[r] < this.keys[small]) small = r
if (small === i) break
this.swap(small, i)
i = small
}
}
return top
}
swap (a, b) {
const k = this.keys[a]; this.keys[a] = this.keys[b]; this.keys[b] = k
const v = this.values[a]; this.values[a] = this.values[b]; this.values[b] = v
}
}
/** Drop every point that does not change direction. */
function simplify (points) {
if (points.length <= 2) return points
const out = [points[0]]
for (let i = 1; i < points.length - 1; i++) {
const prev = out[out.length - 1]
const next = points[i + 1]
const straightX = Math.abs(prev.x - points[i].x) < 0.01 && Math.abs(points[i].x - next.x) < 0.01
const straightY = Math.abs(prev.y - points[i].y) < 0.01 && Math.abs(points[i].y - next.y) < 0.01
if (straightX || straightY) continue
out.push(points[i])
}
out.push(points[points.length - 1])
return out
}
/**
* Where routes from the same source part company.
*
* Three wires leaving one node and fanning out should read as a bus with taps,
* so the point a branch leaves the shared trunk gets a dot — the same thing a
* circuit diagram does, and for the same reason.
*/
export function findJunctions (routes) {
const bySource = new Map()
for (const r of routes) {
if (!bySource.has(r.from)) bySource.set(r.from, [])
bySource.get(r.from).push(r)
}
const junctions = []
for (const group of bySource.values()) {
if (group.length < 2) continue
const counts = new Map()
for (const r of group) {
// Every bend on this route is a candidate tap.
for (let i = 1; i < r.points.length - 1; i++) {
const key = Math.round(r.points[i].x) + ',' + Math.round(r.points[i].y)
counts.set(key, (counts.get(key) || 0) + 1)
}
}
for (const [key, degree] of counts) {
if (degree < 2) continue
const [x, y] = key.split(',').map(Number)
junctions.push({ x, y, degree })
}
}
junctions.sort((a, b) => a.x - b.x || a.y - b.y)
return junctions
}