/* ========================================================= * REPRTERRA WEB — utils.js * Math, RNG, A* pathfinding, spatial hash. * ========================================================= */ 'use strict'; window.RTS = window.RTS || {}; RTS.util = (function () { const U = {}; // ---------- math ---------- U.clamp = (v, a, b) => v < a ? a : (v > b ? b : v); U.lerp = (a, b, t) => a + (b - a) * t; U.dist2 = (ax, ay, bx, by) => { const dx = ax - bx, dy = ay - by; return dx * dx + dy * dy; }; U.dist = (ax, ay, bx, by) => Math.sqrt(U.dist2(ax, ay, bx, by)); U.angleTo = (ax, ay, bx, by) => Math.atan2(by - ay, bx - ax); U.angleLerp = (a, b, t) => { let d = (b - a) % (Math.PI * 2); if (d > Math.PI) d -= Math.PI * 2; if (d < -Math.PI) d += Math.PI * 2; return a + d * t; }; // Mulberry32 seeded RNG U.makeRng = function (seed) { let s = seed >>> 0; const rng = function () { s |= 0; s = (s + 0x6D2B79F5) | 0; let t = Math.imul(s ^ (s >>> 15), 1 | s); t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; }; rng.range = (a, b) => a + rng() * (b - a); rng.int = (a, b) => Math.floor(rng.range(a, b + 1)); rng.pick = (arr) => arr[Math.floor(rng() * arr.length)]; // save/load support (does not alter the sequence) rng.state = () => s >>> 0; rng.setState = (v) => { s = v >>> 0; }; return rng; }; U.rng = U.makeRng(Date.now() & 0xffffffff); // ---------- grid helpers ---------- U.idx = (x, y, W) => y * W + x; U.inBounds = (x, y, W, H) => x >= 0 && y >= 0 && x < W && y < H; // ---------- spatial hash ---------- U.SpatialHash = function (cellSize, W, H) { this.cs = cellSize; this.cw = Math.ceil(W / cellSize); this.ch = Math.ceil(H / cellSize); this.buckets = new Array(this.cw * this.ch); for (let i = 0; i < this.buckets.length; i++) this.buckets[i] = []; }; U.SpatialHash.prototype.clear = function () { for (let i = 0; i < this.buckets.length; i++) this.buckets[i].length = 0; }; U.SpatialHash.prototype._key = function (x, y) { const cx = U.clamp(Math.floor(x / this.cs), 0, this.cw - 1); const cy = U.clamp(Math.floor(y / this.cs), 0, this.ch - 1); return cy * this.cw + cx; }; U.SpatialHash.prototype.insert = function (e) { this.buckets[this._key(e.x, e.y)].push(e); }; // iterate entities within radius r of (x,y); cb(entity) -> truthy stops U.SpatialHash.prototype.eachNear = function (x, y, r, cb) { const minx = U.clamp(Math.floor((x - r) / this.cs), 0, this.cw - 1); const maxx = U.clamp(Math.floor((x + r) / this.cs), 0, this.cw - 1); const miny = U.clamp(Math.floor((y - r) / this.cs), 0, this.ch - 1); const maxy = U.clamp(Math.floor((y + r) / this.cs), 0, this.ch - 1); const r2 = r * r; for (let cy = miny; cy <= maxy; cy++) { for (let cx = minx; cx <= maxx; cx++) { const b = this.buckets[cy * this.cw + cx]; for (let i = 0; i < b.length; i++) { const e = b[i]; if (U.dist2(x, y, e.x, e.y) <= r2) { if (cb(e)) return true; } } } } return false; }; U.SpatialHash.prototype.nearest = function (x, y, r, filter) { let best = null, bd = Infinity; this.eachNear(x, y, r, (e) => { if (filter && !filter(e)) return false; const d = U.dist2(x, y, e.x, e.y); if (d < bd) { bd = d; best = e; } return false; }); return best; }; // ---------- A* on blocked grid ---------- // blocked: Uint8Array(W*H), 1 = blocked. 8-directional, no corner cutting. U.findPath = function (sx, sy, tx, ty, W, H, blocked, maxNodes) { sx |= 0; sy |= 0; tx |= 0; ty |= 0; if (!U.inBounds(tx, ty, W, H)) return null; if (blocked[U.idx(tx, ty, W)]) { // find nearest free tile to target let found = false; outer: for (let rr = 1; rr <= 3; rr++) { for (let dy = -rr; dy <= rr; dy++) for (let dx = -rr; dx <= rr; dx++) { const nx = tx + dx, ny = ty + dy; if (U.inBounds(nx, ny, W, H) && !blocked[U.idx(nx, ny, W)]) { tx = nx; ty = ny; found = true; break outer; } } } if (!found) return null; } if (sx === tx && sy === ty) return []; maxNodes = maxNodes || 6000; const N = W * H; const gScore = new Float32Array(N).fill(Infinity); const cameFrom = new Int32Array(N).fill(-1); const closed = new Uint8Array(N); const open = []; // binary heap of [f, nodeIdx] const push = (f, n) => { open.push([f, n]); let i = open.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (open[p][0] <= open[i][0]) break; const t = open[p]; open[p] = open[i]; open[i] = t; i = p; } }; const pop = () => { const top = open[0]; const last = open.pop(); if (open.length) { open[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < open.length && open[l][0] < open[m][0]) m = l; if (r < open.length && open[r][0] < open[m][0]) m = r; if (m === i) break; const t = open[m]; open[m] = open[i]; open[i] = t; i = m; } } return top; }; const startI = U.idx(sx, sy, W), goalI = U.idx(tx, ty, W); const h = (x, y) => { const dx = Math.abs(x - tx), dy = Math.abs(y - ty); return (dx + dy) * 0.99 + Math.min(dx, dy) * 0.42; }; gScore[startI] = 0; push(h(sx, sy), startI); let nodes = 0; const DIRS = [[1,0,1],[ -1,0,1],[0,1,1],[0,-1,1],[1,1,1.42],[1,-1,1.42],[-1,1,1.42],[-1,-1,1.42]]; while (open.length && nodes < maxNodes) { const [, cur] = pop(); if (cur === goalI) break; if (closed[cur]) continue; closed[cur] = 1; nodes++; const cx = cur % W, cy = (cur / W) | 0; for (let k = 0; k < 8; k++) { const nx = cx + DIRS[k][0], ny = cy + DIRS[k][1]; if (!U.inBounds(nx, ny, W, H)) continue; const ni = U.idx(nx, ny, W); if (blocked[ni] || closed[ni]) continue; if (k >= 4) { // no corner cutting through blocked tiles if (blocked[U.idx(cx + DIRS[k][0], cy, W)] || blocked[U.idx(cx, cy + DIRS[k][1], W)]) continue; } const ng = gScore[cur] + DIRS[k][2]; if (ng < gScore[ni]) { gScore[ni] = ng; cameFrom[ni] = cur; push(ng + h(nx, ny), ni); } } } if (cameFrom[goalI] === -1 && goalI !== startI) return null; // rebuild const path = []; let c = goalI; while (c !== startI && c !== -1) { path.push({ x: (c % W) + 0.5, y: ((c / W) | 0) + 0.5 }); c = cameFrom[c]; } path.reverse(); return path; }; return U; })();