Circuit Trace Generators

// Worker-safe obstacle geometry for circuit-background-v9.
// The ADOM contour is sourced from adom-elements/src/adom-white.svg.

const ADOM_PATH = "M1065.5,25.22h-58.49c-2.98,0-5.68,1.87-6.73,4.65l-44.4,117.54c-.06.17-.31.17-.37,0l-45.44-117.59c-1.07-2.75-3.76-4.6-6.72-4.6h-58.79c-4.09,0-7.4,3.31-7.4,7.4v35.06l-.03-.12c-1.24,4.99-5.89,6-5.89,6,0,0-4.51,1.02-7.61-2.53v.03c-17.82-29.81-50.31-48.93-89.04-48.93-41.5,0-75.86,21.85-92.76,55.23v-.07c-2.86,5.19-8.74,5.13-8.74,5.13,0,0-5.63-.01-8.41-4.61-16.49-32.68-50.56-52.59-94.79-52.59h-73.46c-4.09,0-7.4,3.31-7.4,7.4v121.27s0,.03,0,.04c-.95,5.15-4.75,5.94-4.75,5.94,0,0-3.88.85-6.77-3.32l.05.23-46.05-126.83c-1.03-2.84-3.75-4.74-6.77-4.74h-57.14c-3.01,0-5.73,1.9-6.76,4.73l-68.67,188.38c-1.05,2.88-.18,6.21,2.4,8.19,1.31,1.01,2.98,1.47,4.64,1.47h34.96s6.43,0,6.43,0c2.5,0,4.83-1.39,5.9-3.65,8.49-17.86,26.5-29.64,48.37-29.64s39.71,11.73,48.19,29.53c1.1,2.32,3.49,3.76,6.06,3.76h120.78c31.22,0,57.85-9.95,77.02-28.77,7.38-7.25,13.43-15.72,18.05-25.1v.09c2.74-5.19,8.37-5.13,8.37-5.13,0,0,5.43,0,8.08,4.64,4.88,9.88,11.26,18.78,18.91,26.42,18.6,18.6,44.61,29.78,74.26,29.78,38.74,0,71.23-19.18,89.05-49.07l-.02.07c3.1-3.55,7.61-2.53,7.61-2.53,0,0,4.65,1,5.89,6l.03-.12v36.32c0,4.09,3.31,7.4,7.4,7.4h45.79c4.09,0,7.4-3.31,7.4-7.4v-86.26c0-.23.32-.28.39-.06l30.37,88.86c1,2.91,3.74,4.87,6.81,4.87h39.69c3.08,0,5.82-1.96,6.81-4.87l30.1-88.02c.07-.21.39-.16.39.06v85.43c0,4.09,3.31,7.4,7.4,7.4h45.79c4.09,0,7.4-3.31,7.4-7.4V32.62c0-4.09-3.31-7.4-7.4-7.4ZM372.31,147.57c-.15.21-.5.57-1.1.57h-30.33c-.61,0-.95-.35-1.1-.56-.15-.21-.38-.65-.19-1.23l15.06-45.79c.27-.81.92-.94,1.29-.94h0c.37,0,1.02.12,1.29.93l15.26,45.8c.19.58-.04,1.01-.19,1.23ZM525.72,173.84h-14.52c-.86,0-1.56-.7-1.56-1.56v-92.16c0-.86.7-1.56,1.56-1.56h14.52c30.81,0,48.48,17.47,48.48,47.92s-17.67,47.36-48.48,47.36ZM734.6,173.26c-26.51,0-42.33-17.71-42.34-47.36,0-14.59,3.88-26.68,11.21-34.98,7.33-8.29,18.09-12.67,31.13-12.67,12.11,0,22.28,3.84,29.58,11.13.5.5.98,1.01,1.45,1.54,7.4,8.33,11.31,20.42,11.31,34.97,0,29.21-16.22,47.36-42.34,47.36Z";

const COMMAND = /^[a-z]$/i;
const NUMBER = /[a-z]|[-+]?(?:\d*\.\d+|\d+\.?)(?:e[-+]?\d+)?/gi;

