ShiboSoftwareDev/nema8-20mm-dual-usbc-stepper-controller

scripts/find-signal-escape.mjs

import fs from "node:fs"

const [startXText, startYText, layer = "top", xminText = "-9", xmaxText = "9",
  yminText = "-9", ymaxText = "9", stepText = "0.05", excludeFromText = "125"] = process.argv.slice(2)
const [startX, startY, xmin, xmax, ymin, ymax, step] =
  [startXText, startYText, xminText, xmaxText, yminText, ymaxText, stepText].map(Number)
const excludeFrom = Number(excludeFromText)
if (![startX, startY, xmin, xmax, ymin, ymax, step].every(Number.isFinite)) {
  throw new Error("usage: node scripts/find-signal-escape.mjs START_X START_Y LAYER XMIN XMAX YMIN YMAX [STEP]")
}

const circuit = JSON.parse(fs.readFileSync("dist/index/circuit.json", "utf8"))
  .filter((element) => !String(element.type).endsWith("error"))
const sourceIndexes = (element) => (`${element.source_trace_id ?? ""} ${element.pcb_trace_id ?? ""}`
  .match(/source_trace_(\d+)/g) ?? []).map((id) => Number(id.slice("source_trace_".length)))
const excludedTraceIds = new Set(circuit
  .filter((element) => element.type === "pcb_trace" &&
    sourceIndexes(element).some((index) => index >= excludeFrom))
  .map((element) => element.pcb_trace_id))
const base = circuit.filter((element) =>
  !(element.type === "pcb_trace" && excludedTraceIds.has(element.pcb_trace_id)) &&
  !(element.type === "pcb_via" && excludedTraceIds.has(element.pcb_trace_id)))

const pointSegmentDistance = (px, py, ax, ay, bx, by) => {
  const dx = bx - ax
  const dy = by - ay
  const lengthSquared = dx * dx + dy * dy
  const t = lengthSquared === 0 ? 0 : Math.max(0, Math.min(1,
    ((px - ax) * dx + (py - ay) * dy) / lengthSquared))
  return Math.hypot(px - (ax + t * dx), py - (ay + t * dy))
}
const pointRectDistance = (x, y, element) => {
  const angle = -((element.rotation ?? 0) * Math.PI / 180)
  const dx = x - element.x
  const dy = y - element.y
  const localX = dx * Math.cos(angle) - dy * Math.sin(angle)
  const localY = dx * Math.sin(angle) + dy * Math.cos(angle)
  const outsideX = Math.max(Math.abs(localX) - (element.width ?? 0) / 2, 0)
  const outsideY = Math.max(Math.abs(localY) - (element.height ?? 0) / 2, 0)
  return Math.hypot(outsideX, outsideY)
}

const startPad = circuit
  .filter((element) => element.type === "pcb_smtpad" && element.layer === layer &&
    Number.isFinite(element.x) && Number.isFinite(element.y))
  .sort((a, b) => Math.hypot(a.x - startX, a.y - startY) - Math.hypot(b.x - startX, b.y - startY))[0]
if (!startPad || Math.hypot(startPad.x - startX, startPad.y - startY) > 0.01) {
  throw new Error(`No ${layer} pad at ${startX},${startY}`)
}

const vias = base.filter((element) => element.type === "pcb_via")
const pads = base.filter((element) => ["pcb_smtpad", "pcb_plated_hole"].includes(element.type))
const holes = base.filter((element) => element.type === "pcb_hole")
const segments = base.filter((element) => element.type === "pcb_trace").flatMap((trace) => {
  const output = []
  let previous
  for (const point of trace.route ?? []) {
    if (point.route_type === "via") {
      previous = undefined
      continue
    }
    if (point.route_type !== "wire") continue
    if (previous?.layer === point.layer) output.push({
      ax: previous.x, ay: previous.y, bx: point.x, by: point.y,
      layer: point.layer,
      width: Math.max(previous.width ?? 0.15, point.width ?? 0.15),
    })
    previous = point
  }
  return output
})

const traceRadius = 0.075
const clearance = 0.1
const viaRadius = 0.225
const layerPadBlocks = (pad, targetLayer) => pad.type === "pcb_plated_hole" || pad.layer === targetLayer ||
  pad.layers?.includes(targetLayer)
