arcane-tycoon/js/world/path.js

// ============ path.js — BFS pathfinding over path tiles ============
const DIRS = [[1, 0], [0, 1], [-1, 0], [0, -1]];

/**
 * BFS from (sx,sy) to (tx,ty) over walkable path tiles.
 * Returns array of [x,y] steps (excluding start, including target) or null.
 */
export function findPath(map, sx, sy, tx, ty, maxNodes = 6000) {
  if (!map.isWalkable(sx, sy) || !map.isWalkable(tx, ty)) return null;
  if (sx === tx && sy === ty) return [];
  const size = map.size;
  const prev = new Int32Array(size * size).fill(-1);
  const visited = new Uint8Array(size * size);
  const startIdx = sy * size + sx;
  const queue = [startIdx];
  visited[startIdx] = 1;
  let head = 0, nodes = 0;
  const targetIdx = ty * size + tx;
  while (head < queue.length && nodes < maxNodes) {
    const cur = queue[head++];
    nodes++;
    if (cur === targetIdx) break;
    const cx = cur % size, cy = (cur / size) | 0;
    for (const [dx, dy] of DIRS) {
      const nx = cx + dx, ny = cy + dy;
      if (nx < 0 || ny < 0 || nx >= size || ny >= size) continue;
      const ni = ny * size + nx;
      if (visited[ni] || !map.isWalkable(nx, ny)) continue;
      visited[ni] = 1;
      prev[ni] = cur;
      queue.push(ni);
    }
  }
  if (!visited[targetIdx]) return null;
  const out = [];
  let cur = targetIdx;
  while (cur !== startIdx) {
    out.push([cur % size, (cur / size) | 0]);
    cur = prev[cur];
    if (cur < 0) return null;
  }
  out.reverse();
  return out;
}

/** BFS flood to collect all reachable path tiles within radius r of (x,y) */
export function reachableWithin(map, x, y, r, outSet) {
  const size = map.size;
  const seen = outSet || new Set();
  const startIdx = y * size + x;
  if (!map.isWalkable(x, y)) return seen;
  const q = [[x, y, 0]];
  seen.add(startIdx);
  let head = 0;
  while (head < q.length) {
    const [cx, cy, d] = q[head++];
    if (d >= r) continue;
    for (const [dx, dy] of DIRS) {
      const nx = cx + dx, ny = cy + dy;
      if (!map.isWalkable(nx, ny)) continue;
      const ni = ny * size + nx;
      if (seen.has(ni)) continue;
      seen.add(ni);
      q.push([nx, ny, d + 1]);
    }
  }
  return seen;
}

/** Find nearest tile satisfying predicate via expanding ring search on paths */
export function findNearestPathTile(map, x, y, pred, maxR = 30) {
  for (let r = 0; r <= maxR; r++) {
    for (let dy = -r; dy <= r; dy++) {
      for (let dx = -r; dx <= r; dx++) {
        if (Math.max(Math.abs(dx), Math.abs(dy)) !== r) continue;
        const nx = x + dx, ny = y + dy;
        if (map.isWalkable(nx, ny) && pred(nx, ny)) return [nx, ny];
      }
    }
  }
  return null;
}

/** Random reachable path tile within radius (for wandering) */
export function randomNearbyPath(map, rng, x, y, minR = 3, maxR = 12) {
  const r = minR + Math.floor(rng() * (maxR - minR));
  const cands = [];
  for (let dy = -r; dy <= r; dy++) {
    for (let dx = -r; dx <= r; dx++) {
      const nx = Math.round(x + dx), ny = Math.round(y + dy);
      if (Math.abs(dx) + Math.abs(dy) > r || Math.abs(dx) + Math.abs(dy) < minR * 0.6) continue;
      if (map.isWalkable(nx, ny)) cands.push([nx, ny]);
    }
  }
  if (!cands.length) {
    // fallback: any adjacent path
    for (const [dx, dy] of DIRS) {
      const nx = Math.round(x + dx), ny = Math.round(y + dy);
      if (map.isWalkable(nx, ny)) return [nx, ny];
    }
    return null;
  }
  return cands[Math.floor(rng() * cands.length)];
}

/** Snap a world position to the nearest walkable path tile (searching outward) */
export function snapToPath(map, x, y, maxR = 4) {
  const rx = Math.round(x), ry = Math.round(y);
  if (map.isWalkable(rx, ry)) return [rx, ry];
  for (let r = 1; r <= maxR; r++) {
    for (let dy = -r; dy <= r; dy++) {
      for (let dx = -r; dx <= r; dx++) {
        if (Math.max(Math.abs(dx), Math.abs(dy)) !== r) continue;
        if (map.isWalkable(rx + dx, ry + dy)) return [rx + dx, ry + dy];
      }
    }
  }
  return [Math.min(map.size - 1, Math.max(0, rx)), Math.min(map.size - 1, Math.max(0, ry))];
}