tower / files / src / terrain / compile.ts
compile.ts
| 1 | /** |
| 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 | */ |
| 15 | import { RADIUS_M } from '../canon/constants.js' |
| 16 | import type { |
| 17 | Desert as DesertFeature, Feature, Forest as ForestFeature, Lake, Mountains, River, Sea, SeaIce, World, |
| 18 | } from '../world/schema.js' |
| 19 | import { type CMountainGroup, compileMountains } from './mountains.js' |
| 20 | import { type CDesert, compileDeserts } from './desert.js' |
| 21 | import { type CForest, compileForests } from './forest.js' |
| 22 | import { FALL_MIN_M, foamOf, manningSpeed } from './water.js' |
| 23 | import { hash3 } from './noise.js' |
| 24 | import { iceSide } from './ice.js' |
| 25 | import { GROW_AROUND, GROW_A_M, GROW_M, growFarm } from './farms.js' |
| 26 | import { |
| 27 | type Box, type Line, type Shape, nearestA, shapeBox, shapeOf, signedDistance, sliceLine, smoothLine, |
| 28 | } from './shapes.js' |
| 29 | import { elevationStage, prepare, Stage } from './field.js' |
| 30 | |
| 31 | export interface CUplift { |
| 32 | id: string |
| 33 | /** A region raises ground and claims no cover; a desert or forest does both. */ |
| 34 | kind: 'desert' | 'forest' | 'region' |
| 35 | 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 | |
| 45 | export 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 |
| 55 | /** |
| 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 |
| 61 | seed: number |
| 62 | box: Box |
| 63 | /** 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 |
| 71 | } |
| 72 | |
| 73 | /** Farmland (farms.ts, D-095): where the fields are. The fields themselves are laid out live. */ |
| 74 | export 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 | |
| 85 | /** A waterfall: where a river's surface steps down, and by how much. */ |
| 86 | export 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 | |
| 101 | export interface CRiver { |
| 102 | id: string |
| 103 | line: Line |
| 104 | /** Water surface at each line point, metres. Never rises downstream. */ |
| 105 | level: number[] |
| 106 | /** |
| 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[] |
| 112 | /** 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[] |
| 118 | /** 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[] |
| 126 | /** 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 | |
| 133 | export interface CompiledWorld { |
| 134 | seed: number |
| 135 | ground: { baseM: number; reliefM: number } |
| 136 | uplifts: CUplift[] |
| 137 | /** Optional, so a world compiled before farmland existed still loads from the cache. */ |
| 138 | farms?: CFarm[] |
| 139 | /** The deserts' compiled landforms: plateaus, washes, salt pans (desert.ts). */ |
| 140 | deserts: CDesert[] |
| 141 | /** The forests: their density fields and what grows in them (forest.ts). */ |
| 142 | forests: CForest[] |
| 143 | mountains: CMountainGroup[] |
| 144 | basins: CBasin[] |
| 145 | rivers: CRiver[] |
| 146 | falls: CFall[] |
| 147 | } |
| 148 | |
| 149 | /** One line of the status dialog: a step that is about to run (world-generation.md §10.1). */ |
| 150 | export type StepListener = (label: string) => void |
| 151 | |
| 152 | const 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 | */ |
| 159 | export const channelHalfWidth = (q: number): number => Math.max(3, 2 * Math.sqrt(q)) |
| 160 | export const channelBed = (q: number): number => Math.max(0.6, 0.25 * q ** 0.4) |
| 161 | |
| 162 | export 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 }, |
| 167 | uplifts: [], deserts: [], forests: [], mountains: [], basins: [], rivers: [], falls: [], farms: [], |
| 168 | } |
| 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) { |
| 174 | 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}`) |
| 177 | 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 | |
| 190 | /** |
| 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 | |
| 204 | // 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 | |
| 212 | // 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) |
| 226 | |
| 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) |
| 235 | compileFarms(world, cw, seedOf, onStep) |
| 236 | return cw |
| 237 | } |
| 238 | |
| 239 | /** |
| 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 | */ |
| 243 | function 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 | |
| 280 | /** The greatest distance from any interior point to the edge, sampled. */ |
| 281 | function 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 | |
| 298 | function 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)), |
| 309 | index: cw.basins.length, |
| 310 | seed, |
| 311 | box: grow(shapeBox(shape), flooded ? f.shoreM + 8000 : 50), |
| 312 | 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 |
| 318 | } |
| 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 | |
| 348 | const 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 | */ |
| 353 | const MIN_GRADE = 0.002 |
| 354 | /** |
| 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 | */ |
| 360 | const FILL_QUANTILE = 0.2 |
| 361 | /** Rise per metre of run on the flanks of ground built up to carry a river. */ |
| 362 | export const EMBANKMENT_SLOPE = 0.15 |
| 363 | /** How far past its end a river may be from the water it flows into. */ |
| 364 | const OUTLET_REACH_M = 3000 |
| 365 | |
| 366 | function compileRivers(rivers: River[], cw: CompiledWorld, onStep: StepListener): void { |
| 367 | 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)])) |
| 369 | 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]!] |
| 451 | // 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) |
| 453 | 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 | */ |
| 482 | const grade = MIN_GRADE |
| 483 | /** |
| 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 } |
| 494 | const fitted = nonIncreasing(target.map((v, i) => v + grade * line.s[i]!), weight, FILL_QUANTILE) |
| 495 | /** |
| 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 | |
| 503 | /** |
| 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 | |
| 522 | // 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) |
| 526 | |
| 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 | |
| 557 | const c: CRiver = { |
| 558 | id: r.id, line, level, wallLevel, halfWidth, bed, flow, speed, foam, fallAt, reach, |
| 559 | 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 | |
| 567 | /** |
| 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 | */ |
| 578 | function 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 | |
| 596 | /** |
| 597 | * 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. |
| 605 | */ |
| 606 | export 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[] = [] |
| 621 | y.forEach((v, i) => { |
| 622 | blocks.push({ values: [[v, w[i]!]], stat: v, count: 1 }) |
| 623 | // A later block higher than the one before it is a violation: merge them. |
| 624 | 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 }) |
| 628 | } |
| 629 | }) |
| 630 | const out: number[] = [] |
| 631 | for (const b of blocks) for (let i = 0; i < b.count; i++) out.push(b.stat) |
| 632 | return out |
| 633 | } |