| 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 distance reduction then axis", () => |
| 21 | { |
| 22 | const horizontalPrefer = orderedCardinals(0, 0, -1, -3, false); |
| 23 | assert.deepEqual(horizontalPrefer[0], { x: -1, y: 0 }); |
| 24 | assert.deepEqual(horizontalPrefer[1], { x: 0, y: -1 }); |
| 25 | |
| 26 | const verticalPrefer = orderedCardinals(0, 0, -1, -3, true); |
| 27 | assert.deepEqual(verticalPrefer[0], { x: 0, y: -1 }); |
| 28 | assert.deepEqual(verticalPrefer[1], { x: -1, y: 0 }); |
| 29 | |
| 30 | const horizontalOnly = orderedCardinals(0, 0, 3, 0, false); |
| 31 | assert.deepEqual(horizontalOnly[0], { x: 1, y: 0 }); |
| 32 | }); |
| 33 | |
| 34 | test("player and mob axis bias diverge on diagonal goals", () => |
| 35 | { |
| 36 | const open = () => true; |
| 37 | const mobPath = findPath(0, 0, -1, -3, open, -8, -8, 8, 8, { preferVertical: false }); |
| 38 | const playerPath = findPath(0, 0, -1, -3, open, -8, -8, 8, 8, { preferVertical: true }); |
| 39 | assert.equal(mobPath.length, 4); |
| 40 | assert.equal(playerPath.length, 4); |
| 41 | assert.deepEqual(mobPath[0], { x: -1, y: 0 }); |
| 42 | assert.deepEqual(playerPath[0], { x: 0, y: -1 }); |
| 43 | }); |
| 44 | |
| 45 | test("A* stepCost prefers the cheaper route around an expensive corridor", () => |
| 46 | { |
| 47 | // Two routes from (0,0) to (2,0): through (1,0) cost 10, or via (0,1)-(1,1)-(2,1) cost 1 each. |
| 48 | const expensive = new Set(["1,0"]); |
| 49 | const path = findPath( |
| 50 | 0, |
| 51 | 0, |
| 52 | 2, |
| 53 | 0, |
| 54 | () => true, |
| 55 | -2, |
| 56 | -2, |
| 57 | 4, |
| 58 | 4, |
| 59 | { |
| 60 | stepCost: (x, y) => (expensive.has(`${x},${y}`) ? 10 : 1) |
| 61 | } |
| 62 | ); |
| 63 | assert.ok(path.length > 0); |
| 64 | assert.deepEqual(path.at(-1), { x: 2, y: 0 }); |
| 65 | assert.ok(!path.some((step) => step.x === 1 && step.y === 0)); |
| 66 | }); |