fuzzyworld

tower / files / src / terrain / forest.ts

forest.ts

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

00ceeedb 2026-09-27 Pavel Safronov1/**
2 * Forests: where trees stand, how big they are, and how to find the ones near you without
3 * knowing about any of the others. See world-generation.md §4.6.
4 *
5 * Tower planted these, so the numbers are a statement of what it planted: stems per
6 * hectare, the mix of conifer and broadleaf, the share of ground left open as meadows, and
7 * — in the tall wood — sequoia-class giants grown near the limit of what a tree can be at
8 * 1 g (about 122–130 m, Koch et al. 2004).
9 *
10 * **Placement is stratified, not solved.** The surface is divided into a fixed global grid
11 * of cells about one tree apart. Each cell hashes its own coordinates to decide whether it
12 * holds a tree, where in the cell it stands, and what it is — and accepts it with
13 * probability density/max. That is blue-noise-like, and, the property that matters here,
14 * **any tile or any view can work out its own trees with no knowledge of any other**
15 * (§4.6). Greatwood holds about three billion trees; only the few thousand near the eye
16 * are ever made.
17 */
18import { CIRCUMFERENCE_M, RADIUS_M } from '../canon/constants.js'
19import { type CylPoint, cylPoint, fbm, hash3, mulberry32 } from './noise.js'
20import { type Box, type Shape, nearestA, shapeBox, shapeOf, signedDistance } from './shapes.js'
21import type { Forest } from '../world/schema.js'
22
23export const HECTARE_M2 = 10_000
24
25export interface CForest {
26 id: string
27 shape: Shape
28 box: Box
29 seed: number
30 densityPerHa: number
31 conifer: number
32 giants: boolean
33 edgeM: number
34 treelineM: number
35 /**
36 * The band of this forest's meadow noise that a meadow's edge falls in: below `meadowLo`
37 * is closed forest, above `meadowHi` is open ground. Both are measured over the forest
38 * itself rather than assumed — and so is the *width* between them, or a band guessed in
39 * noise units swallows the whole forest when the noise turns out to vary by less
40 * than that.
41 */
42 meadowLo: number
43 meadowHi: number
44 /** Mean height of a mature tree here, metres: what the canopy stands at from a distance. */
45 canopyM: number
46 /**
47 * Forests inside this one that replace it: the tall wood stands *instead of* Greatwood
48 * where it stands, rather than as giants mixed through it (§4.6). The smaller forest
49 * wins its own ground.
50 */
51 holes: Shape[]
52 /**
53 * Ground the trees are off: a settlement's footprint. Tower did not plant a forest where
54 * it built a city, and the Capital stands in the middle of Greatwood's belt.
55 */
56 clearings: { z: number; a: number; radiusM: number }[]
57}
58
59/** Heights, crown widths and spacing, by what a tree is. See §4.6. */
60export const TREE = {
61 conifer: { minM: 20, maxM: 45, crown: 0.28 },
62 broadleaf: { minM: 15, maxM: 30, crown: 0.62 },
63 /**
64 * Coast redwoods reach 116 m on Earth; hydraulics cap any tree near 122–130 m. Their
65 * crowns are narrow for their height — a 100 m redwood carries about 18 m of crown, not
66 * the 35 m a conifer's usual proportions would give it, and at 0.34 the grove closed
67 * over into unbroken dark.
68 */
69 giant: { minM: 90, maxM: 115, crown: 0.18 },
70} as const
71
72/** Giants stand far apart: a grove is dark and open, not a thicket — 18 m between trunks. */
73export const GIANT_DENSITY_PER_HA = 30
74
75const smoothstep = (e0: number, e1: number, x: number): number => {
76 const t = Math.min(1, Math.max(0, (x - e0) / (e1 - e0)))
77 return t * t * (3 - 2 * t)
78}
79
80const layer = (seed: number, i: number): number => hash3(seed, i, 0x0f0e) & 0x7fffffff
81
82/** The meadow field: high where Tower left the ground open. */
83function meadowNoise(f: CForest, p: CylPoint, detailM: number): number {
84 return fbm(layer(f.seed, 1), p, 2600, 3, detailM) * 0.7
85 + fbm(layer(f.seed, 2), p, 11_000, 2, detailM) * 0.3
86}
87
88export function compileForests(
89 features: Forest[], seedOf: (f: Forest) => number,
90 onStep: (label: string) => void = () => {},
91 clearings: { z: number; a: number; radiusM: number }[] = [],
92): CForest[] {
93 const out: CForest[] = []
94 for (const f of features) {
95 const shape = shapeOf(f.geometry)
96 if (!shape) continue
97 onStep(f.giants ? `Growing the giants of ${f.name}` : `Planting ${f.name}`)
98 const seed = seedOf(f)
99 const box = shapeBox(shape)
100 const density = f.giants ? Math.min(f.densityPerHa, GIANT_DENSITY_PER_HA) : f.densityPerHa
101 const kind = f.giants ? TREE.giant : null
102 const c: CForest = {
103 id: f.id, shape, box: grow(box, f.edgeM), seed,
104 densityPerHa: density, conifer: f.conifer, giants: f.giants,
105 edgeM: f.edgeM, treelineM: f.treelineM, meadowLo: Infinity, meadowHi: Infinity,
106 holes: [], clearings,
107 canopyM: kind
108 ? (kind.minM + kind.maxM) / 2
109 : (f.conifer * (TREE.conifer.minM + TREE.conifer.maxM)
110 + (1 - f.conifer) * (TREE.broadleaf.minM + TREE.broadleaf.maxM)) / 2,
111 }
112 const band = meadowBandOf(c, f.meadows)
113 c.meadowLo = band.lo
114 c.meadowHi = band.hi
115 out.push(c)
116 }
117 // Each forest yields its ground to any smaller forest standing inside it.
118 for (const f of out) {
119 for (const g of out) {
120 if (g === f || areaOf(g.shape) >= areaOf(f.shape)) continue
121 f.holes.push(g.shape)
122 }
123 }
124 return out
125}
126
127/** Roughly how much ground a shape covers, m²: only ever compared with another's. */
128function areaOf(shape: Shape): number {
129 if (shape.type === 'band') return (shape.zTo - shape.zFrom) * CIRCUMFERENCE_M
130 let sum = 0
131 const { pts } = shape
132 for (let i = 0, n = pts.length / 2; i < n; i++) {
133 const j = (i + 1) % n
134 sum += pts[2 * i]! * pts[2 * j + 1]! - pts[2 * j]! * pts[2 * i + 1]!
135 }
136 return Math.abs(sum) / 2
137}
138
139const grow = (b: Box, m: number): Box => ({ z0: b.z0 - m, z1: b.z1 + m, a0: b.a0 - m, a1: b.a1 + m })
140
141/**
142 * The noise levels that leave `coverage` of this forest open, measured by sampling the
143 * forest — the same lesson the deserts taught, and one more besides: the *edge* of a
144 * meadow is a quantile too. Taking it as a fixed ±0.02 of noise left Greatwood as
145 * scattered islands, because its noise only varies by about that much in total.
146 */
147function meadowBandOf(f: CForest, coverage: number): { lo: number; hi: number } {
148 if (coverage <= 0) return { lo: Infinity, hi: Infinity }
149 if (coverage >= 1) return { lo: -Infinity, hi: -Infinity }
150 const samples: number[] = []
151 const rand = mulberry32(hash3(f.seed, 0x3ee, 0x77))
152 const b = f.box
153 // A band rings the world, so its box has no bounds around theta: sample a whole turn.
154 const a0 = Number.isFinite(b.a0) ? b.a0 : 0
155 const a1 = Number.isFinite(b.a1) ? b.a1 : CIRCUMFERENCE_M
156 for (let i = 0; i < 4000; i++) {
157 const z = b.z0 + (b.z1 - b.z0) * rand()
158 const a = a0 + (a1 - a0) * rand()
159 if (signedDistance(f.shape, z, a) < 0) continue
160 samples.push(meadowNoise(f, cylPoint(a / RADIUS_M, z), 40))
161 }
162 if (!samples.length) return { lo: Infinity, hi: Infinity }
163 samples.sort((x, y) => x - y)
164 const at = (share: number): number =>
165 samples[Math.min(samples.length - 1, Math.max(0, Math.round((1 - share) * (samples.length - 1))))]!
166 // The meadow's edge is the fifth of the ground either side of the threshold.
167 return { lo: at(Math.min(1, coverage * 1.35 + 0.01)), hi: at(Math.max(0, coverage * 0.65 - 0.01)) }
168}
169
170/** What the ground at a point says about trees standing on it. */
171export interface Ground {
172 /** Elevation, metres. */
173 h: number
174 /** True where water stands here. */
175 water: boolean
176 /** How much of this ground the desert claims, 0..1. */
177 desert: number
178 /** Bare rock, 0..1: trees do not root on a cliff band or a wash floor. */
179 rock: number
180}
181
182/**
183 * Stems per hectare at a point: the forest's own density, thinned toward its edge, opened
184 * where Tower left a meadow, and stopped by water, rock, sand and the treeline.
185 */
186export function stemsAt(f: CForest, p: CylPoint, z: number, a: number, detailM: number, g: Ground): number {
187 if (g.water) return 0
188 let inside = smoothstep(-f.edgeM, -f.edgeM * 0.15, signedDistance(f.shape, z, a))
189 if (inside <= 0) return 0
190 // Where a smaller forest stands, this one does not.
191 for (const hole of f.holes) {
192 inside *= 1 - smoothstep(-f.edgeM * 0.5, 0, signedDistance(hole, z, a))
193 if (inside <= 0) return 0
194 }
195 // Nor where a settlement stands: the trees thin out over its last fifth and stop.
196 for (const c of f.clearings) {
197 const d = Math.hypot(z - c.z, nearestA(c.a, a) - a)
198 inside *= smoothstep(c.radiusM * 0.8, c.radiusM * 1.15, d)
199 if (inside <= 0) return 0
200 }
201 const open = f.meadowLo === Infinity
202 ? 1
203 : 1 - smoothstep(f.meadowLo, f.meadowHi, meadowNoise(f, p, detailM))
204 // Trees thin out over the last 400 m below the treeline, and stop above it.
205 const height = 1 - smoothstep(f.treelineM - 400, f.treelineM, g.h)
206 const ground = (1 - Math.min(1, g.desert * 1.4)) * (1 - Math.min(1, g.rock * 1.6))
207 return f.densityPerHa * inside * open * height * ground
208}
209
210/** Mean canopy height where that many stems stand, metres: a meadow is no canopy at all. */
211export function canopyAt(f: CForest, stemsPerHa: number): number {
212 if (stemsPerHa <= 0) return 0
213 return f.canopyM * smoothstep(0, f.densityPerHa * 0.35, stemsPerHa)
214}
215
216export interface Tree {
217 z: number
218 a: number
219 heightM: number
220 /** Crown radius, metres. */
221 crownM: number
222 /** Trunk radius at the base, metres. */
223 trunkM: number
224 conifer: boolean
225 giant: boolean
226 /** 0..1, the tree's own number: for turning it, tinting it, and choosing its shape. */
227 rand: number
228}
229
230/** The placement grid's cell size for a forest: about one tree apart at full density. */
231export function cellSizeM(f: CForest): number {
232 return Math.sqrt(HECTARE_M2 / Math.max(1, f.densityPerHa))
233}
234
235/** What a candidate spot is: how thick the wood is there, and how high the ground is. */
236export interface Spot {
237 stems: number
238 h: number
239}
240
241/**
242 * Every tree of `f` whose cell lies in the box, handed to `emit`. `at` answers how thick
243 * the wood is at a point and how high the ground is; it is called once per candidate cell,
244 * so a caller drawing a kilometre of forest should keep it cheap — the view reads both off
245 * a grid it sampled once, rather than working the density out per tree.
246 *
247 * Deterministic in the world's seed and nothing else: two tiles, two views, or two visitors
248 * asking about the same ground get exactly the same trees.
249 */
250export function forEachTree(
251 f: CForest, box: Box,
252 at: (z: number, a: number) => Spot,
253 emit: (tree: Tree) => void,
254 /** Asked before the spot is looked at, so a caller can cut its box down to a circle. */
255 wanted: (z: number, a: number) => boolean = () => true,
256): void {
257 const cell = cellSizeM(f)
258 const i0 = Math.floor(box.z0 / cell), i1 = Math.ceil(box.z1 / cell)
259 const j0 = Math.floor(box.a0 / cell), j1 = Math.ceil(box.a1 / cell)
260 const perCell = (f.densityPerHa * cell * cell) / HECTARE_M2
261 for (let i = i0; i <= i1; i++) {
262 for (let j = j0; j <= j1; j++) {
263 const h = hash3(f.seed, i, j)
264 const rand = mulberry32(h)
265 const z = (i + rand()) * cell
266 const a = (j + rand()) * cell
267 if (z < box.z0 || z > box.z1 || a < box.a0 || a > box.a1) continue
268 if (!wanted(z, a)) continue
269 const spot = at(z, a)
270 // Accept in proportion to how full the forest is here against its fullest.
271 if (rand() > (spot.stems * cell * cell) / HECTARE_M2 / Math.max(1e-6, perCell)) continue
272 emit(treeAt(f, z, a, spot.h, rand()))
273 }
274 }
275}
276
277/**
278 * A clump of trees: what a stand of them is drawn as once single trees are a pixel or two
279 * wide. One of these stands for everything in a cell of `cellM`, so the wood can be drawn
280 * kilometres out for the cost of a card every twenty-odd metres rather than every five.
281 */
282export interface Clump {
283 z: number
284 a: number
285 /** How high the crowns in it reach, metres, and how wide the clump is. */
286 heightM: number
287 widthM: number
288 /** How much of it is conifer, 0..1, and the clump's own number. */
289 conifer: number
290 rand: number
291}
292
293/**
294 * Every clump of `f` in the box. Same idea as `forEachTree` — a fixed grid, hashed per
295 * cell — on a coarser grid, and accepted in proportion to how full the wood is there, so
296 * the meadows stay open at any distance.
297 */
298export function forEachClump(
299 f: CForest, box: Box, cellM: number,
300 at: (z: number, a: number) => Spot,
301 emit: (clump: Clump) => void,
302 wanted: (z: number, a: number) => boolean = () => true,
303): void {
304 const i0 = Math.floor(box.z0 / cellM), i1 = Math.ceil(box.z1 / cellM)
305 const j0 = Math.floor(box.a0 / cellM), j1 = Math.ceil(box.a1 / cellM)
306 for (let i = i0; i <= i1; i++) {
307 for (let j = j0; j <= j1; j++) {
308 const rand = mulberry32(hash3(f.seed ^ 0x5c1a, i, j))
309 const z = (i + 0.25 + rand() * 0.5) * cellM
310 const a = (j + 0.25 + rand() * 0.5) * cellM
311 if (z < box.z0 || z > box.z1 || a < box.a0 || a > box.a1) continue
312 if (!wanted(z, a)) continue
313 const spot = at(z, a)
314 const full = spot.stems / Math.max(1e-6, f.densityPerHa)
315 if (rand() > full) continue
316 // As high as the canopy here, give or take the luck of what grew in this one.
317 const canopy = canopyAt(f, spot.stems)
318 emit({
319 z, a,
320 heightM: canopy * (0.88 + 0.3 * rand()),
321 widthM: cellM * (1.05 + 0.35 * rand()),
322 conifer: f.giants ? 1 : f.conifer,
323 rand: rand(),
324 })
325 }
326 }
327}
328
329/** One tree's dimensions, from its own number and the ground under it. */
330export function treeAt(f: CForest, z: number, a: number, groundM: number, rand: number): Tree {
331 const conifer = !f.giants && rand < f.conifer
332 const kind = f.giants ? TREE.giant : conifer ? TREE.conifer : TREE.broadleaf
333 // Its own size, and smaller with height: the last trees below a treeline are stunted.
334 const size = 0.25 + 0.75 * (1 - (1 - rand) ** 2)
335 const small = 0.55 + 0.45 * (1 - smoothstep(f.treelineM - 900, f.treelineM, groundM))
336 const heightM = (kind.minM + (kind.maxM - kind.minM) * size) * small
337 return {
338 z, a, heightM,
339 crownM: (heightM * kind.crown) / 2,
340 // Trunks: 1/60 of height for a conifer or broadleaf, far stouter for a giant.
341 trunkM: f.giants ? heightM / 22 : heightM / 120,
342 conifer: f.giants ? true : conifer,
343 giant: f.giants,
344 rand,
345 }
346}