pixi-demo/tests/chase/solvability.test.ts

import { describe, expect, it } from "vitest";
import { optimalGuardStep, thiefHasWinningStrategy } from "../../src/stages/games/chase/logic/solvability";
import type { GameGraph } from "../../src/stages/games/chase/logic/types";

function lineGraph(ids: string[]): GameGraph {
  const nodes: GameGraph["nodes"] = {};
  const edgeList: Array<[string, string]> = [];
  for (let i = 0; i < ids.length; i += 1) {
    const id = ids[i];
    const prev = ids[i - 1];
    const next = ids[i + 1];
    const neighbors: string[] = [];
    if (prev) {
      neighbors.push(prev);
    }
    if (next) {
      neighbors.push(next);
    }
    nodes[id] = { id, q: i, r: 0, neighbors };
  }
  for (let i = 0; i < ids.length - 1; i += 1) {
    edgeList.push([ids[i], ids[i + 1]]);
  }
  return { nodes, edgeList };
}

describe("solvability (optimal guard)", () => {
  it("returns false when guard blocks the only exit from a leaf", () => {
    const graph = lineGraph(["L", "N", "E"]);
    expect(thiefHasWinningStrategy(graph, "L", "N", "E")).toBe(false);
  });

  it("returns true when thief reaches exit in one step before guard reacts", () => {
    const graph: GameGraph = {
      nodes: {
        T: { id: "T", q: 0, r: 0, neighbors: ["E", "G"] },
        E: { id: "E", q: 1, r: 0, neighbors: ["T"] },
        G: { id: "G", q: 0, r: 1, neighbors: ["T"] },
      },
      edgeList: [
        ["T", "E"],
        ["T", "G"],
      ],
    };
    expect(thiefHasWinningStrategy(graph, "T", "G", "E")).toBe(true);
  });

  it("optimalGuardStep matches shortest-path tie-break toward thief", () => {
    const graph = lineGraph(["A", "B", "C"]);
    expect(optimalGuardStep(graph, "A", "C")).toBe("B");
    expect(optimalGuardStep(graph, "C", "A")).toBe("B");
  });
});