/**
 * pathfind.js — bounded A* over the walkable grid, biased toward roads and
 * fords. See ROADMAP.md WP8.
 *
 * `goto` normally just aims a body straight at its target and lets the local
 * slide-along-the-shore reflex in world.js handle small obstructions. That
 * reflex has no lookahead, so a river between a body and its target left it
 * sliding along the bank forever, never discovering a ford twenty metres
 * away. This module is the lookahead: called only when the direct approach
 * gets stuck, it searches a bounded window around the start/goal pair for a
 * walkable route and hands back a short list of waypoints. The mind-side
 * contract is unchanged — `goto` just arrives more often.
 *
 * Pure and dependency-free: reads the world through its existing accessors
 * (`_walkable`, `materialAt`, `terrain.riverMask`) and returns plain data. No
 * new sim state, nothing that needs saving — a route is a cache, recomputed
 * whenever it's missing (see world.js `_stepIntent`).
 */
'use strict';

// The search window is the bounding box of (start, goal) padded by MARGIN,
// clamped to MAX_SPAN per axis. Bounding the window is what keeps this a
// bounded lookahead rather than an accidental whole-map flood fill — and it's
// the shape that survives WP1's move to chunked/infinite terrain unchanged
// (a local window, not a global scan).
const MARGIN = 20;
const MAX_SPAN = 128;

// Cheaper to walk than open ground — the route prefers roads and fords
// without being forced onto them (an off-road target still finds a route).
// A ford is the only sand inside a river channel, so favouring sand mildly
// steers crossings toward the shallows without gluing routes to beaches.
const PATH_COST = 0.55;
const SAND_COST = 0.8;

const DIRS = [
  [1, 0, 1], [-1, 0, 1], [0, 1, 1], [0, -1, 1],
  [1, 1, Math.SQRT2], [1, -1, Math.SQRT2], [-1, 1, Math.SQRT2], [-1, -1, Math.SQRT2],
];

/** Small binary min-heap keyed by priority — A*'s open set. */
class MinHeap {
  constructor() { this._a = []; }
  size() { return this._a.length; }
  push(item, priority) {
    const a = this._a;
    a.push([priority, item]);
    let i = a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (a[parent][0] <= a[i][0]) break;
      [a[parent], a[i]] = [a[i], a[parent]];
      i = parent;
    }
  }
  pop() {
    const a = this._a;
    const top = a[0];
    const last = a.pop();
    if (a.length) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const l = i * 2 + 1, r = i * 2 + 2;
        let smallest = i;
        if (l < a.length && a[l][0] < a[smallest][0]) smallest = l;
        if (r < a.length && a[r][0] < a[smallest][0]) smallest = r;
        if (smallest === i) break;
        [a[smallest], a[i]] = [a[i], a[smallest]];
        i = smallest;
      }
    }
    return top[1];
  }
}

/**
 * Find a walkable route from (sx,sz) to (gx,gz), or null if none exists
 * within the search window. Deterministic: same world + same endpoints
 * always yields the same waypoints (the heap breaks ties by insertion order
 * via strict `<` comparisons, and the grid/cost functions are pure reads of
 * world state).
 *
 * @param {object} world  a World instance — reads _walkable and materialAt.
 *                        Never mutated.
 * @param {number} sx,sz  start position (continuous world coords)
 * @param {number} gx,gz  goal position (continuous world coords)
 * @returns {{x:number,z:number}[]|null} waypoints from start to goal
 *          (excluding the start; the final entry is the exact goal, not a
 *          rounded cell), or null if the goal is unreachable or the span is
 *          too large for a bounded search.
 */
