nEngine/packages/core/test/pathfinding.test.ts

import { describe, expect, it } from "vitest";
import { findPath, isWalkableTile, type MapDef } from "../src/index.js";

function map(layers: string[][], walkable?: Record<string, boolean>): MapDef {
  return {
    id: "farm",
    width: layers[0]?.length ?? 0,
    height: layers.length,
    tilesetRef: "tiles",
    spawn: { x: 0, y: 0 },
    layers: [{ name: "ground", data: layers }],
    ...(walkable !== undefined ? { walkable } : {}),
  };
}

const GRASS: MapDef = map([
  ["grass", "grass", "water", "water", "water"],
  ["grass", "grass", "water", "water", "water"],
  ["grass", "grass", "grass", "grass", "grass"],
  ["grass", "grass", "grass", "grass", "grass"],
  ["grass", "grass", "grass", "grass", "grass"],
]);

const OPEN: MapDef = map([
  ["grass", "grass", "grass", "grass", "grass"],
  ["grass", "grass", "grass", "grass", "grass"],
  ["grass", "grass", "grass", "grass", "grass"],
  ["grass", "grass", "grass", "grass", "grass"],
  ["grass", "grass", "grass", "grass", "grass"],
]);

const noBlock = (): boolean => false;

describe("findPath (A* grid pathfinding)", () => {
  it("returns a straight-line path including start and goal", () => {
    const path = findPath(OPEN, { x: 0, y: 0 }, { x: 1, y: 1 }, noBlock);
    expect(path).toEqual([
      { x: 0, y: 0 },
      { x: 1, y: 0 },
      { x: 1, y: 1 },
    ]);
  });

  it("detours around a single blocked tile", () => {
    const path = findPath(OPEN, { x: 0, y: 0 }, { x: 1, y: 1 }, (x, y) => x === 1 && y === 0);
    expect(path).toEqual([
      { x: 0, y: 0 },
      { x: 0, y: 1 },
      { x: 1, y: 1 },
    ]);
  });

  it("finds the shortest detour around multiple obstacles", () => {
    const blocked = (x: number, y: number): boolean =>
      (x === 1 && y === 0) || (x === 2 && y === 0) || (x === 1 && y === 1);
    const path = findPath(OPEN, { x: 0, y: 0 }, { x: 3, y: 0 }, blocked);
    expect(path).not.toBeNull();
    expect(path![0]).toEqual({ x: 0, y: 0 });
    expect(path![path!.length - 1]).toEqual({ x: 3, y: 0 });
    expect(path).toHaveLength(8);
  });

  it("returns null for a U-shaped unreachable goal", () => {
    const box: MapDef = map([
      ["grass", "grass", "grass", "grass", "grass"],
      ["grass", "block", "block", "block", "grass"],
      ["grass", "block", "grass", "block", "grass"],
      ["grass", "block", "block", "block", "grass"],
      ["grass", "grass", "grass", "grass", "grass"],
    ]);
    const blocked = (x: number, y: number): boolean => {
      const tile = box.layers[0]?.data[y]?.[x];
      return tile === "block";
    };
    expect(findPath(box, { x: 0, y: 0 }, { x: 2, y: 2 }, blocked)).toBeNull();
  });

  it("returns null when the goal is on a blocked tile", () => {
    expect(findPath(OPEN, { x: 0, y: 0 }, { x: 1, y: 0 }, (x, y) => x === 1 && y === 0)).toBeNull();
  });

  it("returns a single-element path when start equals goal", () => {
    expect(findPath(OPEN, { x: 2, y: 2 }, { x: 2, y: 2 }, noBlock)).toEqual([{ x: 2, y: 2 }]);
  });

  it("returns null for an out-of-bounds goal", () => {
    expect(findPath(OPEN, { x: 0, y: 0 }, { x: 5, y: 0 }, noBlock)).toBeNull();
    expect(findPath(OPEN, { x: 0, y: 0 }, { x: -1, y: 0 }, noBlock)).toBeNull();
  });

  it("returns null when the goal is not walkable (water fallback)", () => {
    expect(findPath(GRASS, { x: 0, y: 0 }, { x: 2, y: 0 }, noBlock)).toBeNull();
  });

  it("treats a walkable-declared water tile as passable", () => {
    const declared: MapDef = map(
      [
        ["grass", "grass", "water", "grass", "grass"],
        ["grass", "grass", "water", "grass", "grass"],
        ["grass", "grass", "water", "grass", "grass"],
        ["grass", "grass", "water", "grass", "grass"],
        ["grass", "grass", "grass", "grass", "grass"],
      ],
      { water: true },
    );
    const path = findPath(declared, { x: 0, y: 0 }, { x: 4, y: 0 }, noBlock);
    expect(path).not.toBeNull();
    expect(path![0]).toEqual({ x: 0, y: 0 });
    expect(path![path!.length - 1]).toEqual({ x: 4, y: 0 });
  });

  it("returns null when no map is loaded and never mutates inputs", () => {
    expect(findPath(undefined, { x: 0, y: 0 }, { x: 1, y: 1 }, noBlock)).toBeNull();
    const start = { x: 0, y: 0 };
    const goal = { x: 2, y: 2 };
    findPath(GRASS, start, goal, noBlock);
    expect(start).toEqual({ x: 0, y: 0 });
    expect(goal).toEqual({ x: 2, y: 2 });
    expect(GRASS.layers[0]?.data[0]?.[2]).toBe("water");
  });
});

describe("isWalkableTile (map-grid walkability resolution)", () => {
  it("declared-false blocks a tile", () => {
    const m = map([["grass", "water"]], { water: false });
    expect(isWalkableTile(m, 0, 0)).toBe(true);
    expect(isWalkableTile(m, 1, 0)).toBe(false);
  });

  it("undeclared water is blocked via the UNWALKABLE_TILES fallback", () => {
    const m = map([["grass", "water"]]);
    expect(isWalkableTile(m, 1, 0)).toBe(false);
  });

  it("undeclared grass is walkable", () => {
    expect(isWalkableTile(GRASS, 0, 0)).toBe(true);
  });

  it("declared-true overrides the fallback", () => {
    const m = map([["grass", "water"]], { water: true });
    expect(isWalkableTile(m, 1, 0)).toBe(true);
  });

  it("out-of-bounds and unknown tiles are not walkable", () => {
    expect(isWalkableTile(GRASS, -1, 0)).toBe(false);
    expect(isWalkableTile(GRASS, 0, -1)).toBe(false);
    expect(isWalkableTile(GRASS, 5, 0)).toBe(false);
    expect(isWalkableTile(GRASS, 0, 5)).toBe(false);
  });
});