fuzzyworld

tower / files / src / terrain / desert.ts

desert.ts

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

51c39d8b 2026-09-17 Pavel Safronov1/**
2 * The desert: plateaus and mesas, dry washes, salt pans, and the shorelines of lakes that
3 * never were. See world-generation.md §4.5.
4 *
5 * Nothing here is a remnant (§0.1). Tower built a desert because it had seen deserts, so
6 * it laid out the whole grammar of one: tiers of rock standing over sand, a drainage of dry
7 * channels routed the way water would have routed them, flats of salt in the lowest ground,
8 * and bathtub rings around them at the levels a lake would have stood. The washes are cut
9 * by the same priority-flood routing the ranges erode with (grid.ts) — because a channel
10 * network that does not obey drainage is the one thing that would look wrong.
11 *
12 * What is compiled here is what a tile cannot work out for itself: the plateau field, the
13 * wash network, and where the pans and their shorelines are. Dunes and rocky hills are
14 * noise and are added by the tiles (field.ts), which is also what keeps them crisp — the
15 * plateau's height fraction is compiled smooth and the **terraces are applied as the tile
16 * samples it**, so a cliff band is as sharp as the tile is fine, not as sharp as a 250 m
17 * grid allows.
18 */
19import { type Grid, Heap, blur, drainage, sampleGrid } from './grid.js'
20import { type CylPoint, cylPoint, fbm, hash3, mulberry32, ridged } from './noise.js'
21import {
22 type Box, LineIndex, type Line, type Nearest, nearestA, nearestOnSegments, shapeBox, shapeOf,
23 signedDistance, type Shape,
24} from './shapes.js'
25import { CIRCUMFERENCE_M, RADIUS_M } from '../canon/constants.js'
26import type { Desert } from '../world/schema.js'
27
28/** Cell size of the desert grid. Fine enough for a wash, coarse enough for 22,000 km². */
29export const DESERT_CELL_M = 250
30
31export interface CPan {
32 z: number
33 a: number
34 /** Elevation of the pan floor above the datum. */
35 levelM: number
36 radiusM: number
37}
38
39export interface CDesert {
40 id: string
41 shape: Shape
42 box: Box
43 grid: Grid
44 /** 0..1 how much of this cell is desert at all: it fades out over the edge, and is 0
45 * in the corridors kept clear for the rivers. */
46 inside: Float32Array
47 /**
48 * The desert's own broad shape, metres: it crowns toward its middle, so the washes have
49 * somewhere to run. Compiled rather than computed twice, so the routing and the drawn
50 * ground are the same surface by construction.
51 */
52 base: Float32Array
53 /** 0..1 of the way up the plateau, smooth; the tiles terrace it. */
54 plateau: Float32Array
55 /** How deep the washes cut here, metres. */
56 cut: Float32Array
57 /** 0..1 salt crust: the pan floors, and the elevation each pan's floor stands at. */
58 salt: Float32Array
59 panLevelM: Float32Array
60 /** 0..1 how much of the ground here is a shoreline bench, and the pan's elevation. */
61 bench: Float32Array
62 benchLevelM: Float32Array
63 /** Where the dunes are, 0..1: the open sand, away from rock. */
64 sand: Float32Array
65 /** The salt pans Tower laid out, for anything that wants to look at one. */
66 pans: CPan[]
67 plateauHeightM: number
68 terraces: number
69 hillsHeightM: number
70 hillsCoverage: number
71 duneHeightM: number
72 duneSpacingM: number
73 duneDirRad: number
74 /** Whole dune wavelengths around the circumference, so the field closes on itself. */
75 dunePeriods: number
76 duneCoverage: number
77 seed: number
78}
79
80/** Height of the shoreline benches above a pan, and how many stand there. */
81export const BENCH_STEP_M = 20
82export const BENCH_COUNT = 3
83
84/**
85 * The terrace profile: flat tops with steep risers between them. `p` is how far up the
86 * plateau this ground stands, 0..1; the result is the same range, in `terraces` tiers.
87 */
88export function terrace(p: number, terraces: number): number {
89 const x = Math.min(1, Math.max(0, p)) * terraces
90 const tier = Math.min(terraces - 1, Math.floor(x))
91 const f = x - tier
92 // The riser occupies the middle of each tier's band, so tops are flat and faces are steep.
93 const riser = f <= 0.42 ? 0 : f >= 0.78 ? 1 : (f - 0.42) / 0.36
94 const smooth = riser * riser * (3 - 2 * riser)
95 return (tier + smooth) / terraces
96}
97
98const smoothstep = (e0: number, e1: number, x: number): number => {
99 const t = Math.min(1, Math.max(0, (x - e0) / (e1 - e0)))
100 return t * t * (3 - 2 * t)
101}
102
103/** The threshold on a 0..1 field that leaves `coverage` of it above, from a sample of it. */
104function quantile(samples: number[], coverage: number): number {
105 if (!samples.length) return 1
106 const sorted = [...samples].sort((x, y) => x - y)
107 const i = Math.min(sorted.length - 1, Math.max(0, Math.round((1 - coverage) * (sorted.length - 1))))
108 return sorted[i]!
109}
110
111/** How far the middle of a desert stands above its rim, so that washes have a fall. */
112export const CROWN_M = 150
113
114/** Drainage area past which a wash is a channel: fifteen square kilometres of desert. */
115const WASH_AREA_M2 = 1.5e7
116
117/**
118 * `corridors` are lines the desert keeps its rock away from: the rivers Tower had already
119 * routed through here. A mesa dropped across The Narrows would leave the world's whole
120 * drainage cutting a kilometre-deep slot through it, which is not what Tower would build.
121 */
122export function compileDeserts(
123 features: Desert[], worldSeed: number, seedOf: (f: Desert) => number,
124 onStep: (label: string) => void = () => {}, corridors: Line[] = [],
125 landAt: (z: number, a: number) => number = () => 0,
126): CDesert[] {
127 const out: CDesert[] = []
128 for (const f of features) {
129 const shape = shapeOf(f.geometry)
130 if (!shape) continue
131 out.push(compileDesert(f, shape, seedOf(f), worldSeed, onStep, corridors, landAt))
132 }
133 return out
134}
135
136/**
137 * How wide a river's corridor is kept clear of plateau rock: a valley of sand and gravel
138 * either side of the water, which is also what a river crossing a mesa field looks like.
139 */
140export const CORRIDOR_M = 6500
141
142function compileDesert(
143 f: Desert, shape: Shape, seed: number, worldSeed: number, onStep: (label: string) => void,
144 corridors: Line[], landAt: (z: number, a: number) => number,
145): CDesert {
146 const box = shapeBox(shape)
147 const ring = shape.type === 'band'
148 const margin = f.edgeM * 0.5
149 const z0 = box.z0 - margin
150 const a0 = ring ? 0 : box.a0 - margin
151 const na = ring
152 ? Math.round(CIRCUMFERENCE_M / DESERT_CELL_M)
153 : Math.max(4, Math.ceil((box.a1 + margin - a0) / DESERT_CELL_M) + 1)
154 // A ring's cells divide the circumference exactly, or the grid has a seam where it wraps.
155 const cell = ring ? CIRCUMFERENCE_M / na : DESERT_CELL_M
156 const nz = Math.max(4, Math.ceil((box.z1 + margin - z0) / cell) + 1)
157 const grid: Grid = { z0, a0, cell, nz, na, ring }
158 const n = nz * na
159 const rand = mulberry32(hash3(worldSeed, seed, 0xd35e27))
160
161 const at = (k: number): { z: number; a: number; p: CylPoint } => {
162 const i = Math.floor(k / na), j = k % na
163 const z = z0 + i * cell, a = a0 + j * cell
164 return { z, a, p: cylPoint(a / RADIUS_M, z) }
165 }
166
167 // How much of each cell is desert at all: it fades out over the outer half of the edge.
168 onStep(`Quoting the deserts of Earth in ${f.name}`)
169 const inside = new Float32Array(n)
170 const plateauNoise = new Float32Array(n)
171 const samples: number[] = []
172 const indexes = corridors.map((line) => new LineIndex(line, CORRIDOR_M))
173 const near: Nearest = { d: 0, seg: 0, t: 0 }
174 const clear = (z: number, a: number): number => {
175 let m = 1
176 for (let i = 0; i < corridors.length; i++) {
177 const segs = indexes[i]!.near(z, a)
178 if (!segs.length) continue
179 nearestOnSegments(corridors[i]!, z, a, segs, near)
180 m = Math.min(m, smoothstep(CORRIDOR_M * 0.45, CORRIDOR_M, near.d))
181 }
182 return m
183 }
184 for (let k = 0; k < n; k++) {
185 const { z, a, p } = at(k)
186 // Landforms begin at the desert's boundary and are fully themselves a few km in.
187 inside[k] = smoothstep(0, f.edgeM * 0.35, signedDistance(shape, z, a))
188 if (inside[k]! <= 0) continue
189 inside[k]! *= clear(z, a)
190 if (inside[k]! <= 0) continue
191 // Broad blotches the size of a mesa group, warped so their edges are not noise-smooth.
192 const warp = fbm(seed ^ 0x11, p, 9000, 2, cell) - 0.5
193 plateauNoise[k] = fbm(seed ^ 0x27, p, 26_000, 4, cell) + warp * 0.12
194 if (k % 7 === 0) samples.push(plateauNoise[k]!)
195 }
196
197 /**
198 * The plateau field. A threshold picked to leave the authored coverage above it, and a
199 * narrow band of noise either side of it: that band's width is what makes the cliffs
200 * steep, since the whole rise happens across it.
201 */
202 /**
203 * The crown. A desert that is dead flat has no drainage at all — water on it fans out
204 * from wherever it lands and nothing gathers into a channel — so Tower raised the middle
205 * of the Reach a little, and everything runs off it to the edges.
206 */
207 const half = ring ? (box.z1 - box.z0) / 2 : Math.max(500, Math.min(box.z1 - box.z0, box.a1 - box.a0) / 2)
208 const base = new Float32Array(n)
209 for (let k = 0; k < n; k++) {
210 if (inside[k]! <= 0) continue
211 const { z, a, p } = at(k)
212 const t = Math.min(1, Math.max(0, signedDistance(shape, z, a) / half))
213 base[k] = CROWN_M * (1 - (1 - t) * (1 - t)) * inside[k]!
214 + (fbm(layer(seed, 8), p, 7000, 3, cell) - 0.5) * 40 * inside[k]!
215 }
216
217 const thr = quantile(samples, f.plateaus.coverage)
218 const plateau = new Float32Array(n)
219 for (let k = 0; k < n; k++) {
220 if (inside[k]! <= 0) continue
221 plateau[k] = smoothstep(thr, thr + 0.05, plateauNoise[k]!) * inside[k]!
222 }
223
224 /**
225 * The surface the washes are routed over: the crown, the terraced rock and the rocky
226 * hills, all exactly as the tiles make them (field.ts `desert`), so a wash is cut into
227 * the ground that is actually drawn.
228 */
229 const surface = new Float32Array(n)
230 for (let k = 0; k < n; k++) {
231 if (inside[k]! <= 0) continue
232 const { z, a, p } = at(k)
233 // Above the datum, shelf and all: a pan's floor is a height in the world, and the
234 // benches around it are levels in the world, so both are measured from there.
235 surface[k] = landAt(z, a) + base[k]! + terrace(plateau[k]!, f.plateaus.terraces) * f.plateaus.heightM
236 + hillsAt(f, seed, p, cell, plateau[k]!, inside[k]!)
237 }
238
239 const cut = new Float32Array(n)
240 const salt = new Float32Array(n)
241 const panLevelM = new Float32Array(n)
242 const bench = new Float32Array(n)
243 const benchLevelM = new Float32Array(n)
244 const pans: CPan[] = []
245
246 const work = {
247 receiver: new Int32Array(n), stack: new Int32Array(n), reached: new Uint8Array(n),
248 key: new Float64Array(n), heap: new Heap(n),
249 }
250 /** Off the desert, the ground carries the water away: those cells are the outlets. */
251 const outlet = new Uint8Array(n)
252 for (let k = 0; k < n; k++) if (inside[k]! <= 0.02) outlet[k] = 1
253 // A ring desert has no outside along theta, so its two ends are the way out.
254 if (ring) for (let j = 0; j < na; j++) { outlet[j] = 1; outlet[(nz - 1) * na + j] = 1 }
255
256 if (f.pastWater.washes > 0) {
257 onStep(`Cutting riverbeds for rivers that never ran in ${f.name}`)
258 const top = drainage(grid, surface, outlet, work)
259 // Drainage area, accumulated from the far end of the stack back down to the outlets.
260 const area = new Float64Array(n).fill(cell * cell)
261 for (let s = top - 1; s >= 0; s--) {
262 const k = work.stack[s]!
263 const r = work.receiver[k]!
264 if (r >= 0) area[r]! += area[k]!
265 }
266 for (let k = 0; k < n; k++) {
267 if (inside[k]! <= 0 || area[k]! < WASH_AREA_M2) continue
268 // A wash deepens with what it would drain, slowly: a big one is tens of metres.
269 const depth = 4 + 14 * Math.log10(area[k]! / WASH_AREA_M2)
270 cut[k] = Math.min(55, depth) * f.pastWater.washes * inside[k]!
271 }
272 /**
273 * A wash is wider than one cell and flat-floored. Widening is a *dilation* — the
274 * deepest cut within a couple of cells — and only then a blur for the banks: blurring
275 * a one-cell channel straight away had averaged its depth away to nothing.
276 */
277 const wide = new Float32Array(n)
278 const reach = 2
279 for (let i = 0; i < nz; i++) {
280 for (let j = 0; j < na; j++) {
281 let m = 0
282 for (let di = -reach; di <= reach; di++) {
283 const ii = i + di
284 if (ii < 0 || ii >= nz) continue
285 for (let dj = -reach; dj <= reach; dj++) {
286 const jj = ring ? ((j + dj) % na + na) % na : j + dj
287 if (!ring && (jj < 0 || jj >= na)) continue
288 m = Math.max(m, cut[ii * na + jj]!)
289 }
290 }
291 wide[i * na + j] = m
292 }
293 }
294 const banked = blur(grid, wide, 1)
295 for (let k = 0; k < n; k++) cut[k] = Math.max(cut[k]!, banked[k]!)
296 }
297
298 if (f.pastWater.saltPans > 0) {
299 onStep(`Laying salt in the low ground of ${f.name}`)
300 const floor = new Float32Array(n)
301 for (let k = 0; k < n; k++) floor[k] = surface[k]! - cut[k]!
302 /**
303 * Where a pan goes: the lowest ground, spaced out, so the set pieces land where the
304 * desert is deepest rather than on top of each other. A pan is a disc — Tower is
305 * placing these, not discovering them (§4.5) — flattened to one level, with the
306 * ground outside it stepped down in benches: the rings of a lake that never stood.
307 */
308 const order = Array.from({ length: n }, (_, k) => k)
309 .filter((k) => inside[k]! > 0.9)
310 .sort((x, y) => floor[x]! - floor[y]!)
311 const wanted = f.pastWater.saltPans
312 for (const k of order) {
313 if (pans.length >= wanted) break
314 const { z, a } = at(k)
315 const radiusM = 1500 + 1600 * rand()
316 const spacing = radiusM * 4
317 if (pans.some((q) => Math.hypot(q.z - z, nearestA(q.a, a) - a) < spacing)) continue
318 pans.push({ z, a, levelM: floor[k]!, radiusM })
319 }
320 for (const pan of pans) {
321 const reach = pan.radiusM + (f.pastWater.shorelines ? BENCH_STEP_M * BENCH_COUNT * 24 : 0)
322 const cells = Math.ceil(reach / cell)
323 const ci = Math.round((pan.z - z0) / cell), cj = Math.round((pan.a - a0) / cell)
324 for (let i = Math.max(0, ci - cells); i <= Math.min(nz - 1, ci + cells); i++) {
325 for (let jj = cj - cells; jj <= cj + cells; jj++) {
326 const j = ring ? ((jj % na) + na) % na : jj
327 if (!ring && (j < 0 || j >= na)) continue
328 const k = i * na + j
329 const d = Math.hypot(z0 + i * cell - pan.z, a0 + jj * cell - pan.a)
330 if (d > reach) continue
331 /**
332 * The floor of the pan, and a crust that frays at the very edge. The level is
333 * written well beyond the crust as well, or sampling it near the rim would
334 * interpolate against the zeros outside and tilt the floor.
335 */
336 const flat = 1 - smoothstep(pan.radiusM * 0.94, pan.radiusM, d)
337 if (flat > salt[k]!) salt[k] = flat
338 if (d < pan.radiusM * 1.5) panLevelM[k] = pan.levelM
339 if (f.pastWater.shorelines && d > pan.radiusM * 0.9) {
340 const b = (1 - smoothstep(reach * 0.75, reach, d)) * smoothstep(pan.radiusM * 0.9, pan.radiusM * 1.05, d)
341 if (b > bench[k]!) { bench[k] = b; benchLevelM[k] = pan.levelM }
342 }
343 }
344 }
345 }
346 }
347
348 /**
349 * Where the dunes are: the open ground, away from rock and off the salt, and only in the
350 * share of it the authored coverage asks for — thresholded against the *measured* spread
351 * of the noise, as the plateaus are, because a threshold guessed against an assumed
352 * spread puts dunes over everything or nowhere. Blurred, since a dune field is
353 * kilometres across or it is not a field.
354 */
355 const open = new Float32Array(n)
356 const fieldNoise = new Float32Array(n)
357 const fieldSamples: number[] = []
358 for (let k = 0; k < n; k++) {
359 open[k] = inside[k]! * (1 - Math.min(1, plateau[k]! * 2.5)) * (1 - salt[k]!)
360 if (open[k]! <= 0.2) continue
361 const { p } = at(k)
362 fieldNoise[k] = fbm(layer(seed, 5), p, 21_000, 3, cell)
363 if (k % 7 === 0) fieldSamples.push(fieldNoise[k]!)
364 }
365 const fieldThr = quantile(fieldSamples, f.dunes.coverage)
366 for (let k = 0; k < n; k++) {
367 if (open[k]! <= 0.2) { open[k] = 0; continue }
368 open[k]! *= smoothstep(fieldThr - 0.01, fieldThr + 0.04, fieldNoise[k]!)
369 }
370 const sand = blur(grid, open, 4)
371 for (let k = 0; k < n; k++) sand[k] = Math.min(1, Math.max(0, sand[k]! * 1.2))
372
373 return {
374 id: f.id, shape, box: grow(box, f.edgeM * 1.2), grid,
375 inside, base, plateau, cut, salt, panLevelM, bench, benchLevelM, sand, pans,
376 plateauHeightM: f.plateaus.heightM, terraces: f.plateaus.terraces,
377 hillsHeightM: f.hills.heightM, hillsCoverage: f.hills.coverage,
378 duneHeightM: f.dunes.heightM, duneSpacingM: f.dunes.spacingM,
379 duneDirRad: (f.dunes.directionDeg * Math.PI) / 180,
380 dunePeriods: Math.round((CIRCUMFERENCE_M * Math.sin((f.dunes.directionDeg * Math.PI) / 180)) / f.dunes.spacingM),
381 duneCoverage: f.dunes.coverage,
382 seed,
383 }
384}
385
386/**
387 * The rocky hills, as both the compile and the tiles make them: low ridged domes on the
388 * open ground. Shared so the washes are routed over the ground the tiles actually draw.
389 */
390export function hillsAt(
391 f: { hills: { coverage: number; heightM: number } }, seed: number, p: CylPoint, detailM: number,
392 plateau: number, inside: number,
393): number {
394 if (f.hills.heightM <= 0 || f.hills.coverage <= 0) return 0
395 const where = fbm(layer(seed, 3), p, 14_000, 3, detailM)
396 const m = smoothstep(0.92 - f.hills.coverage, 1.02 - f.hills.coverage, where) * inside * (1 - plateau)
397 if (m <= 0) return 0
398 return Math.max(0, (ridged(layer(seed, 4), p, 2600, 3, detailM) - 0.4) * 1.7) * f.hills.heightM * m
399}
400
401/** One layer of a feature's noise, as field.ts numbers them. */
402export const layer = (seed: number, i: number): number => hash3(seed, i, 0x1f7a)
403
404const grow = (b: Box, m: number): Box => ({ z0: b.z0 - m, z1: b.z1 + m, a0: b.a0 - m, a1: b.a1 + m })
405
406/** The compiled fields at a point, for the tiles. */
407export function sampleDesert(d: CDesert, z: number, a: number): {
408 inside: number; base: number; plateau: number; cut: number; salt: number; panLevelM: number
409 bench: number; benchLevelM: number; sand: number
410} {
411 return {
412 inside: sampleGrid(d.grid, d.inside, z, a),
413 base: sampleGrid(d.grid, d.base, z, a),
414 plateau: sampleGrid(d.grid, d.plateau, z, a),
415 cut: sampleGrid(d.grid, d.cut, z, a),
416 salt: sampleGrid(d.grid, d.salt, z, a),
417 panLevelM: sampleGrid(d.grid, d.panLevelM, z, a),
418 bench: sampleGrid(d.grid, d.bench, z, a),
419 benchLevelM: sampleGrid(d.grid, d.benchLevelM, z, a),
420 sand: sampleGrid(d.grid, d.sand, z, a),
421 }
422}