const pointBlocked = (x, y, targetLayer, ignoreStartPad = false) => {
  if (Math.abs(x) > 9.8 - traceRadius || Math.abs(y) > 9.8 - traceRadius) return true
  if (vias.some((via) => Math.hypot(x - via.x, y - via.y) <
    (via.outer_diameter ?? 0.45) / 2 + traceRadius + clearance)) return true
  if (holes.some((hole) => Math.hypot(x - hole.x, y - hole.y) <
    (hole.diameter ?? 0) / 2 + traceRadius + 0.2)) return true
  if (pads.some((pad) => pad !== (ignoreStartPad ? startPad : undefined) &&
    layerPadBlocks(pad, targetLayer) && pointRectDistance(x, y, pad) < traceRadius + clearance)) return true
  if (segments.some((segment) => segment.layer === targetLayer && pointSegmentDistance(x, y,
    segment.ax, segment.ay, segment.bx, segment.by) < traceRadius + segment.width / 2 + clearance)) return true
  return false
}
const viaFree = (x, y) => {
  if (Math.abs(x) > 9.575 || Math.abs(y) > 9.575) return false
  if (vias.some((via) => Math.hypot(x - via.x, y - via.y) <
    viaRadius + (via.outer_diameter ?? 0.45) / 2 + clearance)) return false
  if (holes.some((hole) => Math.hypot(x - hole.x, y - hole.y) <
    viaRadius + (hole.diameter ?? 0) / 2 + 0.2)) return false
  if (pads.some((pad) => pointRectDistance(x, y, pad) < viaRadius + clearance)) return false
  if (segments.some((segment) => pointSegmentDistance(x, y,
    segment.ax, segment.ay, segment.bx, segment.by) < viaRadius + segment.width / 2 + clearance)) return false
  return true
}

const round = (value) => Number(value.toFixed(4))
const key = (x, y) => `${round(x)},${round(y)}`
const candidates = new Set()
for (let y = ymin; y <= ymax + 1e-9; y += step) {
  for (let x = xmin; x <= xmax + 1e-9; x += step) {
    const px = round(x)
    const py = round(y)
    if (viaFree(px, py)) candidates.add(key(px, py))
  }
}
if (candidates.size === 0) throw new Error("No free via candidates in requested region")

const startKey = key(startX, startY)
const open = [{ x: startX, y: startY, g: 0, f: 0 }]
const best = new Map([[startKey, 0]])
const previous = new Map()
const directions = [
  [-1, 0], [1, 0], [0, -1], [0, 1],
  [-1, -1], [-1, 1], [1, -1], [1, 1],
]
let goal
while (open.length) {
  open.sort((a, b) => a.f - b.f)
  const current = open.shift()
  const currentKey = key(current.x, current.y)
  if (current.g !== best.get(currentKey)) continue
  if (candidates.has(currentKey)) {
    goal = current
    break
  }
  for (const [dx, dy] of directions) {
    const nx = round(current.x + dx * step)
    const ny = round(current.y + dy * step)
    if (nx < -9.7 || nx > 9.7 || ny < -9.7 || ny > 9.7) continue
    const nextKey = key(nx, ny)
    const nearStart = Math.hypot(nx - startX, ny - startY) < 0.5
    if (pointBlocked(nx, ny, layer, nearStart)) continue
    const cost = current.g + Math.hypot(dx, dy)
    if (cost >= (best.get(nextKey) ?? Infinity)) continue
    best.set(nextKey, cost)
    previous.set(nextKey, currentKey)
    const nearestGoal = [...candidates].reduce((nearest, candidateKey) => {
      const [cx, cy] = candidateKey.split(",").map(Number)
      return Math.min(nearest, Math.hypot(nx - cx, ny - cy))
    }, Infinity)
    open.push({ x: nx, y: ny, g: cost, f: cost + nearestGoal / step })
  }
}
if (!goal) throw new Error(`No collision-free escape path found (reachable grid points: ${best.size}, candidates: ${candidates.size})`)
const path = []
let cursor = key(goal.x, goal.y)
while (cursor) {
  path.push(cursor.split(",").map(Number))
  cursor = previous.get(cursor)
}
path.reverse()

// Remove collinear grid points for a compact pcb route.
const compact = path.filter((point, index) => {
  if (index === 0 || index === path.length - 1) return true
  const before = path[index - 1]
  const after = path[index + 1]
  return (point[0] - before[0]) * (after[1] - point[1]) !==
    (point[1] - before[1]) * (after[0] - point[0])
})
console.log(JSON.stringify({ start: [startX, startY], goal: [goal.x, goal.y], candidates: candidates.size,
  path: compact }))