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

scripts/find-manual-route.mjs

import fs from "node:fs"

const values = process.argv.slice(2)
if (values.length < 6) {
  throw new Error("usage: node scripts/find-manual-route.mjs SX SY SLAYER EX EY ELAYER [STEP] [IGNORE_SOURCE_TRACE]")
}
const [sx, sy, ex, ey, step = 0.15] = [values[0], values[1], values[3], values[4], values[6] ?? 0.15].map(Number)
const startLayer = values[2]
const endLayer = values[5]
const ignoredSourceTraceIds = new Set((values[7] ?? "").split(",").filter(Boolean))
const layers = values[8] === "alllayers"
  ? ["top", "inner1", "inner2", "bottom"]
  : values[8] === "multilayer"
  ? ["top", "inner2", "bottom"]
  : startLayer !== endLayer
  ? ["top", "bottom"]
  : [startLayer]
const exactVia = values[9] === "exactvia"
if (![sx, sy, ex, ey, step].every(Number.isFinite) ||
  !layers.includes(startLayer) || !layers.includes(endLayer)) {
  throw new Error("invalid coordinate or layer")
}

const circuit = JSON.parse(fs.readFileSync("dist/index/circuit.json", "utf8"))
  .filter((element) => !String(element.type).endsWith("error"))
const usesIgnoredSourceTrace = (element) => {
  if (ignoredSourceTraceIds.has(element.pcb_trace_id)) return true
  const ids = `${element.source_trace_id ?? ""} ${element.pcb_trace_id ?? ""}`
    .match(/source_trace_(\d+)/g) ?? []
  return ids.some((id) =>
    ignoredSourceTraceIds.has(id) || ignoredSourceTraceIds.has(id.slice("source_trace_".length)))
}
const ignoredPcbTraceIds = new Set(circuit.filter((element) =>
  element.type === "pcb_trace" && usesIgnoredSourceTrace(element))
  .map((element) => element.pcb_trace_id))
const pads = circuit.filter((element) => ["pcb_smtpad", "pcb_plated_hole"].includes(element.type))
const holes = circuit.filter((element) => element.type === "pcb_hole")
const vias = circuit.filter((element) => element.type === "pcb_via" &&
  !ignoredPcbTraceIds.has(element.pcb_trace_id))
const segments = circuit.filter((element) => element.type === "pcb_trace" &&
  !usesIgnoredSourceTrace(element)).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 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.ccw_rotation ?? element.rotation ?? 0) * Math.PI) / 180)
  const dx = x - (element.x ?? element.center?.x ?? 0)
  const dy = y - (element.y ?? element.center?.y ?? 0)
  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 ?? element.outer_width ?? element.outer_diameter ?? 0) / 2, 0)
  const outsideY = Math.max(Math.abs(localY) -
    (element.height ?? element.outer_height ?? element.outer_diameter ?? 0) / 2, 0)
  return Math.hypot(outsideX, outsideY)
}
const nearEndpoint = (x, y) =>
  Math.hypot(x - sx, y - sy) < 0.06 || Math.hypot(x - ex, y - ey) < 0.06
const padOnLayer = (pad, layer) => pad.type === "pcb_plated_hole" || pad.layer === layer || pad.layers?.includes(layer)
const traceRadius = 0.075
const clearance = 0.1
const viaRadius = 0.225
const pointFree = (x, y, layer) => {
  if (Math.abs(x) > 9.65 || Math.abs(y) > 9.65) return false
  if (holes.some((hole) => Math.hypot(x - hole.x, y - hole.y) <
    (hole.diameter ?? hole.hole_diameter ?? 0) / 2 + traceRadius + 0.2)) return false
  if (vias.some((via) => !nearEndpoint(via.x, via.y) && Math.hypot(x - via.x, y - via.y) <
    (via.outer_diameter ?? 0.45) / 2 + traceRadius + clearance)) return false
  if (pads.some((pad) => padOnLayer(pad, layer) && !nearEndpoint(pad.x, pad.y) &&
    pointRectDistance(x, y, pad) < traceRadius + clearance)) return false
  if (segments.some((segment) => segment.layer === layer &&
    !nearEndpoint(segment.ax, segment.ay) && !nearEndpoint(segment.bx, segment.by) &&
    pointSegmentDistance(x, y, segment.ax, segment.ay, segment.bx, segment.by) <
      traceRadius + segment.width / 2 + clearance)) return false
  return true
}
const viaFree = (x, y) => {
  if (Math.abs(x) > 9.575 || Math.abs(y) > 9.575) return false
  if (holes.some((hole) => Math.hypot(x - hole.x, y - hole.y) <
    (hole.diameter ?? hole.hole_diameter ?? 0) / 2 + viaRadius + 0.2)) return false
  if (vias.some((via) => !nearEndpoint(via.x, via.y) && Math.hypot(x - via.x, y - via.y) <
    (via.outer_diameter ?? 0.45) / 2 + viaRadius + clearance)) return false
  if (pads.some((pad) => !nearEndpoint(pad.x, pad.y) &&
    pointRectDistance(x, y, pad) < viaRadius + clearance)) return false
  if (segments.some((segment) => !nearEndpoint(segment.ax, segment.ay) &&
    !nearEndpoint(segment.bx, segment.by) && pointSegmentDistance(x, y,
      segment.ax, segment.ay, segment.bx, segment.by) <
      viaRadius + segment.width / 2 + clearance)) return false
  return true
}
const segmentFree = (a, b) => {
  const distance = Math.hypot(a.x - b.x, a.y - b.y)
  const samples = Math.max(1, Math.ceil(distance / 0.05))
  for (let i = 1; i <= samples; i++) {
    const t = i / samples
    if (!pointFree(a.x + (b.x - a.x) * t, a.y + (b.y - a.y) * t, a.layer)) return false
  }
  return true
}

