import {
  Application,
  Container,
  Graphics,
  Sprite,
  Text,
  TextStyle,
  Texture,
} from "pixi.js";
import UPNG from "upng-js";

const stockMaps: Record<string, string> = import.meta.glob("./maps/map*.png", {
  eager: true,
  import: "default",
  query: "?url",
}) as Record<string, string>;

const TILE_SIZE = 32;
const MAP_OFFSET_X = 16;
const MAP_OFFSET_Y = 16;

const PATH_LINE_W = 2;
const PATH_HEAD_SIZE = 8;

const PATH_COLOR = 0x00ffff;
const START_COLOR = 0xffff00;
const GOAL_COLOR = 0xff8800;
const MARKER_R = 8;

const enum Tile {
  Ground = 0,
  Wall = 1,
}

interface World {
  cols: number;
  rows: number;
  tiles: Uint8Array;
}

const TILE_COLORS: { tile: Tile; r: number; g: number; b: number }[] = [
  { tile: Tile.Ground, r: 0, g: 0, b: 0 },
  { tile: Tile.Wall, r: 255, g: 255, b: 255 },
];

function tileToRgb(tile: Tile): { r: number; g: number; b: number } {
  for (const entry of TILE_COLORS) {
    if (entry.tile === tile) return entry;
  }
  return TILE_COLORS[0];
}

function rgbToTile(r: number, g: number, b: number): Tile {
  let best = TILE_COLORS[0];
  let bestDist = Infinity;
  for (const entry of TILE_COLORS) {
    const d = (r - entry.r) ** 2 + (g - entry.g) ** 2 + (b - entry.b) ** 2;
    if (d < bestDist) {
      bestDist = d;
      best = entry;
    }
  }
  return best.tile;
}

type Coord = { col: number; row: number };
type Path = Coord[];

interface SearchResult {
  path: Path | null;
  visited: Int32Array; // expansion order per tile (-1 = not visited)
  maxOrder: number;
  gScore: Float32Array;
  cameFrom: Int32Array;
}

function makeWorld(cols: number, rows: number): World {
  return { cols, rows, tiles: new Uint8Array(cols * rows) };
}

function getTile(world: World, col: number, row: number): Tile {
  return world.tiles[row * world.cols + col] as Tile;
}

function tileCenter(col: number, row: number): { x: number; y: number } {
  return {
    x: MAP_OFFSET_X + col * TILE_SIZE + TILE_SIZE / 2,
    y: MAP_OFFSET_Y + row * TILE_SIZE + TILE_SIZE / 2,
  };
}

function coordToIndex(world: World, col: number, row: number): number {
  return row * world.cols + col;
}

function inBounds(world: World, col: number, row: number): boolean {
  return col >= 0 && col < world.cols && row >= 0 && row < world.rows;
}

interface HeapNode {
  index: number;
  score: number;
}

class MinHeap {
  private data: HeapNode[] = [];

  push(node: HeapNode): void {
    this.data.push(node);
    this.bubbleUp(this.data.length - 1);
  }

  pop(): HeapNode | undefined {
    if (this.data.length === 0) return undefined;
    const top = this.data[0];
    const last = this.data.pop()!;
    if (this.data.length > 0) {
      this.data[0] = last;
      this.sinkDown(0);
    }
    return top;
  }

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

  private bubbleUp(i: number): void {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.data[parent].score <= this.data[i].score) break;
      [this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
      i = parent;
    }
  }

  private sinkDown(i: number): void {
    const n = this.data.length;
    while (true) {
      let smallest = i;
      const l = 2 * i + 1;
      const r = 2 * i + 2;
      if (l < n && this.data[l].score < this.data[smallest].score) smallest = l;
      if (r < n && this.data[r].score < this.data[smallest].score) smallest = r;
      if (smallest === i) break;
      [this.data[smallest], this.data[i]] = [this.data[i], this.data[smallest]];
      i = smallest;
    }
  }
}

const NEIGHBORS = [
  { dc: 0, dr: -1 },
  { dc: 0, dr: 1 },
  { dc: -1, dr: 0 },
  { dc: 1, dr: 0 },
];

