fuzzyworld

tower / files / src / terrain / compile.ts

compile.ts

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

376f2ce6 2026-09-16 Pavel Safronov1/**
2 * The world compile. See world-generation.md §5.2.
3 *
4 * Turns the authored world file into plain data the elevation function can sample
5 * fast and from any thread: shapes unwrapped, rivers smoothed and given a long
6 * profile, lake levels resolved, mountain domes normalised to their summits. It is
7 * the only place that looks at the whole world at once. Everything after it — every
8 * tile, every pixel of the map, standing on the ground — only ever asks about one
9 * point.
10 *
11 * Deterministic: the same world file compiles to the same data on every machine.
12 * The result is structured-cloneable, so one worker compiles and the rest are handed
13 * the answer.
14 */
15import { RADIUS_M } from '../canon/constants.js'
00ceeedb 2026-09-27 Pavel Safronov16import type {
e18dad04 2026-09-30 Pavel Safronov17 Desert as DesertFeature, Feature, Forest as ForestFeature, Lake, Mountains, River, Sea, SeaIce, World,
00ceeedb 2026-09-27 Pavel Safronov18} from '../world/schema.js'
e7a9f9dd 2026-09-17 Pavel Safronov19import { type CMountainGroup, compileMountains } from './mountains.js'
51c39d8b 2026-09-17 Pavel Safronov20import { type CDesert, compileDeserts } from './desert.js'
00ceeedb 2026-09-27 Pavel Safronov21import { type CForest, compileForests } from './forest.js'
a088e5d5 2026-09-17 Pavel Safronov22import { FALL_MIN_M, foamOf, manningSpeed } from './water.js'
376f2ce6 2026-09-16 Pavel Safronov23import { hash3 } from './noise.js'
e18dad04 2026-09-30 Pavel Safronov24import { iceSide } from './ice.js'
abc0aad0 2026-10-01 Pavel Safronov25import { GROW_AROUND, GROW_A_M, GROW_M, growFarm } from './farms.js'
376f2ce6 2026-09-16 Pavel Safronov26import {
80bcc97a 2026-09-17 Pavel Safronov27 type Box, type Line, type Shape, nearestA, shapeBox, shapeOf, signedDistance, sliceLine, smoothLine,
376f2ce6 2026-09-16 Pavel Safronov28} from './shapes.js'
29import { elevationStage, prepare, Stage } from './field.js'
30
31export interface CUplift {
32 id: string
14d35b7d 2026-09-16 Pavel Safronov33 /** A region raises ground and claims no cover; a desert or forest does both. */
34 kind: 'desert' | 'forest' | 'region'
376f2ce6 2026-09-16 Pavel Safronov35 shape: Shape
36 upliftM: number
37 edgeM: number
38 warpM: number
39 noiseAmpM: number
40 noiseScaleM: number
41 seed: number
42 box: Box
43}
44
45export interface CBasin {
46 id: string
47 kind: 'lake' | 'sea'
48 shape: Shape
49 levelM: number
50 depthM: number
51 basin: 'bowl' | 'flooded'
52 shoreM: number
53 rimM: number
54 maxInsideM: number
a088e5d5 2026-09-17 Pavel Safronov55 /**
56 * Its place in `CompiledWorld.basins`, which is how a water vertex names the body it
57 * belongs to. The sea state is not compiled: it follows the weather, which changes by
58 * the hour without the ground changing (sea-state.ts).
59 */
60 index: number
376f2ce6 2026-09-16 Pavel Safronov61 seed: number
62 box: Box
e18dad04 2026-09-30 Pavel Safronov63 /** A sea's ice, or null (D-090). */
64 ice: SeaIce | null
65 /**
66 * Where the open water begins on the far side from the ice, z in metres: where Tower's
67 * aimed light begins to fall toward it (ice.ts `aimedShare`). A band sea's end away from
68 * the ice; anything else has no open-water dim, and this is the ice edge.
69 */
70 openM: number
376f2ce6 2026-09-16 Pavel Safronov71}
72
abc0aad0 2026-10-01 Pavel Safronov73/** Farmland (farms.ts, D-095): where the fields are. The fields themselves are laid out live. */
74export interface CFarm {
75 id: string
76 /** The outline of a drawn farm, or null for a grown one. */
77 shape: Shape | null
78 edgeM: number
79 seed: number
80 box: Box
81 /** A grown farm's patches of ground (farms.ts `growFarm`), or empty for a drawn one. */
82 nodes: number[]
83}
84
80bcc97a 2026-09-17 Pavel Safronov85/** A waterfall: where a river's surface steps down, and by how much. */
86export interface CFall {
87 river: string
88 /** The lip, on the river's centre line. */
89 z: number
90 a: number
91 /** Unit direction the river flows over it, in (z, a). */
92 dz: number
93 da: number
94 topM: number
95 bottomM: number
96 widthM: number
97 /** Speed the water leaves the lip at. */
98 speedMS: number
99}
100
376f2ce6 2026-09-16 Pavel Safronov101export interface CRiver {
102 id: string
103 line: Line
104 /** Water surface at each line point, metres. Never rises downstream. */
105 level: number[]
80bcc97a 2026-09-17 Pavel Safronov106 /**
107 * What the valley's walls are shaped from: the same as `level`, except through a
108 * waterfall and the gorge below it, where it ramps smoothly from the lip's height to
109 * the foot's. The channel steps; the valley around it does not.
110 */
111 wallLevel: number[]
376f2ce6 2026-09-16 Pavel Safronov112 /** Channel half-width at each point, metres. */
113 halfWidth: number[]
114 /** Depth of the channel bed below the surface, metres. */
115 bed: number[]
116 /** Flow at each point, m³/s, tributaries included. */
117 flow: number[]
80bcc97a 2026-09-17 Pavel Safronov118 /** Mean speed at each point, m/s (Manning), and how white the water is there, 0..1. */
119 speed: number[]
120 foam: number[]
121 /**
122 * Segments whose downstream end drops a waterfall's height. The surface steps at the
123 * segment's middle rather than sloping across it (field.ts).
124 */
125 fallAt: number[]
376f2ce6 2026-09-16 Pavel Safronov126 /** How far from the centre line the valley, or the embankment carrying it, can reach. */
127 reach: number
128 box: Box
129 /** What the river ends in, resolved: a lake, sea or river id, or null. */
130 outlet: string | null
131}
132
133export interface CompiledWorld {
134 seed: number
135 ground: { baseM: number; reliefM: number }
136 uplifts: CUplift[]
abc0aad0 2026-10-01 Pavel Safronov137 /** Optional, so a world compiled before farmland existed still loads from the cache. */
138 farms?: CFarm[]
51c39d8b 2026-09-17 Pavel Safronov139 /** The deserts' compiled landforms: plateaus, washes, salt pans (desert.ts). */
140 deserts: CDesert[]
00ceeedb 2026-09-27 Pavel Safronov141 /** The forests: their density fields and what grows in them (forest.ts). */
142 forests: CForest[]
e7a9f9dd 2026-09-17 Pavel Safronov143 mountains: CMountainGroup[]
376f2ce6 2026-09-16 Pavel Safronov144 basins: CBasin[]
145 rivers: CRiver[]
80bcc97a 2026-09-17 Pavel Safronov146 falls: CFall[]
376f2ce6 2026-09-16 Pavel Safronov147}
148
149/** One line of the status dialog: a step that is about to run (world-generation.md §10.1). */
150export type StepListener = (label: string) => void
151
152const grow = (b: Box, m: number): Box => ({ z0: b.z0 - m, z1: b.z1 + m, a0: b.a0 - m, a1: b.a1 + m })
153
154/**
155 * Hydraulic geometry (Leopold & Maddock). Width grows as the square root of flow and
156 * depth a little slower, so a river's size comes from how much water it carries
157 * rather than from a number typed in beside it.
158 */
159export const channelHalfWidth = (q: number): number => Math.max(3, 2 * Math.sqrt(q))
160export const channelBed = (q: number): number => Math.max(0.6, 0.25 * q ** 0.4)
161
162export function compileWorld(world: World, onStep: StepListener = () => {}): CompiledWorld {
163 onStep('Reading the plans')
164 const cw: CompiledWorld = {
165 seed: world.seed,
166 ground: { baseM: world.ground.baseM, reliefM: world.ground.reliefM },
abc0aad0 2026-10-01 Pavel Safronov167 uplifts: [], deserts: [], forests: [], mountains: [], basins: [], rivers: [], falls: [], farms: [],
376f2ce6 2026-09-16 Pavel Safronov168 }
169 const seedOf = (f: Feature): number => hash3(world.seed, f.seed, 0x5eed)
170
171 // Order is the order of the elevation stack (field.ts): each stage may sample
172 // everything compiled before it, and nothing after.
173 for (const f of world.features) {
14d35b7d 2026-09-16 Pavel Safronov174 if (f.kind !== 'desert' && f.kind !== 'forest' && !(f.kind === 'region' && f.upliftM)) continue
175 onStep(f.kind === 'desert' ? `Quoting the deserts of Earth in ${f.name}`
176 : f.kind === 'forest' ? `Planting ${f.name}` : `Raising ${f.name}`)
376f2ce6 2026-09-16 Pavel Safronov177 const shape = shapeOf(f.geometry)
178 if (!shape) continue
179 cw.uplifts.push({
180 id: f.id, kind: f.kind, shape, upliftM: f.upliftM, edgeM: f.edgeM,
181 warpM: f.edgeM * 0.65,
182 // A desert is broken up at a finer grain than a forest floor.
183 noiseAmpM: Math.min(f.kind === 'desert' ? 90 : 70, Math.abs(f.upliftM) * 0.3),
184 noiseScaleM: f.kind === 'desert' ? 9000 : 15_000,
185 seed: seedOf(f),
186 box: grow(shapeBox(shape), f.edgeM * 1.7),
187 })
188 }
189
51c39d8b 2026-09-17 Pavel Safronov190 /**
191 * The deserts' own landforms stand on the shelf the uplift above raised, so they are
192 * compiled after it and before the ranges — which may stand on a desert's plateau.
193 */
194 // The shelf a desert's landforms stand on: the open ground and the uplift under it, so a
195 // salt pan's floor and its shorelines are elevations in the world rather than in the sand.
196 const shelf = prepare({ ...cw, deserts: [], mountains: [], basins: [], rivers: [] })
197 cw.deserts = compileDeserts(
198 world.features.filter((f): f is DesertFeature => f.kind === 'desert'), world.seed, seedOf, onStep,
199 // The rivers, as authored: the desert keeps its plateaus clear of them (desert.ts).
200 world.features.flatMap((f) => (f.kind === 'river' && f.geometry.type === 'polyline'
201 ? [smoothLine(f.geometry.points, 400)] : [])),
202 (z, a) => shelf.sample(a / RADIUS_M, z, 1).h)
203
00ceeedb 2026-09-27 Pavel Safronov204 // Forests need nothing but their own shape: what thins them out — water, rock, the
205 // treeline — is read off the ground as a tile samples it (forest.ts).
206 cw.forests = compileForests(
207 world.features.filter((f): f is ForestFeature => f.kind === 'forest'), seedOf, onStep,
208 // Settlements clear the ground they stand on: no forest inside a city (§4.6).
209 world.features.flatMap((f) => (f.kind === 'settlement' && f.geometry.type === 'point'
210 ? [{ z: f.geometry.z, a: f.geometry.theta * RADIUS_M, radiusM: f.radiusM }] : [])))
211
e7a9f9dd 2026-09-17 Pavel Safronov212 // Authored tarns keep a shelf of ground in whatever range they sit in (mountains.ts).
213 const benches = world.features.flatMap((f) => {
214 if (f.kind !== 'lake' || f.basin !== 'bowl') return []
215 const shape = shapeOf(f.geometry)
216 if (!shape || shape.type !== 'polygon') return []
217 const b = shape.box
218 return [{ z: (b.z0 + b.z1) / 2, a: (b.a0 + b.a1) / 2, radiusM: Math.max(b.z1 - b.z0, b.a1 - b.a0) / 2 }]
219 })
220 // The land a range stands on: open ground and the shelves already compiled, at the
221 // detail the observer's feet are sampled at, so a summit's elevation is exact there.
222 const land = prepare({ ...cw, mountains: [], basins: [], rivers: [] })
223 cw.mountains = compileMountains(
224 world.features.filter((f): f is Mountains => f.kind === 'mountains'), world.seed, seedOf, onStep, benches,
225 (z, a) => land.sample(a / RADIUS_M, z, 1).h)
376f2ce6 2026-09-16 Pavel Safronov226
227 for (const f of world.features) {
228 if (f.kind !== 'lake' && f.kind !== 'sea') continue
229 onStep(`Filling ${f.name}`)
230 const b = compileBasin(f, seedOf(f), cw)
231 if (b) cw.basins.push(b)
232 }
233
234 compileRivers(world.features.filter((f): f is River => f.kind === 'river'), cw, onStep)
abc0aad0 2026-10-01 Pavel Safronov235 compileFarms(world, cw, seedOf, onStep)
376f2ce6 2026-09-16 Pavel Safronov236 return cw
237}
238
abc0aad0 2026-10-01 Pavel Safronov239/**
240 * Farmland, last: a farm grows over the land as it is, water and rivers and all (D-097). A
241 * drawn farm is only its outline; its fields are laid out live (farms.ts).
242 */
243function compileFarms(world: World, cw: CompiledWorld, seedOf: (f: Feature) => number, onStep: StepListener): void {
244 const land = prepare({ ...cw, farms: [] })
245 /** Ground a farm may take: dry, not sand or rock or a range, and gentle enough to plough. */
246 const fits = (z: number, a: number): boolean => {
247 const theta = a / RADIUS_M
248 const s = land.sample(theta, z, 50)
249 if (s.water > s.h || s.desert > 0.2 || s.rock > 0.2 || s.relief > 150 || s.glacier > 0) return false
250 const h = s.h
251 const gz = (land.sample(theta, z + 100, 50).h - h) / 100
252 const ga = (land.sample(theta + 100 / RADIUS_M, z, 50).h - h) / 100
253 return Math.hypot(gz, ga) < 0.12
254 }
255 for (const f of world.features) {
256 if (f.kind !== 'farmland') continue
257 onStep(`Sowing ${f.name}`)
258 const seed = seedOf(f)
259 if (f.geometry.type === 'point') {
260 const z = f.geometry.z, a = f.geometry.theta * RADIUS_M
261 const nodes = growFarm(z, a, f.areaKm2 * 1e6, seed % 289, fits)
262 // The box, measured round from the seed so a farm across θ = 0 is not the whole ring.
263 let z0 = Infinity, z1 = -Infinity, a0 = Infinity, a1 = -Infinity
264 for (const n of nodes) {
265 const nz = Math.floor(n / GROW_AROUND) * GROW_M
266 const na = a + nearestA((n % GROW_AROUND) * GROW_A_M, a) - a
267 z0 = Math.min(z0, nz); z1 = Math.max(z1, nz); a0 = Math.min(a0, na); a1 = Math.max(a1, na)
268 }
269 const pad = 1200
270 cw.farms!.push({ id: f.id, shape: null, edgeM: f.edgeM, seed, nodes,
271 box: { z0: z0 - pad, z1: z1 + pad, a0: a0 - pad, a1: a1 + pad } })
272 continue
273 }
274 const shape = shapeOf(f.geometry)
275 if (!shape) continue
276 cw.farms!.push({ id: f.id, shape, edgeM: f.edgeM, seed, nodes: [], box: grow(shapeBox(shape), f.edgeM) })
277 }
278}
279
376f2ce6 2026-09-16 Pavel Safronov280/** The greatest distance from any interior point to the edge, sampled. */
281function maxInside(shape: Shape): number {
282 if (shape.type === 'band') return (shape.zTo - shape.zFrom) / 2
283 const b = shape.box
284 const N = 64
285 let best = 0
286 for (let i = 0; i < N; i++) {
287 for (let j = 0; j < N; j++) {
288 const z = b.z0 + ((b.z1 - b.z0) * (i + 0.5)) / N
289 const a = b.a0 + ((b.a1 - b.a0) * (j + 0.5)) / N
290 best = Math.max(best, signedDistance(shape, z, a))
291 }
292 }
293 return best
294}
295
296// ----------------------------------------------------------------------- basins
297
298function compileBasin(f: Lake | Sea, seed: number, cw: CompiledWorld): CBasin | null {
299 const shape = shapeOf(f.geometry)
300 if (!shape) return null
301 const flooded = f.kind === 'sea' || f.basin === 'flooded'
302 const b: CBasin = {
303 id: f.id, kind: f.kind, shape,
304 levelM: 0, depthM: f.depthM,
305 basin: flooded ? 'flooded' : 'bowl',
306 shoreM: f.shoreM,
307 rimM: f.kind === 'lake' ? f.rimM : 0,
308 maxInsideM: Math.max(10, maxInside(shape)),
a088e5d5 2026-09-17 Pavel Safronov309 index: cw.basins.length,
376f2ce6 2026-09-16 Pavel Safronov310 seed,
311 box: grow(shapeBox(shape), flooded ? f.shoreM + 8000 : 50),
e18dad04 2026-09-30 Pavel Safronov312 ice: f.kind === 'sea' ? f.ice : null,
313 openM: 0,
314 }
315 if (b.ice) {
316 b.openM = shape.type !== 'band' ? b.ice.edgeM
317 : iceSide(b.ice) > 0 ? shape.zFrom : shape.zTo
376f2ce6 2026-09-16 Pavel Safronov318 }
319
320 const level = f.levelM
321 if (typeof level === 'number') {
322 b.levelM = level
323 return b
324 }
325 /**
326 * An automatic level fills the basin from its floor upward. Taking the level from
327 * the rim instead lets the water spill downhill and leaves a half-moon rather than
328 * a lake — the bug D-020 recorded for v1's tarns.
329 */
330 const rt = prepare({ ...cw, basins: [...cw.basins, { ...b, levelM: -Infinity }], rivers: [] })
331 let floor = Infinity
332 const box = shapeBox(shape)
333 const N = 48
334 for (let i = 0; i < N; i++) {
335 for (let j = 0; j < N; j++) {
336 const z = box.z0 + ((box.z1 - box.z0) * (i + 0.5)) / N
337 const a = box.a0 + ((box.a1 - box.a0) * (j + 0.5)) / N
338 if (signedDistance(shape, z, a) <= 0) continue
339 floor = Math.min(floor, elevationStage(rt, a / RADIUS_M, z, 100, Stage.Basins))
340 }
341 }
342 b.levelM = Number.isFinite(floor) ? floor + f.depthM * 0.6 : 0
343 return b
344}
345
346// ----------------------------------------------------------------------- rivers
347
348const RIVER_STEP_M = 200
349/**
350 * The gentlest a river is allowed to run: 2 m per km, about the Mississippi's lower
351 * reaches. Anything flatter is a canal, and a canal has to be pumped.
352 */
353const MIN_GRADE = 0.002
14d35b7d 2026-09-16 Pavel Safronov354/**
355 * How strongly a river's profile prefers cutting to filling: the quantile of the ground
356 * it sits at. 0.5 would treat a metre of embankment like a metre of cutting; 0.2 lets
357 * the water run below four-fifths of the ground in any pooled reach, so the floor is
358 * mostly dug and only built up where it has to be.
359 */
360const FILL_QUANTILE = 0.2
376f2ce6 2026-09-16 Pavel Safronov361/** Rise per metre of run on the flanks of ground built up to carry a river. */
362export const EMBANKMENT_SLOPE = 0.15
363/** How far past its end a river may be from the water it flows into. */
364const OUTLET_REACH_M = 3000
365
366function compileRivers(rivers: River[], cw: CompiledWorld, onStep: StepListener): void {
80bcc97a 2026-09-17 Pavel Safronov367 const lines = new Map(rivers.map((r) => [r.id, trimToShores(smoothLine(
368 (r.geometry.type === 'polyline' ? r.geometry.points : []) as [number, number][], RIVER_STEP_M), cw.basins, cw)]))
376f2ce6 2026-09-16 Pavel Safronov369 const endOf = (l: Line): [number, number] => [l.pts[l.pts.length - 2]!, l.pts[l.pts.length - 1]!]
370
371 /** Where a river ends: into which basin or river, and where along that river. */
372 type Outlet = { basin: CBasin } | { river: River; at: number } | null
373 const outletOf = (r: River): Outlet => {
374 const [ez, ea] = endOf(lines.get(r.id)!)
375 const wanted = r.outlet === 'auto' ? null : r.outlet
376 for (const b of cw.basins) {
377 if (wanted && b.id !== wanted) continue
378 if (wanted || signedDistance(b.shape, ez, ea) > -OUTLET_REACH_M) return { basin: b }
379 }
380 /**
381 * Into another river: the nearest river that passes the end point. A river whose
382 * own end is the nearest point is not a candidate — two tributaries meeting
383 * head-on at a confluence (Westwall Water and Eastwall Water at the gap, D-020)
384 * both flow into the river that carries on from there, not into each other.
385 */
386 let best: Outlet = null
387 let bestD = OUTLET_REACH_M
388 for (const other of rivers) {
389 if (other.id === r.id || (wanted && other.id !== wanted)) continue
390 const l = lines.get(other.id)!
391 const last = l.pts.length / 2 - 1
392 let d = Infinity, at = 0
393 for (let i = 0; i <= last; i++) {
394 const di = Math.hypot(l.pts[2 * i]! - ez, nearestA(l.pts[2 * i + 1]!, ea) - ea)
395 if (di < d) { d = di; at = i }
396 }
397 if (at >= last - 2 && !wanted) continue
398 if (d < bestD || wanted) { bestD = d; best = { river: other, at } }
399 }
400 return best
401 }
402 const outlets = new Map(rivers.map((r) => [r.id, outletOf(r)]))
403
404 // A river into a river is resolved after the river it joins. A cycle — two rivers
405 // each draining into the other — cannot happen in water, so it is broken here.
406 const order: River[] = []
407 const state = new Map<string, 'visiting' | 'done'>()
408 const visit = (r: River): void => {
409 if (state.get(r.id)) return
410 state.set(r.id, 'visiting')
411 const o = outlets.get(r.id)
412 if (o && 'river' in o && state.get(o.river.id) !== 'visiting') visit(o.river)
413 state.set(r.id, 'done')
414 order.push(r)
415 }
416 rivers.forEach(visit)
417
418 // Flow, children first: a tributary's whole flow joins its parent below the confluence.
419 const flows = new Map(rivers.map((r) => [r.id, lines.get(r.id)!.s.map(() => r.flowM3S)]))
420 for (const r of [...order].reverse()) {
421 const o = outlets.get(r.id)
422 if (!o || !('river' in o)) continue
423 const mine = flows.get(r.id)!
424 const theirs = flows.get(o.river.id)!
425 const total = mine[mine.length - 1]!
426 for (let i = o.at; i < theirs.length; i++) theirs[i] = theirs[i]! + total
427 }
428
429 // Levels, parents first, since a tributary's mouth is its parent's surface.
430 const done = new Map<string, CRiver>()
431 const rt = prepare({ ...cw, rivers: [] })
432 for (const r of order) {
433 onStep(`Teaching ${r.name} which way is down`)
434 const line = lines.get(r.id)!
435 const flow = flows.get(r.id)!
436 const n = line.s.length
437 const halfWidth = flow.map(channelHalfWidth)
438 const bed = flow.map(channelBed)
439
440 // The ground the river crosses: land surface, or water where it crosses water.
441 const surface = new Array<number>(n)
442 for (let i = 0; i < n; i++) {
443 const s = rt.sample(line.pts[2 * i + 1]! / RADIUS_M, line.pts[2 * i]!, 60)
444 surface[i] = Math.max(s.h, s.water)
445 }
446
447 const o = outlets.get(r.id)
448 // A river that rises in a lake leaves it at the lake's level: the tarns are the top
449 // of the world's water loop (design.md §1.11).
450 const [sz, sa] = [line.pts[0]!, line.pts[1]!]
80bcc97a 2026-09-17 Pavel Safronov451 // Within a step of the shore: the line was trimmed to start there (trimToShores).
452 const lake = cw.basins.find((b) => signedDistance(b.shape, sz, sa) > -RIVER_STEP_M)
376f2ce6 2026-09-16 Pavel Safronov453 let mouth: number
454 if (o && 'basin' in o) mouth = o.basin.levelM
455 else if (o && 'river' in o && done.has(o.river.id)) mouth = done.get(o.river.id)!.level[o.at]!
456 else mouth = surface[n - 1]! - bed[n - 1]!
457
458 /**
459 * The long profile: never rising downstream (design.md §1.9.3), and otherwise as
460 * close to the ground the river crosses as it can be.
461 *
462 * A Tower river exists only because the floor was shaped to make it descend, so
463 * where the ground rises across its course something has to give. Clamping the
464 * water to the ground lets one dip drag the whole river down after it — v1's world
465 * has a lowland 60 m high between the Girdle and the Dry Reach, and a river forced
466 * down into it would need a canyon 900 m deep for a hundred kilometres to reach The
467 * Narrows. Holding the water up at a graded profile instead needs an embankment
468 * over a kilometre high across that lowland.
469 *
470 * So the profile is the monotone one nearest the ground: an isotonic regression,
471 * which cuts where the ground is high and builds up where it is low in whatever
472 * balance moves the least earth. Where the ground dips and rises again the answer
473 * is a level pool, which is what an engineered river has there anyway.
474 */
475 const total = line.s[n - 1]! || 1
476 const cap = lake ? lake.levelM : typeof r.sourceM === 'number' ? r.sourceM : Infinity
477 /**
478 * With one refinement: water on a level has nowhere to go, so the fit is made to
479 * fall by at least `grade` per metre everywhere. Fitting `level + grade·s` as
480 * non-increasing is exactly that constraint, and the trend is taken back out after.
481 */
e7a9f9dd 2026-09-17 Pavel Safronov482 const grade = MIN_GRADE
376f2ce6 2026-09-16 Pavel Safronov483 /**
484 * The ends are held, by weight: the mouth has to meet the water it flows into, and
485 * a source in a lake has to leave at the lake's level.
486 */
487 const target = surface.map((g, i) => g - bed[i]!)
488 const weight = target.map(() => 1)
489 target[n - 1] = mouth
490 weight[n - 1] = n
491 // An authored source height is only a ceiling: pinning the water to it where the
492 // ground is far lower would stand the river's first kilometre on a tower of fill.
493 if (lake) { target[0] = lake.levelM; weight[0] = n }
14d35b7d 2026-09-16 Pavel Safronov494 const fitted = nonIncreasing(target.map((v, i) => v + grade * line.s[i]!), weight, FILL_QUANTILE)
376f2ce6 2026-09-16 Pavel Safronov495 /**
496 * Never below the water it drains into plus the grade still to fall. Where the whole
497 * course lies lower than the river it joins — a tributary drawn across a lowland to
498 * a confluence up on a plateau — this is the embankment that carries it there.
499 */
500 const level = fitted.map((v, i) =>
501 Math.min(cap, Math.max(mouth + grade * (total - line.s[i]!), v - grade * line.s[i]!)))
502
80bcc97a 2026-09-17 Pavel Safronov503 /**
504 * Where the profile steps down several times in a row — a river coming off a range
505 * steps every 200 m for kilometres — the steps become one fall. A river meeting a hard
506 * edge drops at the lip and cuts a gorge below it; it does not descend a staircase of
507 * identical ten-storey falls. The run's lower points take the bottom level, which is
508 * what cuts the gorge (field.ts).
509 */
510 const wallLevel = [...level]
511 for (let i = 0; i < n - 1; i++) {
512 if (level[i]! - level[i + 1]! < FALL_MIN_M) continue
513 let j = i + 1
514 while (j < n - 1 && level[j]! - level[j + 1]! >= FALL_MIN_M) j++
515 for (let k = i + 1; k < j; k++) {
516 wallLevel[k] = level[i]! + ((level[j]! - level[i]!) * (k - i)) / (j - i)
517 level[k] = level[j]!
518 }
519 i = j - 1
520 }
521
376f2ce6 2026-09-16 Pavel Safronov522 // Far enough for the widest embankment this river has to build.
523 let fill = 0
524 for (let i = 0; i < n; i++) fill = Math.max(fill, level[i]! - surface[i]!)
525 const reach = Math.max(...halfWidth) + Math.max(4500, fill / EMBANKMENT_SLOPE)
80bcc97a 2026-09-17 Pavel Safronov526
527 /**
528 * Speed and whiteness from the local grade, and waterfalls where the surface steps.
529 * The profile's pools come out level and meet at steps (the isotonic fit pools
530 * reaches together), so a big enough step between two points is a fall, not a
531 * steep chute: the river holds its level to the lip and drops.
532 */
533 const speed: number[] = [], foam: number[] = [], fallAt: number[] = []
534 for (let i = 0; i < n; i++) {
535 const j0 = Math.max(0, i - 2), j1 = Math.min(n - 1, i + 2)
536 const run = line.s[j1]! - line.s[j0]! || 1
537 let drop = level[j0]! - level[j1]!
538 // A fall inside the window is not the reach's grade: take it out.
539 for (let k = j0; k < j1; k++) if (level[k]! - level[k + 1]! >= FALL_MIN_M) drop -= level[k]! - level[k + 1]!
540 const grade = Math.max(0, drop / run)
541 speed.push(manningSpeed(bed[i]!, grade))
542 foam.push(foamOf(grade))
543 }
544 for (let i = 0; i < n - 1; i++) {
545 const top = level[i]!, bottom = level[i + 1]!
546 if (top - bottom < FALL_MIN_M) continue
547 fallAt.push(i)
548 const z0 = line.pts[2 * i]!, a0 = line.pts[2 * i + 1]!
549 const z1 = line.pts[2 * i + 2]!, a1 = line.pts[2 * i + 3]!
550 const len = Math.hypot(z1 - z0, a1 - a0) || 1
551 cw.falls.push({
552 river: r.id, z: (z0 + z1) / 2, a: (a0 + a1) / 2, dz: (z1 - z0) / len, da: (a1 - a0) / len,
553 topM: top, bottomM: bottom, widthM: 2 * halfWidth[i]!, speedMS: speed[i]!,
554 })
555 }
556
376f2ce6 2026-09-16 Pavel Safronov557 const c: CRiver = {
80bcc97a 2026-09-17 Pavel Safronov558 id: r.id, line, level, wallLevel, halfWidth, bed, flow, speed, foam, fallAt, reach,
376f2ce6 2026-09-16 Pavel Safronov559 box: grow(line.box, reach),
560 outlet: o ? ('basin' in o ? o.basin.id : o.river.id) : null,
561 }
562 done.set(r.id, c)
563 cw.rivers.push(c)
564 }
565}
566
80bcc97a 2026-09-17 Pavel Safronov567/**
568 * A river drawn from the middle of a lake, or into one, starts and ends at the water's
569 * edge. v1 drew the Long Water from the centre of Hollow Tarn; kept whole, its channel
570 * was cut across the lake floor and its water drawn inside the lake a few metres off the
571 * lake's level, a stripe across the tarn (the author saw it).
572 *
573 * The edge is found by sampling the water itself, not the outline: a tarn's water fills
574 * only as much of its bowl as lies below its level, about the inner 70%, and trimmed to
575 * a guess the river stopped short of it. The river keeps one point inside the water, so
576 * its channel runs into the lake rather than stopping at the shore.
577 */
578function trimToShores(line: Line, basins: CBasin[], cw: CompiledWorld): Line {
579 const n = line.pts.length / 2
580 if (n < 3 || !basins.length) return line
581 const rt = prepare({ ...cw, rivers: [] })
582 const wet = (i: number): boolean => {
583 const s = rt.sample(line.pts[2 * i + 1]! / RADIUS_M, line.pts[2 * i]!, 20, Stage.Basins)
584 return s.waterMesh
585 }
586 let from = 0, to = n - 1
587 if (wet(0)) {
588 while (from < n - 2 && wet(from + 1)) from++
589 }
590 if (wet(n - 1)) {
591 while (to > from + 1 && wet(to - 1)) to--
592 }
593 return from === 0 && to === n - 1 ? line : sliceLine(line, from, to)
594}
595
376f2ce6 2026-09-16 Pavel Safronov596/**
14d35b7d 2026-09-16 Pavel Safronov597 * The non-increasing sequence nearest `y`, by pool adjacent violators.
598 *
599 * `tau` sets what "nearest" means. At 0.5 each pooled block takes the weighted median
600 * of its values — least absolute error, cut and fill alike. Below 0.5 it takes a lower
601 * quantile, so the sequence prefers to sit *under* the data: for a river, cutting the
602 * ground is cheaper than building it up, which is the right way round (D-064). The
603 * blocks keep their values, so this is quadratic in the worst case; a river is a few
604 * hundred points.
376f2ce6 2026-09-16 Pavel Safronov605 */
14d35b7d 2026-09-16 Pavel Safronov606export function nonIncreasing(
607 y: readonly number[], w: readonly number[] = y.map(() => 1), tau = 0.5,
608): number[] {
609 type Block = { values: [number, number][]; stat: number; count: number }
610 const quantile = (values: [number, number][]): number => {
611 values.sort((a, b) => a[0] - b[0])
612 const total = values.reduce((t, v) => t + v[1], 0)
613 let run = 0
614 for (const [v, wt] of values) {
615 run += wt
616 if (run >= tau * total) return v
617 }
618 return values[values.length - 1]![0]
619 }
620 const blocks: Block[] = []
376f2ce6 2026-09-16 Pavel Safronov621 y.forEach((v, i) => {
14d35b7d 2026-09-16 Pavel Safronov622 blocks.push({ values: [[v, w[i]!]], stat: v, count: 1 })
376f2ce6 2026-09-16 Pavel Safronov623 // A later block higher than the one before it is a violation: merge them.
14d35b7d 2026-09-16 Pavel Safronov624 while (blocks.length > 1 && blocks[blocks.length - 1]!.stat > blocks[blocks.length - 2]!.stat) {
625 const b1 = blocks.pop()!, b0 = blocks.pop()!
626 const values = b0.values.concat(b1.values)
627 blocks.push({ values, stat: quantile(values), count: b0.count + b1.count })
376f2ce6 2026-09-16 Pavel Safronov628 }
629 })
630 const out: number[] = []
14d35b7d 2026-09-16 Pavel Safronov631 for (const b of blocks) for (let i = 0; i < b.count; i++) out.push(b.stat)
376f2ce6 2026-09-16 Pavel Safronov632 return out
633}