BlueGit

timfa questward

Files

questward / server / tests / astar.test.js

astar.test.js

astar.test.js 6.0 KiB Download Raw
1import test from "node:test";
2import assert from "node:assert/strict";
3import { findPath, orderedCardinals } from "../src/navigation/astar.js";
4import { PATH_GROUND_STEP_COST, SOFT_OCCUPIED_STEP_PENALTY, stepCostForGround } from "../../shared/navigation/pathGround.js";
5import { GroundType } from "../../shared/definitions/tiles.js";
6
7test("A* walks around an impassable tile", () =>
8{
9 const blocked = new Set(["1,0"]);
10 const path = findPath(0, 0, 2, 0, (x, y) => !blocked.has(`${x},${y}`), -4, -4, 4, 4);
11 assert.ok(path.length > 0);
12 assert.deepEqual(path.at(-1), { x: 2, y: 0 });
13 assert.ok(!path.some((step) => step.x === 1 && step.y === 0));
14});
15
16test("A* returns empty when the goal is blocked", () =>
17{
18 const path = findPath(0, 0, 1, 0, (x, y) => x === 0 && y === 0, -2, -2, 2, 2);
19 assert.deepEqual(path, []);
20});
21
22test("ordered cardinals prefer longer remaining axis over axis-tie flag", () =>
23{
24 // |dy|=3 > |dx|=1 → vertical first even when axis-tie prefers horizontal.
25 const tallGoal = orderedCardinals(0, 0, -1, -3, false);
26 assert.deepEqual(tallGoal[0], { x: 0, y: -1 });
27 assert.deepEqual(tallGoal[1], { x: -1, y: 0 });
28
29 // |dx|=3 > |dy|=1 → horizontal first even when axis-tie prefers vertical.
30 const wideGoal = orderedCardinals(0, 0, -3, -1, true);
31 assert.deepEqual(wideGoal[0], { x: -1, y: 0 });
32 assert.deepEqual(wideGoal[1], { x: 0, y: -1 });
33
34 const horizontalOnly = orderedCardinals(0, 0, 3, 0, false);
35 assert.deepEqual(horizontalOnly[0], { x: 1, y: 0 });
36});
37
38test("axis-tie preference diverges only when |dx| equals |dy|", () =>
39{
40 const open = () => true;
41 const mobPath = findPath(0, 0, -2, -2, open, -8, -8, 8, 8, { preferVertical: false });
42 const playerPath = findPath(0, 0, -2, -2, open, -8, -8, 8, 8, { preferVertical: true });
43 assert.equal(mobPath.length, 4);
44 assert.equal(playerPath.length, 4);
45 assert.deepEqual(mobPath[0], { x: -1, y: 0 });
46 assert.deepEqual(playerPath[0], { x: 0, y: -1 });
47
48 // Tall goal: both close the larger vertical gap first (no mob/player swap dance).
49 const tallMob = findPath(0, 0, -1, -3, open, -8, -8, 8, 8, { preferVertical: false });
50 const tallPlayer = findPath(0, 0, -1, -3, open, -8, -8, 8, 8, { preferVertical: true });
51 assert.deepEqual(tallMob[0], { x: 0, y: -1 });
52 assert.deepEqual(tallPlayer[0], { x: 0, y: -1 });
53});
54
55test("A* stepCost prefers the cheaper route around an expensive corridor", () =>
56{
57 // Two routes from (0,0) to (2,0): through (1,0) cost 10, or via (0,1)-(1,1)-(2,1) cost 1 each.
58 const expensive = new Set(["1,0"]);
59 const path = findPath(
60 0,
61 0,
62 2,
63 0,
64 () => true,
65 -2,
66 -2,
67 4,
68 4,
69 {
70 stepCost: (x, y) => (expensive.has(`${x},${y}`) ? 10 : 1)
71 }
72 );
73 assert.ok(path.length > 0);
74 assert.deepEqual(path.at(-1), { x: 2, y: 0 });
75 assert.ok(!path.some((step) => step.x === 1 && step.y === 0));
76});
77
78test("A* path-ground stepCost prefers a road of equal Manhattan length", () =>
79{
80 // (0,0) → (1,1): via (1,0) path then (1,1), or via (0,1) grass then (1,1).
81 const pathTiles = new Set(["1,0"]);
82 const route = findPath(
83 0,
84 0,
85 1,
86 1,
87 () => true,
88 -2,
89 -2,
90 4,
91 4,
92 {
93 preferVertical: false,
94 minStepCost: PATH_GROUND_STEP_COST,
95 stepCost: (x, y) => stepCostForGround(
96 pathTiles.has(`${x},${y}`) ? GroundType.path : GroundType.grass,
97 { preferPaths: true }
98 )
99 }
100 );
101 assert.ok(route.some((step) => step.x === 1 && step.y === 0), JSON.stringify(route));
102 assert.ok(PATH_GROUND_STEP_COST < 1);
103});
104
105test("A* with cheap paths takes a short detour onto the road", () =>
106{
107 // Player above middle of top bar; vertical road on the right; goal middle of bottom.
108 // Straight down is 12 grass steps; via road is +2 tiles but much cheaper at 0.1/step.
109 const pathTiles = new Set();
110 for (let x = 0; x <= 2; x++)
111 { pathTiles.add(`${x},1`); }
112 for (let y = 2; y <= 11; y++)
113 { pathTiles.add(`2,${y}`); }
114 for (let x = 0; x <= 2; x++)
115 { pathTiles.add(`${x},12`); }
116
117 const route = findPath(
118 1,
119 0,
120 1,
121 12,
122 () => true,
123 -2,
124 -2,
125 20,
126 20,
127 {
128 preferVertical: true,
129 minStepCost: PATH_GROUND_STEP_COST,
130 stepCost: (x, y) => stepCostForGround(
131 pathTiles.has(`${x},${y}`) ? GroundType.path : GroundType.grass,
132 { preferPaths: true }
133 )
134 }
135 );
136 const onRoad = route.filter((step) => pathTiles.has(`${step.x},${step.y}`));
137 assert.ok(onRoad.length >= 10, `expected mostly road, got ${JSON.stringify(route)}`);
138 assert.ok(route.some((step) => step.x === 2), "should use the vertical road column");
139});
140
141test("soft-occupied penalty is weaker than path preference", () =>
142{
143 assert.ok(SOFT_OCCUPIED_STEP_PENALTY > 0);
144 assert.ok(SOFT_OCCUPIED_STEP_PENALTY < 1 - PATH_GROUND_STEP_COST);
145 assert.equal(stepCostForGround(GroundType.grass, { softOccupied: true }), 1 + SOFT_OCCUPIED_STEP_PENALTY);
146 assert.equal(
147 stepCostForGround(GroundType.path, { preferPaths: true, softOccupied: true }),
148 PATH_GROUND_STEP_COST + SOFT_OCCUPIED_STEP_PENALTY
149 );
150});
151
152test("A* soft-occupied cost prefers an equal-length route that avoids the stood-on tile", () =>
153{
154 // (0,0) → (1,1): via (1,0) soft-occupied, or via (0,1) clear.
155 const occupied = new Set(["1,0"]);
156 const path = findPath(
157 0,
158 0,
159 1,
160 1,
161 () => true,
162 -2,
163 -2,
164 4,
165 4,
166 {
167 preferVertical: false,
168 minStepCost: 1,
169 stepCost: (x, y) => stepCostForGround(
170 GroundType.grass,
171 { softOccupied: occupied.has(`${x},${y}`) }
172 )
173 }
174 );
175 assert.ok(path.length > 0);
176 assert.ok(!path.some((step) => step.x === 1 && step.y === 0), JSON.stringify(path));
177 assert.ok(path.some((step) => step.x === 0 && step.y === 1), JSON.stringify(path));
178});
179
180test("A* still crosses soft-occupied when the detour is much longer", () =>
181{
182 // Only corridor is through (1,0); far detour would be around a wall of blocked tiles.
183 const occupied = new Set(["1,0"]);
184 const blocked = new Set(["0,1", "1,1", "2,1", "0,-1", "1,-1", "2,-1"]);
185 const path = findPath(
186 0,
187 0,
188 2,
189 0,
190 (x, y) => !blocked.has(`${x},${y}`),
191 -2,
192 -2,
193 4,
194 4,
195 {
196 minStepCost: 1,
197 stepCost: (x, y) => stepCostForGround(
198 GroundType.grass,
199 { softOccupied: occupied.has(`${x},${y}`) }
200 )
201 }
202 );
203 assert.ok(path.some((step) => step.x === 1 && step.y === 0), JSON.stringify(path));
204});