function findPathAStar(world: World, start: Coord, goal: Coord): SearchResult {
  const visited = new Int32Array(world.cols * world.rows).fill(-1);
  let order = 0;

  const n = world.cols * world.rows;
  const emptyG = new Float32Array(n).fill(Infinity);
  const emptyCF = new Int32Array(n).fill(-1);

  if (getTile(world, start.col, start.row) === Tile.Wall)
    return {
      path: null,
      visited,
      maxOrder: 0,
      gScore: emptyG,
      cameFrom: emptyCF,
    };
  if (getTile(world, goal.col, goal.row) === Tile.Wall)
    return {
      path: null,
      visited,
      maxOrder: 0,
      gScore: emptyG,
      cameFrom: emptyCF,
    };

  const startIdx = coordToIndex(world, start.col, start.row);
  const goalIdx = coordToIndex(world, goal.col, goal.row);

  const gScore = new Float32Array(n).fill(Infinity);
  const cameFrom = new Int32Array(n).fill(-1);
  gScore[startIdx] = 0;

  const open = new MinHeap();
  const heuristic = (col: number, row: number) =>
    Math.abs(col - goal.col) + Math.abs(row - goal.row);

  open.push({ index: startIdx, score: heuristic(start.col, start.row) });
  const inOpen = new Uint8Array(n);
  inOpen[startIdx] = 1;

  while (open.size > 0) {
    const { index: current } = open.pop()!;
    inOpen[current] = 0;

    visited[current] = order++;

    if (current === goalIdx) {
      const path: Path = [];
      let idx = goalIdx;
      while (idx !== -1) {
        path.push({ col: idx % world.cols, row: Math.floor(idx / world.cols) });
        idx = cameFrom[idx];
      }
      return {
        path: path.reverse(),
        visited,
        maxOrder: order - 1,
        gScore,
        cameFrom,
      };
    }

    const col = current % world.cols;
    const row = Math.floor(current / world.cols);

    for (const { dc, dr } of NEIGHBORS) {
      const nc = col + dc;
      const nr = row + dr;
      if (!inBounds(world, nc, nr)) continue;
      if (getTile(world, nc, nr) === Tile.Wall) continue;

      const neighborIdx = coordToIndex(world, nc, nr);
      const tentativeG = gScore[current] + 1;

      if (tentativeG < gScore[neighborIdx]) {
        cameFrom[neighborIdx] = current;
        gScore[neighborIdx] = tentativeG;
        if (!inOpen[neighborIdx]) {
          open.push({
            index: neighborIdx,
            score: tentativeG + heuristic(nc, nr),
          });
          inOpen[neighborIdx] = 1;
        }
      }
    }
  }

  return { path: null, visited, maxOrder: order - 1, gScore, cameFrom };
}

function lineOfSight(world: World, a: Coord, b: Coord): boolean {
  const x0 = a.col + 0.5;
  const y0 = a.row + 0.5;
  const x1 = b.col + 0.5;
  const y1 = b.row + 0.5;
  const dx = x1 - x0;
  const dy = y1 - y0;
  const stepX = dx > 0 ? 1 : -1;
  const stepY = dy > 0 ? 1 : -1;
  const tDeltaX = dx !== 0 ? Math.abs(1 / dx) : Infinity;
  const tDeltaY = dy !== 0 ? Math.abs(1 / dy) : Infinity;
  let tMaxX =
    dx !== 0
      ? Math.abs((Math.floor(x0) + (dx > 0 ? 1 : 0) - x0) / dx)
      : Infinity;
  let tMaxY =
    dy !== 0
      ? Math.abs((Math.floor(y0) + (dy > 0 ? 1 : 0) - y0) / dy)
      : Infinity;
  let col = Math.floor(x0);
  let row = Math.floor(y0);
  const endCol = Math.floor(x1);
  const endRow = Math.floor(y1);

  while (true) {
    if (getTile(world, col, row) === Tile.Wall) return false;
    if (col === endCol && row === endRow) break;
    if (tMaxX < tMaxY) {
      tMaxX += tDeltaX;
      col += stepX;
    } else if (tMaxY < tMaxX) {
      tMaxY += tDeltaY;
      row += stepY;
    } else {
      tMaxX += tDeltaX;
      tMaxY += tDeltaY;
      if (
        getTile(world, col + stepX, row) === Tile.Wall ||
        getTile(world, col, row + stepY) === Tile.Wall
      )
        return false;
      col += stepX;
      row += stepY;
    }
  }
  return true;
}

