Made of little things.

import { createRng, type Rng } from './rng.ts';

/** World units per terrain cell. */
export const CELL = 4;
export const WORLD_COLS = 1200;
export const WORLD_ROWS = 260;
/** The surface landscape is laid out as if the world were this many rows deep; the rest is cave country. */
const SURFACE_ROWS = 160;

// Foreground materials: these take part in collision.
export const AIR = 0;
export const DIRT = 1;
export const GRASS = 2;
export const STONE = 3;
export const BEDROCK = 4;
export const BRICK = 5;
export const PLANK = 6;
export const LEAF = 7;
export const CAP = 8;
export const ROOF = 9;
export const CRATE = 10;

// Background materials: decorative and passable, still destroyed by blasts.
export const BG_NONE = 0;
export const BG_WALL = 1;
export const BG_TRUNK = 2;
export const BG_STEM = 3;
export const BG_WINDOW = 4;
export const BG_WINDOW_DARK = 5;
/** Bioluminescent cave fungus cap. */
export const BG_GLOW = 6;
/** Dark timber: posts, ceiling beams, window frames and furniture legs. */
export const BG_BEAM = 7;
/** A second plaster tone so neighbouring rooms read apart. */
export const BG_WALL_ALT = 8;
/** Bookshelf backs; the renderer varies book colors per cell. */
export const BG_SHELF = 9;

export const COLLIDE_NONE = 0;
export const COLLIDE_SOLID = 1;
/** One-way platforms: land on them from above, jump up through them. */
export const COLLIDE_ONEWAY = 2;

const COLLISION = new Uint8Array(16);
COLLISION[DIRT] = COLLIDE_SOLID;
COLLISION[GRASS] = COLLIDE_SOLID;
COLLISION[STONE] = COLLIDE_SOLID;
COLLISION[BEDROCK] = COLLIDE_SOLID;
COLLISION[BRICK] = COLLIDE_SOLID;
COLLISION[ROOF] = COLLIDE_SOLID;
COLLISION[CRATE] = COLLIDE_SOLID;
COLLISION[PLANK] = COLLIDE_ONEWAY;
COLLISION[LEAF] = COLLIDE_ONEWAY;
COLLISION[CAP] = COLLIDE_ONEWAY;

/** How much of a blast radius a material resists (1 = no resistance). */
const BLAST_REACH = new Float32Array(16).fill(1);
BLAST_REACH[STONE] = 0.8;
BLAST_REACH[BRICK] = 0.9;
BLAST_REACH[BEDROCK] = 0;

export interface DirtyRect {
  x0: number;
  y0: number;
  x1: number;
  y1: number;
}

export interface CarveResult {
  removed: number;
  /** A small sample of removed foreground materials, for debris colors. */
  sample: number[];
}

export class Terrain {
  readonly cols: number;
  readonly rows: number;
  readonly fg: Uint8Array;
  readonly bg: Uint8Array;
  /** Stable per-cell texture noise (0–255). */
  readonly noise: Uint8Array;
  /** Blast scorching (0–255). */
  readonly scorch: Uint8Array;
  /** Original ground row per column; open cells below it show the earth back wall. */
  readonly surface: Int16Array;
  /** Cell indices of glowing fungus caps, for the renderer's light pass. */
  glows: number[] = [];
  dirty: DirtyRect | null = null;

  constructor(cols: number, rows: number, seed = 1) {
    this.cols = cols;
    this.rows = rows;
    this.fg = new Uint8Array(cols * rows);
    this.bg = new Uint8Array(cols * rows);
    this.noise = new Uint8Array(cols * rows);
    this.scorch = new Uint8Array(cols * rows);
    this.surface = new Int16Array(cols).fill(rows);
    const rng = createRng(seed ^ 0x9e3779b9);
    for (let i = 0; i < this.noise.length; i++) this.noise[i] = Math.floor(rng.next() * 256);
  }

  get width(): number {
    return this.cols * CELL;
  }

  get height(): number {
    return this.rows * CELL;
  }

  inBounds(cx: number, cy: number): boolean {
    return cx >= 0 && cy >= 0 && cx < this.cols && cy < this.rows;
  }

  /** Foreground material; the world sides and floor behave as bedrock. */
  fgAt(cx: number, cy: number): number {
    if (cx < 0 || cx >= this.cols || cy >= this.rows) return BEDROCK;
    if (cy < 0) return AIR;
    return this.fg[cy * this.cols + cx];
  }

  set(cx: number, cy: number, material: number): void {
    if (this.inBounds(cx, cy)) this.fg[cy * this.cols + cx] = material;
  }

  setBg(cx: number, cy: number, material: number): void {
    if (this.inBounds(cx, cy)) this.bg[cy * this.cols + cx] = material;
  }

  collisionAt(cx: number, cy: number): number {
    return COLLISION[this.fgAt(cx, cy)];
  }

  /** Collision class at a world-space point. */
  collisionAtPoint(x: number, y: number): number {
    return this.collisionAt(Math.floor(x / CELL), Math.floor(y / CELL));
  }

  /** Cells below the original ground line at a world point (negative above ground). */
  depthAt(x: number, y: number): number {
    const cx = Math.max(0, Math.min(this.cols - 1, Math.floor(x / CELL)));
    return y / CELL - this.surface[cx];
  }

  /** First row (from the top) that something could stand on. */
  surfaceRow(cx: number): number {
    for (let cy = 0; cy < this.rows; cy++) {
      if (this.collisionAt(cx, cy) !== COLLIDE_NONE) return cy;
    }
    return this.rows;
  }

