procedural-gen

# Dungeon and level generation

Three families cover most 2D level generation. All write into a plain grid
(`0 = wall`, `1 = floor`) that a tile pass renders later. All take a seeded RNG.

## A. Rooms and corridors

Simple, readable, gives recognizable rooms. Place rectangles, then connect.

```python
def generate(W, H, rng, attempts=200, rmin=4, rmax=9):
    grid = [[0]*W for _ in range(H)]          # 0 = wall
    rooms = []
    for _ in range(attempts):
        w = rng.randint(rmin, rmax); h = rng.randint(rmin, rmax)
        x = rng.randint(1, W - w - 1); y = rng.randint(1, H - h - 1)
        new = (x, y, w, h)
        if any(_overlap(new, o, pad=1) for o in rooms):
            continue                          # keep at least one tile between rooms
        _carve_room(grid, new)
        if rooms:                             # connect to the previously placed room
            (cx, cy), (px, py) = _center(new), _center(rooms[-1])
            _carve_h(grid, px, cx, py)        # horizontal leg
            _carve_v(grid, py, cy, cx)        # vertical leg -> L-shaped corridor
        rooms.append(new)
    return grid, rooms
```

For more interesting connectivity than "chain the rooms", connect rooms via a
minimum spanning tree of their centers, then add a few extra edges for loops.

## B. BSP (binary space partitioning)

Splits space recursively, guaranteeing rooms never overlap and tile the map. Good
for structured, building-like dungeons.

```python
def bsp(node, rng, depth, min_size=8):
    if depth == 0 or (node.w < min_size*2 and node.h < min_size*2):
        node.room = _random_room_inside(node, rng)   # leaf: place one room
        return
    if node.w > node.h:                               # split the longer axis
        cut = rng.randint(min_size, node.w - min_size)
        left, right = node.split_vertical(cut)
    else:
        cut = rng.randint(min_size, node.h - min_size)
        left, right = node.split_horizontal(cut)
    bsp(left, rng, depth-1, min_size); bsp(right, rng, depth-1, min_size)
    node.children = (left, right)
    _connect(left.room_or_subroom(), right.room_or_subroom(), rng)  # join siblings
```

Connect siblings as the recursion unwinds, so every region links to its sibling
and the whole tree stays connected.

## C. Random-walk / cellular caves

Organic caverns. Either carve with a drunkard's walk, or seed noise then smooth
with cellular automata.

```python
# Drunkard's walk: a digger wanders, carving floor, until enough is open.
def drunkard(W, H, rng, target_ratio=0.45):
    grid = [[0]*W for _ in range(H)]
    x, y = W//2, H//2; carved = 0; goal = int(W*H*target_ratio)
    while carved < goal:
        if grid[y][x] == 0: grid[y][x] = 1; carved += 1
        x = clamp(x + rng.choice([-1,0,1]), 1, W-2)   # random step, stay in bounds
        y = clamp(y + rng.choice([-1,0,1]), 1, H-2)
    return grid

# Cellular automata smoothing: a cell becomes wall if most neighbors are walls.
def smooth(grid, W, H, steps=4):
    for _ in range(steps):
        new = [row[:] for row in grid]
        for y in range(1, H-1):
            for x in range(1, W-1):
                walls = sum(1 for dy in (-1,0,1) for dx in (-1,0,1)
                            if grid[y+dy][x+dx] == 0)
                new[y][x] = 0 if walls >= 5 else 1   # 5/9 majority rule
        grid = new
    return grid
```

## Connectivity validation (do this every time)

Generation can isolate regions. Flood-fill from the spawn; if floor tiles remain
unreached, either discard the map, dig a tunnel to the nearest reached tile, or
keep only the largest region.

```python
def reachable_floor(grid, start):
    seen, stack = set(), [start]
    while stack:
        x, y = stack.pop()
        if (x, y) in seen or grid[y][x] == 0: continue
        seen.add((x, y))
        stack += [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]
    return seen        # compare len(seen) to total floor count; reconnect the rest
```