function cubicPoint(start, first, second, end, t) {
  const inverse = 1 - t;
  const a = inverse * inverse * inverse;
  const b = 3 * inverse * inverse * t;
  const c = 3 * inverse * t * t;
  const d = t * t * t;
  return [
    a * start[0] + b * first[0] + c * second[0] + d * end[0],
    a * start[1] + b * first[1] + c * second[1] + d * end[1],
  ];
}

function flattenSvgPath(data, curveSteps = 14) {
  const tokens = data.match(NUMBER) || [];
  const rings = [];
  let index = 0;
  let command = null;
  let current = [0, 0];
  let start = [0, 0];
  let previousControl = null;
  let previousCommand = null;
  let ring = [];

  const number = () => Number(tokens[index++]);
  const point = (relative) => {
    const result = [number(), number()];
    if (relative) {
      result[0] += current[0];
      result[1] += current[1];
    }
    return result;
  };
  const finishRing = () => {
    if (ring.length < 3) return;
    const last = ring.at(-1);
    if (last[0] !== start[0] || last[1] !== start[1]) ring.push(start.slice());
    rings.push(ring);
    ring = [];
  };

  while (index < tokens.length) {
    if (COMMAND.test(tokens[index])) command = tokens[index++];
    if (!command) throw new Error("Invalid ADOM path data");
    const relative = command === command.toLowerCase();
    const upper = command.toUpperCase();

    if (upper === "M") {
      if (ring.length) finishRing();
      current = point(relative);
      start = current.slice();
      ring = [current.slice()];
      command = relative ? "l" : "L";
      previousControl = null;
    } else if (upper === "L") {
      current = point(relative);
      ring.push(current.slice());
      previousControl = null;
    } else if (upper === "H") {
      const x = number() + (relative ? current[0] : 0);
      current = [x, current[1]];
      ring.push(current.slice());
      previousControl = null;
    } else if (upper === "V") {
      const y = number() + (relative ? current[1] : 0);
      current = [current[0], y];
      ring.push(current.slice());
      previousControl = null;
    } else if (upper === "C") {
      const first = point(relative);
      const second = point(relative);
      const end = point(relative);
      const origin = current;
      for (let step = 1; step <= curveSteps; step += 1) {
        ring.push(cubicPoint(origin, first, second, end, step / curveSteps));
      }
      current = end;
      previousControl = second;
    } else if (upper === "S") {
      const reflected = previousControl && (previousCommand === "C" || previousCommand === "S")
        ? [2 * current[0] - previousControl[0], 2 * current[1] - previousControl[1]]
        : current.slice();
      const second = point(relative);
      const end = point(relative);
      const origin = current;
      for (let step = 1; step <= curveSteps; step += 1) {
        ring.push(cubicPoint(origin, reflected, second, end, step / curveSteps));
      }
      current = end;
      previousControl = second;
    } else if (upper === "Z") {
      finishRing();
      current = start.slice();
      previousControl = null;
      command = null;
    } else {
      throw new Error(`Unsupported SVG path command: ${command}`);
    }
    previousCommand = upper;
  }
  if (ring.length) finishRing();
  return rings;
}

function boundsOfRings(rings) {
  let minX = Infinity;
  let minY = Infinity;
  let maxX = -Infinity;
  let maxY = -Infinity;
  for (const ring of rings) {
    for (const [x, y] of ring) {
      minX = Math.min(minX, x);
      minY = Math.min(minY, y);
      maxX = Math.max(maxX, x);
      maxY = Math.max(maxY, y);
    }
  }
  return { minX, minY, maxX, maxY, width: maxX - minX, height: maxY - minY };
}

const ADOM_RINGS = flattenSvgPath(ADOM_PATH);
const ADOM_BOUNDS = boundsOfRings(ADOM_RINGS);

function pointInRing(x, y, ring) {
  let inside = false;
  for (let current = 0, previous = ring.length - 1; current < ring.length; previous = current, current += 1) {
    const [cx, cy] = ring[current];
    const [px, py] = ring[previous];
    if ((cy > y) === (py > y)) continue;
    const crossing = (px - cx) * (y - cy) / (py - cy || Number.EPSILON) + cx;
    if (x < crossing) inside = !inside;
  }
  return inside;
}

