BlueGit

timfa questward

Files

questward / server / tests / astar.test.js

astar.test.js

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