fuzzyworld

tower / files / test / terrain.test.ts

terrain.test.ts

16.7 KB · history · blame

1import { readFileSync } from 'node:fs'
2import { describe, expect, it } from 'vitest'
3import { LENGTH_M, RADIUS_M } from '../src/canon/constants.js'
4import { compileWorld } from '../src/terrain/compile.js'
5import { Stage, prepare } from '../src/terrain/field.js'
6import { nearestA } from '../src/terrain/shapes.js'
7import { buildTile, tileSize } from '../src/terrain/tile.js'
8import { parseWorld, type Mountains, type River } from '../src/world/schema.js'
9
10const world = parseWorld(JSON.parse(readFileSync('content/world.json', 'utf8')))
11const steps: string[] = []
12const t0 = performance.now()
13const cw = compileWorld(world, (s) => steps.push(s))
14const compileMs = performance.now() - t0
15const rt = prepare(cw)
16
17describe('the world compiles', () => {
18 it('ports every v1 feature, plus the ground raised under the rivers', () => {
19 // Twenty-nine ported from v1, plus The Tall Wood, which Tower placed from the seed (D-071),
20 // the two railways (D-086), and the Cap Range's name (D-093), and nine farms (D-095, D-096).
21 expect(world.features).toHaveLength(42)
22 // Eight ranges in two groups: the Girdle with the four massifs on it, and the
23 // three desert ridges, which overlap each other.
24 expect(cw.mountains).toHaveLength(2)
25 expect(cw.mountains.flatMap((g) => g.ids)).toHaveLength(8)
26 expect(cw.basins).toHaveLength(7)
27 expect(cw.rivers).toHaveLength(4)
28 // The Dry Reach, Greatwood, and The Uplands (D-064); the tall wood raises nothing.
29 expect(cw.uplifts).toHaveLength(4)
30 expect(cw.forests.map((f) => f.id)).toEqual(['greatwood', 'the-tall-wood'])
31 })
32
33 it('names every step it takes, in the order it takes them', () => {
34 expect(steps[0]).toBe('Reading the plans')
35 expect(steps).toContain('Raising Snowcrown')
36 expect(steps).toContain('Filling The Deep')
37 expect(steps).toContain('Teaching The Long Water which way is down')
38 // Deserts before mountains before water: the order of the elevation stack.
39 expect(steps.indexOf('Quoting the deserts of Earth in The Dry Reach'))
40 .toBeLessThan(steps.indexOf('Raising Snowcrown'))
41 expect(steps.indexOf('Raising Snowcrown')).toBeLessThan(steps.indexOf('Filling The Deep'))
42 })
43
44 it('is quick enough to run on every edit', () => {
45 // A loose ceiling for CI machines; the status dialog covers anything slower.
46 expect(compileMs).toBeLessThan(15_000)
47 })
48})
49
50describe('determinism', () => {
51 // Compiling is the slow part of this file — a few seconds, mostly erosion — so the
52 // second compile is shared by both checks rather than done once for each.
53 const second = compileWorld(world)
54
55 it('compiles the same world to the same data twice', () => {
56 expect(second.mountains.map((g) => Array.from(g.relief))).toEqual(cw.mountains.map((g) => Array.from(g.relief)))
57 expect(JSON.stringify({ ...second, mountains: [] })).toBe(JSON.stringify({ ...cw, mountains: [] }))
58 })
59
60 it('samples the same point to the same height from a fresh runtime', () => {
61 const again = prepare(second)
62 for (const [theta, z] of [[0.3, 88_000], [0.02, 270_000], [3, 500_000], [-1, 180_000]] as const) {
63 expect(again.sample(theta, z, 1).h).toBe(rt.sample(theta, z, 1).h)
64 }
65 })
66
67 it('has no seam where theta wraps', () => {
68 for (const z of [30_000, 90_000, 180_000, 300_000]) {
69 const a = rt.sample(1e-9, z, 1).h
70 const b = rt.sample(2 * Math.PI - 1e-9, z, 1).h
71 expect(Math.abs(a - b)).toBeLessThan(0.01)
72 }
73 })
74})
75
76describe('mountains', () => {
77 it('groups the ranges that overlap, so they erode as one', () => {
78 const girdle = cw.mountains.find((g) => g.ids.includes('the-girdle'))!
79 for (const id of ['snowcrown', 'the-sisters', 'westwall', 'eastwall']) expect(girdle.ids).toContain(id)
80 expect(girdle.name).toBe('The Girdle')
81 expect(girdle.ring).toBe(true)
82 })
83
84 it('puts every authored summit at exactly its elevation above the datum', () => {
85 for (const f of world.features.filter((x): x is Mountains => x.kind === 'mountains')) {
86 for (const p of f.peaks) {
87 // The whole ground, not the range alone: an elevation is above the datum.
88 const h = prepare({ ...cw, basins: [], rivers: [] }).sample(p.theta, p.z, 1).h
89 expect(Math.abs(h - p.elevationM)).toBeLessThan(1)
90 }
91 }
92 })
93
94 it('makes every authored summit the top of its own ground', () => {
95 const ground = prepare({ ...cw, basins: [], rivers: [] })
96 for (const f of world.features.filter((x): x is Mountains => x.kind === 'mountains')) {
97 for (const p of f.peaks) {
98 let higher = 0
99 for (let k = 0; k < 64; k++) {
100 const t = (k / 64) * 2 * Math.PI
101 const d = 250 + (k % 4) * 80
102 const h = ground.sample(p.theta + (Math.sin(t) * d) / RADIUS_M, p.z + Math.cos(t) * d, 1).h
103 if (h > p.elevationM) higher++
104 }
105 expect(higher).toBe(0)
106 }
107 }
108 })
109
110 it('joins the named summits by ridges that stay high', () => {
111 // Walk from Snowcrown to The Sisters along the highest path the grid allows, and
112 // check the lowest point on it — the pass between them — is still well up the
113 // mountain. They are 29 km apart, so the pass is a real one, not a notch.
114 const g = cw.mountains.find((x) => x.ids.includes('the-girdle'))!
115 // Summits in a group carry their height above the land, so find them by place.
116 const away = (p: { z: number; a: number }, theta: number, z: number) =>
117 Math.hypot(p.z - z, nearestA(p.a, theta * RADIUS_M) - theta * RADIUS_M)
118 const nearest = (theta: number, z: number) => g.summits.reduce((best, p) =>
119 away(p, theta, z) < away(best, theta, z) ? p : best)
120 const snow = nearest(0.3, 88_000)
121 const sisters = nearest(-0.52, 94_000)
122 expect(highestPathMin(g, snow, sisters)).toBeGreaterThan(1000)
123 })
124
125 it('cuts valleys: the range has low ground inside it, not only at its edge', () => {
126 const g = cw.mountains.find((x) => x.ids.includes('the-girdle'))!
127 // Cells well inside the range (within 15 km of the ring's centre line) that are
128 // under a fifth of the crest height are valley floors.
129 const zc = 90_000
130 let inside = 0, low = 0
131 for (let i = 0; i < g.nz; i++) {
132 const z = g.z0 + i * g.cell
133 if (Math.abs(z - zc) > 15_000) continue
134 for (let j = 0; j < g.na; j += 3) {
135 inside++
136 if (g.relief[i * g.na + j]! < 2900 * 0.2) low++
137 }
138 }
139 expect(low / inside).toBeGreaterThan(0.05)
140 })
141})
142
143/** The best-connected path's lowest point between two summits: a bottleneck search. */
144function highestPathMin(
145 g: { z0: number; a0: number; cell: number; nz: number; na: number; relief: Float32Array },
146 from: { z: number; a: number }, to: { z: number; a: number },
147): number {
148 const idx = (p: { z: number; a: number }) =>
149 Math.round((p.z - g.z0) / g.cell) * g.na + ((Math.round((p.a - g.a0) / g.cell) % g.na) + g.na) % g.na
150 const start = idx(from), goal = idx(to)
151 const best = new Float32Array(g.nz * g.na).fill(-1)
152 const queue: [number, number][] = [[g.relief[start]!, start]]
153 best[start] = g.relief[start]!
154 while (queue.length) {
155 queue.sort((x, y) => y[0] - x[0])
156 const [v, c] = queue.shift()!
157 if (c === goal) return v
158 if (v < best[c]!) continue
159 const ci = Math.floor(c / g.na), cj = c % g.na
160 for (const [di, dj] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
161 const ni = ci + di!, nj = (cj + dj! + g.na) % g.na
162 if (ni < 0 || ni >= g.nz) continue
163 const nk = ni * g.na + nj
164 const nv = Math.min(v, g.relief[nk]!)
165 if (nv > best[nk]!) { best[nk] = nv; queue.push([nv, nk]) }
166 }
167 }
168 return -1
169}
170
171describe('water', () => {
172 it('keeps every tarn up in its range, on the shelf the range keeps for it', () => {
173 // Sisters Tarn's ski station is at about 2,100 m (design.md §1.11). Cold Tarn
174 // stands furthest from its summit, on the lowest ground of the four.
175 const level = Object.fromEntries(cw.basins.map((b) => [b.id, b.levelM]))
176 expect(level['sisters-tarn']).toBeGreaterThan(1800)
177 expect(level['sisters-tarn']).toBeLessThan(2500)
178 for (const id of ['hollow-tarn', 'sisters-tarn', 'east-tarn', 'west-tarn']) {
179 expect(level[id]).toBeGreaterThan(600)
180 expect(level[id]).toBeLessThan(4300)
181 }
182 })
183
184 it('puts water on the lakes and seas', () => {
185 expect(rt.sample(0.38, 320_000, 50).water).toBe(120) // The Deep
186 expect(rt.sample(2, 10_000, 50).water).toBe(90) // The Sunward Sea
187 expect(rt.sample(2, 520_000, 50).water).toBe(90) // The Deepward Sea, short of its ice mountains
188 })
189
190 it('never lets a river flow uphill', () => {
191 for (const r of cw.rivers) {
192 for (let i = 1; i < r.level.length; i++) {
193 expect(r.level[i]!).toBeLessThanOrEqual(r.level[i - 1]!)
194 }
195 }
196 })
197
198 it('finds where each river ends', () => {
199 const outlet = Object.fromEntries(cw.rivers.map((r) => [r.id, r.outlet]))
200 expect(outlet['the-long-water']).toBe('the-deep')
201 for (const trib of ['westwall-water', 'sisters-water', 'eastwall-water']) {
202 expect(outlet[trib]).toBe('the-long-water')
203 }
204 })
205
206 it('flows: every river falls by at least a canal-free grade, source to mouth', () => {
207 for (const r of cw.rivers) {
208 const drop = r.level[0]! - r.level.at(-1)!
209 expect(drop / r.line.s.at(-1)!).toBeGreaterThan(0.0015)
210 }
211 })
212
213 it('shapes the floor to the river: never water standing above its own banks', () => {
214 for (const r of cw.rivers) {
215 // Every tenth point, and never the last: it has no next point to be across from.
216 for (let i = 0; i < r.level.length - 1; i += 10) {
217 const z = r.line.pts[2 * i]!, theta = r.line.pts[2 * i + 1]! / RADIUS_M
218 const s = rt.sample(theta, z, 5)
219 // On the centre line the ground is the channel bed, below the water.
220 expect(s.h).toBeLessThan(r.level[i]! + 0.01)
221 // Just past the bank it is above it: cut down to, or built up to, the river.
222 // Across the channel, not along it: the tributaries run around the world.
223 const dz = r.line.pts[2 * i + 2]! - z, da = r.line.pts[2 * i + 3]! - r.line.pts[2 * i + 1]!
224 const len = Math.hypot(dz, da) || 1
225 const off = r.halfWidth[i]! + 30
226 const bank = rt.sample(theta + ((dz / len) * off) / RADIUS_M, z - (da / len) * off, 5)
227 expect(bank.h).toBeGreaterThan(r.level[i]! - 5)
228 }
229 }
230 })
231
232 it('ends each river at the level of what it flows into', () => {
233 const trunk = cw.rivers.find((r) => r.id === 'the-long-water')!
234 expect(trunk.level.at(-1)).toBeCloseTo(120, 6)
235 })
236
237 it('adds tributaries to the flow downstream of where they join', () => {
238 const trunk = cw.rivers.find((r) => r.id === 'the-long-water')!
239 const own = world.features.find((f): f is River => f.id === 'the-long-water')!.flowM3S
240 expect(trunk.flow[0]).toBe(own)
241 // All four rivers' water leaves through The Narrows: 392 m³/s (design.md §1.11).
242 expect(trunk.flow.at(-1)).toBeCloseTo(392, 5)
243 })
244
245 it('cuts a canyon where the river crosses the ridges', () => {
246 // The ridges are at z 176, 190 and 203 km; The Narrows is the only breach in all
247 // three (D-020), and design.md §1.11 puts it at up to 480 m deep.
248 const trunk = cw.rivers.find((r) => r.id === 'the-long-water')!
249 let deepest = 0
250 for (let i = 0; i < trunk.level.length; i++) {
251 const z = trunk.line.pts[2 * i]!
252 if (z < 170_000 || z > 210_000) continue
253 const theta = trunk.line.pts[2 * i + 1]! / RADIUS_M
254 const floor = rt.sample(theta, z, 5).h
255 let rim = -Infinity
256 for (const off of [2000, 3000, 4000, 5000]) {
257 rim = Math.max(rim, rt.sample(theta + off / RADIUS_M, z, 5).h, rt.sample(theta - off / RADIUS_M, z, 5).h)
258 }
259 deepest = Math.max(deepest, rim - floor)
260 }
261 expect(deepest).toBeGreaterThan(300)
262 // Since the Dry Reach grew mesas (D-069), the rim above the lower river is the desert's
263 // rock as often as the ridge's, and the deepest section runs about 780 m.
264 expect(deepest).toBeLessThan(1100)
265 })
266
267 it('puts the Capital at the centre of the world with its edge on the water', () => {
268 // D-070: 19 km across, centred on the axial midpoint, reaching The Deep's shore.
269 const capital = world.features.find((f) => f.id === 'the-capital')!
270 expect(capital.kind).toBe('settlement')
271 if (capital.kind !== 'settlement' || capital.geometry.type !== 'point') throw new Error('shape')
272 expect(capital.geometry.z).toBe(LENGTH_M / 2)
273 const { theta, z } = capital.geometry
274 // Dry at the marker, and wet at the spinward edge: the city has a waterfront.
275 expect(rt.sample(theta, z, 5).water).toBe(-Infinity)
276 expect(rt.sample(theta + capital.radiusM / RADIUS_M, z, 5).water).toBeGreaterThan(0)
277 // And the shore is inside the city rather than a long way outside it: within 2 km.
278 expect(rt.sample(theta + (capital.radiusM - 2000) / RADIUS_M, z, 5).water).toBe(-Infinity)
279 })
280
281 it('keeps the plateaus off the river, so The Narrows is a gap and not a slot', () => {
282 // Tower did not raise rock across a route it had already cut (desert.ts CORRIDOR_M).
283 const trunk = cw.rivers.find((r) => r.id === 'the-long-water')!
284 let deepest = 0
285 for (let i = 0; i < trunk.level.length; i++) {
286 const z = trunk.line.pts[2 * i]!
287 if (z < 165_000 || z > 180_000) continue
288 const theta = trunk.line.pts[2 * i + 1]! / RADIUS_M
289 const floor = rt.sample(theta, z, 5).h
290 for (const off of [2000, 3000, 4000, 5000]) {
291 deepest = Math.max(deepest,
292 rt.sample(theta + off / RADIUS_M, z, 5).h - floor,
293 rt.sample(theta - off / RADIUS_M, z, 5).h - floor)
294 }
295 }
296 expect(deepest).toBeGreaterThan(150)
297 expect(deepest).toBeLessThan(500)
298 })
299
300 it('builds the floor up under a river only a little, now the lowland is raised', () => {
301 // v1's lowland needed embankments of up to 950 m; The Uplands bring that under
302 // 250 m (D-064). Measured against the ground as it is before the rivers shape it.
303 const before = prepare({ ...cw, rivers: [] })
304 for (const r of cw.rivers) {
305 let fill = 0
306 for (let i = 0; i < r.level.length; i++) {
307 const s = before.sample(r.line.pts[2 * i + 1]! / RADIUS_M, r.line.pts[2 * i]!, 60, Stage.Basins)
308 fill = Math.max(fill, r.level[i]! - Math.max(s.h, s.water))
309 }
310 expect(fill).toBeLessThan(250)
311 }
312 })
313})
314
315describe('water as geometry', () => {
316 /** The tile at `level` containing (theta, z). */
317 const tileAt = (level: number, theta: number, z: number) => {
318 const size = tileSize(level)
319 const a = ((theta * RADIUS_M) % (2 * Math.PI * RADIUS_M) + 2 * Math.PI * RADIUS_M) % (2 * Math.PI * RADIUS_M)
320 return { level, i: Math.floor(z / size.along), j: Math.floor(a / size.around) }
321 }
322
323 it('gives a tile over a lake a water surface at the lake\'s level', () => {
324 const t = buildTile(rt, tileAt(2, 0.38, 320_000), 33)
325 expect(t.water).not.toBeNull()
326 expect(t.water!.indices.length).toBeGreaterThan(0)
327 })
328
329 it('draws no water on a tile of dry desert', () => {
330 expect(buildTile(rt, tileAt(3, 2.5, 190_000), 33).water).toBeNull()
331 })
332
333 it('draws a river as a surface only once the tile is fine enough to hold it', () => {
334 const trunk = cw.rivers.find((r) => r.id === 'the-long-water')!
335 const i = Math.floor(trunk.level.length * 0.75)
336 const z = trunk.line.pts[2 * i]!, theta = trunk.line.pts[2 * i + 1]! / RADIUS_M
337 // 60 m across: a level-9 tile has a vertex a metre apart; a level-2 tile, 130 m.
338 expect(buildTile(rt, tileAt(9, theta, z), 65).water).not.toBeNull()
339 expect(buildTile(rt, tileAt(2, theta, z), 65).water).toBeNull()
340 })
341
342 it('starts a river at its lake\'s water, not across the lake floor or short of it', () => {
343 const trunk = cw.rivers.find((r) => r.id === 'the-long-water')!
344 const noRivers = prepare({ ...cw, rivers: [] })
345 const wet = (i: number) => noRivers.sample(trunk.line.pts[2 * i + 1]! / RADIUS_M, trunk.line.pts[2 * i]!, 20, Stage.Basins).waterMesh
346 // Its first point is in the tarn's water; its second is already out of it.
347 expect(wet(0)).toBe(true)
348 expect(wet(1)).toBe(false)
349 const tarn = cw.basins.find((b) => b.id === 'hollow-tarn')!
350 expect(trunk.level[0]).toBeCloseTo(tarn.levelM, 3)
351 })
352
353 it('makes every waterfall a single drop, not a staircase', () => {
354 for (const r of cw.rivers) {
355 for (let k = 1; k < r.fallAt.length; k++) expect(r.fallAt[k]! - r.fallAt[k - 1]!).toBeGreaterThan(1)
356 }
357 expect(cw.falls.some((f) => f.topM - f.bottomM > 300)).toBe(true)
358 })
359})
360
361describe('cost', () => {
362 it('samples fast enough to build a tile in well under a frame budget per worker', () => {
363 const n = 20_000
364 const t = performance.now()
365 for (let i = 0; i < n; i++) rt.sample((i * 0.37) % 6.28, (i * 97) % 540_000, 1)
366 const perSampleMs = (performance.now() - t) / n
367 // A 65 x 65 tile at full detail. The world-generation.md budget is 60 ms.
368 expect(perSampleMs * 67 * 67).toBeLessThan(200)
369 })
370})