slaguru666andClaude Opus 4.8
100e514c4d
Buildings (modern/fantasy, multi-floor, footprint shapes), caves, outdoor biomes, and town/village + city-block settlements. Auto-places Foundry walls, doors, windows, lighting; furniture as locked tiles; live preview. Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
262 lines
8.9 KiB
JavaScript
262 lines
8.9 KiB
JavaScript
/**
|
||
* 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;
|
||
}
|