fuzzyworld

basin / files / src / model / heightmap.ts

heightmap.ts

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

9e605e0f 2026-06-30 Pavel Safronov1import type { Rng } from '../rng';
2
a7bf123a 2026-07-01 Pavel Safronov3/** A board side is either ocean (water exits) or a mountain wall (water is blocked). */
4export type EdgeType = 'ocean' | 'wall';
5
6/** Per-side edge configuration. e.g. n+s wall, e+w ocean = a canyon. */
7export interface Edges {
8 n: EdgeType;
9 e: EdgeType;
10 s: EdgeType;
11 w: EdgeType;
12}
13
14/** The v1 default: all four sides ocean. */
15export const ALL_OCEAN: Edges = { n: 'ocean', e: 'ocean', s: 'ocean', w: 'ocean' };
16
9e605e0f 2026-06-30 Pavel Safronov17export interface Heightmap {
18 width: number;
19 height: number;
20 /** Row-major elevations in [0, 1]. Ocean-border cells are exactly 0. */
21 data: Float32Array;
a7bf123a 2026-07-01 Pavel Safronov22 /** Which borders are ocean (water exits) vs wall (blocks & rises as terrain). */
23 edges: Edges;
9e605e0f 2026-06-30 Pavel Safronov24}
25
26export function heightAt(hm: Heightmap, x: number, y: number): number {
27 return hm.data[y * hm.width + x];
28}
29
30/**
a7bf123a 2026-07-01 Pavel Safronov31 * Is border cell (x, y) on an ocean side — i.e. a place water can exit? Corner
32 * cells count as ocean if *either* adjoining side is ocean.
33 */
34export function isOceanEdge(
35 edges: Edges,
36 x: number,
37 y: number,
38 width: number,
39 height: number,
40): boolean {
41 return (
42 (y === 0 && edges.n === 'ocean') ||
43 (y === height - 1 && edges.s === 'ocean') ||
44 (x === 0 && edges.w === 'ocean') ||
45 (x === width - 1 && edges.e === 'ocean')
46 );
47}
48
49/** Cell distance to the nearest ocean edge (0 on an ocean edge, rising inland). */
50function distToOcean(x: number, y: number, width: number, height: number, edges: Edges): number {
51 let d = Infinity;
52 if (edges.n === 'ocean') d = Math.min(d, y);
53 if (edges.s === 'ocean') d = Math.min(d, height - 1 - y);
54 if (edges.w === 'ocean') d = Math.min(d, x);
55 if (edges.e === 'ocean') d = Math.min(d, width - 1 - x);
56 return Number.isFinite(d) ? d : 0;
57}
58
59/**
60 * Dome terrain, perturbed by smooth value noise so watersheds branch
61 * interestingly. Elevation rises with distance from the nearest *ocean* edge, so
62 * ocean sides fall to 0 while mountain-wall sides stand up as high ground —
63 * water runs off the walls toward the oceans (e.g. n+s walls make a canyon that
64 * drains east and west).
03c2cc12 2026-07-01 Pavel Safronov65 *
66 * `erosion` (0 = pristine) then ages the freshly-raised dome with simulated
67 * hydraulic erosion before drainage is resolved, carving grooves that also shift
68 * the eventual outflow signature (see {@link erode}). `erosion === 0` consumes no
69 * `rng`, so a pristine board is bit-for-bit what it always was.
9e605e0f 2026-06-30 Pavel Safronov70 */
a7bf123a 2026-07-01 Pavel Safronov71export function generateDome(
72 width: number,
73 height: number,
74 rng: Rng,
75 edges: Edges = ALL_OCEAN,
03c2cc12 2026-07-01 Pavel Safronov76 erosion = 0,
a7bf123a 2026-07-01 Pavel Safronov77): Heightmap {
9e605e0f 2026-06-30 Pavel Safronov78 const data = new Float32Array(width * height);
79
80 // Coarse value-noise lattice, bilinearly sampled across the board.
81 const noiseCols = Math.max(2, Math.round(width / 2));
82 const noiseRows = Math.max(2, Math.round(height / 2));
83 const lattice = new Float32Array(noiseCols * noiseRows);
84 for (let i = 0; i < lattice.length; i++) lattice[i] = rng();
85
86 const sampleNoise = (x: number, y: number): number => {
87 const gx = (x / Math.max(1, width - 1)) * (noiseCols - 1);
88 const gy = (y / Math.max(1, height - 1)) * (noiseRows - 1);
89 const x0 = Math.floor(gx);
90 const y0 = Math.floor(gy);
91 const x1 = Math.min(x0 + 1, noiseCols - 1);
92 const y1 = Math.min(y0 + 1, noiseRows - 1);
93 const fx = gx - x0;
94 const fy = gy - y0;
95 const a = lattice[y0 * noiseCols + x0];
96 const b = lattice[y0 * noiseCols + x1];
97 const c = lattice[y1 * noiseCols + x0];
98 const d = lattice[y1 * noiseCols + x1];
99 const top = a + (b - a) * fx;
100 const bot = c + (d - c) * fx;
101 return top + (bot - top) * fy;
102 };
103
104 const amp = 0.6;
105 let peak = 0;
106 for (let y = 0; y < height; y++) {
107 for (let x = 0; x < width; x++) {
a7bf123a 2026-07-01 Pavel Safronov108 const dome = distToOcean(x, y, width, height, edges); // 0 on ocean edges
109 const n = 1 + amp * (sampleNoise(x, y) * 2 - 1); // n > 0, so v >= 0
110 const v = dome * n;
9e605e0f 2026-06-30 Pavel Safronov111 data[y * width + x] = v;
112 if (v > peak) peak = v;
113 }
114 }
115
a7bf123a 2026-07-01 Pavel Safronov116 // Normalise to [0, 1]; ocean edges stay 0, walls stand up as high ground.
9e605e0f 2026-06-30 Pavel Safronov117 if (peak > 0) for (let i = 0; i < data.length; i++) data[i] /= peak;
118
a7bf123a 2026-07-01 Pavel Safronov119 const hm: Heightmap = { width, height, data, edges };
03c2cc12 2026-07-01 Pavel Safronov120 erode(hm, rng, erosion); // age the terrain before resolving drainage
9e605e0f 2026-06-30 Pavel Safronov121 resolveDrainage(hm);
122 return hm;
123}
124
03c2cc12 2026-07-01 Pavel Safronov125// 8-connected neighbours for erosion droplets — diagonals included so carved
126// channels aren't locked to the cardinal grid (the flow model still uses the 4
127// cardinals; erosion is purely terrain shaping).
128const EROSION_NEIGHBORS: ReadonlyArray<readonly [number, number]> = [
129 [0, -1],
130 [1, -1],
131 [1, 0],
132 [1, 1],
133 [0, 1],
134 [-1, 1],
135 [-1, 0],
136 [-1, -1],
137];
138
139/**
140 * Simulated aging by hydraulic ("droplet") erosion — the geomorphic process that
141 * turns a smooth dome into a grooved, dissected landscape. `strength` is roughly
142 * "how much time has passed": each unit rains more droplets over the board.
143 *
144 * Every droplet starts on a random interior cell and runs downhill by steepest
145 * descent, carrying sediment. On a steep, fast reach it picks terrain up (cutting
146 * a channel); where it slows or overfills it drops sediment back (silting flats
147 * and pit floors). Repeated over many droplets this concentrates flow into
148 * dendritic grooves and reshapes where water finally reaches the sea — so a
149 * heavily-aged board reads a visibly different edge signature from its pristine
150 * self.
151 *
152 * Invariants preserved for the caller:
153 * - Ocean-edge cells are never written (they stay exactly 0 — that's the sea a
154 * droplet washes out into and stops).
155 * - Erosion is capped at the local descent, so it never digs a cell below the
156 * neighbour it flows to; any residual flats/pits are still cleaned up by the
157 * {@link resolveDrainage} pass the generator runs afterwards.
158 * - `strength <= 0` returns immediately without touching `rng`, so a pristine
159 * board is identical to one generated before erosion existed.
160 */
161export function erode(hm: Heightmap, rng: Rng, strength: number): void {
162 if (strength <= 0) return;
163 const { width, height, data, edges } = hm;
164 if (width < 3 || height < 3) return; // no interior to seed droplets on
165
166 // Tuning constants for grid-droplet hydraulic erosion. Chosen so strength 1
167 // lightly weathers the dome and the max clearly dissects it into grooves.
168 const dropsPerCell = 0.6;
169 const maxSteps = width + height;
170 const capacity = 6; // sediment a droplet holds per unit of slope·speed
171 const minSlope = 0.005; // keeps near-flat reaches still mildly erosive
172 const erodeRate = 0.3;
173 const depositRate = 0.25;
174 const gravity = 8;
175 const evaporate = 0.01;
176
177 const drops = Math.round(strength * width * height * dropsPerCell);
178
179 for (let d = 0; d < drops; d++) {
180 // Two rng draws per droplet — the only rng this function consumes, so the
181 // stream stays a deterministic function of (seed, strength, board size).
182 let x = 1 + Math.floor(rng() * (width - 2));
183 let y = 1 + Math.floor(rng() * (height - 2));
184 let sediment = 0;
185 let speed = 0;
186 let water = 1;
187
188 for (let step = 0; step < maxSteps; step++) {
189 // Reaching the sea ends the droplet; its sediment washes out and is lost.
190 if (isOceanEdge(edges, x, y, width, height)) break;
191
192 const i = y * width + x;
193 const h = data[i];
194
195 // Steepest-descent 8-neighbour.
196 let bx = -1;
197 let by = -1;
198 let bh = h;
199 for (const [dx, dy] of EROSION_NEIGHBORS) {
200 const nx = x + dx;
201 const ny = y + dy;
202 if (nx < 0 || ny < 0 || nx >= width || ny >= height) continue;
203 const nh = data[ny * width + nx];
204 if (nh < bh) {
205 bh = nh;
206 bx = nx;
207 by = ny;
208 }
209 }
210
211 if (bx < 0) {
212 // Local pit: nowhere lower to go. Silt it up with the carried load.
213 data[i] = Math.min(1, h + sediment);
214 break;
215 }
216
217 const drop = h - bh; // > 0
218 const cap = Math.max(drop, minSlope) * (speed + 1) * water * capacity;
219
220 if (sediment > cap) {
221 // Over capacity → deposit, but never above the cell we came to rest on.
222 const dep = Math.min((sediment - cap) * depositRate, sediment);
223 data[i] = Math.min(1, h + dep);
224 sediment -= dep;
225 } else {
226 // Under capacity → cut, but never below the neighbour we descend to, so
227 // the path stays monotone and we don't spike a fresh pit.
228 const ero = Math.min((cap - sediment) * erodeRate, drop);
229 data[i] = h - ero;
230 sediment += ero;
231 }
232
233 speed = Math.sqrt(Math.max(0, speed * speed + drop * gravity));
234 water *= 1 - evaporate;
235 x = bx;
236 y = by;
237 }
238 }
239}
240
9e605e0f 2026-06-30 Pavel Safronov241const DRAIN_NEIGHBORS: ReadonlyArray<readonly [number, number]> = [
242 [0, -1],
243 [1, 0],
244 [0, 1],
245 [-1, 0],
246];
247
248/**
249 * Priority-flood + epsilon depression filling (Barnes, Lehman & Mulla 2014).
250 *
a7bf123a 2026-07-01 Pavel Safronov251 * Guarantees every cell has a strictly-decreasing 4-connected path to an *ocean*
252 * edge — so water released anywhere always drains out to an ocean side, never
253 * trapping in an interior pit and never needing to cross a wall. Depressions are
254 * raised to their spill elevation (a natural "lake" surface) and given an
255 * imperceptible gradient via `eps`; real peaks and slopes (already above their
256 * spill) are left untouched.
9e605e0f 2026-06-30 Pavel Safronov257 */
258export function resolveDrainage(hm: Heightmap, eps = 1e-4): void {
a7bf123a 2026-07-01 Pavel Safronov259 const { width, height, data, edges } = hm;
9e605e0f 2026-06-30 Pavel Safronov260 const closed = new Uint8Array(width * height);
261 const heap = new MinHeap();
262
a7bf123a 2026-07-01 Pavel Safronov263 // Seed the flood from ocean-edge cells only — these are the spill points.
264 // Wall edges are treated as ordinary (floodable) terrain and rise like it.
9e605e0f 2026-06-30 Pavel Safronov265 const seed = (x: number, y: number): void => {
a7bf123a 2026-07-01 Pavel Safronov266 if (!isOceanEdge(edges, x, y, width, height)) return;
9e605e0f 2026-06-30 Pavel Safronov267 const i = y * width + x;
268 closed[i] = 1;
269 heap.push(i, data[i]);
270 };
271 for (let x = 0; x < width; x++) {
272 seed(x, 0);
273 seed(x, height - 1);
274 }
275 for (let y = 1; y < height - 1; y++) {
276 seed(0, y);
277 seed(width - 1, y);
278 }
279
280 // Pop cells lowest-first; each unseen neighbour is raised to at least
281 // (current + eps), so elevation strictly increases away from the ocean.
282 while (heap.size > 0) {
283 const { idx, key } = heap.pop();
284 const cx = idx % width;
285 const cy = (idx / width) | 0;
286 for (const [dx, dy] of DRAIN_NEIGHBORS) {
287 const nx = cx + dx;
288 const ny = cy + dy;
289 if (nx < 0 || ny < 0 || nx >= width || ny >= height) continue;
290 const ni = ny * width + nx;
291 if (closed[ni]) continue;
292 closed[ni] = 1;
293 const raised = Math.max(data[ni], key + eps);
294 data[ni] = raised;
295 heap.push(ni, raised);
296 }
297 }
298}
299
300/** Tiny binary min-heap over (cell index, elevation key). */
301class MinHeap {
302 private idx: number[] = [];
303 private key: number[] = [];
304
305 get size(): number {
306 return this.idx.length;
307 }
308
309 push(i: number, k: number): void {
310 this.idx.push(i);
311 this.key.push(k);
312 let n = this.idx.length - 1;
313 while (n > 0) {
314 const p = (n - 1) >> 1;
315 if (this.key[p] <= this.key[n]) break;
316 this.swap(p, n);
317 n = p;
318 }
319 }
320
321 pop(): { idx: number; key: number } {
322 const ri = this.idx[0];
323 const rk = this.key[0];
324 const li = this.idx.pop()!;
325 const lk = this.key.pop()!;
326 if (this.idx.length > 0) {
327 this.idx[0] = li;
328 this.key[0] = lk;
329 let n = 0;
330 const len = this.idx.length;
331 for (;;) {
332 let s = n;
333 const l = 2 * n + 1;
334 const r = 2 * n + 2;
335 if (l < len && this.key[l] < this.key[s]) s = l;
336 if (r < len && this.key[r] < this.key[s]) s = r;
337 if (s === n) break;
338 this.swap(s, n);
339 n = s;
340 }
341 }
342 return { idx: ri, key: rk };
343 }
344
345 private swap(a: number, b: number): void {
346 const ti = this.idx[a];
347 this.idx[a] = this.idx[b];
348 this.idx[b] = ti;
349 const tk = this.key[a];
350 this.key[a] = this.key[b];
351 this.key[b] = tk;
352 }
353}