fuzzyworld

tower / files / src / terrain / grid.ts

grid.ts

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

51c39d8b 2026-09-17 Pavel Safronov1/**
2 * Grids on the unrolled surface, and the passes that run over them.
3 *
4 * A generator that has to know what the ground next door is doing — a range eroding to a
5 * drainage network, a desert routing washes and finding its closed basins — works on a
6 * grid of cells rather than on one sample at a time. This is the machinery they share:
7 * the grid itself, a priority flood that finds which cell drains into which, a separable
8 * box blur, bilinear sampling for the tiles that read the result back, and a walk over
9 * the cells near a point.
10 *
11 * A grid rings the world when its feature does (`ring`), so a band's drainage and blur
12 * wrap round theta instead of stopping at a seam.
13 */
14import { nearestA } from './shapes.js'
15
16export interface Grid {
17 z0: number
18 a0: number
19 cell: number
20 nz: number
21 na: number
22 ring: boolean
23}
24
25/** A binary min-heap of cell indices keyed by height, on typed arrays. */
26export class Heap {
27 private keys: Float64Array
28 private ids: Int32Array
29 size = 0
30 constructor(capacity: number) {
31 this.keys = new Float64Array(capacity)
32 this.ids = new Int32Array(capacity)
33 }
34 push(key: number, id: number): void {
35 let i = this.size++
36 while (i > 0) {
37 const parent = (i - 1) >> 1
38 if (this.keys[parent]! <= key) break
39 this.keys[i] = this.keys[parent]!
40 this.ids[i] = this.ids[parent]!
41 i = parent
42 }
43 this.keys[i] = key
44 this.ids[i] = id
45 }
46 pop(): number {
47 const top = this.ids[0]!
48 const key = this.keys[--this.size]!
49 const id = this.ids[this.size]!
50 let i = 0
51 for (;;) {
52 let child = 2 * i + 1
53 if (child >= this.size) break
54 if (child + 1 < this.size && this.keys[child + 1]! < this.keys[child]!) child++
55 if (this.keys[child]! >= key) break
56 this.keys[i] = this.keys[child]!
57 this.ids[i] = this.ids[child]!
58 i = child
59 }
60 this.keys[i] = key
61 this.ids[i] = id
62 return top
63 }
64}
65
66/** Priority flood from the outlets: receivers, and cells in order from the outlets up. */
67export function drainage(grid: Grid, h: Float32Array, outlet: Uint8Array, out: {
68 receiver: Int32Array; stack: Int32Array; reached: Uint8Array; key: Float64Array; heap: Heap
69}): number {
70 const n = grid.nz * grid.na
71 const { receiver, stack, reached, key, heap } = out
72 reached.fill(0)
73 heap.size = 0
74 for (let k = 0; k < n; k++) {
75 if (!outlet[k]) continue
76 reached[k] = 1
77 receiver[k] = -1
78 key[k] = h[k]!
79 heap.push(h[k]!, k)
80 }
81 let top = 0
82 while (heap.size) {
83 const c = heap.pop()
84 stack[top++] = c
85 const ci = Math.floor(c / grid.na), cj = c % grid.na
86 for (let e = 0; e < 8; e++) {
87 const ni = ci + DI[e]!
88 if (ni < 0 || ni >= grid.nz) continue
89 let nj = cj + DJ[e]!
90 if (grid.ring) nj = (nj + grid.na) % grid.na
91 else if (nj < 0 || nj >= grid.na) continue
92 const nk = ni * grid.na + nj
93 if (reached[nk]) continue
94 reached[nk] = 1
95 receiver[nk] = c
96 key[nk] = Math.max(h[nk]!, key[c]!)
97 heap.push(key[nk]!, nk)
98 }
99 }
100 return top
101}
102
103export const DI = [-1, -1, -1, 0, 0, 1, 1, 1]
104export const DJ = [-1, 0, 1, -1, 1, -1, 0, 1]
105
106/** A separable box blur over a grid: three passes, which is near enough a Gaussian. */
107export function blur(grid: Grid, src: Float32Array, radius: number): Float32Array {
108 let a = Float32Array.from(src)
109 let b = new Float32Array(src.length)
110 const { nz, na } = grid
111 const width = 2 * radius + 1
112 for (let pass = 0; pass < 3; pass++) {
113 for (let i = 0; i < nz; i++) {
114 let sum = 0
115 for (let d = -radius; d <= radius; d++) {
116 const j = grid.ring ? ((d % na) + na) % na : Math.min(na - 1, Math.max(0, d))
117 sum += a[i * na + j]!
118 }
119 for (let j = 0; j < na; j++) {
120 b[i * na + j] = sum / width
121 const outJ = grid.ring ? ((j - radius) % na + na) % na : Math.max(0, j - radius)
122 const inJ = grid.ring ? (j + radius + 1) % na : Math.min(na - 1, j + radius + 1)
123 sum += a[i * na + inJ]! - a[i * na + outJ]!
124 }
125 }
126 ;[a, b] = [b, a]
127 for (let j = 0; j < na; j++) {
128 let sum = 0
129 for (let d = -radius; d <= radius; d++) sum += a[Math.min(nz - 1, Math.max(0, d)) * na + j]!
130 for (let i = 0; i < nz; i++) {
131 b[i * na + j] = sum / width
132 sum += a[Math.min(nz - 1, i + radius + 1) * na + j]! - a[Math.max(0, i - radius) * na + j]!
133 }
134 }
135 ;[a, b] = [b, a]
136 }
137 return a
138}
139
140/** Call `fn` for every cell within `radius` of (z, a): its index, the distance, and its own (z, a). */
141export function forCells(
142 grid: Grid, z: number, a: number, radius: number, fn: (k: number, d: number, z: number, a: number) => void,
143): void {
144 const cells = Math.ceil(radius / grid.cell)
145 const ci = Math.round((z - grid.z0) / grid.cell)
146 const aa = grid.ring ? a : nearestA(a, grid.a0 + ((grid.na - 1) * grid.cell) / 2)
147 const cj = Math.round((aa - grid.a0) / grid.cell)
148 for (let i = ci - cells; i <= ci + cells; i++) {
149 if (i < 0 || i >= grid.nz) continue
150 for (let jj = cj - cells; jj <= cj + cells; jj++) {
151 let j = jj
152 if (grid.ring) j = ((jj % grid.na) + grid.na) % grid.na
153 else if (jj < 0 || jj >= grid.na) continue
154 const cz = grid.z0 + i * grid.cell, ca = grid.a0 + jj * grid.cell
155 const d = Math.hypot(cz - z, ca - aa)
156 if (d <= radius) fn(i * grid.na + j, d, cz, ca)
157 }
158 }
159}
160
161/** Bilinear value of a grid at (z, a), zero outside a bounded grid. */
162export function sampleGrid(g: Grid, relief: Float32Array, z: number, a: number): number {
163 const fi = (z - g.z0) / g.cell
164 if (fi < 0 || fi > g.nz - 1) return 0
165 let fj: number
166 if (g.ring) {
167 fj = ((((a - g.a0) / g.cell) % g.na) + g.na) % g.na
168 } else {
169 fj = (nearestA(a, g.a0 + ((g.na - 1) * g.cell) / 2) - g.a0) / g.cell
170 if (fj < 0 || fj > g.na - 1) return 0
171 }
172 const i0 = Math.min(g.nz - 2, Math.floor(fi)), j0 = Math.min(g.ring ? g.na - 1 : g.na - 2, Math.floor(fj))
173 const ti = fi - i0, tj = fj - j0
174 const j1 = g.ring ? (j0 + 1) % g.na : j0 + 1
175 const at = (i: number, j: number): number => relief[i * g.na + j]!
176 const top = at(i0, j0) * (1 - tj) + at(i0, j1) * tj
177 const bot = at(i0 + 1, j0) * (1 - tj) + at(i0 + 1, j1) * tj
178 return top * (1 - ti) + bot * ti
179}