import { test } from 'brittle'
import { routeEdges, findJunctions } from '../lib/floor/routing.js'
// Edges were drawn as bezier curves straight from A to B, so they ran BEHIND
// whatever happened to be in between. At 105 edges that is a wall of spaghetti.
// These routes are orthogonal and obstacle-aware: they look like circuitry
// because they behave like it.
function rect (id, x, y, w = 200, h = 60) {
return { id, x, y, w, h }
}
function pointInRect (p, r) {
return p.x > r.x && p.x < r.x + r.w && p.y > r.y && p.y < r.y + r.h
}
// Does a horizontal/vertical segment pass through a rectangle?
function segmentHitsRect (a, b, r) {
const minX = Math.min(a.x, b.x)
const maxX = Math.max(a.x, b.x)
const minY = Math.min(a.y, b.y)
const maxY = Math.max(a.y, b.y)
return minX < r.x + r.w && maxX > r.x && minY < r.y + r.h && maxY > r.y
}
test('routing: a route is orthogonal — every segment is horizontal or vertical', (t) => {
const nodes = [rect('a', 0, 0), rect('b', 400, 200)]
const { routes } = routeEdges(nodes, [{ from: 'a', to: 'b' }])
t.is(routes.length, 1, 'one route')
const pts = routes[0].points
t.ok(pts.length >= 2, 'with at least two points')
for (let i = 1; i < pts.length; i++) {
const dx = Math.abs(pts[i].x - pts[i - 1].x)
const dy = Math.abs(pts[i].y - pts[i - 1].y)
t.ok(dx < 0.01 || dy < 0.01, 'segment ' + i + ' is axis-aligned')
}
})
test('routing: NO route passes through a node — the whole point', (t) => {
// c sits directly between a and b, which is exactly where a straight line
// would go.
const nodes = [rect('a', 0, 200), rect('c', 300, 180, 200, 100), rect('b', 700, 200)]
const { routes } = routeEdges(nodes, [{ from: 'a', to: 'b' }])
const pts = routes[0].points
t.ok(pts.length > 2, 'it had to bend: ' + pts.length + ' points')
for (let i = 1; i < pts.length; i++) {
t.absent(segmentHitsRect(pts[i - 1], pts[i], nodes[1]), 'segment ' + i + ' clears the obstacle')
}
})
test('routing: a clear shot stays straight, no gratuitous bends', (t) => {
const nodes = [rect('a', 0, 100), rect('b', 400, 100)]
const { routes } = routeEdges(nodes, [{ from: 'a', to: 'b' }])
const pts = routes[0].points
const ys = new Set(pts.map(p => Math.round(p.y)))
t.is(ys.size, 1, 'a clear horizontal run has one y: ' + [...ys].join(','))
})
test('routing: every route clears every node, on a crowded board', (t) => {
const nodes = []
for (let col = 0; col < 5; col++) {
for (let row = 0; row < 4; row++) {
nodes.push(rect('n' + col + row, col * 330, row * 120))
}
}
const links = [
{ from: 'n00', to: 'n43' }, { from: 'n01', to: 'n40' },
{ from: 'n03', to: 'n20' }, { from: 'n10', to: 'n33' },
{ from: 'n21', to: 'n02' }
]
const { routes } = routeEdges(nodes, links)
t.is(routes.length, links.length, 'every link routed')
let hits = 0
for (const route of routes) {
const endpoints = new Set([route.from, route.to])
for (let i = 1; i < route.points.length; i++) {
for (const n of nodes) {
if (endpoints.has(n.id)) continue
if (segmentHitsRect(route.points[i - 1], route.points[i], n)) hits++
}
}
}
t.is(hits, 0, 'no segment crosses a node it does not belong to')
})
test('routing: edges leaving one node share a trunk and get a JUNCTION', (t) => {
// One source feeding three targets should look like a bus with taps, not
// three separate wires drawn over each other.
const nodes = [rect('src', 0, 200), rect('t1', 400, 0), rect('t2', 400, 200), rect('t3', 400, 400)]
const links = [{ from: 'src', to: 't1' }, { from: 'src', to: 't2' }, { from: 'src', to: 't3' }]
const { routes } = routeEdges(nodes, links)
const junctions = findJunctions(routes)
t.ok(junctions.length > 0, 'there are junctions: ' + junctions.length)
for (const j of junctions) {
t.ok(j.degree >= 2, 'a junction joins at least two routes')
t.ok(Number.isFinite(j.x) && Number.isFinite(j.y), 'and has a position')
}
// Every route that BENDS leaves through the same trunk. One that has a clear
// straight shot does not detour to join it — adding bends to a wire that does
// not need them is the opposite of the goal.
const bending = routes.filter(r => r.points.length > 2)
t.ok(bending.length >= 2, 'at least two routes bend: ' + bending.length)
const trunkXs = new Set(bending.map(r => Math.round(r.points[1].x)))
t.is(trunkXs.size, 1, 'and they share one trunk: ' + [...trunkXs].join(','))
})
test('routing: a backward edge goes around rather than through', (t) => {
const nodes = [rect('a', 600, 100), rect('b', 0, 100)]
const { routes } = routeEdges(nodes, [{ from: 'a', to: 'b' }])
const pts = routes[0].points
t.ok(pts.length >= 4, 'it takes a path around: ' + pts.length + ' points')
for (let i = 1; i < pts.length; i++) {
for (const n of nodes) {
if (n.id === 'a' || n.id === 'b') continue
t.absent(segmentHitsRect(pts[i - 1], pts[i], n), 'clears everything')
}
}
})
// How much of segment A is covered by a collinear segment of B.
function sharedLength (a1, a2, b1, b2) {
const aVert = Math.abs(a1.x - a2.x) < 0.01
const bVert = Math.abs(b1.x - b2.x) < 0.01
if (aVert !== bVert) return 0
if (aVert) {
if (Math.abs(a1.x - b1.x) > 0.01) return 0
const lo = Math.max(Math.min(a1.y, a2.y), Math.min(b1.y, b2.y))
const hi = Math.min(Math.max(a1.y, a2.y), Math.max(b1.y, b2.y))
return Math.max(0, hi - lo)
}
if (Math.abs(a1.y - b1.y) > 0.01) return 0
const lo = Math.max(Math.min(a1.x, a2.x), Math.min(b1.x, b2.x))
const hi = Math.min(Math.max(a1.x, a2.x), Math.max(b1.x, b2.x))
return Math.max(0, hi - lo)
}
function overlapBetween (r1, r2) {
let total = 0
for (let i = 1; i < r1.points.length; i++) {
for (let j = 1; j < r2.points.length; j++) {
total += sharedLength(r1.points[i - 1], r1.points[i], r2.points[j - 1], r2.points[j])
}
}
return total
}
test('routing: wires from DIFFERENT sources get their own lane', (t) => {
// Unrelated wires drawn down the same channel sit exactly on top of each
// other, which reads as one wire — or worse, as a short between two circuits
// that are not connected at all.
const nodes = [
rect('a1', 0, 0), rect('a2', 0, 200), rect('a3', 0, 400),
rect('b1', 700, 400), rect('b2', 700, 200), rect('b3', 700, 0)
]
const links = [
{ from: 'a1', to: 'b1' }, { from: 'a2', to: 'b2' }, { from: 'a3', to: 'b3' }
]
const { routes } = routeEdges(nodes, links)
for (let i = 0; i < routes.length; i++) {
for (let j = i + 1; j < routes.length; j++) {
const shared = overlapBetween(routes[i], routes[j])
t.ok(shared < 60, routes[i].from + ' and ' + routes[j].from +
' share only ' + Math.round(shared) + 'px of lane')
}
}
})
test('routing: wires from the SAME source still share their trunk', (t) => {
// Lane separation must not break the bus: siblings SHOULD run together, that
// is what makes a junction a junction rather than a crossing.
const nodes = [rect('src', 0, 200), rect('t1', 600, 0), rect('t2', 600, 400)]
const { routes } = routeEdges(nodes, [{ from: 'src', to: 't1' }, { from: 'src', to: 't2' }])
t.is(routes.length, 2, 'both routed')
t.ok(overlapBetween(routes[0], routes[1]) > 0, 'siblings do share a trunk')
})
test('routing: deterministic, and degenerate input does not throw', (t) => {
const nodes = [rect('a', 0, 0), rect('b', 300, 0)]
const links = [{ from: 'a', to: 'b' }]
t.alike(routeEdges(nodes, links), routeEdges(nodes, links), 'same in, same out')
t.alike(routeEdges([], []).routes, [], 'empty')
t.alike(routeEdges(nodes, [{ from: 'a', to: 'nope' }]).routes, [], 'a link to nothing is dropped')
t.alike(findJunctions([]), [], 'no routes, no junctions')
})
test('routing: explicit socket ports are met exactly, still with no diagonal', (t) => {
// The Nodes tab anchors edges to SOCKETS, not to node edges, so a router that
// only knows about rectangles would move every wire off its connector.
const nodes = [rect('a', 0, 0, 200, 120), rect('b', 500, 200, 200, 120)]
const from = { x: 200, y: 44 } // a's third output socket
const to = { x: 500, y: 266 } // b's second input socket
const { routes } = routeEdges(nodes, [{ from: 'a', to: 'b', fromPoint: from, toPoint: to }])
const pts = routes[0].points
t.alike(pts[0], from, 'starts exactly on the source socket')
t.alike(pts[pts.length - 1], to, 'ends exactly on the target socket')
for (let i = 1; i < pts.length; i++) {
const dx = Math.abs(pts[i].x - pts[i - 1].x)
const dy = Math.abs(pts[i].y - pts[i - 1].y)
t.ok(dx < 0.01 || dy < 0.01, 'segment ' + i + ' is axis-aligned')
}
})