function findPath(world, sx, sz, gx, gz) {
  // Infinite world: cells are just rounded coordinates, no edges to clamp to.
  const sX = Math.round(sx), sZ = Math.round(sz), gX = Math.round(gx), gZ = Math.round(gz);

  if (sX === gX && sZ === gZ) return [{ x: gx, z: gz }];
  if (!world._walkable(gX, gZ)) return null; // an unreachable goal stays unreachable — no point searching

  const bboxMinX = Math.min(sX, gX), bboxMaxX = Math.max(sX, gX);
  const bboxMinZ = Math.min(sZ, gZ), bboxMaxZ = Math.max(sZ, gZ);
  if (bboxMaxX - bboxMinX > MAX_SPAN || bboxMaxZ - bboxMinZ > MAX_SPAN) return null; // too far for a bounded lookahead

  const minX = bboxMinX - MARGIN;
  const maxX = bboxMaxX + MARGIN;
  const minZ = bboxMinZ - MARGIN;
  const maxZ = bboxMaxZ + MARGIN;
  const h = maxZ - minZ + 1;
  const N = (maxX - minX + 1) * h;

  const localKey = (x, z) => (x - minX) * h + (z - minZ);
  const heuristic = (x, z) => Math.hypot(x - gX, z - gZ);

  // Walkability is memoised per cell (each is queried from several
  // neighbours) — _walkable does a handful of array reads, not free at
  // window scale.
  const walk = new Uint8Array(N); // 0 unknown, 1 walkable, 2 blocked
  const isWalkable = (x, z) => {
    const k = localKey(x, z);
    if (walk[k] === 0) walk[k] = world._walkable(x, z) ? 1 : 2;
    return walk[k] === 1;
  };

  const cellCost = (x, z) => {
    const m = world.materialAt(x, z);
    if (m && m.name === 'path') return PATH_COST;
    if (m && m.name === 'sand') return SAND_COST; // fords are channel sand — see header
    return 1;
  };

  const gScore = new Float32Array(N).fill(Infinity);
  const cameFrom = new Int32Array(N).fill(-1);
  const closed = new Uint8Array(N);

  const startKey = localKey(sX, sZ);
  const goalKey = localKey(gX, gZ);
  gScore[startKey] = 0;
  const open = new MinHeap();
  open.push(startKey, heuristic(sX, sZ));

  let found = false;
  let steps = 0;
  while (open.size() && steps < N) {
    steps++;
    const curKey = open.pop();
    if (closed[curKey]) continue;
    closed[curKey] = 1;
    if (curKey === goalKey) { found = true; break; }

    const cx = minX + Math.floor(curKey / h);
    const cz = minZ + (curKey % h);
    for (const [dx, dz, stepDist] of DIRS) {
      const nx = cx + dx, nz = cz + dz;
      if (nx < minX || nx > maxX || nz < minZ || nz > maxZ) continue;
      if (!isWalkable(nx, nz)) continue;
      // Don't let a diagonal step cut through a blocked corner — a being
      // can't squeeze between two solid orthogonal cells.
      if (dx !== 0 && dz !== 0 && !isWalkable(cx + dx, cz) && !isWalkable(cx, cz + dz)) continue;
      const nKey = localKey(nx, nz);
      if (closed[nKey]) continue;
      const tentative = gScore[curKey] + stepDist * cellCost(nx, nz);
      if (tentative < gScore[nKey]) {
        gScore[nKey] = tentative;
        cameFrom[nKey] = curKey;
        open.push(nKey, tentative + heuristic(nx, nz));
      }
    }
  }
  if (!found) return null;

  // Reconstruct the cell path, start to goal.
  const cells = [];
  for (let k = goalKey; k !== -1; k = cameFrom[k]) {
    cells.push({ x: minX + Math.floor(k / h), z: minZ + (k % h) });
  }
  cells.reverse();

  // Compress straight runs into single waypoints — the standing-intent
  // stepper already turns and walks smoothly between them; we don't need a
  // waypoint for every cell, just for every direction change.
  if (cells.length === 1) return [{ x: gx, z: gz }];
  const simplified = [cells[0]];
  let prevDx = cells[1].x - cells[0].x, prevDz = cells[1].z - cells[0].z;
  for (let i = 1; i < cells.length - 1; i++) {
    const dx = cells[i + 1].x - cells[i].x, dz = cells[i + 1].z - cells[i].z;
    if (dx !== prevDx || dz !== prevDz) {
      simplified.push(cells[i]);
      prevDx = dx; prevDz = dz;
    }
  }
  simplified.push(cells[cells.length - 1]);

  const waypoints = simplified.slice(1).map((c) => ({ x: c.x, z: c.z }));
  waypoints[waypoints.length - 1] = { x: gx, z: gz }; // exact target, not the rounded cell
  return waypoints;
}

module.exports = { findPath };
