mapwright/module/lib/organic.mjs

/**
 * Organic geometry core — shared by dungeons (caves) and outdoor biomes.
 *
 * Cellular-automata blob -> traced boundary loops -> simplified (diagonal,
 * NON-axis-aligned) wall segments for Foundry + smoothed curves for the SVG.
 *
 * This is what frees us from the right-angle grid. Pure / Node-testable.
 * Works on a SUB-CELL grid (subRes sub-cells per map cell) for smooth contours;
 * all output is converted back to map-cell coordinates.
 */

import { Rng } from "./rng.mjs";

/**
 * Generate a cellular-automata cave/blob as a floor mask on the sub grid.
 * @returns {{ floor: Uint8Array, sw: number, sh: number, subRes: number, cols: number, rows: number }}
 */
export function generateBlob(opts) {
  const cols = opts.cols;
  const rows = opts.rows;
  const subRes = opts.subRes ?? 3;
  const sw = cols * subRes;
  const sh = rows * subRes;
  const rng = new Rng(opts.seed ?? "cave");
  const fill = opts.fill ?? 0.46;
  const steps = opts.steps ?? 5;
  const margin = Math.max(1, Math.round((opts.margin ?? 1) * subRes));

  let grid = new Uint8Array(sw * sh); // 1 = floor, 0 = wall
  const at = (g, x, y) => (x < 0 || y < 0 || x >= sw || y >= sh ? 0 : g[y * sw + x]);

  // Seed noise, with a wall margin so the blob never touches the edge.
  for (let y = 0; y < sh; y += 1) {
    for (let x = 0; x < sw; x += 1) {
      const edge = x < margin || y < margin || x >= sw - margin || y >= sh - margin;
      grid[y * sw + x] = edge ? 0 : (rng.float() < fill ? 0 : 1);
    }
  }

  // Smooth with the classic 4-5 rule (+ fill large voids).
  for (let s = 0; s < steps; s += 1) {
    const next = new Uint8Array(sw * sh);
    for (let y = 0; y < sh; y += 1) {
      for (let x = 0; x < sw; x += 1) {
        let walls1 = 0;
        for (let dy = -1; dy <= 1; dy += 1) {
          for (let dx = -1; dx <= 1; dx += 1) {
            if (dx === 0 && dy === 0) continue;
            if (at(grid, x + dx, y + dy) === 0) walls1 += 1;
          }
        }
        const isWall = grid[y * sw + x] === 0;
        // Wall if surrounded; open up otherwise.
        next[y * sw + x] = (isWall ? walls1 >= 4 : walls1 >= 5) ? 0 : 1;
      }
    }
    grid = next;
  }

  // Keep only the largest connected floor region (guarantees one cave).
  grid = keepLargestRegion(grid, sw, sh);

  // Remove small enclosed wall pockets (declutter tiny pillars).
  const holeFloor = (opts.removeHolesBelow ?? 2.2) * subRes * subRes;
  grid = removeSmallHoles(grid, sw, sh, holeFloor);

  return { floor: grid, sw, sh, subRes, cols, rows };
}

/** Fill enclosed wall regions (not touching the border) smaller than minArea. */
function removeSmallHoles(grid, sw, sh, minArea) {
  const seen = new Uint8Array(sw * sh);
  const stack = [];
  for (let i = 0; i < grid.length; i += 1) {
    if (grid[i] !== 0 || seen[i]) continue;
    const cells = [];
    let touchesBorder = false;
    stack.length = 0;
    stack.push(i);
    seen[i] = 1;
    while (stack.length) {
      const idx = stack.pop();
      cells.push(idx);
      const x = idx % sw, y = (idx / sw) | 0;
      if (x === 0 || y === 0 || x === sw - 1 || y === sh - 1) touchesBorder = true;
      const ns = [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]];
      for (const [nx, ny] of ns) {
        if (nx < 0 || ny < 0 || nx >= sw || ny >= sh) continue;
        const ni = ny * sw + nx;
        if (grid[ni] === 0 && !seen[ni]) { seen[ni] = 1; stack.push(ni); }
      }
    }
    if (!touchesBorder && cells.length < minArea) {
      for (const idx of cells) grid[idx] = 1;
    }
  }
  return grid;
}

function keepLargestRegion(grid, sw, sh) {
  const label = new Int32Array(sw * sh).fill(-1);
  let best = -1, bestSize = 0, current = 0;
  const stack = [];
  for (let i = 0; i < grid.length; i += 1) {
    if (grid[i] !== 1 || label[i] !== -1) continue;
    let size = 0;
    stack.length = 0;
    stack.push(i);
    label[i] = current;
    while (stack.length) {
      const idx = stack.pop();
      size += 1;
      const x = idx % sw, y = (idx / sw) | 0;
      const ns = [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]];
      for (const [nx, ny] of ns) {
        if (nx < 0 || ny < 0 || nx >= sw || ny >= sh) continue;
        const ni = ny * sw + nx;
        if (grid[ni] === 1 && label[ni] === -1) { label[ni] = current; stack.push(ni); }
      }
    }
    if (size > bestSize) { bestSize = size; best = current; }
    current += 1;
  }
  const out = new Uint8Array(sw * sh);
  if (best < 0) return out;
  for (let i = 0; i < grid.length; i += 1) out[i] = label[i] === best ? 1 : 0;
  return out;
}