  markDirty(x0: number, y0: number, x1: number, y1: number): void {
    const rect = {
      x0: Math.max(0, x0),
      y0: Math.max(0, y0),
      x1: Math.min(this.cols - 1, x1),
      y1: Math.min(this.rows - 1, y1),
    };
    if (!this.dirty) {
      this.dirty = rect;
      return;
    }
    this.dirty.x0 = Math.min(this.dirty.x0, rect.x0);
    this.dirty.y0 = Math.min(this.dirty.y0, rect.y0);
    this.dirty.x1 = Math.max(this.dirty.x1, rect.x1);
    this.dirty.y1 = Math.max(this.dirty.y1, rect.y1);
  }

  /** Blow a roughly circular hole in the world and scorch its rim. */
  carve(wx: number, wy: number, radius: number): CarveResult {
    const scorchRadius = radius * 1.4;
    const cx0 = Math.floor((wx - scorchRadius) / CELL);
    const cx1 = Math.floor((wx + scorchRadius) / CELL);
    const cy0 = Math.floor((wy - scorchRadius) / CELL);
    const cy1 = Math.floor((wy + scorchRadius) / CELL);
    let removed = 0;
    const sample: number[] = [];

    for (let cy = cy0; cy <= cy1; cy++) {
      for (let cx = cx0; cx <= cx1; cx++) {
        if (!this.inBounds(cx, cy)) continue;
        const i = cy * this.cols + cx;
        const dx = (cx + 0.5) * CELL - wx;
        const dy = (cy + 0.5) * CELL - wy;
        const d = Math.hypot(dx, dy);
        // A little noise roughens the crater edge.
        const rough = radius * (0.92 + (this.noise[i] / 255) * 0.16);
        const m = this.fg[i];
        if (m !== AIR && d < rough * BLAST_REACH[m]) {
          this.fg[i] = AIR;
          removed++;
          if (sample.length < 48 && (removed & 1) === 0) sample.push(m);
        }
        if (this.bg[i] !== BG_NONE && d < rough * 0.95) this.bg[i] = BG_NONE;
        if (d < scorchRadius) {
          const heat = Math.min(1, Math.max(0, 1 - (d - radius * 0.7) / (scorchRadius - radius * 0.7)));
          this.scorch[i] = Math.max(this.scorch[i], Math.round(heat * 235));
        }
      }
    }
    this.markDirty(cx0 - 1, cy0 - 1, cx1 + 1, cy1 + 1);
    return { removed, sample };
  }
}

export interface Landmark {
  kind: 'building' | 'tree' | 'mushroom' | 'island' | 'cave-mouth';
  x0: number;
  x1: number;
}

export interface World {
  terrain: Terrain;
  spawnX: number;
  spawnY: number;
  landmarks: Landmark[];
}

/** Generate a new world: cliffs, ledges, islands, houses, trees and mushrooms over a cave network. */
export function generateWorld(seed: number, cols = WORLD_COLS, rows = WORLD_ROWS): World {
  const rng = createRng(seed);
  const terrain = new Terrain(cols, rows, seed);
  const ground = buildHeightmap(rng, cols, Math.min(rows, SURFACE_ROWS));
  const flats: { x0: number; x1: number }[] = [];
  const landmarks: Landmark[] = [];
  /** Feature counts were tuned for a 600-column world; scale them with width. */
  const scale = cols / 600;

  fillGround(rng, terrain, ground);
  addOverhangs(rng, terrain, ground);
  terrain.surface.set(ground);

  // Near-flat runs are candidate building lots; the house levels the rest.
  let runStart = 0;
  for (let x = 1; x <= cols; x++) {
    if (x === cols || Math.abs(ground[x] - ground[runStart]) > 2) {
      if (x - runStart >= HOUSE_MIN_WIDTH + 4) flats.push({ x0: runStart, x1: x - 1 });
      runStart = x;
    }
  }

  const used = new Uint8Array(cols);
  const reserve = (x0: number, x1: number, pad: number): boolean => {
    for (let x = Math.max(0, x0 - pad); x <= Math.min(cols - 1, x1 + pad); x++) if (used[x]) return false;
    for (let x = Math.max(0, x0); x <= Math.min(cols - 1, x1); x++) used[x] = 1;
    return true;
  };
  // Keep the spawn column clear of buildings.
  const spawnCol = Math.floor(cols / 2);
  for (let x = spawnCol - 5; x <= spawnCol + 5; x++) used[x] = 1;

  // Caves come first so houses and trees never stand over a cave mouth.
  for (const mouth of carveCaves(rng, terrain, ground, spawnCol, scale)) {
    for (let x = Math.max(0, mouth - 8); x <= Math.min(cols - 1, mouth + 8); x++) used[x] = 1;
    landmarks.push({ kind: 'cave-mouth', x0: mouth - 5, x1: mouth + 5 });
  }

  const houseTarget = Math.round(6 * scale);
  let houses = 0;
  for (const flat of flats.sort(() => rng.next() - 0.5)) {
    const width = rng.int(HOUSE_MIN_WIDTH, Math.min(HOUSE_MAX_WIDTH, flat.x1 - flat.x0 - 2));
    if (width < HOUSE_MIN_WIDTH) continue;
    const x0 = rng.int(flat.x0 + 1, flat.x1 - width - 1);
    // The reservation also covers eaves, balconies and the graded approach on each side.
    if (x0 < 24 || x0 + width > cols - 24 || !reserve(x0 - HOUSE_YARD, x0 + width - 1 + HOUSE_YARD, 2)) continue;
    buildHouse(rng, terrain, ground, x0, width);
    landmarks.push({ kind: 'building', x0, x1: x0 + width - 1 });
    if (++houses >= houseTarget) break;
  }

  const treeTarget = Math.round(rng.int(12, 18) * scale);
  for (let attempt = 0, made = 0; attempt < 200 * scale && made < treeTarget; attempt++) {
    const x = rng.int(22, cols - 23);
    const level = terrain.surfaceRow(x);
    if (Math.abs(terrain.surfaceRow(x + 1) - level) > 1 || terrain.fgAt(x, level) !== GRASS) continue;
    if (!reserve(x - 3, x + 4, 1)) continue;
    plantTree(rng, terrain, x, level);
    landmarks.push({ kind: 'tree', x0: x - 3, x1: x + 4 });
    made++;
  }

  const shroomTarget = Math.round(rng.int(9, 15) * scale);
  for (let attempt = 0, made = 0; attempt < 200 * scale && made < shroomTarget; attempt++) {
    const x = rng.int(22, cols - 23);
    const level = terrain.surfaceRow(x);
    if (terrain.fgAt(x, level) !== GRASS) continue;
    if (!reserve(x - 2, x + 2, 0)) continue;
    growMushroom(rng, terrain, x, level);
    landmarks.push({ kind: 'mushroom', x0: x - 2, x1: x + 2 });
    made++;
  }

  for (let i = Math.round(rng.int(6, 10) * scale); i > 0; i--) {
    const x = rng.int(25, cols - 26);
    const level = terrain.surfaceRow(x);
    if (used[x] || used[x + 2] || terrain.fgAt(x, level) !== GRASS) continue;
    if (rng.chance(0.55)) placeBoulder(rng, terrain, x, level);
    else placeCrates(rng, terrain, x, level);
  }

  for (let i = Math.round(rng.int(3, 6) * scale); i > 0; i--) {
    const width = rng.int(9, 20);
    const x0 = rng.int(25, cols - width - 25);
    let top = rows;
    for (let x = x0; x < x0 + width; x++) top = Math.min(top, terrain.surfaceRow(x));
    const y = top - rng.int(17, 26);
    if (y < 12 || (x0 <= spawnCol + 6 && x0 + width >= spawnCol - 6)) continue;
    floatIsland(rng, terrain, x0, y, width);
    landmarks.push({ kind: 'island', x0, x1: x0 + width - 1 });
  }

  // Re-clear the spawn pocket in case a canopy or island hangs over it.
  const spawnRow = terrain.surfaceRow(spawnCol);
  for (let y = spawnRow - 9; y < spawnRow; y++) {
    for (let x = spawnCol - 2; x <= spawnCol + 2; x++) {
      if (terrain.collisionAt(x, y) !== COLLIDE_NONE) terrain.set(x, y, AIR);
    }
  }
  terrain.dirty = { x0: 0, y0: 0, x1: cols - 1, y1: rows - 1 };
  return {
    terrain,
    spawnX: (spawnCol + 0.5) * CELL,
    spawnY: terrain.surfaceRow(spawnCol) * CELL,
    landmarks,
  };
}