Also validate: a path from spawn to exit exists (reuse `game-ai` A*), the spawn
tile is safe, and key items aren't behind locks they themselves gate.

## Distribution control for loot/spawns

Pure weighted rolls produce streaks (ten commons in a row). Two fixes:

- **Bag / deck**: fill a bag with items in proportion to weights, shuffle, draw
  without replacement, refill when empty. Guarantees the rate over a window.
- **Pity timer**: track rolls since the last rare; once a threshold is passed,
  force or boost the rare's chance. Common in gacha/loot systems.

Keep these in the seeded RNG too, so drop sequences stay reproducible.

# Noise for terrain, biomes, and scatter

Gradient noise (Perlin, Simplex, OpenSimplex) is the workhorse of procedural
terrain. A noise function maps a continuous 2D/3D coordinate to a smooth value;
sampling it across a grid gives a coherent heightfield. **Use a library** —
implementing correct gradient noise is fiddly and rarely worth it.

Libraries by ecosystem: `FastNoiseLite` (C/C++/C#/Rust/JS/GLSL/HLSL and many
more), `opensimplex` (Python), `simplex-noise` (JS/TS), `Unity.Mathematics.noise`
or `Mathf.PerlinNoise` (Unity). Note the output range differs: some return
`0..1`, others `-1..+1`. Rescale to a known range before combining.

## Frequency and wavelength

Sampling `noise(freq * x, freq * y)` zooms the pattern. Higher frequency = more,
smaller features; `wavelength = map_size / frequency`. Always normalize the input
coordinate (e.g. `nx = x / width`) so the same frequency means the same thing
across map sizes.

## Octaves (fractal Brownian motion)

Real terrain mixes large landforms with small detail. Sum octaves: each octave
multiplies frequency by **lacunarity** (commonly 2.0) and amplitude by **gain**
(a.k.a. persistence, commonly 0.5).

```python
def fbm(noise, x, y, octaves=5, lacunarity=2.0, gain=0.5):
    total, amp, freq, norm = 0.0, 1.0, 1.0, 0.0
    for _ in range(octaves):
        total += amp * noise(x * freq, y * freq)
        norm  += amp
        amp   *= gain
        freq  *= lacunarity
    return total / norm        # divide by summed amplitude -> stays in 0..1
```

To keep octaves independent (avoid correlation artifacts near the origin), give
each octave its own seed, or add a per-octave offset like
`noise(2*x + 5.3, 2*y + 9.1)`.

## Redistribution: shaping the elevation curve

Raw fBm is "all hills". Reshape it with a function `e = f(e)`:

- **Valleys/plateaus**: `e = pow(e, exponent)` with `exponent > 1` pushes mid
  elevations down into flats; `< 1` pulls them up toward peaks.
- **Ridges (mountain spines)**: `r = 1 - abs(2*noise - 1)` (a "ridged" transform)
  before summing octaves.
- **Terraces**: `e = round(e * levels) / levels` snaps to discrete bands.

These are the same image-filter ideas as a photo "curves" tool; experiment and
keep a fudge factor near 1.0 (`pow(e * 1.2, exponent)`).

## Biome lookup from two fields

One noise value bands the map; two decorrelated values give variety. Sample
**elevation** and **moisture** from different seeds, then table-lookup:

```python
def biome(e, m):
    if e < 0.10: return "OCEAN"
    if e < 0.12: return "BEACH"
    if e > 0.80:
        return "SNOW" if m > 0.5 else "TUNDRA"
    if e > 0.60:
        return "TAIGA" if m > 0.66 else "SHRUBLAND"
    if m < 0.16: return "DESERT"
    if m < 0.50: return "GRASSLAND"
    return "FOREST"
# These thresholds are starting points — every generator needs its own tuning.
```

## Island shaping

To force water at the map borders, blend the elevation toward a distance-based
shape. With `nx, ny` in `-1..+1` from center:

