diablo2d/js/game/path.js

/* ============================================================
 * Diablo2D — path.js : A* pathfinding + line of sight
 * ============================================================ */
'use strict';
window.D2 = window.D2 || {};
(function (D2) {

  const DIRS = [
    [1, 0, 1], [-1, 0, 1], [0, 1, 1], [0, -1, 1],
    [1, 1, 1.414], [1, -1, 1.414], [-1, 1, 1.414], [-1, -1, 1.414],
  ];

  /**
   * A* over world tiles. walkable(x,y) -> bool.
   * Returns array of {x,y} tile coords (excluding start), or null.
   */
  function find(walkable, w, h, sx, sy, tx, ty, maxNodes = 4000) {
    if (!walkable(tx, ty)) return null;
    if (sx === tx && sy === ty) return [];

    const open = new MinHeap();
    const gScore = new Float32Array(w * h).fill(Infinity);
    const cameFrom = new Int32Array(w * h).fill(-1);
    const closed = new Uint8Array(w * h);
    const idx = (x, y) => y * w + x;

    gScore[idx(sx, sy)] = 0;
    open.push(idx(sx, sy), octile(sx, sy, tx, ty));

    let nodes = 0;
    while (open.size > 0 && nodes < maxNodes) {
      const cur = open.pop();
      const cx = cur % w, cy = (cur / w) | 0;
      if (closed[cur]) continue;
      closed[cur] = 1;
      nodes++;

      if (cx === tx && cy === ty) {
        const path = [];
        let n = cur;
        while (n !== idx(sx, sy) && n >= 0) {
          path.push({ x: n % w, y: (n / w) | 0 });
          n = cameFrom[n];
        }
        path.reverse();
        return path;
      }

      for (const [dx, dy, cost] of DIRS) {
        const nx = cx + dx, ny = cy + dy;
        if (nx < 0 || ny < 0 || nx >= w || ny >= h) continue;
        if (!walkable(nx, ny)) continue;
        // no corner cutting
        if (dx !== 0 && dy !== 0) {
          if (!walkable(cx + dx, cy) || !walkable(cx, cy + dy)) continue;
        }
        const ni = idx(nx, ny);
        if (closed[ni]) continue;
        const tentative = gScore[cur] + cost;
        if (tentative < gScore[ni]) {
          gScore[ni] = tentative;
          cameFrom[ni] = cur;
          open.push(ni, tentative + octile(nx, ny, tx, ty) * 1.02);
        }
      }
    }
    return null;
  }

  function octile(x0, y0, x1, y1) {
    const dx = Math.abs(x1 - x0), dy = Math.abs(y1 - y0);
    return (dx + dy) + (1.414 - 2) * Math.min(dx, dy);
  }

  /** lightweight binary min-heap keyed by f-score */
  class MinHeap {
    constructor() { this.items = []; this.f = []; this.size = 0; }
    push(idx, f) {
      let i = this.size++;
      this.items[i] = idx; this.f[i] = f;
      while (i > 0) {
        const p = (i - 1) >> 1;
        if (this.f[p] <= this.f[i]) break;
        this.swap(p, i); i = p;
      }
    }
    pop() {
      const top = this.items[0];
      this.size--;
      if (this.size > 0) {
        this.items[0] = this.items[this.size];
        this.f[0] = this.f[this.size];
        let i = 0;
        for (;;) {
          const l = 2 * i + 1, r = l + 1;
          let m = i;
          if (l < this.size && this.f[l] < this.f[m]) m = l;
          if (r < this.size && this.f[r] < this.f[m]) m = r;
          if (m === i) break;
          this.swap(m, i); i = m;
        }
      }
      return top;
    }
    swap(a, b) {
      [this.items[a], this.items[b]] = [this.items[b], this.items[a]];
      [this.f[a], this.f[b]] = [this.f[b], this.f[a]];
    }
  }

  /** Bresenham line-of-sight through walkable/transparent tiles */
  function hasLOS(transparent, x0, y0, x1, y1) {
    let dx = Math.abs(x1 - x0), dy = Math.abs(y1 - y0);
    const sx = x0 < x1 ? 1 : -1, sy = y0 < y1 ? 1 : -1;
    let err = dx - dy;
    let x = x0, y = y0;
    for (;;) {
      if (x === x1 && y === y1) return true;
      const e2 = 2 * err;
      if (e2 > -dy) { err -= dy; x += sx; }
      if (e2 < dx) { err += dx; y += sy; }
      if (x === x1 && y === y1) return true;
      if (!transparent(x, y)) return false;
    }
  }

  D2.path = { find, hasLOS, MinHeap };
})(window.D2);