function pointInRings(x, y, rings) {
  let inside = false;
  for (const ring of rings) if (pointInRing(x, y, ring)) inside = !inside;
  return inside;
}

function transformWordmark(spec, width, height) {
  const targetWidth = Math.max(24, width * Number(spec.width ?? spec.scale ?? 0.66));
  const targetHeight = targetWidth * ADOM_BOUNDS.height / ADOM_BOUNDS.width;
  const centerX = width * Number(spec.x ?? 0.5);
  const centerY = height * Number(spec.y ?? 0.66);
  const scale = targetWidth / ADOM_BOUNDS.width;
  return ADOM_RINGS.map((ring) => ring.map(([x, y]) => [
    centerX + (x - ADOM_BOUNDS.minX - ADOM_BOUNDS.width / 2) * scale,
    centerY + (y - ADOM_BOUNDS.minY - ADOM_BOUNDS.height / 2) * scale,
  ]));
}

function resolveValue(value, extent, normalized) {
  return Number(value || 0) * (normalized ? extent : 1);
}

function compileGenericObstacle(spec, width, height) {
  const normalized = spec.space !== "world";
  const centerX = resolveValue(spec.x ?? 0.5, width, normalized);
  const centerY = resolveValue(spec.y ?? 0.5, height, normalized);
  const obstacleWidth = Math.max(0, resolveValue(spec.width ?? 0.2, width, normalized));
  const obstacleHeight = Math.max(0, resolveValue(spec.height ?? 0.2, height, normalized));

  if (spec.type === "rect") {
    const left = centerX - obstacleWidth / 2;
    const top = centerY - obstacleHeight / 2;
    const ring = [[left, top], [left + obstacleWidth, top], [left + obstacleWidth, top + obstacleHeight], [left, top + obstacleHeight], [left, top]];
    return { id: spec.id || "rect", rings: [ring], contains: (x, y) => x >= left && x <= left + obstacleWidth && y >= top && y <= top + obstacleHeight };
  }
  if (spec.type === "ellipse") {
    const rx = obstacleWidth / 2;
    const ry = obstacleHeight / 2;
    const ring = Array.from({ length: 97 }, (_, index) => {
      const angle = index / 96 * Math.PI * 2;
      return [centerX + Math.cos(angle) * rx, centerY + Math.sin(angle) * ry];
    });
    return { id: spec.id || "ellipse", rings: [ring], contains: (x, y) => ((x - centerX) / (rx || 1)) ** 2 + ((y - centerY) / (ry || 1)) ** 2 <= 1 };
  }
  const sourceRings = spec.type === "polygon" ? [spec.points || []] : spec.rings || [];
  const rings = sourceRings.map((ring) => {
    const transformed = ring.map(([x, y]) => [resolveValue(x, width, normalized), resolveValue(y, height, normalized)]);
    if (transformed.length && transformed.at(-1).some((value, axis) => value !== transformed[0][axis])) transformed.push(transformed[0].slice());
    return transformed;
  }).filter((ring) => ring.length >= 4);
  return { id: spec.id || spec.type || "shape", rings, contains: (x, y) => pointInRings(x, y, rings) };
}

function normalizeSpecs(config) {
  const specs = Array.isArray(config.obstacles) ? config.obstacles.slice() : [];
  if (config.obstaclePreset === "adom") {
    specs.unshift({
      id: "adom-wordmark",
      type: "wordmark",
      preset: "adom",
      x: Number(config.obstacleX ?? 0.5),
      y: Number(config.obstacleY ?? 0.66),
      width: Number(config.obstacleScale ?? 0.66),
    });
  }
  return specs.filter((spec) => spec && spec.enabled !== false);
}

function compileObstacle(spec, width, height) {
  if (spec.type === "wordmark" || spec.preset === "adom") {
    const rings = transformWordmark(spec, width, height);
    return { id: spec.id || "adom-wordmark", rings, contains: (x, y) => pointInRings(x, y, rings) };
  }
  return compileGenericObstacle(spec, width, height);
}