```python
# Square-bump distance: 0 at center, ~1 at edges.
d = 1 - (1 - nx*nx) * (1 - ny*ny)
e = lerp(e, 1 - d, mix)        # mix=0 -> original; mix~0.5 -> island
```

Round islands: `d = min(1, (nx*nx + ny*ny) / sqrt(2))`. Apply island shaping only
to low-frequency octaves to keep coastline detail.

## Object scatter (trees, rocks)

For natural spacing, do **not** threshold high-frequency noise. Prefer **Poisson
disc sampling** or a **jittered grid**, which guarantee a minimum spacing and
avoid clumping. Vary the minimum radius per biome for variable density (dense
forest vs sparse desert).

## Wraparound (seamless) maps

For a map whose east edge tiles with its west edge, sample noise on a cylinder:
map `x` to an angle and feed `cos/sin` into 3D noise. Tiling both axes uses 4D
noise on a torus. Higher-dimensional noise has a narrower output range, so
rescale afterward.

## Determinism checklist

- One seeded noise generator per field, stored in the save.
- No time-, frame-, or hash-randomized input feeding generation.
- Same engine + same library version = same output (note: switching noise
  libraries changes results even with the same seed).

---
name: procedural-gen
description: >
  Generate game content procedurally — seeded deterministic RNG, value/Perlin/
  Simplex noise for terrain and heightmaps, grid dungeon generation (rooms +
  corridors, BSP, random walk), and weighted loot/drop tables. Engine-neutral
  algorithms. Use when the user mentions procedural generation, perlin/simplex
  noise, random seed, dungeon generator, heightmap/terrain, or loot tables.
---

# Procedural generation

Generate levels, terrain, and loot from compact rules and a seed. The throughline
of good procgen is **determinism**: a single seed reproduces the same world, so
bugs are repeatable and players can share seeds. This skill owns the core
algorithms — noise, seeded RNG, dungeon layout, weighted tables; genres like
`roguelike` and `survival-crafting` consume it.

## When to use

- Use to generate maps, dungeons, terrain heightmaps, item drops, or any content
  you do not want to author by hand.
- Use when results must be **reproducible from a seed** (debugging, daily
  challenges, shareable worlds).
- Use to pick weighted random outcomes (loot rarity, spawn tables).

**When *not* to use:** for the engine's tile API to *paint* the result, use
`godot-tilemap` or `unity-tilemap-2d`. For routing AI through the generated map,
use `game-ai`. For carefully hand-paced levels, use `level-design` — procgen and
authored design are complementary, not interchangeable.

## Core workflow

1. **Own your randomness.** Create one seeded RNG instance and pass it
   everywhere. Never call the global/static random in generation code — it makes
   results irreproducible and order-dependent.
2. **Pick the technique for the content.** Continuous terrain/heightmaps → noise.
   Discrete rooms/corridors → space partitioning or agent-based carving.
   Outcomes with rarities → weighted tables.
3. **Generate into a plain data grid/array first**, decoupled from rendering.
   Generation fills `int[][]` or a dict; a separate pass draws it.
4. **Validate before shipping the result to the player.** Is every room
   reachable? Is the spawn safe? Is there a path to the exit? Reject or repair
   layouts that fail; do not hand the player a broken map.
5. **Tune with the seed fixed** so each parameter change is visible in isolation,
   then sweep seeds to check the distribution, not just one lucky map.

## Patterns

### 1. Seeded, deterministic RNG (the foundation)

```python
import random
rng = random.Random(seed)        # a dedicated instance — NOT the global random.*
room_count = rng.randint(5, 12)  # same seed -> same sequence, every run
# RIGHT: thread `rng` through every function that makes a choice.
# WRONG: calling random.randint(...) (global state) — order-dependent, unseedable.
```

Engine equivalents: Godot `var rng = RandomNumberGenerator.new(); rng.seed = s`;
Unity `var rng = new System.Random(seed)` (or `UnityEngine.Random.InitState`).
Store the seed in the save file so a world can be regenerated.

### 2. Fractal (fBm) noise for heightmaps

