import test from "node:test"; import assert from "node:assert/strict"; import { findPath, orderedCardinals } from "../src/navigation/astar.js"; import { PATH_GROUND_STEP_COST, SOFT_OCCUPIED_STEP_PENALTY, stepCostForGround } from "../../shared/navigation/pathGround.js"; import { GroundType } from "../../shared/definitions/tiles.js"; test("A* walks around an impassable tile", () => { const blocked = new Set(["1,0"]); const path = findPath(0, 0, 2, 0, (x, y) => !blocked.has(`${x},${y}`), -4, -4, 4, 4); assert.ok(path.length > 0); assert.deepEqual(path.at(-1), { x: 2, y: 0 }); assert.ok(!path.some((step) => step.x === 1 && step.y === 0)); }); test("A* returns empty when the goal is blocked", () => { const path = findPath(0, 0, 1, 0, (x, y) => x === 0 && y === 0, -2, -2, 2, 2); assert.deepEqual(path, []); }); test("ordered cardinals prefer longer remaining axis over axis-tie flag", () => { // |dy|=3 > |dx|=1 → vertical first even when axis-tie prefers horizontal. const tallGoal = orderedCardinals(0, 0, -1, -3, false); assert.deepEqual(tallGoal[0], { x: 0, y: -1 }); assert.deepEqual(tallGoal[1], { x: -1, y: 0 }); // |dx|=3 > |dy|=1 → horizontal first even when axis-tie prefers vertical. const wideGoal = orderedCardinals(0, 0, -3, -1, true); assert.deepEqual(wideGoal[0], { x: -1, y: 0 }); assert.deepEqual(wideGoal[1], { x: 0, y: -1 }); const horizontalOnly = orderedCardinals(0, 0, 3, 0, false); assert.deepEqual(horizontalOnly[0], { x: 1, y: 0 }); }); test("axis-tie preference diverges only when |dx| equals |dy|", () => { const open = () => true; const mobPath = findPath(0, 0, -2, -2, open, -8, -8, 8, 8, { preferVertical: false }); const playerPath = findPath(0, 0, -2, -2, open, -8, -8, 8, 8, { preferVertical: true }); assert.equal(mobPath.length, 4); assert.equal(playerPath.length, 4); assert.deepEqual(mobPath[0], { x: -1, y: 0 }); assert.deepEqual(playerPath[0], { x: 0, y: -1 }); // Tall goal: both close the larger vertical gap first (no mob/player swap dance). const tallMob = findPath(0, 0, -1, -3, open, -8, -8, 8, 8, { preferVertical: false }); const tallPlayer = findPath(0, 0, -1, -3, open, -8, -8, 8, 8, { preferVertical: true }); assert.deepEqual(tallMob[0], { x: 0, y: -1 }); assert.deepEqual(tallPlayer[0], { x: 0, y: -1 }); }); test("A* stepCost prefers the cheaper route around an expensive corridor", () => { // Two routes from (0,0) to (2,0): through (1,0) cost 10, or via (0,1)-(1,1)-(2,1) cost 1 each. const expensive = new Set(["1,0"]); const path = findPath( 0, 0, 2, 0, () => true, -2, -2, 4, 4, { stepCost: (x, y) => (expensive.has(`${x},${y}`) ? 10 : 1) } ); assert.ok(path.length > 0); assert.deepEqual(path.at(-1), { x: 2, y: 0 }); assert.ok(!path.some((step) => step.x === 1 && step.y === 0)); }); test("A* path-ground stepCost prefers a road of equal Manhattan length", () => { // (0,0) → (1,1): via (1,0) path then (1,1), or via (0,1) grass then (1,1). const pathTiles = new Set(["1,0"]); const route = findPath( 0, 0, 1, 1, () => true, -2, -2, 4, 4, { preferVertical: false, minStepCost: PATH_GROUND_STEP_COST, stepCost: (x, y) => stepCostForGround( pathTiles.has(`${x},${y}`) ? GroundType.path : GroundType.grass, { preferPaths: true } ) } ); assert.ok(route.some((step) => step.x === 1 && step.y === 0), JSON.stringify(route)); assert.ok(PATH_GROUND_STEP_COST < 1); }); test("A* with cheap paths takes a short detour onto the road", () => { // Player above middle of top bar; vertical road on the right; goal middle of bottom. // Straight down is 12 grass steps; via road is +2 tiles but much cheaper at 0.1/step. const pathTiles = new Set(); for (let x = 0; x <= 2; x++) { pathTiles.add(`${x},1`); } for (let y = 2; y <= 11; y++) { pathTiles.add(`2,${y}`); } for (let x = 0; x <= 2; x++) { pathTiles.add(`${x},12`); } const route = findPath( 1, 0, 1, 12, () => true, -2, -2, 20, 20, { preferVertical: true, minStepCost: PATH_GROUND_STEP_COST, stepCost: (x, y) => stepCostForGround( pathTiles.has(`${x},${y}`) ? GroundType.path : GroundType.grass, { preferPaths: true } ) } ); const onRoad = route.filter((step) => pathTiles.has(`${step.x},${step.y}`)); assert.ok(onRoad.length >= 10, `expected mostly road, got ${JSON.stringify(route)}`); assert.ok(route.some((step) => step.x === 2), "should use the vertical road column"); }); test("soft-occupied penalty is weaker than path preference", () => { assert.ok(SOFT_OCCUPIED_STEP_PENALTY > 0); assert.ok(SOFT_OCCUPIED_STEP_PENALTY < 1 - PATH_GROUND_STEP_COST); assert.equal(stepCostForGround(GroundType.grass, { softOccupied: true }), 1 + SOFT_OCCUPIED_STEP_PENALTY); assert.equal( stepCostForGround(GroundType.path, { preferPaths: true, softOccupied: true }), PATH_GROUND_STEP_COST + SOFT_OCCUPIED_STEP_PENALTY ); }); test("A* soft-occupied cost prefers an equal-length route that avoids the stood-on tile", () => { // (0,0) → (1,1): via (1,0) soft-occupied, or via (0,1) clear. const occupied = new Set(["1,0"]); const path = findPath( 0, 0, 1, 1, () => true, -2, -2, 4, 4, { preferVertical: false, minStepCost: 1, stepCost: (x, y) => stepCostForGround( GroundType.grass, { softOccupied: occupied.has(`${x},${y}`) } ) } ); assert.ok(path.length > 0); assert.ok(!path.some((step) => step.x === 1 && step.y === 0), JSON.stringify(path)); assert.ok(path.some((step) => step.x === 0 && step.y === 1), JSON.stringify(path)); }); test("A* still crosses soft-occupied when the detour is much longer", () => { // Only corridor is through (1,0); far detour would be around a wall of blocked tiles. const occupied = new Set(["1,0"]); const blocked = new Set(["0,1", "1,1", "2,1", "0,-1", "1,-1", "2,-1"]); const path = findPath( 0, 0, 2, 0, (x, y) => !blocked.has(`${x},${y}`), -2, -2, 4, 4, { minStepCost: 1, stepCost: (x, y) => stepCostForGround( GroundType.grass, { softOccupied: occupied.has(`${x},${y}`) } ) } ); assert.ok(path.some((step) => step.x === 1 && step.y === 0), JSON.stringify(path)); });