function dilateMask(source, columns, rows, radius) {
  if (radius <= 0) return source.slice();
  const result = source.slice();
  const offsets = [];
  for (let dy = -radius; dy <= radius; dy += 1) {
    for (let dx = -radius; dx <= radius; dx += 1) {
      if (dx * dx + dy * dy <= radius * radius) offsets.push([dx, dy]);
    }
  }
  for (let y = 1; y < rows - 1; y += 1) {
    for (let x = 1; x < columns - 1; x += 1) {
      if (!source[y * columns + x]) continue;
      for (const [dx, dy] of offsets) {
        const nx = x + dx;
        const ny = y + dy;
        if (nx > 0 && ny > 0 && nx < columns - 1 && ny < rows - 1) result[ny * columns + nx] = 1;
      }
    }
  }
  return result;
}

function distanceField(blocked, columns, rows, band) {
  const unseen = 65535;
  const distance = new Uint16Array(columns * rows);
  distance.fill(unseen);
  const queue = new Int32Array(columns * rows);
  let head = 0;
  let tail = 0;
  for (let index = 0; index < blocked.length; index += 1) {
    if (!blocked[index]) continue;
    distance[index] = 0;
    queue[tail++] = index;
  }
  while (head < tail) {
    const index = queue[head++];
    const nextDistance = distance[index] + 1;
    if (nextDistance > band) continue;
    const x = index % columns;
    const y = Math.floor(index / columns);
    const neighbors = [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]];
    for (const [nx, ny] of neighbors) {
      if (nx < 0 || ny < 0 || nx >= columns || ny >= rows) continue;
      const next = ny * columns + nx;
      if (distance[next] <= nextDistance) continue;
      distance[next] = nextDistance;
      queue[tail++] = next;
    }
  }
  return distance;
}

function rasterizeObstacle(mask, obstacle, pitch, columns, rows) {
  for (let row = 1; row < rows - 1; row += 1) {
    const worldY = row * pitch;
    const intersections = [];
    for (const ring of obstacle.rings) {
      for (let current = 0, previous = ring.length - 1; current < ring.length; previous = current, current += 1) {
        const [cx, cy] = ring[current];
        const [px, py] = ring[previous];
        if ((cy > worldY) === (py > worldY)) continue;
        intersections.push(cx + (px - cx) * (worldY - cy) / (py - cy || Number.EPSILON));
      }
    }
    intersections.sort((left, right) => left - right);
    for (let pair = 0; pair + 1 < intersections.length; pair += 2) {
      const first = Math.max(1, Math.ceil(intersections[pair] / pitch));
      const last = Math.min(columns - 2, Math.floor(intersections[pair + 1] / pitch));
      for (let column = first; column <= last; column += 1) mask[row * columns + column] = 1;
    }
  }
}

export function createObstacleField(config, dimensions) {
  const { width, height, pitch, columns, rows } = dimensions;
  const specs = normalizeSpecs(config);
  if (!specs.length) return null;
  const compiled = specs.map((spec) => compileObstacle(spec, width, height)).filter((item) => item.rings.length);
  if (!compiled.length) return null;

  const inside = new Uint8Array(columns * rows);
  for (const obstacle of compiled) rasterizeObstacle(inside, obstacle, pitch, columns, rows);
  const viaClearance = Math.max(0, Number(config.viaOuterRadius) || 0) / pitch;
  const radius = Math.max(1, Math.ceil(Math.max(0, Number(config.obstacleClearance) || 0) + viaClearance));
  const blocked = dilateMask(inside, columns, rows, radius);
  const band = Math.max(4, Math.ceil(6 + (Number(config.obstaclePull) || 0) * 2));
  const distance = distanceField(blocked, columns, rows, band + 1);
  let blockedCells = 0;
  for (let y = 1; y < rows - 1; y += 1) {
    for (let x = 1; x < columns - 1; x += 1) blockedCells += blocked[y * columns + x];
  }
  return {
    blocked,
    distance,
    band,
    rings: compiled.flatMap((obstacle) => obstacle.rings.map((ring) => ({ id: obstacle.id, points: ring }))),
    count: compiled.length,
    blockedCells,
    mode: config.obstacleMode || "avoid",
  };
}