function buildHeightmap(rng: Rng, cols: number, rows: number): Int16Array {
  const ground = new Int16Array(cols);
  const minLevel = Math.round(rows * 0.4);
  const maxLevel = Math.round(rows * 0.74);
  let level = Math.round(rows * 0.6);
  let x = 0;
  while (x < cols) {
    const len = rng.int(16, 52);
    const kind = rng.next();
    const start = level;
    let target = level;
    if (kind < 0.28) {
      // Cliff: an abrupt step up or down.
      level = clamp(level + rng.sign() * rng.int(9, 20), minLevel, maxLevel);
      target = level;
    } else if (kind < 0.6) {
      target = clamp(level + rng.sign() * rng.int(4, 14), minLevel, maxLevel);
    }
    const hill = kind > 0.82 ? rng.int(3, 9) : 0;
    for (let i = 0; i < len && x < cols; i++, x++) {
      const t = i / len;
      const base = kind < 0.28 ? level : Math.round(start + (target - start) * t);
      ground[x] = base - Math.round(Math.sin(t * Math.PI) * hill);
    }
    level = target;
  }
  // Raise the world edges into tall walls so the level reads as bounded.
  for (let i = 0; i < 16; i++) {
    const lift = Math.round(((16 - i) / 16) ** 2 * 42);
    ground[i] = Math.max(8, ground[i] - lift);
    ground[cols - 1 - i] = Math.max(8, ground[cols - 1 - i] - lift);
  }
  return ground;
}

function fillGround(rng: Rng, terrain: Terrain, ground: Int16Array): void {
  const { cols, rows } = terrain;
  let stoneDepth = 16;
  for (let x = 0; x < cols; x++) {
    stoneDepth = clamp(stoneDepth + rng.int(-1, 1), 10, 26);
    const bedrockTop = rows - 3 - (rng.chance(0.4) ? 1 : 0);
    for (let y = ground[x]; y < rows; y++) {
      const depth = y - ground[x];
      let m = depth === 0 ? GRASS : depth < stoneDepth ? DIRT : STONE;
      if (y >= bedrockTop) m = BEDROCK;
      terrain.set(x, y, m);
    }
  }
  // Stone pockets in the dirt for texture and tougher spots.
  for (let i = Math.round(rng.int(14, 24) * (cols / 600)); i > 0; i--) {
    const x = rng.int(0, cols - 1);
    const y = ground[x] + rng.int(4, 18);
    const r = rng.range(1.5, 4);
    for (let dy = -4; dy <= 4; dy++) {
      for (let dx = -5; dx <= 5; dx++) {
        if (dx * dx * 0.6 + dy * dy <= r * r && terrain.fgAt(x + dx, y + dy) === DIRT) {
          terrain.set(x + dx, y + dy, STONE);
        }
      }
    }
  }
}

