fuzzyworld

tower / files / src / terrain / shapes.ts

shapes.ts

8.4 KB · history · blame

1/**
2 * Shapes on the unrolled surface, for the generators. See world-generation.md §5.3.
3 *
4 * Everything here works in (z, a): z metres along the axis and a = θR metres around
5 * it. The unrolled plane is exact — unrolling a cylinder preserves lengths — so a
6 * distance here is a distance walked on the floor. The only complication is that
7 * `a` wraps every circumference, and every function below handles it the same way:
8 * a shape is stored unwrapped around its own first vertex, and a query point is
9 * moved by whole circumferences to the copy of itself nearest the shape.
10 *
11 * All of this is plain data, so a compiled world can be posted to a worker.
12 */
13import { CIRCUMFERENCE_M, RADIUS_M } from '../canon/constants.js'
14import type { Geometry } from '../world/schema.js'
15
16const C = CIRCUMFERENCE_M
17
18/** Bring `a` to within half a circumference of `ref`. */
19export function nearestA(a: number, ref: number): number {
20 return a - Math.round((a - ref) / C) * C
21}
22
23export interface Box { z0: number; z1: number; a0: number; a1: number }
24
25export type Shape =
26 | { type: 'band'; zFrom: number; zTo: number }
27 /** Flat [z, a, z, a, ...] with `a` unwrapped so no edge jumps the seam. */
28 | { type: 'polygon'; pts: number[]; box: Box }
29
30export interface Line {
31 /** Flat [z, a, ...], unwrapped, dense enough to treat as straight segments. */
32 pts: number[]
33 /** Distance along the line at each point, metres. */
34 s: number[]
35 box: Box
36}
37
38/** Unwrap a list of [theta, z] into flat [z, a] with no jumps across the seam. */
39function unwrap(points: readonly [number, number][]): number[] {
40 const out: number[] = []
41 let prevA = 0
42 points.forEach(([theta, z], i) => {
43 let a = theta * RADIUS_M
44 if (i > 0) a = nearestA(a, prevA)
45 out.push(z, a)
46 prevA = a
47 })
48 return out
49}
50
51function boxOf(pts: readonly number[]): Box {
52 const b = { z0: Infinity, z1: -Infinity, a0: Infinity, a1: -Infinity }
53 for (let i = 0; i < pts.length; i += 2) {
54 b.z0 = Math.min(b.z0, pts[i]!); b.z1 = Math.max(b.z1, pts[i]!)
55 b.a0 = Math.min(b.a0, pts[i + 1]!); b.a1 = Math.max(b.a1, pts[i + 1]!)
56 }
57 return b
58}
59
60export function shapeOf(g: Geometry): Shape | null {
61 if (g.type === 'band') return { type: 'band', zFrom: g.zFrom, zTo: g.zTo }
62 if (g.type === 'polygon') {
63 const pts = unwrap(g.points)
64 return { type: 'polygon', pts, box: boxOf(pts) }
65 }
66 return null
67}
68
69/**
70 * Signed distance to a shape's boundary: positive inside, negative outside, metres.
71 * The generators all key off this, so a lake or a desert can be any outline, not
72 * only the ellipses and rectangles v1 knew.
73 */
74export function signedDistance(shape: Shape, z: number, a: number): number {
75 if (shape.type === 'band') return Math.min(z - shape.zFrom, shape.zTo - z)
76 const { pts, box } = shape
77 const q = nearestA(a, (box.a0 + box.a1) / 2)
78 const n = pts.length / 2
79 let inside = false
80 let best = Infinity
81 for (let i = 0, j = n - 1; i < n; j = i++) {
82 const zi = pts[2 * i]!, ai = pts[2 * i + 1]!
83 const zj = pts[2 * j]!, aj = pts[2 * j + 1]!
84 if ((ai > q) !== (aj > q) && z < ((zj - zi) * (q - ai)) / (aj - ai) + zi) inside = !inside
85 const ez = zj - zi, ea = aj - ai
86 const len2 = ez * ez + ea * ea || 1
87 const t = Math.max(0, Math.min(1, ((z - zi) * ez + (q - ai) * ea) / len2))
88 const d = Math.hypot(z - (zi + ez * t), q - (ai + ea * t))
89 if (d < best) best = d
90 }
91 return inside ? best : -best
92}
93
94/** Rough lower bound on the distance from a box to a shape, for rejecting tiles. */
95export function shapeBox(shape: Shape): Box {
96 if (shape.type === 'band') return { z0: shape.zFrom, z1: shape.zTo, a0: -Infinity, a1: Infinity }
97 return shape.box
98}
99
100/** True if two boxes, each grown by `margin`, overlap anywhere around the circumference. */
101export function boxesOverlap(p: Box, q: Box, margin: number): boolean {
102 if (p.z1 + margin < q.z0 || q.z1 + margin < p.z0) return false
103 if (!Number.isFinite(p.a0) || !Number.isFinite(q.a0)) return true
104 // Try q shifted to the copy nearest p.
105 const shift = nearestA((q.a0 + q.a1) / 2, (p.a0 + p.a1) / 2) - (q.a0 + q.a1) / 2
106 return !(p.a1 + margin < q.a0 + shift || q.a1 + shift + margin < p.a0)
107}
108
109/**
110 * Catmull–Rom through authored waypoints, resampled every `stepM` metres. A river
111 * drawn as eighteen clicks should curve, not zigzag.
112 */
113export function smoothLine(points: readonly [number, number][], stepM: number): Line {
114 const raw = unwrap(points)
115 const n = raw.length / 2
116 const at = (i: number, k: 0 | 1): number => raw[2 * Math.max(0, Math.min(n - 1, i)) + k]!
117 const dense: number[] = []
118 const PER = 24
119 for (let i = 0; i < n - 1; i++) {
120 for (let s = 0; s < PER; s++) {
121 const u = s / PER, u2 = u * u, u3 = u2 * u
122 for (const k of [0, 1] as const) {
123 const p0 = at(i - 1, k), p1 = at(i, k), p2 = at(i + 1, k), p3 = at(i + 2, k)
124 dense.push(0.5 * (2 * p1 + (p2 - p0) * u + (2 * p0 - 5 * p1 + 4 * p2 - p3) * u2
125 + (-p0 + 3 * p1 - 3 * p2 + p3) * u3))
126 }
127 }
128 }
129 dense.push(at(n - 1, 0), at(n - 1, 1))
130
131 // Resample at an even spacing, so distance along the line is simple to reason about.
132 const pts: number[] = [dense[0]!, dense[1]!]
133 const s: number[] = [0]
134 let carried = 0
135 let total = 0
136 for (let i = 2; i < dense.length; i += 2) {
137 const z0 = dense[i - 2]!, a0 = dense[i - 1]!, z1 = dense[i]!, a1 = dense[i + 1]!
138 const seg = Math.hypot(z1 - z0, a1 - a0)
139 let along = stepM - carried
140 while (along <= seg) {
141 const t = along / seg
142 pts.push(z0 + (z1 - z0) * t, a0 + (a1 - a0) * t)
143 s.push(total + along)
144 along += stepM
145 }
146 carried = seg - (along - stepM)
147 total += seg
148 }
149 const lastZ = dense[dense.length - 2]!, lastA = dense[dense.length - 1]!
150 if (Math.hypot(lastZ - pts[pts.length - 2]!, lastA - pts[pts.length - 1]!) > 1) {
151 pts.push(lastZ, lastA)
152 s.push(total)
153 }
154 return { pts, s, box: boxOf(pts) }
155}
156
157/** Nearest point on a line: distance to it, and which segment and how far along. */
158export interface Nearest { d: number; seg: number; t: number }
159
160/**
161 * Distance from (z, a) to a line. Linear in the number of segments, which is why
162 * callers go through a `LineIndex` when they have many samples to take.
163 */
164export function nearestOnSegments(
165 line: Line, z: number, a: number, segs: Iterable<number>, out: Nearest,
166): Nearest {
167 const q = nearestA(a, (line.box.a0 + line.box.a1) / 2)
168 out.d = Infinity
169 for (const i of segs) {
170 const z0 = line.pts[2 * i]!, a0 = line.pts[2 * i + 1]!
171 const ez = line.pts[2 * i + 2]! - z0, ea = line.pts[2 * i + 3]! - a0
172 const len2 = ez * ez + ea * ea || 1
173 const t = Math.max(0, Math.min(1, ((z - z0) * ez + (q - a0) * ea) / len2))
174 const d = Math.hypot(z - (z0 + ez * t), q - (a0 + ea * t))
175 if (d < out.d) { out.d = d; out.seg = i; out.t = t }
176 }
177 return out
178}
179
180/**
181 * A bucket grid over a line's segments, built per thread (it is not plain data and
182 * never needs to travel). Turns thousands of distance tests per sample into a few.
183 */
184export class LineIndex {
185 private cells = new Map<number, number[]>()
186 private readonly cell: number
187 constructor(readonly line: Line, reach: number) {
188 this.cell = Math.max(500, reach)
189 const nSeg = line.pts.length / 2 - 1
190 for (let i = 0; i < nSeg; i++) {
191 const z0 = Math.min(line.pts[2 * i]!, line.pts[2 * i + 2]!) - reach
192 const z1 = Math.max(line.pts[2 * i]!, line.pts[2 * i + 2]!) + reach
193 const a0 = Math.min(line.pts[2 * i + 1]!, line.pts[2 * i + 3]!) - reach
194 const a1 = Math.max(line.pts[2 * i + 1]!, line.pts[2 * i + 3]!) + reach
195 for (let cz = Math.floor(z0 / this.cell); cz <= Math.floor(z1 / this.cell); cz++) {
196 for (let ca = Math.floor(a0 / this.cell); ca <= Math.floor(a1 / this.cell); ca++) {
197 const key = cz * 100_003 + ca
198 let list = this.cells.get(key)
199 if (!list) this.cells.set(key, (list = []))
200 list.push(i)
201 }
202 }
203 }
204 }
205
206 /** Segments that could be within `reach` of the point, or none. */
207 near(z: number, a: number): readonly number[] {
208 const q = nearestA(a, (this.line.box.a0 + this.line.box.a1) / 2)
209 return this.cells.get(Math.floor(z / this.cell) * 100_003 + Math.floor(q / this.cell)) ?? []
210 }
211}
212
213/** Points `from`..`to` of a line, inclusive, with distances measured from the new start. */
214export function sliceLine(line: Line, from: number, to: number): Line {
215 const pts = line.pts.slice(2 * from, 2 * to + 2)
216 const s0 = line.s[from]!
217 const s = line.s.slice(from, to + 1).map((v) => v - s0)
218 return { pts, s, box: boxOf(pts) }
219}