gronod/ICCery-CPU
1
0
Fork 0
Code Issues Pull Requests 1 Actions Packages Projects Releases 5 Wiki Activity
Files
development
ICCery-CPU/.grok/skills/building-games/references/procedural-generation.md
T

10 KiB
Raw Permalink Blame History

Procedural Generation (seeded RNG, noise, dungeons/mazes/terrain, wave function collapse)

Consolidated from Red Blob Games, the simplex-noise library, and WFC primary sources (see Sources). Focus: what an AI builder needs to generate varied but reproducible worlds without the classic bugs — non-deterministic output, disconnected dungeons, blobby/banded terrain.

1. Seeded RNG is the foundation — never use bare Math.random()

Math.random() is not seedable, so you can't reproduce a level, share a seed, debug a bad map, or sync generation across clients in multiplayer. Always drive procedural generation from a seeded PRNG.

mulberry32 — the go-to small, fast, good-quality 32-bit seeded PRNG:

function mulberry32(seed) {
  return function () {
    let t = (seed += 0x6D2B79F5);
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296; // [0,1)
  };
}
const rng = mulberry32(12345); // same seed → identical sequence forever

Rules:

  • Hash string seeds to an int first (e.g. xmur3) so "cave-42" maps to a stable number.
  • Use separate RNG streams for independent systems (terrain vs loot vs enemy placement) so changing one doesn't reshuffle the others (mulberry32(seed), mulberry32(seed ^ 0x9e3779b9), …).
  • Add helpers: randRange(a,b)=a+rng()*(b-a), randInt, pick(arr), shuffle (Fisher–Yates using rng).
  • For networked/deterministic generation, both sides must run the same PRNG and consume it in the same order (deterministic multiplayer is out of scope on this deploy target). Order-of-consumption bugs are the #1 desync source.
  • Alternatives: alea, PCG. mulberry32 is plenty for games.

2. Noise: value / Perlin / simplex (for terrain, textures, organic fields)

Random-per-cell is white noise (harsh, uncorrelated). Coherent noise produces smooth, natural-looking fields where nearby points are similar.

  • Value noise — cheap, interpolate random lattice values. OK for simple stuff.
  • Perlin noise — classic gradient noise; can show axis-aligned artifacts.
  • Simplex / OpenSimplex — fewer directional artifacts, scales better to higher dimensions; preferred default. Use the simplex-noise npm package.
    • v4 API changed: no more new SimplexNoise(). Use factory functions and pass your seeded PRNG:
    import { createNoise2D } from 'simplex-noise';
const noise2D = createNoise2D(mulberry32(12345)); // returns ~[-1, 1]
const v = noise2D(x * 0.01, y * 0.01);            // scale coords = "frequency"
    (Also createNoise3D/createNoise4D; passing a PRNG makes output reproducible — without one it uses Math.random() = non-reproducible.)

Key techniques (from Red Blob Games "Making maps with noise"):

  • Frequency: multiply input coords by a scale; small scale = large smooth features.
  • Octaves / fBm: sum several noise layers at increasing frequency and decreasing amplitude (amplitude *= persistence(≈0.5), frequency *= lacunarity(≈2)) for natural detail.
  • Normalize noise from [−1,1] to [0,1] before thresholding.
  • Redistribution: elev = Math.pow(elev, k) to bias toward valleys/plains vs peaks.
  • Island mask: multiply by a radial falloff so edges are water.
  • Biomes: sample two independent noise fields (elevation + moisture) and look up a Whittaker-style biome table — don't derive moisture from elevation (they'd correlate and look wrong).

3. Dungeon / room generation

Common approaches, pick per game:

  • Rooms + corridors (BSP or random placement): place non-overlapping rooms, then connect. BSP recursively splits space and puts a room in each leaf; connect sibling leaves → guaranteed structure. Random placement: drop rooms, reject overlaps, connect with L-shaped/A* corridors.
  • Cellular automata caves: fill grid randomly (~45% wall), run several smoothing passes (cell = neighbors≥5 ? wall : floor) → organic caverns. Then flood-fill and keep only the largest connected region (or carve tunnels to connect regions).
  • Drunkard's walk / random walk: carve floors along a random walk for winding caves.

Critical rule: guarantee connectivity. After generation, flood-fill from the entrance and verify every important tile (exit, key rooms, loot) is reachable. Discard/regenerate or carve connectors otherwise. "Unreachable exit / locked-in player" is the #1 procgen bug. Also validate: min room count, spawn ≠ exit, no soft-locks.