/** Stone lips that jut out over cliff drops. */
function addOverhangs(rng: Rng, terrain: Terrain, ground: Int16Array): void {
  for (let x = 20; x < terrain.cols - 20; x++) {
    const step = ground[x + 1] - ground[x];
    if (Math.abs(step) < 9 || !rng.chance(0.7)) continue;
    const dir = step > 0 ? 1 : -1;
    const top = Math.min(ground[x], ground[x + 1]);
    const reach = rng.int(3, 8);
    const from = dir > 0 ? x + 1 : x;
    for (let i = 0; i < reach; i++) {
      const cx = from + dir * i;
      const thickness = i < reach - 2 ? 3 : 2;
      for (let t = 0; t < thickness; t++) terrain.set(cx, top + t, t === 0 ? GRASS : STONE);
    }
  }
}

/** House footprint limits, in cells. */
const HOUSE_MIN_WIDTH = 28;
const HOUSE_MAX_WIDTH = 46;
/** Clear ground kept beside a house for eaves, balconies and its graded approach. */
const HOUSE_YARD = 7;
/** Floor-to-floor height: the 30-unit stickman needs ~8 cells, plus room to jump. */
const STOREY = 14;
/** Doorway height: 36 units, comfortably taller than the stickman, under a brick lintel. */
const DOOR = 9;
/** Exterior wall thickness. */
const WALL = 2;
/** Stair treads are 3 cells wide and rise 2; the top tread sits just under the stairwell. */
const STAIR_STEPS = (STOREY - 2) / 2;
const STAIR_RUN = 3;

/**
 * A multi-storey brick house: doors on both ground-floor sides, a plank
 * staircase and stairwell on every floor, furnished rooms, upper-floor
 * balconies, an optional cellar under a trapdoor, and an attic or roof deck.
 */