```python
# Sum several octaves: each higher octave has higher frequency, lower amplitude.
def fbm(noise, x, y, octaves=5, lacunarity=2.0, gain=0.5):
    total, amp, freq, norm = 0.0, 1.0, 1.0, 0.0
    for _ in range(octaves):
        total += amp * noise(x * freq, y * freq)   # noise() returns ~0..1
        norm  += amp                                # track total amplitude
        amp   *= gain                               # each octave contributes less
        freq  *= lacunarity                         # ...at a higher frequency
    return total / norm                             # normalize back into 0..1

# Redistribute to carve flat valleys / sharpen peaks: higher exp -> more lowland.
elevation = pow(fbm(noise, nx, ny), 2.2)
```

Use a real noise library (`FastNoiseLite`, `opensimplex`,
`Unity.Mathematics.noise`, or `Mathf.PerlinNoise`) — do not implement gradient
noise yourself. Seed **elevation and moisture with different seeds** so a
biome lookup over both fields isn't perfectly correlated. Full biome lookup and
island shaping are in `references/noise.md`.

### 3. Weighted loot table (rarity-correct selection)

```python
# Roll proportional to weight: common drops far more often than legendary.
def weighted_pick(rng, table):           # table: list of (item, weight)
    total = sum(w for _, w in table)
    roll = rng.uniform(0, total)          # a point on the cumulative line
    upto = 0.0
    for item, w in table:
        upto += w
        if roll < upto:                   # first bucket the roll falls into
            return item
    return table[-1][0]                   # float-safety fallback

loot = weighted_pick(rng, [("common", 70), ("rare", 25), ("legendary", 5)])
```

Weights need not sum to 100 — they are relative. To prevent bad streaks, use a
"pity"/bag system (see `references/dungeon-generation.md` notes on distributions).

### 4. Rooms-and-corridors dungeon (sketch)

```python
# 1. Place non-overlapping rooms; 2. connect them; 3. carve into the grid.
rooms = []
for _ in range(attempts):
    r = Rect(rng.randint(1, W-w-1), rng.randint(1, H-h-1), w, h)
    if not any(r.intersects(o.expand(1)) for o in rooms):  # keep a 1-tile gap
        rooms.append(r)
for a, b in zip(rooms, rooms[1:]):       # connect each room to the next
    carve_l_corridor(grid, a.center, b.center, rng)   # horizontal then vertical
```

The complete generator (BSP partitioning, L-corridors, reachability check, and
random-walk caves) is in `references/dungeon-generation.md`.

## Pitfalls

- **Using the global RNG** inside generation makes worlds unreproducible and
  breaks the moment call order changes. Always pass a seeded instance.
- **Correlated noise fields**: sampling elevation and moisture from the *same*
  seed/offset produces biomes that line up in bands. Offset or reseed each field.
- **Octave artifacts**: adding octaves without renormalizing pushes values out of
  `0..1`; divide by the summed amplitude (and beware library output ranges — some
  return `-1..1`, some `0..1`).
- **No connectivity check**: rooms or caves can end up isolated. Flood-fill from
  the spawn and discard/reconnect unreachable regions before play.
- **Unbounded placement loops**: "keep trying until N rooms fit" can spin forever
  on a small grid. Cap attempts and accept fewer rooms.
- **Seeding once globally, then relying on frame timing**: any non-deterministic
  input (time, physics, hash randomization) leaking into generation destroys
  reproducibility.

## References

- `references/noise.md` — octaves/lacunarity/gain, redistribution, island
  shaping, two-axis biome lookup, blue-noise object scatter.
- `references/dungeon-generation.md` — BSP, rooms+corridors, random-walk caves,
  cellular-automata smoothing, connectivity validation, distribution/pity tables.

## Related skills

- `godot-tilemap`, `unity-tilemap-2d` — paint the generated grid into the engine.
- `game-ai` — pathfinding over the generated graph.
- `level-design` — pacing and hand-authored structure that procgen complements.
- `roguelike`, `survival-crafting` — genres that compose this skill.