repterra-web/js/utils.js

/* =========================================================
 * 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;
})();