function buildHouse(rng: Rng, terrain: Terrain, ground: Int16Array, x0: number, width: number): void {
  let base = 0;
  for (let x = x0; x < x0 + width; x++) base = Math.max(base, ground[x]);
  const floors = Math.max(1, Math.min(rng.int(1, 3), Math.floor((base - 34) / STOREY)));
  const top = base - floors * STOREY;
  const x1 = x0 + width - 1;
  const inner0 = x0 + WALL;
  const inner1 = x1 - WALL;
  const pitched = rng.chance(0.6);

  // Level the lot: foundation below, clear air above (high enough for any roof).
  for (let x = x0 - 2; x <= x1 + 2; x++) {
    for (let y = top - 32; y < base; y++) {
      terrain.set(x, y, AIR);
      terrain.setBg(x, y, BG_NONE);
    }
    for (let y = base; y < base + 3; y++) if (terrain.fgAt(x, y) === AIR || y === base) terrain.set(x, y, y === base ? GRASS : DIRT);
    // The levelled lot is the new ground line, so the house interior stays sky-backed.
    terrain.surface[x] = base;
  }
  gradeApproach(terrain, ground, x0 - 3, -1, base);
  gradeApproach(terrain, ground, x1 + 3, 1, base);
  for (let x = x0; x <= x1; x++) terrain.set(x, base, BRICK);

  // Shell: thick brick side walls around plastered rooms.
  for (let y = top; y < base; y++) {
    for (let x = x0; x <= x1; x++) {
      if (x < inner0 || x > inner1) terrain.set(x, y, BRICK);
      else terrain.setBg(x, y, BG_WALL);
    }
  }

  let stairSide = rng.chance(0.5) ? -1 : 1;
  for (let f = 0; f < floors; f++) {
    const floorRow = base - f * STOREY;
    const ceiling = floorRow - STOREY;
    const topFloor = f === floors - 1;
    const busy = new Uint8Array(width);
    const claim = (from: number, to: number): boolean => {
      for (let x = from; x <= to; x++) if (x < inner0 || x > inner1 || busy[x - x0]) return false;
      for (let x = from; x <= to; x++) busy[x - x0] = 1;
      return true;
    };

    // Rooms: a timber post splits wide floors, and each room gets its own plaster.
    const split = inner1 - inner0 > 30 ? rng.int(inner0 + 12, inner1 - 12) : -1;
    if (rng.chance(0.5) || split > 0) {
      const from = split > 0 && rng.chance(0.5) ? split : inner0;
      const to = from === split ? inner1 : split > 0 ? split : inner1;
      for (let y = ceiling + 1; y < floorRow; y++) for (let x = from; x <= to; x++) terrain.setBg(x, y, BG_WALL_ALT);
    }
    for (let x = inner0; x <= inner1; x++) terrain.setBg(x, ceiling + 1, BG_BEAM);
    if (split > 0) {
      for (let y = ceiling + 1; y < floorRow; y++) terrain.setBg(split, y, BG_BEAM);
      busy[split - x0] = 1;
    }

    // Ceiling / next floor: one-way planks, or a solid roof deck over a flat-roofed top floor.
    for (let x = inner0; x <= inner1; x++) terrain.set(x, ceiling, topFloor && !pitched ? ROOF : PLANK);

    // Staircase up to a stairwell gap, alternating sides floor to floor.
    const run = STAIR_STEPS * STAIR_RUN;
    const sx = stairSide < 0 ? inner0 + 2 : inner1 - 2 - run + 1;
    for (let k = 0; k < STAIR_STEPS; k++) {
      const tx = stairSide < 0 ? sx + k * STAIR_RUN : sx + run - (k + 1) * STAIR_RUN;
      const row = floorRow - 2 * (k + 1);
      for (let dx = 0; dx < STAIR_RUN; dx++) terrain.set(tx + dx, row, PLANK);
      // A diagonal stringer under the treads.
      terrain.setBg(stairSide < 0 ? tx : tx + STAIR_RUN - 1, row + 1, BG_BEAM);
    }
    claim(sx, sx + run - 1);
    const wellX = stairSide < 0 ? sx + run - STAIR_RUN : sx - 2;
    const hatch = topFloor && !pitched ? PLANK : AIR;
    for (let dx = 0; dx < STAIR_RUN + 2; dx++) terrain.set(wellX + dx, ceiling, hatch);
    stairSide = -stairSide;

    // Doors: both sides on the ground floor; upper floors open onto a balcony.
    const doorSides = f === 0 ? [-1, 1] : [rng.chance(0.5) ? -1 : 1];
    for (const side of doorSides) {
      const wx = side < 0 ? x0 : inner1 + 1;
      for (let y = floorRow - DOOR; y < floorRow; y++) {
        for (let dx = 0; dx < WALL; dx++) terrain.set(wx + dx, y, AIR);
      }
      if (f > 0) {
        const edge = side < 0 ? x0 - 1 : x1 + 1;
        for (let i = 0; i < 5; i++) terrain.set(edge + side * i, floorRow, PLANK);
        // Timber brace under the balcony.
        for (let i = 0; i < 3; i++) terrain.setBg(edge + side * i, floorRow + 3 - i, BG_BEAM);
      }
    }

    // Framed windows along the back wall.
    for (let wx = inner0 + 3; wx + 5 < inner1 - 1; wx += rng.int(9, 13)) {
      if (Math.abs(wx + 2 - split) < 4) continue;
      const lit = rng.chance(0.6) ? BG_WINDOW : BG_WINDOW_DARK;
      for (let dy = 0; dy < 5; dy++) {
        for (let dx = 0; dx < 5; dx++) terrain.setBg(wx + dx, floorRow - 10 + dy, dx === 2 || dy === 2 ? BG_BEAM : lit);
      }
      for (let dx = -1; dx <= 5; dx++) terrain.setBg(wx + dx, floorRow - 5, BG_BEAM);
    }

    furnish(rng, terrain, floorRow, ceiling, inner0, inner1, claim);
  }

  if (rng.chance(0.5)) digCellar(rng, terrain, base, inner0, inner1);

  if (pitched) {
    // Hollow attic under a 2-cell roof with overhanging eaves, a gable window and a chimney.
    const e0 = x0 - 2;
    const e1 = x1 + 2;
    const roofRow = (x: number): number => top - 1 - Math.floor(Math.min(x - e0, e1 - x) * 0.8);
    for (let x = e0; x <= e1; x++) {
      const r = roofRow(x);
      terrain.set(x, r, ROOF);
      terrain.set(x, r - 1, ROOF);
      if (x >= x0 && x <= x1) for (let y = r + 1; y < top; y++) terrain.setBg(x, y, BG_WALL_ALT);
    }
    const mid = Math.floor((x0 + x1) / 2);
    for (let dy = 0; dy < 3; dy++) for (let dx = -1; dx <= 1; dx++) terrain.setBg(mid + dx, top - 6 + dy, BG_WINDOW);
    if (rng.chance(0.6)) {
      const lx = rng.chance(0.5) ? inner0 + 1 : inner1 - 4;
      for (let dy = 1; dy <= 3; dy++) for (let dx = 0; dx < 4; dx++) terrain.set(lx + dx, top - dy, CRATE);
    }
    const chimney = rng.chance(0.5) ? x0 + 4 : x1 - 5;
    const chimneyTop = roofRow(chimney + 1) - 6;
    for (let y = chimneyTop; y < roofRow(chimney + 1); y++) {
      for (let dx = 0; dx < 2; dx++) {
        if (terrain.fgAt(chimney + dx, y) === AIR) terrain.set(chimney + dx, y, BRICK);
      }
    }
  } else {
    // Flat roof deck with a parapet, reached through the top-floor trapdoor.
    for (let y = top - 2; y < top; y++) {
      for (let dx = 0; dx < WALL; dx++) {
        terrain.set(x0 + dx, y, BRICK);
        terrain.set(x1 - dx, y, BRICK);
      }
    }
    // A water tank on stilts: planks to perch on, timber legs behind.
    const tx = rng.chance(0.5) ? inner0 + 2 : inner1 - 8;
    for (let y = top - 6; y < top; y++) {
      terrain.setBg(tx + 1, y, BG_BEAM);
      terrain.setBg(tx + 5, y, BG_BEAM);
    }
    for (let dx = 0; dx < 7; dx++) terrain.set(tx + dx, top - 6, PLANK);
    for (let y = top - 11; y < top - 6; y++) for (let dx = 1; dx < 6; dx++) terrain.setBg(tx + dx, y, BG_WALL_ALT);
  }
}

/** Ease the ground beside a lot toward its foundation in walkable 2-cell steps. */
function gradeApproach(terrain: Terrain, ground: Int16Array, from: number, dir: number, base: number): void {
  let level = base;
  for (let i = 0; i < HOUSE_YARD; i++) {
    const x = from + dir * i;
    if (x < 1 || x >= terrain.cols - 1) return;
    const g = ground[x];
    if (Math.abs(g - level) <= 2) return;
    level = g < level ? level - 2 : level + 2;
    for (let y = Math.min(g, level); y < Math.max(g, level); y++) terrain.set(x, y, g < level ? AIR : DIRT);
    terrain.set(x, level, GRASS);
    ground[x] = level;
    terrain.surface[x] = level;
  }
}