const round = (value) => Number(value.toFixed(3))
const key = (node) => `${node.layer}:${round(node.x)},${round(node.y)}`
class Heap {
  items = []
  push(item) {
    this.items.push(item)
    let index = this.items.length - 1
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2)
      if (this.items[parent].f <= item.f) break
      this.items[index] = this.items[parent]
      index = parent
    }
    this.items[index] = item
  }
  pop() {
    if (!this.items.length) return undefined
    const root = this.items[0]
    const last = this.items.pop()
    if (!this.items.length) return root
    let index = 0
    while (true) {
      const left = index * 2 + 1
      const right = left + 1
      if (left >= this.items.length) break
      const child = right < this.items.length && this.items[right].f < this.items[left].f ? right : left
      if (this.items[child].f >= last.f) break
      this.items[index] = this.items[child]
      index = child
    }
    this.items[index] = last
    return root
  }
}

const layerIndex = (layer) => layers.indexOf(layer)
const heuristic = (node) => Math.hypot(node.x - ex, node.y - ey) / step +
  Math.abs(layerIndex(node.layer) - layerIndex(endLayer)) * 8
const start = { x: sx, y: sy, layer: startLayer }
const open = new Heap()
open.push({ ...start, g: 0, f: heuristic(start) })
const best = new Map([[key(start), 0]])
const previous = new Map()
const nodes = new Map([[key(start), start]])
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]
let goal
let iterations = 0
while (open.items.length && iterations++ < 400000) {
  const current = open.pop()
  const currentKey = key(current)
  if (current.g !== best.get(currentKey)) continue
  const end = { x: ex, y: ey, layer: endLayer }
  if (current.layer === endLayer && Math.hypot(current.x - ex, current.y - ey) <= step * 1.6 &&
    segmentFree(current, end)) {
    if (key(end) === currentKey) {
      goal = current
    } else {
      goal = end
      previous.set(key(end), currentKey)
      nodes.set(key(end), end)
    }
    break
  }
  for (const [dx, dy] of directions) {
    const next = { x: round(current.x + dx * step), y: round(current.y + dy * step), layer: current.layer }
    if (!pointFree(next.x, next.y, next.layer) || !segmentFree(current, next)) continue
    const nextKey = key(next)
    const g = current.g + Math.hypot(dx, dy)
    if (g >= (best.get(nextKey) ?? Infinity)) continue
    best.set(nextKey, g)
    previous.set(nextKey, currentKey)
    nodes.set(nextKey, next)
    open.push({ ...next, g, f: g + heuristic(next) })
  }
  if (viaFree(current.x, current.y) && (!exactVia || Math.hypot(current.x - ex, current.y - ey) <= step * 0.6)) {
    for (const layer of layers) {
      if (layer === current.layer) continue
      const next = { x: current.x, y: current.y, layer }
      const nextKey = key(next)
      const g = current.g + 9
      if (g >= (best.get(nextKey) ?? Infinity)) continue
      best.set(nextKey, g)
      previous.set(nextKey, currentKey)
      nodes.set(nextKey, next)
      open.push({ ...next, g, f: g + heuristic(next) })
    }
  }
}
if (!goal) {
  const reached = [...nodes.values()]
  const bounds = reached.length ? {
    minX: Math.min(...reached.map((node) => node.x)),
    maxX: Math.max(...reached.map((node) => node.x)),
    minY: Math.min(...reached.map((node) => node.y)),
    maxY: Math.max(...reached.map((node) => node.y)),
  } : undefined
  const nearest = reached.sort((a, b) =>
    Math.hypot(a.x - ex, a.y - ey) - Math.hypot(b.x - ex, b.y - ey))[0]
  throw new Error(`no path after ${iterations} iterations; visited ${best.size} states; reached ${JSON.stringify(bounds)}; nearest ${JSON.stringify(nearest)}`)
}
const path = []
let cursor = key(goal)
while (cursor) {
  path.push(nodes.get(cursor))
  cursor = previous.get(cursor)
}
path.reverse()
const collinearCompact = path.filter((point, index) => {
  if (index === 0 || index === path.length - 1) return true
  const before = path[index - 1]
  const after = path[index + 1]
  if (before.layer !== point.layer || point.layer !== after.layer) return true
  return (point.x - before.x) * (after.y - point.y) !== (point.y - before.y) * (after.x - point.x)
})
const compact = []
for (let index = 0; index < collinearCompact.length;) {
  compact.push(collinearCompact[index])
  if (index === collinearCompact.length - 1) break
  let nextIndex = index + 1
  for (let candidate = collinearCompact.length - 1; candidate > index + 1; candidate--) {
    if (collinearCompact[candidate].layer !== collinearCompact[index].layer) continue
    if (segmentFree(collinearCompact[index], collinearCompact[candidate])) {
      nextIndex = candidate
      break
    }
  }
  index = nextIndex
}
console.log(JSON.stringify({ iterations, visited: best.size, path: collinearCompact, shortcutPath: compact }, null, 2))