/**
 * Trace the floor/wall boundary into ordered, oriented loops.
 * Each loop is an array of {x, y} points in SUB-GRID coordinates.
 */
export function traceContours(floor, sw, sh) {
  const at = (x, y) => (x < 0 || y < 0 || x >= sw || y >= sh ? 0 : floor[y * sw + x]);
  // Directed boundary edges, floor-cell traversed clockwise (screen y-down).
  const edges = new Map(); // tailKey -> [{tail,head}]
  const addEdge = (ax, ay, bx, by) => {
    const key = `${ax},${ay}`;
    if (!edges.has(key)) edges.set(key, []);
    edges.get(key).push({ head: { x: bx, y: by } });
  };
  for (let y = 0; y < sh; y += 1) {
    for (let x = 0; x < sw; x += 1) {
      if (at(x, y) !== 1) continue;
      if (at(x, y - 1) === 0) addEdge(x, y, x + 1, y);         // top
      if (at(x + 1, y) === 0) addEdge(x + 1, y, x + 1, y + 1); // right
      if (at(x, y + 1) === 0) addEdge(x + 1, y + 1, x, y + 1); // bottom
      if (at(x - 1, y) === 0) addEdge(x, y + 1, x, y);         // left
    }
  }

  const loops = [];
  for (const [startKey, list] of edges) {
    while (list.length) {
      const first = list.pop();
      const startPt = startKey.split(",").map(Number);
      const loop = [{ x: startPt[0], y: startPt[1] }];
      let cur = first.head;
      let guard = 0;
      while (guard++ < sw * sh * 4) {
        loop.push({ x: cur.x, y: cur.y });
        const key = `${cur.x},${cur.y}`;
        const outs = edges.get(key);
        if (!outs || !outs.length) break;
        const next = outs.pop();
        cur = next.head;
        if (cur.x === startPt[0] && cur.y === startPt[1]) break;
      }
      if (loop.length > 3) loops.push(loop);
    }
  }
  return loops;
}

/** Chaikin corner-cutting smoothing for a closed loop. */
export function chaikin(points, iterations = 2) {
  let pts = points;
  for (let it = 0; it < iterations; it += 1) {
    const out = [];
    const n = pts.length;
    for (let i = 0; i < n; i += 1) {
      const a = pts[i];
      const b = pts[(i + 1) % n];
      out.push({ x: a.x * 0.75 + b.x * 0.25, y: a.y * 0.75 + b.y * 0.25 });
      out.push({ x: a.x * 0.25 + b.x * 0.75, y: a.y * 0.25 + b.y * 0.75 });
    }
    pts = out;
  }
  return pts;
}

/** Douglas–Peucker simplification of a CLOSED loop. tol in same units as points. */
export function simplifyClosed(points, tol) {
  const n = points.length;
  if (n < 5) return points.slice();
  // Split the loop at the two most distant points, DP each half.
  let iFar = 0, jFar = 1, dMax = -1;
  // cheap diameter estimate: farthest from point 0, then farthest from that
  iFar = 0;
  for (let k = 1; k < n; k += 1) {
    const d = dist2(points[0], points[k]);
    if (d > dMax) { dMax = d; jFar = k; }
  }
  dMax = -1; iFar = jFar; let opp = 0;
  for (let k = 0; k < n; k += 1) {
    const d = dist2(points[iFar], points[k]);
    if (d > dMax) { dMax = d; opp = k; }
  }
  const a = Math.min(iFar, opp), b = Math.max(iFar, opp);
  const half1 = points.slice(a, b + 1);
  const half2 = points.slice(b).concat(points.slice(0, a + 1));
  const s1 = dpOpen(half1, tol);
  const s2 = dpOpen(half2, tol);
  // stitch, dropping duplicated shared endpoints
  const merged = s1.concat(s2.slice(1, -1));
  return merged.length >= 3 ? merged : points.slice();
}

function dpOpen(points, tol) {
  if (points.length < 3) return points.slice();
  const keep = new Array(points.length).fill(false);
  keep[0] = keep[points.length - 1] = true;
  const stack = [[0, points.length - 1]];
  while (stack.length) {
    const [s, e] = stack.pop();
    let maxD = -1, idx = -1;
    for (let i = s + 1; i < e; i += 1) {
      const d = perpDist(points[i], points[s], points[e]);
      if (d > maxD) { maxD = d; idx = i; }
    }
    if (maxD > tol && idx !== -1) {
      keep[idx] = true;
      stack.push([s, idx], [idx, e]);
    }
  }
  return points.filter((_, i) => keep[i]);
}

function dist2(a, b) { const dx = a.x - b.x, dy = a.y - b.y; return dx * dx + dy * dy; }

function perpDist(p, a, b) {
  const dx = b.x - a.x, dy = b.y - a.y;
  const len = Math.hypot(dx, dy) || 1;
  return Math.abs((p.x - a.x) * dy - (p.y - a.y) * dx) / len;
}

/** Convert a loop of sub-grid points to map-cell coords. */
export function loopToCells(loop, subRes) {
  return loop.map((p) => ({ x: p.x / subRes, y: p.y / subRes }));
}

/** A loop's signed area (screen y-down): >0 clockwise (outer), <0 hole. */
export function signedArea(loop) {
  let a = 0;
  for (let i = 0; i < loop.length; i += 1) {
    const p = loop[i], q = loop[(i + 1) % loop.length];
    a += p.x * q.y - q.x * p.y;
  }
  return a / 2;
}