/** Tables, bookshelves, crates and hanging lamps on one floor. */
function furnish(
  rng: Rng, terrain: Terrain, floorRow: number, ceiling: number, inner0: number, inner1: number,
  claim: (from: number, to: number) => boolean,
): void {
  for (let attempt = 0, placed = 0; attempt < 14 && placed < 3; attempt++) {
    const kind = rng.int(0, 2);
    const w = kind === 0 ? rng.int(5, 7) : kind === 1 ? 4 : 3;
    const x = rng.int(inner0 + 3, inner1 - 3 - w);
    if (!claim(x - 1, x + w)) continue;
    placed++;
    if (kind === 0) {
      // Table: a one-way top to hop onto, with timber legs.
      for (let dx = 0; dx < w; dx++) terrain.set(x + dx, floorRow - 3, PLANK);
      for (let dy = 1; dy <= 2; dy++) {
        terrain.setBg(x, floorRow - dy, BG_BEAM);
        terrain.setBg(x + w - 1, floorRow - dy, BG_BEAM);
      }
      if (rng.chance(0.5)) terrain.setBg(x + rng.int(1, w - 2), floorRow - 4, BG_WINDOW);
    } else if (kind === 1) {
      // Bookshelf against the back wall.
      for (let dy = 1; dy <= 7; dy++) {
        for (let dx = 0; dx < w; dx++) {
          const frame = dx === 0 || dx === w - 1 || dy % 2 === 1;
          terrain.setBg(x + dx, floorRow - dy, frame ? BG_BEAM : BG_SHELF);
        }
      }
    } else {
      // Crates, sometimes stacked into a step.
      for (let dy = 1; dy <= 3; dy++) for (let dx = 0; dx < 3; dx++) terrain.set(x + dx, floorRow - dy, CRATE);
      if (rng.chance(0.35)) {
        for (let dy = 4; dy <= 5; dy++) for (let dx = 1; dx < 3; dx++) terrain.set(x + dx, floorRow - dy, CRATE);
      }
    }
  }
  // A hanging lamp or two, clear of anything on the floor.
  for (let i = rng.int(1, 2); i > 0; i--) {
    const x = rng.int(inner0 + 3, inner1 - 4);
    for (let y = ceiling + 2; y < ceiling + 4; y++) terrain.setBg(x, y, BG_BEAM);
    terrain.setBg(x - 1, ceiling + 4, BG_WINDOW);
    terrain.setBg(x, ceiling + 4, BG_WINDOW);
    terrain.setBg(x + 1, ceiling + 4, BG_WINDOW);
  }
}

/** A brick-lined cellar under the ground floor, reached through a plank trapdoor. */
function digCellar(rng: Rng, terrain: Terrain, base: number, inner0: number, inner1: number): void {
  const c0 = inner0 + 2;
  const c1 = inner1 - 2;
  const floor = base + STOREY - 1;
  if (floor >= terrain.rows - 6) return;
  for (let y = base + 1; y <= floor; y++) {
    for (let x = c0 - 1; x <= c1 + 1; x++) {
      const edge = y === floor || x === c0 - 1 || x === c1 + 1;
      // Where the cellar meets a cave it breaks through rather than plugging the passage.
      if (edge && terrain.fgAt(x, y) === AIR) continue;
      terrain.set(x, y, edge ? BRICK : AIR);
      if (!edge) terrain.setBg(x, y, BG_WALL_ALT);
    }
  }
  for (let x = c0; x <= c1; x++) terrain.setBg(x, base + 1, BG_BEAM);
  const hatch = rng.int(c0 + 2, c1 - 6);
  for (let dx = 0; dx < 4; dx++) terrain.set(hatch + dx, base, PLANK);
  // Barrels of supplies: crates along the cellar floor.
  for (let x = c0 + 1; x + 3 <= c1; x += rng.int(5, 9)) {
    if (x + 3 > hatch - 1 && x < hatch + 5) continue;
    if (!rng.chance(0.6)) continue;
    for (let dy = 1; dy <= 3; dy++) for (let dx = 0; dx < 3; dx++) terrain.set(x + dx, floor - dy, CRATE);
  }
}

/** Solid rock kept between the landscape and the cave network, in cells. */
const CAVE_CRUST = 14;
/** Steepest cave passage, in radians from horizontal: walkable with step-ups and jumps. */
const CAVE_SLOPE = 0.6;

/**
 * Worm-carved cave network: a chain of chambers linked by tunnels across the
 * whole world, dead-end mole nooks, and a few sloping mouths from the surface.
 * Returns the mouth columns.
 */
