tower / files / src / terrain / grid.ts
grid.ts
| 1 | /** |
| 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 | */ |
| 14 | import { nearestA } from './shapes.js' |
| 15 | |
| 16 | export 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. */ |
| 26 | export 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. */ |
| 67 | export 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 | |
| 103 | export const DI = [-1, -1, -1, 0, 0, 1, 1, 1] |
| 104 | export 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. */ |
| 107 | export 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). */ |
| 141 | export 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. */ |
| 162 | export 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 | } |