function findPathTheta(world: World, start: Coord, goal: Coord): SearchResult {
  const visited = new Int32Array(world.cols * world.rows).fill(-1);
  let order = 0;

  const n = world.cols * world.rows;
  const emptyG = new Float32Array(n).fill(Infinity);
  const emptyCF = new Int32Array(n).fill(-1);

  if (getTile(world, start.col, start.row) === Tile.Wall)
    return {
      path: null,
      visited,
      maxOrder: 0,
      gScore: emptyG,
      cameFrom: emptyCF,
    };
  if (getTile(world, goal.col, goal.row) === Tile.Wall)
    return {
      path: null,
      visited,
      maxOrder: 0,
      gScore: emptyG,
      cameFrom: emptyCF,
    };

  const startIdx = coordToIndex(world, start.col, start.row);
  const goalIdx = coordToIndex(world, goal.col, goal.row);

  const gScore = new Float32Array(n).fill(Infinity);
  const cameFrom = new Int32Array(n).fill(-1);
  gScore[startIdx] = 0;

  const open = new MinHeap();
  const heuristic = (col: number, row: number) => {
    const dc = col - goal.col;
    const dr = row - goal.row;
    return Math.sqrt(dc * dc + dr * dr);
  };

  open.push({ index: startIdx, score: heuristic(start.col, start.row) });
  const closed = new Uint8Array(n);

  while (open.size > 0) {
    const { index: current } = open.pop()!;
    if (closed[current]) continue;
    closed[current] = 1;

    visited[current] = order++;

    if (current === goalIdx) {
      const path: Path = [];
      let idx = goalIdx;
      while (idx !== -1) {
        path.push({ col: idx % world.cols, row: Math.floor(idx / world.cols) });
        idx = cameFrom[idx];
      }
      return {
        path: path.reverse(),
        visited,
        maxOrder: order - 1,
        gScore,
        cameFrom,
      };
    }

    const col = current % world.cols;
    const row = Math.floor(current / world.cols);
    const parentIdx = cameFrom[current];

    for (const { dc, dr } of NEIGHBORS) {
      const nc = col + dc;
      const nr = row + dr;
      if (!inBounds(world, nc, nr)) continue;
      if (getTile(world, nc, nr) === Tile.Wall) continue;

      const neighborIdx = coordToIndex(world, nc, nr);
      if (closed[neighborIdx]) continue;

      let tentativeG: number;
      let newParent: number;
      if (parentIdx !== -1) {
        const pCol = parentIdx % world.cols;
        const pRow = Math.floor(parentIdx / world.cols);
        if (
          lineOfSight(world, { col: pCol, row: pRow }, { col: nc, row: nr })
        ) {
          const dpc = nc - pCol;
          const dpr = nr - pRow;
          tentativeG = gScore[parentIdx] + Math.sqrt(dpc * dpc + dpr * dpr);
          newParent = parentIdx;
        } else {
          tentativeG = gScore[current] + Math.sqrt(dc * dc + dr * dr);
          newParent = current;
        }
      } else {
        tentativeG = gScore[current] + Math.sqrt(dc * dc + dr * dr);
        newParent = current;
      }

      if (tentativeG < gScore[neighborIdx]) {
        cameFrom[neighborIdx] = newParent;
        gScore[neighborIdx] = tentativeG;
        open.push({
          index: neighborIdx,
          score: tentativeG + heuristic(nc, nr),
        });
      }
    }
  }

  return { path: null, visited, maxOrder: order - 1, gScore, cameFrom };
}

function pathLength(path: Path): number {
  let len = 0;
  for (let i = 1; i < path.length; i++) {
    const dc = path[i].col - path[i - 1].col;
    const dr = path[i].row - path[i - 1].row;
    len += Math.sqrt(dc * dc + dr * dr);
  }
  return len;
}

function drawPath(g: Graphics, path: Path, color: number): void {
  if (path.length < 2) return;

  const first = tileCenter(path[0].col, path[0].row);
  g.moveTo(first.x, first.y);
  for (let i = 1; i < path.length; i++) {
    const { x, y } = tileCenter(path[i].col, path[i].row);
    g.lineTo(x, y);
  }
  g.stroke({ color, width: PATH_LINE_W });

  const last = tileCenter(path[path.length - 1].col, path[path.length - 1].row);
  const prev = tileCenter(path[path.length - 2].col, path[path.length - 2].row);
  const dx = last.x - prev.x;
  const dy = last.y - prev.y;
  const dist = Math.sqrt(dx * dx + dy * dy);
  const ux = dx / dist;
  const uy = dy / dist;
  const px = -uy * (PATH_HEAD_SIZE * 0.5);
  const py = ux * (PATH_HEAD_SIZE * 0.5);
  const base = {
    x: last.x - ux * PATH_HEAD_SIZE,
    y: last.y - uy * PATH_HEAD_SIZE,
  };
  g.moveTo(last.x, last.y);
  g.lineTo(base.x + px, base.y + py);
  g.lineTo(base.x - px, base.y - py);
  g.fill(color);
}

function worldToIndexedPng(world: World): ArrayBuffer {
  const rgba = new Uint8Array(world.cols * world.rows * 4);
  for (let i = 0; i < world.tiles.length; i++) {
    const { r, g, b } = tileToRgb(world.tiles[i] as Tile);
    rgba[i * 4 + 0] = r;
    rgba[i * 4 + 1] = g;
    rgba[i * 4 + 2] = b;
    rgba[i * 4 + 3] = 255;
  }
  return UPNG.encode([rgba.buffer], world.cols, world.rows, 0, []);
}

function worldFromIndexedPng(buffer: ArrayBuffer): World | null {
  try {
    const img = UPNG.decode(buffer);
    const rgba = new Uint8Array(UPNG.toRGBA8(img)[0]);
    const world = makeWorld(img.width, img.height);
    const area = img.width * img.height;
    for (let i = 0; i < area; i++) {
      world.tiles[i] = rgbToTile(rgba[i * 4], rgba[i * 4 + 1], rgba[i * 4 + 2]);
    }
    return world;
  } catch {
    return null;
  }
}

type Algorithm = "astar" | "theta";

const ALGORITHM_META: Record<Algorithm, { label: string }> = {
  astar: { label: "A*" },
  theta: { label: "Theta*" },
};