function carveCaves(rng: Rng, terrain: Terrain, ground: Int16Array, spawnCol: number, scale: number): number[] {
  const { cols, rows } = terrain;
  const bottom = rows - 8;
  const open = new Uint8Array(cols * rows);
  const top = (x: number): number => ground[clamp(Math.round(x), 0, cols - 1)] + CAVE_CRUST;

  const dig = (x: number, y: number, r: number): void => {
    const r2 = r * r;
    for (let cy = Math.floor(y - r); cy <= Math.ceil(y + r); cy++) {
      for (let cx = Math.floor(x - r); cx <= Math.ceil(x + r); cx++) {
        if (!terrain.inBounds(cx, cy) || cx < 3 || cx >= cols - 3) continue;
        const dx = cx + 0.5 - x;
        const dy = cy + 0.5 - y;
        if (dx * dx + dy * dy > r2 || terrain.fgAt(cx, cy) === BEDROCK) continue;
        terrain.set(cx, cy, AIR);
        open[cy * cols + cx] = 1;
      }
    }
  };

  /** Walk a worm from (x, y) along `steer`, carving as it goes. */
  const worm = (
    x: number, y: number, heading: number, steps: number, radius: number,
    steer: (x: number, y: number) => number | null, crust = true,
  ): void => {
    const wobble = rng.range(0, Math.PI * 2);
    for (let i = 0; i < steps; i++) {
      const want = steer(x, y);
      if (want === null) return;
      heading = clampSlope(turnToward(heading, want, 0.14) + rng.range(-0.3, 0.3));
      x += Math.cos(heading);
      y += Math.sin(heading);
      const r = radius + Math.sin(i * 0.13 + wobble) * 0.6;
      if (crust) y = clamp(y, top(x) + r + 1, bottom - r);
      if (x < 8 || x > cols - 9) return;
      dig(x, y, r);
    }
  };

  const chamber = (x: number, y: number): void => {
    const rx = rng.range(11, 22);
    const ry = rng.range(8, 13);
    const a = rng.range(0, Math.PI * 2);
    const b = rng.range(0, Math.PI * 2);
    // Lumpy, flat-floored ellipse: the lower part is cut off so the floor is walkable.
    for (let dy = -Math.ceil(ry * 1.3); dy <= Math.floor(ry * 0.55); dy++) {
      for (let dx = -Math.ceil(rx * 1.3); dx <= Math.ceil(rx * 1.3); dx++) {
        const theta = Math.atan2(dy / ry, dx / rx);
        const lump = 1 + Math.sin(theta * 3 + a) * 0.16 + Math.sin(theta * 5 + b) * 0.09;
        if ((dx / rx) ** 2 + (dy / ry) ** 2 <= lump * lump) dig(x + dx, y + dy, 0.75);
      }
    }
  };

  const tunnel = (a: { x: number; y: number }, b: { x: number; y: number }): void => {
    const steps = Math.round((Math.abs(b.x - a.x) + Math.abs(b.y - a.y)) * 2.5);
    worm(a.x, a.y, Math.atan2(b.y - a.y, b.x - a.x), steps, rng.range(4.6, 5.6), (x, y) =>
      Math.hypot(b.x - x, b.y - y) < 2 ? null : Math.atan2(b.y - y, b.x - x));
  };

  /** A left-to-right chain of chambers, each within a walkable slope of the last. */
  const chain = (count: number, lo: (x: number) => number, hi: (x: number) => number): { x: number; y: number }[] => {
    const span = (cols - 70) / count;
    const points: { x: number; y: number }[] = [];
    for (let i = 0; i < count; i++) {
      const x = Math.round(35 + span * (i + 0.5 + rng.range(-0.22, 0.22)));
      const prev = points[i - 1];
      let y = rng.int(Math.round(lo(x)), Math.round(Math.max(lo(x), hi(x))));
      if (prev) {
        const reach = (x - prev.x) * 0.5;
        y = clamp(y, prev.y - reach, prev.y + reach);
      }
      y = Math.min(y, bottom - 8);
      points.push({ x, y });
      chamber(x, y);
      if (prev) tunnel(prev, points[i]);
    }
    return points;
  };

  const upper = chain(Math.round(rng.int(6, 8) * scale), (x) => top(x) + 7, (x) => top(x) + 26);
  const lower = chain(Math.round(rng.int(5, 7) * scale), (x) => top(x) + 46, () => bottom - 10);
  const chambers = [...upper, ...lower];

  // Sloping links between the shallow and deep networks.
  for (let links = 0, attempt = 0; links < Math.round(3 * scale) && attempt < 12 * scale; attempt++) {
    const b = lower[rng.int(0, lower.length - 1)];
    let best: { x: number; y: number } | null = null;
    for (const a of upper) {
      const dx = Math.abs(a.x - b.x);
      if (dx * 0.5 < b.y - a.y || dx > 140) continue;
      if (!best || dx < Math.abs(best.x - b.x)) best = a;
    }
    if (!best) continue;
    tunnel(best, b);
    links++;
  }

  // Dead-end nooks: often too tight to walk, which suits the moles.
  for (let i = Math.round(rng.int(4, 7) * scale); i > 0; i--) {
    const from = chambers[rng.int(0, chambers.length - 1)];
    const tilt = rng.sign() * rng.range(0.2, CAVE_SLOPE);
    let heading = rng.chance(0.5) ? tilt : Math.PI - tilt;
    worm(from.x, from.y, heading, rng.int(14, 38), rng.range(3.4, 5), () => (heading += rng.range(-0.1, 0.1)));
  }

  // Sloping mouths from the surface down into the network, away from the spawn.
  const network = open.slice();
  const mouths: number[] = [];
  for (let attempt = 0; attempt < 40 * scale && mouths.length < Math.round(3 * scale); attempt++) {
    const x = rng.int(40, cols - 41);
    if (Math.abs(x - spawnCol) < 45 || mouths.some((m) => Math.abs(m - x) < 70)) continue;
    const dir = x < cols / 2 ? 1 : -1;
    const slope = rng.range(0.5, CAVE_SLOPE);
    worm(x, ground[x] - 2, dir > 0 ? slope : Math.PI - slope, 260, rng.range(4.8, 5.4), (cx, cy) => {
      const i = Math.floor(cy) * cols + Math.floor(cx);
      if (cy > top(cx) + 2 && network[i]) return null;
      return cy >= bottom - 6 ? null : dir > 0 ? slope : Math.PI - slope;
    }, false);
    mouths.push(x);
  }

  smoothCaves(terrain, open);
  decorateCaves(rng, terrain, open);
  return mouths;
}

/** Erode thin slivers and single-cell bumps left where carved shapes nearly meet. */
function smoothCaves(terrain: Terrain, open: Uint8Array): void {
  const { cols, rows } = terrain;
  for (let pass = 0; pass < 2; pass++) {
    const erode: number[] = [];
    for (let y = 1; y < rows - 1; y++) {
      for (let x = 1; x < cols - 1; x++) {
        const i = y * cols + x;
        if (open[i] || terrain.fg[i] === AIR || terrain.fg[i] === BEDROCK || y <= terrain.surface[x] + 1) continue;
        let around = 0;
        for (let dy = -1; dy <= 1; dy++) for (let dx = -1; dx <= 1; dx++) around += open[i + dy * cols + dx];
        if (around >= 5) erode.push(i);
      }
    }
    for (const i of erode) {
      terrain.fg[i] = AIR;
      open[i] = 1;
    }
  }
}

