fuzzyworld

basin / files / src / model / flow.ts

flow.ts

Blame: the commit that last changed each line · file · history

9e605e0f 2026-06-30 Pavel Safronov1import type { Heightmap } from './heightmap';
a7bf123a 2026-07-01 Pavel Safronov2import { heightAt, isOceanEdge } from './heightmap';
9e605e0f 2026-06-30 Pavel Safronov3
4export interface Cell {
5 x: number;
6 y: number;
7}
8
9export interface FlowResult {
10 /** 1 where water reaches, row-major. */
11 wet: Uint8Array;
12 /** Wet border cells — where water exits the board. */
13 outflow: Cell[];
a7bf123a 2026-07-01 Pavel Safronov14 /** The springs that produced this flow (order preserved). */
15 springs: Cell[];
9e605e0f 2026-06-30 Pavel Safronov16}
17
18// 4-connected (cardinal) neighbours: N, E, S, W.
19const NEIGHBORS: ReadonlyArray<readonly [number, number]> = [
20 [0, -1],
21 [1, 0],
22 [0, 1],
23 [-1, 0],
24];
25
26/**
a7bf123a 2026-07-01 Pavel Safronov27 * Flood from a single spring. Convenience wrapper over {@link simulateFlows}.
9e605e0f 2026-06-30 Pavel Safronov28 */
29export function simulateFlow(hm: Heightmap, sx: number, sy: number): FlowResult {
a7bf123a 2026-07-01 Pavel Safronov30 return simulateFlows(hm, [{ x: sx, y: sy }]);
31}
32
33/**
34 * Flood from a set of springs and union their wet sets: a cell is wet iff it's
35 * reachable from *some* spring along a path of strictly decreasing heights.
36 * Water branches to every lower neighbour, never pools, and stops at interior
37 * pits or board edges.
38 *
39 * A shared visited array is sound for the union: floods only ever move downhill,
40 * so the first time a cell is wetted its entire strictly-lower descendant set is
41 * already scheduled — a later spring reaching the same cell adds nothing new.
42 */
43export function simulateFlows(hm: Heightmap, springs: readonly Cell[]): FlowResult {
9e605e0f 2026-06-30 Pavel Safronov44 const { width, height } = hm;
45 const wet = new Uint8Array(width * height);
46 const stack: number[] = [];
47
a7bf123a 2026-07-01 Pavel Safronov48 for (const s of springs) {
49 const i = s.y * width + s.x;
50 if (!wet[i]) {
51 wet[i] = 1;
52 stack.push(s.x, s.y);
53 }
54 }
9e605e0f 2026-06-30 Pavel Safronov55
56 while (stack.length) {
57 const y = stack.pop()!;
58 const x = stack.pop()!;
59 const h = heightAt(hm, x, y);
60 for (const [dx, dy] of NEIGHBORS) {
61 const nx = x + dx;
62 const ny = y + dy;
63 if (nx < 0 || ny < 0 || nx >= width || ny >= height) continue;
64 if (wet[ny * width + nx]) continue;
65 if (heightAt(hm, nx, ny) < h) {
66 wet[ny * width + nx] = 1;
67 stack.push(nx, ny);
68 }
69 }
70 }
71
a7bf123a 2026-07-01 Pavel Safronov72 // Water exits only where it reaches an *ocean* edge; wet cells that pool
73 // against a wall stop there and are not outflow.
9e605e0f 2026-06-30 Pavel Safronov74 const outflow: Cell[] = [];
75 for (let y = 0; y < height; y++) {
76 for (let x = 0; x < width; x++) {
a7bf123a 2026-07-01 Pavel Safronov77 if (wet[y * width + x] && isOceanEdge(hm.edges, x, y, width, height)) {
78 outflow.push({ x, y });
79 }
9e605e0f 2026-06-30 Pavel Safronov80 }
81 }
82
a7bf123a 2026-07-01 Pavel Safronov83 return { wet, outflow, springs: springs.map((s) => ({ x: s.x, y: s.y })) };
9e605e0f 2026-06-30 Pavel Safronov84}