4. Maze generation

  • Grid where each cell has walls; carve passages.
  • Recursive backtracker (randomized DFS): deep, winding mazes with long corridors — most common.
  • Randomized Prim's / Kruskal's: more uniform, bushier mazes.
  • All produce a "perfect maze" (exactly one path between any two cells). Add loops by knocking out extra walls if you want multiple routes.
  • Use your seeded rng for neighbor choice so the maze is reproducible.

5. Terrain generation

  • Heightmap from fBm simplex (see §2): sample noise per cell → elevation → color/mesh. Threshold into water/sand/grass/rock/snow bands.
  • Domain warping (offset sample coords by another noise) for more natural, less "blobby" coastlines.
  • For 3D: feed the heightmap into a plane geometry's vertex Y (Three.js PlaneGeometry + displace vertices) and computeVertexNormals(); consider chunking + LOD for large worlds.
  • Keep generation deterministic per chunk: derive each chunk's local seed from (worldSeed, chunkX, chunkY) so infinite/streamed worlds are stable and reproducible.

6. Wave Function Collapse (WFC) basics

WFC is a constraint-solver that generates output where every local neighborhood matches examples/adjacency rules — great for tile maps, textures, and levels that must "fit together."

Algorithm (overlapping or simple-tiled):

  1. Every cell starts in superposition (all tiles possible).
  2. Observe: pick the lowest-entropy cell (fewest remaining options) and collapse it to one tile (weighted-random).
  3. Propagate: remove now-impossible neighbors' options based on adjacency rules; repeat until stable.
  4. Loop until all cells collapsed, or backtrack/restart on contradiction (a cell with zero options).

Rules & gotchas:

  • Adjacency rules come from a sample image (overlapping model) or hand-authored tile edges (simple-tiled model).
  • Contradictions happen — implement restart or backtracking; without it, generation hangs/throws.
  • Weight tiles for aesthetics; use noise (from §2) to bias regional weights for large-scale structure, then WFC for coherent local detail.
  • For JS: mxgmn/WaveFunctionCollapse (original), Boris the Brave's write-up + DeBroglie, or ndarray-based JS ports.

Note: Red Blob Games does not have a WFC tutorial (a common false citation). Cite Maxim Gumin's repo and Boris the Brave instead. Red Blob Games is the canonical source for noise maps and A*/grids.

7. Bug-prevention checklist

  • Math.random() for generation → non-reproducible, unshareable, undebuggable, desyncs multiplayer; use a seeded PRNG.
  • String seed used directly → NaN/garbage; hash to int (xmur3) first.
  • Shared single RNG stream across systems → tweaking one system reshuffles all; use separate streams.
  • No connectivity check → unreachable exits / trapped player; flood-fill validate & regenerate.
  • Forgetting to seed simplex-noise (v4) → falls back to Math.random(), non-reproducible; pass your PRNG to createNoise2D.
  • Single-octave noise → smooth but featureless; add fBm octaves.
  • Deriving moisture from elevation → correlated, unrealistic biomes; use independent noise fields.
  • WFC with no contradiction handling → infinite loop / crash; add restart/backtrack.
  • Per-frame regeneration or huge synchronous gen → jank; generate in chunks / a web worker / on level load.
  • Non-deterministic chunk seeds → seams/flicker in streamed worlds; derive chunk seed from (worldSeed, cx, cy).

Defaults to apply

  • Every generated procgen game gets a visible/optional seed driven by mulberry32 (with xmur3 for string seeds), plus randRange/randInt/pick/shuffle helpers and separate RNG streams per system. Reproducibility is free QA, shareable content, and multiplayer-safe.
  • Terrain/organic → seeded simplex-noise v4 (createNoise2D(rng)) with fBm octaves + redistribution + island mask + independent elevation/moisture per Red Blob Games.
  • Dungeons → rooms+corridors or cellular-automata caves, ALWAYS followed by a flood-fill connectivity guarantee (regenerate on failure). Ship this validation step by default — it prevents the worst procgen bug.
  • Offer WFC for tile-based levels/textures (with contradiction restart), optionally seeded by noise for macro structure. Do heavy generation in a worker/on load, not per frame.

Sources

Reference in New Issue View Git Blame Copy Permalink