/** Stalactites over tall chambers and glowing fungus on cave floors. */
function decorateCaves(rng: Rng, terrain: Terrain, open: Uint8Array): void {
  const { cols, rows, surface } = terrain;
  for (let x = 4; x < cols - 4; x++) {
    for (let y = surface[x] + 8; y < rows - 4; y++) {
      const i = y * cols + x;
      if (!open[i]) continue;
      const solid = (cy: number): boolean => terrain.collisionAt(x, cy) === COLLIDE_SOLID;
      if (solid(y - 1) && rng.chance(0.07)) {
        let clear = 0;
        while (clear < 16 && !solid(y + clear)) clear++;
        if (clear < 16) continue;
        const length = rng.int(2, 5);
        for (let d = 0; d < length; d++) terrain.set(x, y + d, STONE);
        y += length;
      } else if (solid(y + 1) && !solid(y - 1) && rng.chance(0.035)) {
        const stem = rng.int(0, 2);
        for (let d = 0; d < stem; d++) terrain.setBg(x, y - d, BG_STEM);
        terrain.setBg(x, y - stem, BG_GLOW);
        terrain.glows.push((y - stem) * cols + x);
      }
    }
  }
}

function turnToward(angle: number, target: number, maxTurn: number): number {
  const diff = Math.atan2(Math.sin(target - angle), Math.cos(target - angle));
  return angle + clamp(diff, -maxTurn, maxTurn);
}

/** Keep a heading within CAVE_SLOPE of horizontal, preserving its left/right sense. */
function clampSlope(heading: number): number {
  const dx = Math.cos(heading);
  const dy = Math.sin(heading);
  if (Math.abs(dy) <= Math.sin(CAVE_SLOPE)) return heading;
  return Math.atan2(Math.sign(dy) * Math.sin(CAVE_SLOPE), (dx < 0 ? -1 : 1) * Math.cos(CAVE_SLOPE));
}

function plantTree(rng: Rng, terrain: Terrain, x: number, level: number): void {
  const height = rng.int(9, 20);
  for (let y = level - height; y < level; y++) {
    terrain.setBg(x, y, BG_TRUNK);
    terrain.setBg(x + 1, y, BG_TRUNK);
  }
  const top = level - height;
  if (rng.chance(0.35)) {
    // Pine: stacked one-way tiers.
    for (let tier = 0; tier < 3; tier++) {
      const y = top + tier * 4;
      const half = 2 + tier * 2;
      for (let dy = 0; dy < 2; dy++) {
        for (let dx = -half + dy; dx <= half + 1 - dy; dx++) terrain.set(x + dx, y - dy, LEAF);
      }
    }
    return;
  }
  const rx = rng.range(4, 8);
  const ry = rng.range(3, 5);
  for (let dy = -Math.ceil(ry); dy <= Math.ceil(ry); dy++) {
    for (let dx = -Math.ceil(rx); dx <= Math.ceil(rx) + 1; dx++) {
      const nx = (dx - 0.5) / rx;
      const ny = dy / ry;
      if (nx * nx + ny * ny <= 1 - rng.next() * 0.18) terrain.set(x + dx, top + dy, LEAF);
    }
  }
}

function growMushroom(rng: Rng, terrain: Terrain, x: number, level: number): void {
  const big = rng.chance(0.4);
  const height = big ? rng.int(5, 8) : rng.int(2, 4);
  const stemWidth = big ? 2 : 1;
  for (let y = level - height; y < level; y++) {
    for (let dx = 0; dx < stemWidth; dx++) terrain.setBg(x + dx, y, BG_STEM);
  }
  const rx = big ? rng.int(4, 6) : rng.int(2, 3);
  const ry = big ? 3 : 2;
  const capBase = level - height;
  for (let dy = 0; dy < ry; dy++) {
    const span = Math.round(rx * Math.sqrt(1 - (dy / ry) ** 2));
    for (let dx = -span; dx <= span + stemWidth - 1; dx++) terrain.set(x + dx, capBase - dy, CAP);
  }
}

function placeBoulder(rng: Rng, terrain: Terrain, x: number, level: number): void {
  const r = rng.range(1.8, 3.6);
  for (let dy = -4; dy <= 2; dy++) {
    for (let dx = -4; dx <= 4; dx++) {
      if (dx * dx + dy * dy * 1.4 <= r * r) terrain.set(x + dx, level + dy, STONE);
    }
  }
}

function placeCrates(rng: Rng, terrain: Terrain, x: number, level: number): void {
  const stack = rng.int(1, 2);
  for (let s = 0; s < stack; s++) {
    const ox = x + (s === 1 ? 1 : 0);
    for (let dy = 0; dy < 3; dy++) {
      for (let dx = 0; dx < 3; dx++) terrain.set(ox + dx, level - 1 - s * 3 - dy, CRATE);
    }
  }
}

function floatIsland(rng: Rng, terrain: Terrain, x0: number, y: number, width: number): void {
  const depth = rng.int(3, 6);
  for (let i = 0; i < width; i++) {
    const t = (i + 0.5) / width;
    const under = Math.max(1, Math.round(depth * Math.sin(t * Math.PI)));
    for (let d = 0; d <= under; d++) terrain.set(x0 + i, y + d, d === 0 ? GRASS : d === 1 ? DIRT : STONE);
  }
  if (width > 12 && rng.chance(0.5)) growMushroom(rng, terrain, x0 + Math.floor(width / 2), y);
}

function clamp(value: number, min: number, max: number): number {
  return Math.max(min, Math.min(max, value));
}