function mountControls(
  getWorld: () => World,
  statusLabel: Text,
  onLoad: (loaded: World) => void,
  getAlgorithm: () => Algorithm,
  setAlgorithm: (a: Algorithm) => void,
): void {
  const wrap = document.createElement("div");
  wrap.style.cssText =
    "position:fixed;top:16px;right:16px;display:flex;flex-direction:column;gap:8px;";

  const btnStyle =
    "padding:6px 12px;background:#333;color:#ccc;border:1px solid #666;cursor:pointer;font-family:monospace;font-size:13px;";

  const select = document.createElement("select");
  select.style.cssText = btnStyle;
  for (const [key, meta] of Object.entries(ALGORITHM_META)) {
    const opt = document.createElement("option");
    opt.value = key;
    opt.textContent = meta.label;
    if (key === getAlgorithm()) opt.selected = true;
    select.appendChild(opt);
  }
  select.addEventListener("change", () =>
    setAlgorithm(select.value as Algorithm),
  );
  wrap.appendChild(select);

  const sep1 = document.createElement("hr");
  sep1.style.cssText = "border:none;border-top:1px solid #666;margin:4px 0;";
  wrap.appendChild(sep1);

  const dlBtn = document.createElement("button");
  dlBtn.textContent = "Download PNG";
  dlBtn.style.cssText = btnStyle;
  dlBtn.addEventListener("click", () => {
    const buf = worldToIndexedPng(getWorld());
    const blob = new Blob([buf], { type: "image/png" });
    const url = URL.createObjectURL(blob);
    const a = document.createElement("a");
    a.href = url;
    a.download = "world.png";
    a.click();
    URL.revokeObjectURL(url);
  });

  const applyWorld = (buf: ArrayBuffer, label: string) => {
    const loaded = worldFromIndexedPng(buf);
    if (!loaded) {
      statusLabel.text = `${label} failed: not a valid indexed PNG`;
      return;
    }
    onLoad(loaded);
  };

  const rtBtn = document.createElement("button");
  rtBtn.textContent = "Round-trip";
  rtBtn.style.cssText = btnStyle;
  rtBtn.addEventListener("click", () =>
    applyWorld(worldToIndexedPng(getWorld()), "Round-trip"),
  );

  const fileInput = document.createElement("input");
  fileInput.type = "file";
  fileInput.accept = ".png,image/png";
  fileInput.style.display = "none";
  fileInput.addEventListener("change", () => {
    const file = fileInput.files?.[0];
    if (!file) return;
    file.arrayBuffer().then((buf) => applyWorld(buf, "Upload"));
    fileInput.value = "";
  });

  const ulBtn = document.createElement("button");
  ulBtn.textContent = "Upload PNG";
  ulBtn.style.cssText = btnStyle;
  ulBtn.addEventListener("click", () => fileInput.click());

  wrap.appendChild(dlBtn);
  wrap.appendChild(rtBtn);
  wrap.appendChild(ulBtn);
  wrap.appendChild(fileInput);

  const mapEntries = Object.entries(stockMaps)
    .map(([path, url]) => {
      const name = path.replace(/^.*\//, "").replace(/\.png$/, "");
      return { name, url };
    })
    .sort((a, b) => a.name.localeCompare(b.name));

  if (mapEntries.length > 0) {
    const sep = document.createElement("hr");
    sep.style.cssText = "border:none;border-top:1px solid #666;margin:4px 0;";
    wrap.appendChild(sep);

    const loadMap = (url: string, label: string) =>
      fetch(url)
        .then((r) => r.arrayBuffer())
        .then((buf) => applyWorld(buf, label));

    for (const { name, url } of mapEntries) {
      const btn = document.createElement("button");
      btn.textContent = name;
      btn.style.cssText = btnStyle;
      btn.addEventListener("click", () => loadMap(url, name));
      wrap.appendChild(btn);
    }

    const hash = location.hash.replace(/^#/, "");
    const match = mapEntries.find((e) => e.name === hash);
    if (match) loadMap(match.url, match.name);
  }

  const linkSep = document.createElement("hr");
  linkSep.style.cssText = "border:none;border-top:1px solid #666;margin:4px 0;";
  wrap.appendChild(linkSep);

  const linkStyle =
    "padding:4px 12px;color:#88aacc;font-family:monospace;font-size:13px;text-decoration:none;display:block;";

  const homeLink = document.createElement("a");
  homeLink.href = "/";
  homeLink.textContent = "← All demos";
  homeLink.style.cssText = linkStyle;
  wrap.appendChild(homeLink);

  const codeLink = document.createElement("a");
  codeLink.href = "scratch_pathfinding2_source.html";
  codeLink.textContent = "View source";
  codeLink.style.cssText = linkStyle;
  wrap.appendChild(codeLink);

  document.body.appendChild(wrap);
}

function pixelToTile(world: World, px: number, py: number): Coord | null {
  const col = Math.floor((px - MAP_OFFSET_X) / TILE_SIZE);
  const row = Math.floor((py - MAP_OFFSET_Y) / TILE_SIZE);
  if (!inBounds(world, col, row)) return null;
  return { col, row };
}

async function setup() {
  const app = new Application();
  await app.init({ background: "#111111", resizeTo: window, antialias: true });
  document.getElementById("pixi-container")!.appendChild(app.canvas);
  return app;
}

function makeTileTextures(app: Application): Record<Tile, Texture> {
  const wallGfx = new Graphics()
    .rect(0, 0, TILE_SIZE, TILE_SIZE)
    .fill(0x444444);
  const groundGfx = new Graphics()
    .rect(0, 0, TILE_SIZE, TILE_SIZE)
    .fill(0x222222)
    .rect(0, 0, TILE_SIZE, TILE_SIZE)
    .stroke({ color: 0x1a1a1a, width: 1, alignment: 1 });
  return {
    [Tile.Wall]: app.renderer.generateTexture(wallGfx),
    [Tile.Ground]: app.renderer.generateTexture(groundGfx),
  };
}

function lerpColor(t: number): number {
  // Blue (early) → Green (mid) → Yellow (late)
  const r = t < 0.5 ? 0 : Math.round((t - 0.5) * 2 * 255);
  const g = t < 0.5 ? Math.round(t * 2 * 255) : 255;
  const b = t < 0.5 ? Math.round((1 - t * 2) * 255) : 0;
  return (r << 16) | (g << 8) | b;
}

(async () => {
  const app = await setup();
  const textures = makeTileTextures(app);

  const map0Buf = await fetch(stockMaps["./maps/map0.png"]).then((r) =>
    r.arrayBuffer(),
  );
  let world = worldFromIndexedPng(map0Buf) ?? makeWorld(1, 1);

  const mapContainer = new Container();
  const searchContainer = new Container();
  const overlayContainer = new Container();
  const belowMapContainer = new Container();
  const colorbarContainer = new Container();
  belowMapContainer.x = MAP_OFFSET_X;
  app.stage.addChild(mapContainer);
  app.stage.addChild(searchContainer);
  app.stage.addChild(overlayContainer);
  app.stage.addChild(belowMapContainer);
  app.stage.addChild(colorbarContainer);

  let startCoord: Coord | null = null;
  let goalCoord: Coord | null = null;
  type Mode = "route" | "edit";
  let mode: Mode = "route";
  let algorithm: Algorithm = "astar";
  let tileSprites: Sprite[][] = [];

  const depthLabelStyle = new TextStyle({
    fill: 0xffffff,
    fontSize: 9,
    fontFamily: "monospace",
  });

  const gLabelStyle = new TextStyle({
    fill: 0x88ccff,
    fontSize: 8,
    fontFamily: "monospace",
  });

  const hLabelStyle = new TextStyle({
    fill: 0xffcc88,
    fontSize: 8,
    fontFamily: "monospace",
  });

  let animate = true;
  const ANIM_TILES_PER_FRAME = 1;
  let animTickerFn: ((ticker: import("pixi.js").Ticker) => void) | null = null;

  const colorbarLabelStyle = new TextStyle({
    fill: 0x888888,
    fontSize: 11,
    fontFamily: "monospace",
  });

  const colorbarTitleStyle = new TextStyle({
    fill: 0xaaaaaa,
    fontSize: 12,
    fontFamily: "monospace",
  });

  const diagramLabelStyle = new TextStyle({
    fill: 0xaaaaaa,
    fontSize: 11,
    fontFamily: "monospace",
  });

  function stopAnimation(): void {
    if (animTickerFn) {
      app.ticker.remove(animTickerFn);
      animTickerFn = null;
    }
  }

  const COLORBAR_WIDTH = 20;
  const COLORBAR_GAP = 12;
  const COLORBAR_STEPS = 64;

  function onPointerDown(event: import("pixi.js").FederatedPointerEvent): void {
    const pos = event.getLocalPosition(app.stage);
    const coord = pixelToTile(world, pos.x, pos.y);
    if (!coord) return;
    if (mode === "edit") {
      applyEditAt(
        coord.col,
        coord.row,
        event.button === 0 ? Tile.Wall : Tile.Ground,
      );
      return;
    }
    if (getTile(world, coord.col, coord.row) === Tile.Wall) return;
    if (event.button === 0) {
      startCoord = coord;
    } else if (event.button === 2) {
      goalCoord = coord;
    }
    redrawOverlay();
  }

  function onPointerMove(event: import("pixi.js").FederatedPointerEvent): void {
    if (mode !== "edit" || event.buttons === 0) return;
    const pos = event.getLocalPosition(app.stage);
    const coord = pixelToTile(world, pos.x, pos.y);
    if (!coord) return;
    applyEditAt(
      coord.col,
      coord.row,
      event.buttons & 1 ? Tile.Wall : Tile.Ground,
    );
  }

  function applyEditAt(col: number, row: number, tile: Tile): void {
    if (world.tiles[row * world.cols + col] === tile) return;
    world.tiles[row * world.cols + col] = tile;
    tileSprites[row][col].texture = textures[tile];
    redrawOverlay(true);
  }

  function buildMap(): void {
    for (const child of mapContainer.removeChildren()) child.destroy();
    tileSprites = Array.from(
      { length: world.rows },
      () => new Array<Sprite>(world.cols),
    );
    for (let row = 0; row < world.rows; row++) {
      for (let col = 0; col < world.cols; col++) {
        const sprite = new Sprite(textures[getTile(world, col, row)]);
        sprite.x = MAP_OFFSET_X + col * TILE_SIZE;
        sprite.y = MAP_OFFSET_Y + row * TILE_SIZE;
        tileSprites[row][col] = sprite;
        mapContainer.addChild(sprite);
      }
    }

    const mapW = world.cols * TILE_SIZE;
    const mapH = world.rows * TILE_SIZE;

    const border = new Graphics()
      .rect(MAP_OFFSET_X, MAP_OFFSET_Y, mapW, mapH)
      .stroke({ width: 1, color: 0x888888 });
    mapContainer.addChild(border);

    const hit = new Graphics()
      .rect(MAP_OFFSET_X, MAP_OFFSET_Y, mapW, mapH)
      .fill({ color: 0x000000, alpha: 0 });
    hit.eventMode = "static";
    hit.cursor = "pointer";
    hit.on("pointerdown", onPointerDown);
    hit.on("pointermove", onPointerMove);
    mapContainer.addChild(hit);

    belowMapContainer.y = Math.round(MAP_OFFSET_Y + mapH + 8);
  }

  buildMap();
  drawColorbar(null);

  // --- Below-map: stats + legend + mode toggle ---
  const LEGEND_LOCAL_X = 340;
  const LEGEND_ROW = 20;
  const LEGEND_LINE_LEN = 20;

  const statusLabel = new Text({
    text: "",
    style: new TextStyle({
      fill: 0x888888,
      fontSize: 14,
      fontFamily: "monospace",
      lineHeight: 20,
    }),
  });
  belowMapContainer.addChild(statusLabel);

  const legendContainer = new Container();
  legendContainer.x = LEGEND_LOCAL_X;
  belowMapContainer.addChild(legendContainer);

  const legendStyle = new TextStyle({
    fill: 0x888888,
    fontSize: 14,
    fontFamily: "monospace",
  });

  function rebuildLegend(): void {
    for (const child of legendContainer.removeChildren()) child.destroy();

    const meta = ALGORITHM_META[algorithm];
    const items = [
      { color: PATH_COLOR, label: meta.label, isLine: true },
      { color: START_COLOR, label: "start", isLine: false },
      { color: GOAL_COLOR, label: "goal", isLine: false },
    ];

    const gfx = new Graphics();
    for (let i = 0; i < items.length; i++) {
      const y = i * LEGEND_ROW + 7;
      if (items[i].isLine) {
        gfx
          .moveTo(0, y)
          .lineTo(LEGEND_LINE_LEN, y)
          .stroke({ color: items[i].color, width: PATH_LINE_W });
      } else {
        gfx.circle(LEGEND_LINE_LEN / 2, y, 5).fill(items[i].color);
      }
    }
    legendContainer.addChild(gfx);

    for (let i = 0; i < items.length; i++) {
      const lbl = new Text({ text: items[i].label, style: legendStyle });
      lbl.x = Math.round(LEGEND_LINE_LEN + 8);
      lbl.y = Math.round(i * LEGEND_ROW);
      legendContainer.addChild(lbl);
    }
  }

  rebuildLegend();

  // --- Mode buttons (Route / Edit) ---
  const modeContainer = new Container();
  modeContainer.x = LEGEND_LOCAL_X + 160;
  belowMapContainer.addChild(modeContainer);

  const modeEntries: { m: Mode; label: string }[] = [
    { m: "route", label: "Route" },
    { m: "edit", label: "Edit" },
  ];
  const modeActiveStyle = new TextStyle({
    fill: 0xdddddd,
    fontSize: 14,
    fontFamily: "monospace",
  });
  const modeInactiveStyle = new TextStyle({
    fill: 0x555555,
    fontSize: 14,
    fontFamily: "monospace",
  });

  const modeBtns = modeEntries.map(({ m, label }, i) => {
    const btn = new Text({
      text: label,
      style: m === mode ? modeActiveStyle : modeInactiveStyle,
    });
    btn.y = i * LEGEND_ROW;
    btn.eventMode = "static";
    btn.cursor = "pointer";
    modeContainer.addChild(btn);
    return btn;
  });
  const setMode = (m: Mode) => {
    mode = m;
    for (let j = 0; j < modeBtns.length; j++) {
      modeBtns[j].style =
        modeEntries[j].m === mode ? modeActiveStyle : modeInactiveStyle;
    }
  };
  modeBtns.forEach((btn, i) =>
    btn.on("pointerdown", () => setMode(modeEntries[i].m)),
  );

  // --- Animate toggle ---
  const animBtn = new Text({
    text: "Animate: on",
    style: modeActiveStyle,
  });
  animBtn.y = modeEntries.length * LEGEND_ROW + 8;
  animBtn.eventMode = "static";
  animBtn.cursor = "pointer";
  modeContainer.addChild(animBtn);

  const updateAnimBtn = () => {
    animBtn.text = animate ? "Animate: on" : "Animate: off";
    animBtn.style = animate ? modeActiveStyle : modeInactiveStyle;
  };
  animBtn.on("pointerdown", () => {
    animate = !animate;
    updateAnimBtn();
    redrawOverlay();
  });

  function drawColorbar(maxOrder: number | null): void {
    for (const child of colorbarContainer.removeChildren()) child.destroy();

    const mapW = world.cols * TILE_SIZE;
    const mapH = world.rows * TILE_SIZE;
    const barX = MAP_OFFSET_X + mapW + COLORBAR_GAP;
    const barY = MAP_OFFSET_Y;
    const barH = mapH;
    const stepH = barH / COLORBAR_STEPS;

    const gfx = new Graphics();
    for (let i = 0; i < COLORBAR_STEPS; i++) {
      const t = i / (COLORBAR_STEPS - 1);
      gfx
        .rect(barX, barY + i * stepH, COLORBAR_WIDTH, stepH + 1)
        .fill(lerpColor(t));
    }
    gfx
      .rect(barX, barY, COLORBAR_WIDTH, barH)
      .stroke({ color: 0x888888, width: 1 });
    colorbarContainer.addChild(gfx);

    if (maxOrder !== null && maxOrder > 0) {
      const tickCount = 5;
      for (let i = 0; i <= tickCount; i++) {
        const t = i / tickCount;
        const value = Math.round(t * maxOrder);
        const lbl = new Text({
          text: String(value),
          style: colorbarLabelStyle,
        });
        lbl.x = barX + COLORBAR_WIDTH + 4;
        lbl.y = Math.round(barY + t * barH - 6);
        colorbarContainer.addChild(lbl);
      }
    }

    const title = new Text({
      text: "expansion\norder",
      style: colorbarTitleStyle,
    });
    title.x = barX - 2;
    title.y = barY - 30;
    colorbarContainer.addChild(title);

    drawTileDiagram(barX + COLORBAR_WIDTH + 50, barY + 10);
  }

  function drawTileDiagram(diagramX: number, diagramY: number): void {
    const diagramSize = 64;

    const dgfx = new Graphics();
    dgfx
      .rect(diagramX, diagramY, diagramSize, diagramSize)
      .fill({ color: 0x222222 })
      .rect(diagramX, diagramY, diagramSize, diagramSize)
      .stroke({ color: 0x888888, width: 1 });
    colorbarContainer.addChild(dgfx);

    const orderLbl = new Text({ text: "#", style: depthLabelStyle });
    orderLbl.x = diagramX + 4;
    orderLbl.y = diagramY + 3;
    colorbarContainer.addChild(orderLbl);

    const gLbl = new Text({ text: "g", style: gLabelStyle });
    gLbl.anchor.set(0, 1);
    gLbl.x = diagramX + 4;
    gLbl.y = diagramY + diagramSize - 4;
    colorbarContainer.addChild(gLbl);

    const hLbl = new Text({ text: "h", style: hLabelStyle });
    hLbl.anchor.set(1, 1);
    hLbl.x = diagramX + diagramSize - 4;
    hLbl.y = diagramY + diagramSize - 4;
    colorbarContainer.addChild(hLbl);

    const keyLabels = [
      { text: "# = expansion order", y: diagramY + diagramSize + 8 },
      { text: "g = cost from start", y: diagramY + diagramSize + 22 },
      { text: "h = est. to goal", y: diagramY + diagramSize + 36 },
    ];
    for (const { text, y } of keyLabels) {
      const lbl = new Text({ text, style: diagramLabelStyle });
      lbl.x = diagramX;
      lbl.y = y;
      colorbarContainer.addChild(lbl);
    }
  }

  function makeTileContainer(
    result: SearchResult,
    col: number,
    row: number,
    heuristic: (c: number, r: number) => number,
  ): Container {
    const idx = row * world.cols + col;
    const ord = result.visited[idx];
    const t = result.maxOrder > 0 ? ord / result.maxOrder : 0;
    const color = lerpColor(t);
    const tx = MAP_OFFSET_X + col * TILE_SIZE;
    const ty = MAP_OFFSET_Y + row * TILE_SIZE;

    const container = new Container();

    const gfx = new Graphics();
    gfx.rect(tx, ty, TILE_SIZE, TILE_SIZE).fill({ color, alpha: 0.3 });
    container.addChild(gfx);

    const orderLabel = new Text({
      text: String(ord),
      style: depthLabelStyle,
    });
    orderLabel.x = tx + 2;
    orderLabel.y = ty + 1;
    container.addChild(orderLabel);

    const g = result.gScore[idx];
    const gLabel = new Text({
      text: g < Infinity ? String(Math.round(g)) : "",
      style: gLabelStyle,
    });
    gLabel.anchor.set(0, 1);
    gLabel.x = tx + 2;
    gLabel.y = ty + TILE_SIZE - 2;
    container.addChild(gLabel);

    const h = heuristic(col, row);
    const hLabel = new Text({
      text: String(Math.round(h)),
      style: hLabelStyle,
    });
    hLabel.anchor.set(1, 1);
    hLabel.x = tx + TILE_SIZE - 2;
    hLabel.y = ty + TILE_SIZE - 2;
    container.addChild(hLabel);

    return container;
  }

  function drawSearchVisualization(
    result: SearchResult,
    pathGraphics: Graphics | null,
    skipAnimation: boolean,
  ): void {
    stopAnimation();
    for (const child of searchContainer.removeChildren()) child.destroy();

    if (result.maxOrder === 0) {
      drawColorbar(null);
      return;
    }

    const heuristic =
      algorithm === "astar"
        ? (c: number, r: number) =>
            Math.abs(c - goalCoord!.col) + Math.abs(r - goalCoord!.row)
        : (c: number, r: number) => {
            const dc = c - goalCoord!.col;
            const dr = r - goalCoord!.row;
            return Math.sqrt(dc * dc + dr * dr);
          };

    // Build containers sorted by expansion order
    const tileEntries: {
      ord: number;
      tileIdx: number;
      container: Container;
    }[] = [];
    for (let row = 0; row < world.rows; row++) {
      for (let col = 0; col < world.cols; col++) {
        const idx = row * world.cols + col;
        const ord = result.visited[idx];
        if (ord < 0) continue;
        const container = makeTileContainer(result, col, row, heuristic);
        tileEntries.push({ ord, tileIdx: idx, container });
        searchContainer.addChild(container);
      }
    }

    drawColorbar(result.maxOrder);

    if (animate && !skipAnimation) {
      tileEntries.sort((a, b) => a.ord - b.ord);
      for (const { container } of tileEntries) container.visible = false;
      if (pathGraphics) pathGraphics.visible = false;

      const bestPathGfx = new Graphics();
      overlayContainer.addChild(bestPathGfx);

      let revealed = 0;
      let frameAccum = 0;
      const fn = () => {
        frameAccum++;
        if (frameAccum < 4) return;
        frameAccum = 0;

        const target = Math.min(
          revealed + ANIM_TILES_PER_FRAME,
          tileEntries.length,
        );
        for (let i = revealed; i < target; i++) {
          tileEntries[i].container.visible = true;
        }
        revealed = target;

        // Draw best-path-so-far from most recently revealed tile back to start
        bestPathGfx.clear();
        if (revealed > 0) {
          const frontIdx = tileEntries[revealed - 1].tileIdx;
          const bestPath: Path = [];
          let idx = frontIdx;
          while (idx !== -1) {
            bestPath.push({
              col: idx % world.cols,
              row: Math.floor(idx / world.cols),
            });
            idx = result.cameFrom[idx];
          }
          bestPath.reverse();
          drawPath(bestPathGfx, bestPath, PATH_COLOR);
        }

        if (revealed >= tileEntries.length) {
          bestPathGfx.clear();
          if (pathGraphics) pathGraphics.visible = true;
          stopAnimation();
        }
      };
      animTickerFn = fn;
      app.ticker.add(fn);
    }
  }

  function redrawOverlay(skipAnimation = false): void {
    stopAnimation();
    for (const child of overlayContainer.removeChildren()) child.destroy();

    for (const child of searchContainer.removeChildren()) child.destroy();
    for (const child of colorbarContainer.removeChildren()) child.destroy();

    const g = new Graphics();

    if (startCoord) {
      const { x, y } = tileCenter(startCoord.col, startCoord.row);
      g.circle(x, y, MARKER_R).fill(START_COLOR);
    }

    if (goalCoord) {
      const { x, y } = tileCenter(goalCoord.col, goalCoord.row);
      g.circle(x, y, MARKER_R).fill(GOAL_COLOR);
    }

    overlayContainer.addChild(g);

    if (startCoord && goalCoord) {
      const meta = ALGORITHM_META[algorithm];
      const result =
        algorithm === "astar"
          ? findPathAStar(world, startCoord, goalCoord)
          : findPathTheta(world, startCoord, goalCoord);

      let pathGfx: Graphics | null = null;
      if (result.path) {
        const len = pathLength(result.path);
        const dc = goalCoord.col - startCoord.col;
        const dr = goalCoord.row - startCoord.row;
        const straight = Math.sqrt(dc * dc + dr * dr);

        statusLabel.text = [
          `${meta.label}  ${len.toFixed(2)} tiles  (${result.maxOrder + 1} expanded)`,
          `straight: ${straight.toFixed(2)} tiles`,
        ].join("\n");

        pathGfx = new Graphics();
        drawPath(pathGfx, result.path, PATH_COLOR);
        overlayContainer.addChild(pathGfx);
      } else {
        statusLabel.text = `${meta.label}: no path found  (${result.maxOrder + 1} expanded)`;
      }

      drawSearchVisualization(result, pathGfx, skipAnimation);
    } else {
      drawColorbar(null);
    }
  }

  app.canvas.addEventListener("contextmenu", (e) => e.preventDefault());

  mountControls(
    () => world,
    statusLabel,
    (loaded) => {
      world = loaded;
      startCoord = null;
      goalCoord = null;
      buildMap();
      redrawOverlay();
    },
    () => algorithm,
    (a) => {
      algorithm = a;
      rebuildLegend();
      redrawOverlay();
    },
  );
})();