basin / files / src / model / flow.ts
flow.ts
| 1 | import type { Heightmap } from './heightmap'; |
| 2 | import { heightAt, isOceanEdge } from './heightmap'; |
| 3 | |
| 4 | export interface Cell { |
| 5 | x: number; |
| 6 | y: number; |
| 7 | } |
| 8 | |
| 9 | export interface FlowResult { |
| 10 | /** 1 where water reaches, row-major. */ |
| 11 | wet: Uint8Array; |
| 12 | /** Wet border cells — where water exits the board. */ |
| 13 | outflow: Cell[]; |
| 14 | /** The springs that produced this flow (order preserved). */ |
| 15 | springs: Cell[]; |
| 16 | } |
| 17 | |
| 18 | // 4-connected (cardinal) neighbours: N, E, S, W. |
| 19 | const NEIGHBORS: ReadonlyArray<readonly [number, number]> = [ |
| 20 | [0, -1], |
| 21 | [1, 0], |
| 22 | [0, 1], |
| 23 | [-1, 0], |
| 24 | ]; |
| 25 | |
| 26 | /** |
| 27 | * Flood from a single spring. Convenience wrapper over {@link simulateFlows}. |
| 28 | */ |
| 29 | export function simulateFlow(hm: Heightmap, sx: number, sy: number): FlowResult { |
| 30 | return simulateFlows(hm, [{ x: sx, y: sy }]); |
| 31 | } |
| 32 | |
| 33 | /** |
| 34 | * Flood from a set of springs and union their wet sets: a cell is wet iff it's |
| 35 | * reachable from *some* spring along a path of strictly decreasing heights. |
| 36 | * Water branches to every lower neighbour, never pools, and stops at interior |
| 37 | * pits or board edges. |
| 38 | * |
| 39 | * A shared visited array is sound for the union: floods only ever move downhill, |
| 40 | * so the first time a cell is wetted its entire strictly-lower descendant set is |
| 41 | * already scheduled — a later spring reaching the same cell adds nothing new. |
| 42 | */ |
| 43 | export function simulateFlows(hm: Heightmap, springs: readonly Cell[]): FlowResult { |
| 44 | const { width, height } = hm; |
| 45 | const wet = new Uint8Array(width * height); |
| 46 | const stack: number[] = []; |
| 47 | |
| 48 | for (const s of springs) { |
| 49 | const i = s.y * width + s.x; |
| 50 | if (!wet[i]) { |
| 51 | wet[i] = 1; |
| 52 | stack.push(s.x, s.y); |
| 53 | } |
| 54 | } |
| 55 | |
| 56 | while (stack.length) { |
| 57 | const y = stack.pop()!; |
| 58 | const x = stack.pop()!; |
| 59 | const h = heightAt(hm, x, y); |
| 60 | for (const [dx, dy] of NEIGHBORS) { |
| 61 | const nx = x + dx; |
| 62 | const ny = y + dy; |
| 63 | if (nx < 0 || ny < 0 || nx >= width || ny >= height) continue; |
| 64 | if (wet[ny * width + nx]) continue; |
| 65 | if (heightAt(hm, nx, ny) < h) { |
| 66 | wet[ny * width + nx] = 1; |
| 67 | stack.push(nx, ny); |
| 68 | } |
| 69 | } |
| 70 | } |
| 71 | |
| 72 | // Water exits only where it reaches an *ocean* edge; wet cells that pool |
| 73 | // against a wall stop there and are not outflow. |
| 74 | const outflow: Cell[] = []; |
| 75 | for (let y = 0; y < height; y++) { |
| 76 | for (let x = 0; x < width; x++) { |
| 77 | if (wet[y * width + x] && isOceanEdge(hm.edges, x, y, width, height)) { |
| 78 | outflow.push({ x, y }); |
| 79 | } |
| 80 | } |
| 81 | } |
| 82 | |
| 83 | return { wet, outflow, springs: springs.map((s) => ({ x: s.x, y: s.y })) }; |
| 84 | } |