function sampleClosedRing(points, spacing) {
  const ring = points.slice();
  if (ring.length > 1 && ring[0][0] === ring.at(-1)[0] && ring[0][1] === ring.at(-1)[1]) ring.pop();
  if (ring.length < 3) return [];
  const segments = [];
  let total = 0;
  for (let index = 0; index < ring.length; index += 1) {
    const start = ring[index];
    const end = ring[(index + 1) % ring.length];
    const length = Math.hypot(end[0] - start[0], end[1] - start[1]);
    segments.push({ start, end, length, at: total });
    total += length;
  }
  const count = Math.max(12, Math.ceil(total / spacing));
  const result = [];
  let segmentIndex = 0;
  for (let sample = 0; sample < count; sample += 1) {
    const target = sample / count * total;
    while (segmentIndex < segments.length - 1 && segments[segmentIndex].at + segments[segmentIndex].length < target) segmentIndex += 1;
    const segment = segments[segmentIndex];
    const local = (target - segment.at) / (segment.length || 1);
    result.push([
      segment.start[0] + (segment.end[0] - segment.start[0]) * local,
      segment.start[1] + (segment.end[1] - segment.start[1]) * local,
    ]);
  }
  return result;
}

export function obstacleOutlineTraces(field, options) {
  if (!field || !field.mode.includes("outline")) return [];
  const pitch = options.pitch;
  const spacing = Math.max(2, pitch * 0.48);
  const viaRadius = Math.max(0, Number(options.viaOuterRadius) || 0);
  const traces = [];
  for (let ringIndex = 0; ringIndex < field.rings.length; ringIndex += 1) {
    const ring = field.rings[ringIndex];
    const sampled = sampleClosedRing(ring.points, spacing);
    if (sampled.length < 12) continue;
    let seam = 0;
    for (let index = 1; index < sampled.length; index += 1) {
      if (sampled[index][1] > sampled[seam][1] || (sampled[index][1] === sampled[seam][1] && sampled[index][0] > sampled[seam][0])) seam = index;
    }
    const gap = Math.min(Math.floor(sampled.length * 0.14), Math.max(2, Math.ceil((viaRadius * 2.4 + pitch * 0.45) / spacing)));
    const start = (seam + Math.ceil(gap / 2)) % sampled.length;
    const points = [];
    for (let offset = 0; offset <= sampled.length - gap; offset += 1) points.push(sampled[(start + offset) % sampled.length]);
    if (points.length < 6) continue;
    let length = 0;
    for (let index = 1; index < points.length; index += 1) length += Math.hypot(points[index][0] - points[index - 1][0], points[index][1] - points[index - 1][1]);
    traces.push({
      points,
      length,
      viaStart: true,
      viaEnd: true,
      kind: "obstacle-outline",
      obstacleId: ring.id,
      ringIndex,
    });
  }
  return traces;
}

export function obstacleEdgeWeight(field, x, y, dx, dy, columns, pull) {
  if (!field || !field.mode.includes("wrap") || pull <= 0) return 1;
  const index = y * columns + x;
  const distance = field.distance[index];
  if (!distance || distance > field.band) return 1;
  const left = field.distance[index - 1];
  const right = field.distance[index + 1];
  const up = field.distance[index - columns];
  const down = field.distance[index + columns];
  const gx = Math.min(right, field.band + 1) - Math.min(left, field.band + 1);
  const gy = Math.min(down, field.band + 1) - Math.min(up, field.band + 1);
  const magnitude = Math.hypot(gx, gy);
  if (magnitude < 0.001) return 1;
  const tangent = Math.abs((-gy * dx + gx * dy) / magnitude);
  const normal = Math.abs((gx * dx + gy * dy) / magnitude);
  const proximity = 1 - (distance - 1) / Math.max(1, field.band);
  const attraction = 1 + pull * proximity * (0.55 + tangent * tangent * 3.4);
  const approachPenalty = 1 - Math.min(0.68, pull * proximity * normal * 0.34);
  return Math.max(0.16, attraction * approachPenalty);
}

export const ADOM_WORDMARK_ASPECT = ADOM_BOUNDS.width / ADOM_BOUNDS.height;