Made of little things.

// Port of BrowserQuest client/js/pathfinder.js and lib/astar.js (MPL-2.0;
// A* by Andrea Giammarchi, MIT-style licence). Manhattan distance, no diagonals.
import type { Path } from './entity.js';

interface Node {
  x: number;
  y: number;
  f: number;
  g: number;
  v: number;
  p?: Node;
}

function successors(x: number, y: number, grid: number[][], rows: number, cols: number): Node[] {
  const N = y - 1;
  const S = y + 1;
  const E = x + 1;
  const W = x - 1;
  const result: Node[] = [];
  const node = (nx: number, ny: number): Node => ({ x: nx, y: ny, f: 0, g: 0, v: 0 });
  if (N > -1 && !grid[N][x]) result.push(node(x, N));
  if (E < cols && !grid[y][E]) result.push(node(E, y));
  if (S < rows && !grid[S][x]) result.push(node(x, S));
  if (W > -1 && !grid[y][W]) result.push(node(W, y));
  return result;
}

const manhattan = (a: { x: number; y: number }, b: { x: number; y: number }): number =>
  Math.abs(a.x - b.x) + Math.abs(a.y - b.y);

export function astar(grid: number[][], start: [number, number], end: [number, number]): Path {
  const cols = grid[0].length;
  const rows = grid.length;
  const limit = cols * rows;
  const list = new Set<number>();
  const result: Path = [];
  const open: Node[] = [{ x: start[0], y: start[1], f: 0, g: 0, v: start[0] + start[1] * cols }];
  const goal = { x: end[0], y: end[1], v: end[0] + end[1] * cols };

  while (open.length) {
    let max = limit;
    let min = 0;
    for (let i = 0; i < open.length; ++i) {
      if (open[i].f < max) {
        max = open[i].f;
        min = i;
      }
    }
    const current = open.splice(min, 1)[0];
    if (current.v !== goal.v) {
      for (const adj of successors(current.x, current.y, grid, rows, cols)) {
        adj.p = current;
        adj.v = adj.x + adj.y * cols;
        if (!list.has(adj.v)) {
          adj.g = current.g + manhattan(adj, current);
          adj.f = adj.g + manhattan(adj, goal);
          open.push(adj);
          list.add(adj.v);
        }
      }
    } else {
      let node: Node | undefined = current;
      while (node) {
        result.push([node.x, node.y]);
        node = node.p;
      }
      result.reverse();
      break;
    }
  }
  return result;
}

interface Pathable {
  gridX: number;
  gridY: number;
  nextGridX?: number;
  nextGridY?: number;
  isMoving(): boolean;
}

export class Pathfinder {
  private grid: number[][] | null = null;
  private readonly blankGrid: number[][] = [];
  private ignored: Pathable[] = [];

  constructor(
    readonly width: number,
    readonly height: number,
  ) {
    for (let i = 0; i < height; i += 1) this.blankGrid[i] = new Array<number>(width).fill(0);
  }

  findPath(grid: number[][], entity: Pathable, x: number, y: number, findIncomplete: boolean): Path {
    const start: [number, number] = [entity.gridX, entity.gridY];
    const end: [number, number] = [x, y];
    this.grid = grid;
    this.applyIgnoreList(true);
    let path = astar(this.grid, start, end);
    if (path.length === 0 && findIncomplete) {
      // If no path was found, try and find an incomplete one to at least get closer to destination.
      path = this.findIncompletePath(start, end);
    }
    return path;
  }

  /** Finds a path which leads the closest possible to an unreachable x, y position. */
  private findIncompletePath(start: [number, number], end: [number, number]): Path {
    const perfect = astar(this.blankGrid, start, end);
    for (let i = perfect.length - 1; i > 0; i -= 1) {
      const [x, y] = perfect[i];
      if (this.grid![y][x] === 0) return astar(this.grid!, start, [x, y]);
    }
    return [];
  }

  ignoreEntity(entity: Pathable | null): void {
    if (entity) this.ignored.push(entity);
  }

  private applyIgnoreList(ignored: boolean): void {
    for (const entity of this.ignored) {
      const moving = entity.isMoving();
      const x = moving ? (entity.nextGridX ?? -1) : entity.gridX;
      const y = moving ? (entity.nextGridY ?? -1) : entity.gridY;
      if (x >= 0 && y >= 0 && this.grid?.[y]) this.grid[y][x] = ignored ? 0 : 1;
    }
  }

  clearIgnoreList(): void {
    this.applyIgnoreList(false);
    this.ignored = [];
  }
}