| 1 | import test from "node:test"; |
| 2 | import assert from "node:assert/strict"; |
| 3 | import { findPath, orderedCardinals } from "../src/navigation/astar.js"; |
| 4 | |
| 5 | test("A* walks around an impassable tile", () => |
| 6 | { |
| 7 | const blocked = new Set(["1,0"]); |
| 8 | const path = findPath(0, 0, 2, 0, (x, y) => !blocked.has(`${x},${y}`), -4, -4, 4, 4); |
| 9 | assert.ok(path.length > 0); |
| 10 | assert.deepEqual(path.at(-1), { x: 2, y: 0 }); |
| 11 | assert.ok(!path.some((step) => step.x === 1 && step.y === 0)); |
| 12 | }); |
| 13 | |
| 14 | test("A* returns empty when the goal is blocked", () => |
| 15 | { |
| 16 | const path = findPath(0, 0, 1, 0, (x, y) => x === 0 && y === 0, -2, -2, 2, 2); |
| 17 | assert.deepEqual(path, []); |
| 18 | }); |
| 19 | |
| 20 | test("ordered cardinals prefer longer remaining axis over axis-tie flag", () => |
| 21 | { |
| 22 | // |dy|=3 > |dx|=1 → vertical first even when axis-tie prefers horizontal. |
| 23 | const tallGoal = orderedCardinals(0, 0, -1, -3, false); |
| 24 | assert.deepEqual(tallGoal[0], { x: 0, y: -1 }); |
| 25 | assert.deepEqual(tallGoal[1], { x: -1, y: 0 }); |
| 26 | |
| 27 | // |dx|=3 > |dy|=1 → horizontal first even when axis-tie prefers vertical. |
| 28 | const wideGoal = orderedCardinals(0, 0, -3, -1, true); |
| 29 | assert.deepEqual(wideGoal[0], { x: -1, y: 0 }); |
| 30 | assert.deepEqual(wideGoal[1], { x: 0, y: -1 }); |
| 31 | |
| 32 | const horizontalOnly = orderedCardinals(0, 0, 3, 0, false); |
| 33 | assert.deepEqual(horizontalOnly[0], { x: 1, y: 0 }); |
| 34 | }); |
| 35 | |
| 36 | test("axis-tie preference diverges only when |dx| equals |dy|", () => |
| 37 | { |
| 38 | const open = () => true; |
| 39 | const mobPath = findPath(0, 0, -2, -2, open, -8, -8, 8, 8, { preferVertical: false }); |
| 40 | const playerPath = findPath(0, 0, -2, -2, open, -8, -8, 8, 8, { preferVertical: true }); |
| 41 | assert.equal(mobPath.length, 4); |
| 42 | assert.equal(playerPath.length, 4); |
| 43 | assert.deepEqual(mobPath[0], { x: -1, y: 0 }); |
| 44 | assert.deepEqual(playerPath[0], { x: 0, y: -1 }); |
| 45 | |
| 46 | // Tall goal: both close the larger vertical gap first (no mob/player swap dance). |
| 47 | const tallMob = findPath(0, 0, -1, -3, open, -8, -8, 8, 8, { preferVertical: false }); |
| 48 | const tallPlayer = findPath(0, 0, -1, -3, open, -8, -8, 8, 8, { preferVertical: true }); |
| 49 | assert.deepEqual(tallMob[0], { x: 0, y: -1 }); |
| 50 | assert.deepEqual(tallPlayer[0], { x: 0, y: -1 }); |
| 51 | }); |
| 52 | |
| 53 | test("A* stepCost prefers the cheaper route around an expensive corridor", () => |
| 54 | { |
| 55 | // Two routes from (0,0) to (2,0): through (1,0) cost 10, or via (0,1)-(1,1)-(2,1) cost 1 each. |
| 56 | const expensive = new Set(["1,0"]); |
| 57 | const path = findPath( |
| 58 | 0, |
| 59 | 0, |
| 60 | 2, |
| 61 | 0, |
| 62 | () => true, |
| 63 | -2, |
| 64 | -2, |
| 65 | 4, |
| 66 | 4, |
| 67 | { |
| 68 | stepCost: (x, y) => (expensive.has(`${x},${y}`) ? 10 : 1) |
| 69 | } |
| 70 | ); |
| 71 | assert.ok(path.length > 0); |
| 72 | assert.deepEqual(path.at(-1), { x: 2, y: 0 }); |
| 73 | assert.ok(!path.some((step) => step.x === 1 && step.y === 0)); |
| 74 | }); |