/** 猫の経路探索。危険なマス (稼働中コンベア・ボイラー) には重いコストを付け、
 *  「安全な正規ルートが無ければ危険なショートカットを通ってしまう」挙動を作る。 */
import { GRID_H, GRID_W } from './config';
import { idx, inBounds, isHazardousForCat, tx, ty, walkableForCat } from './grid';
import type { Tile, TileKind } from './types';

const SAFE_COST = 10;
const HAZARD_COST = 140;

export interface PathResult {
  /** start を含まず goal を含むタイルindexの列。到達不能なら null。 */
  path: number[] | null;
  /** 経路上に危険マスが含まれていたか (=正規ルートが無かった) */
  usedHazard: boolean;
  goal: number;
}

const NO_PATH: PathResult = { path: null, usedHazard: false, goal: -1 };

/** 最小ヒープ (コスト, タイルindex) */
class Heap {
  private cost: number[] = [];
  private node: number[] = [];

  get size(): number {
    return this.node.length;
  }

  push(c: number, n: number): void {
    this.cost.push(c);
    this.node.push(n);
    let i = this.node.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.cost[p] <= this.cost[i]) break;
      this.swap(p, i);
      i = p;
    }
  }

  pop(): number {
    const top = this.node[0];
    const lastC = this.cost.pop()!;
    const lastN = this.node.pop()!;
    if (this.node.length > 0) {
      this.cost[0] = lastC;
      this.node[0] = lastN;
      let i = 0;
      for (;;) {
        const l = i * 2 + 1;
        const r = l + 1;
        let m = i;
        if (l < this.node.length && this.cost[l] < this.cost[m]) m = l;
        if (r < this.node.length && this.cost[r] < this.cost[m]) m = r;
        if (m === i) break;
        this.swap(m, i);
        i = m;
      }
    }
    return top;
  }

  private swap(a: number, b: number): void {
    [this.cost[a], this.cost[b]] = [this.cost[b], this.cost[a]];
    [this.node[a], this.node[b]] = [this.node[b], this.node[a]];
  }
}

function reconstruct(prev: Int32Array, tiles: Tile[], start: number, goal: number): PathResult {
  const path: number[] = [];
  let cur = goal;
  let usedHazard = false;
  while (cur !== start) {
    path.push(cur);
    if (isHazardousForCat(tiles[cur])) usedHazard = true;
    cur = prev[cur];
    if (cur < 0) return NO_PATH;
  }
  path.reverse();
  return { path, usedHazard, goal };
}

/** goalPredicate を満たす最も「安全に近い」マスへの経路を返す。 */
export function findPath(
  tiles: Tile[],
  start: number,
  isGoal: (t: Tile, index: number) => boolean,
): PathResult {
  if (isGoal(tiles[start], start)) return { path: [], usedHazard: false, goal: start };

  const dist = new Float64Array(GRID_W * GRID_H).fill(Infinity);
  const prev = new Int32Array(GRID_W * GRID_H).fill(-1);
  const done = new Uint8Array(GRID_W * GRID_H);
  const heap = new Heap();

  dist[start] = 0;
  heap.push(0, start);

  while (heap.size > 0) {
    const cur = heap.pop();
    if (done[cur]) continue;
    done[cur] = 1;

    if (isGoal(tiles[cur], cur)) return reconstruct(prev, tiles, start, cur);

    const cx = tx(cur);
    const cy = ty(cur);
    for (let d = 0; d < 4; d++) {
      const nx = cx + (d === 0 ? 1 : d === 2 ? -1 : 0);
      const ny = cy + (d === 1 ? 1 : d === 3 ? -1 : 0);
      if (!inBounds(nx, ny)) continue;
      const n = idx(nx, ny);
      if (done[n]) continue;
      const t = tiles[n];
      // 目的地そのものは通行不可判定を免除する (搬入口の点検などは無いので実質不要だが安全側に)
      if (!walkableForCat(t) && !isGoal(t, n)) continue;
      const step = isHazardousForCat(t) ? HAZARD_COST : SAFE_COST;
      const nd = dist[cur] + step;
      if (nd < dist[n]) {
        dist[n] = nd;
        prev[n] = cur;
        heap.push(nd, n);
      }
    }
  }
  return NO_PATH;
}

export function findPathToKind(tiles: Tile[], start: number, kind: TileKind): PathResult {
  return findPath(tiles, start, (t) => t.kind === kind && t.brokenFor <= 0);
}

export function findPathToIndex(tiles: Tile[], start: number, goal: number): PathResult {
  return findPath(tiles, start, (_t, i) => i === goal);
}

/** 目的地に隣接するマスまでの経路 (目的地そのものには乗らない場合に使う) */
export function findPathAdjacentTo(tiles: Tile[], start: number, goal: number): PathResult {
  const gx = tx(goal);
  const gy = ty(goal);
  return findPath(tiles, start, (t, i) => {
    if (!walkableForCat(t)) return false;
    const dx = Math.abs(tx(i) - gx);
    const dy = Math.abs(ty(i) - gy);
    return dx + dy === 1;
  });
}

/** コンベア自動配線用の最短経路探索 (始点から終点までのインデックス配列を返す) */
export function findConveyorRoute(tiles: Tile[], start: number, goal: number): number[] {
  if (start < 0 || goal < 0 || start === goal) return [];

  const prev = new Int32Array(GRID_W * GRID_H).fill(-1);
  const dist = new Int32Array(GRID_W * GRID_H).fill(1e9);
  const queue: number[] = [start];
  dist[start] = 0;

  let reached = false;
  let qHead = 0;

  while (qHead < queue.length) {
    const cur = queue[qHead++];
    if (cur === goal) {
      reached = true;
      break;
    }

    const cx = tx(cur);
    const cy = ty(cur);

    for (let d = 0; d < 4; d++) {
      const nx = cx + (d === 0 ? 1 : d === 2 ? -1 : 0);
      const ny = cy + (d === 1 ? 1 : d === 3 ? -1 : 0);
      if (!inBounds(nx, ny)) continue;
      const n = idx(nx, ny);
      const t = tiles[n];

      // 始点・終点以外で壁や侵入不可の施設は回避
      if (n !== goal) {
        if (t.kind === 'wall' || t.kind === 'boiler' || t.kind === 'intake' || t.kind === 'output') continue;
        // 他の機械や大型施設も避ける (ただし既存コンベアや床、ストッカー、カゴはOK)
        if (
          t.kind !== 'floor' &&
          t.kind !== 'conveyor' &&
          t.kind !== 'stocker' &&
          t.kind !== 'basket'
        ) {
          continue;
        }
      }

      // 既存コンベアや床を優先するコスト
      const stepCost = t.kind === 'conveyor' ? 1 : t.kind === 'floor' ? 2 : 4;
      const nd = dist[cur] + stepCost;

      if (nd < dist[n]) {
        dist[n] = nd;
        prev[n] = cur;
        queue.push(n);
      }
    }
  }

  if (!reached) return [];

  const path: number[] = [];
  let cur = goal;
  while (cur !== start && cur !== -1) {
    path.push(cur);
    cur = prev[cur];
  }
  path.push(start);
  path.reverse();
  return path;
}
