BlueGit

timfa questward

Files

questward / server / src / navigation / astar.js

astar.js

astar.js 6.7 KiB Download Raw
1import { CHUNK_SIZE } from "../../../shared/protocol/constants.js";
2import { tileToChunk, tileToLocal } from "../world/coordinates.js";
3
4class MinHeap
5{
6 constructor ()
7 {
8 this.items = [];
9 }
10
11 push (node)
12 {
13 this.items.push(node);
14 this.#siftUp(this.items.length - 1);
15 }
16
17 pop ()
18 {
19 if (this.items.length === 0)
20 { return null; }
21
22 const root = this.items[0];
23 const last = this.items.pop();
24 if (this.items.length > 0)
25 {
26 this.items[0] = last;
27 this.#siftDown(0);
28 }
29 return root;
30 }
31
32 get size ()
33 {
34 return this.items.length;
35 }
36
37 #siftUp (index)
38 {
39 while (index > 0)
40 {
41 const parent = (index - 1) >> 1;
42 if (this.items[parent].f <= this.items[index].f)
43 { break; }
44 [this.items[parent], this.items[index]] = [this.items[index], this.items[parent]];
45 index = parent;
46 }
47 }
48
49 #siftDown (index)
50 {
51 const length = this.items.length;
52 while (true)
53 {
54 let smallest = index;
55 const left = index * 2 + 1;
56 const right = left + 1;
57 if (left < length && this.items[left].f < this.items[smallest].f)
58 { smallest = left; }
59 if (right < length && this.items[right].f < this.items[smallest].f)
60 { smallest = right; }
61 if (smallest === index)
62 { break; }
63 [this.items[smallest], this.items[index]] = [this.items[index], this.items[smallest]];
64 index = smallest;
65 }
66 }
67}
68
69const CARDINALS = Object.freeze([
70 Object.freeze({ x: 1, y: 0 }),
71 Object.freeze({ x: -1, y: 0 }),
72 Object.freeze({ x: 0, y: 1 }),
73 Object.freeze({ x: 0, y: -1 })
74]);
75
76/** Tiny f-cost nudge so equal-length paths prefer the preferred axis. */
77const AXIS_TIE_BIAS = 0.001;
78
79/**
80 * Prefer the axis with more remaining Manhattan distance to the goal.
81 * When |dx| === |dy|, use `axisTiePreferVertical` (players vertical, mobs horizontal)
82 * so opposing pathfinders still diverge on square diagonals.
83 */
84export function preferVerticalAxis (fromX, fromY, goalX, goalY, axisTiePreferVertical = false)
85{
86 const dx = Math.abs(goalX - fromX);
87 const dy = Math.abs(goalY - fromY);
88 if (dy > dx)
89 { return true; }
90 if (dx > dy)
91 { return false; }
92 return !!axisTiePreferVertical;
93}
94
95/**
96 * Neighbour order: most distance-to-goal reduction first, then the longer remaining
97 * axis (or axis-tie preference when equal).
98 */
99export function orderedCardinals (fromX, fromY, goalX, goalY, axisTiePreferVertical = false)
100{
101 const preferVertical = preferVerticalAxis(fromX, fromY, goalX, goalY, axisTiePreferVertical);
102 const currentDist = Math.abs(goalX - fromX) + Math.abs(goalY - fromY);
103 return CARDINALS
104 .map((dir) =>
105 {
106 const nx = fromX + dir.x;
107 const ny = fromY + dir.y;
108 const nextDist = Math.abs(goalX - nx) + Math.abs(goalY - ny);
109 return {
110 dir,
111 reduction: currentDist - nextDist,
112 vertical: dir.y !== 0
113 };
114 })
115 .sort((a, b) =>
116 {
117 if (b.reduction !== a.reduction)
118 { return b.reduction - a.reduction; }
119 if (a.vertical !== b.vertical)
120 {
121 if (preferVertical)
122 { return a.vertical ? -1 : 1; }
123 return a.vertical ? 1 : -1;
124 }
125 return 0;
126 })
127 .map((entry) => entry.dir);
128}
129
130/**
131 * @param {object} [options]
132 * @param {boolean} [options.preferVertical] axis-tie break only: players vertical, mobs horizontal
133 * @param {(x: number, y: number) => number} [options.stepCost] movement cost into a tile (default 1)
134 * @param {number} [options.minStepCost] lowest possible stepCost (default 1). Required for
135 * admissible heuristics when some tiles cost less than 1 (e.g. path preference).
136 */
137export function findPath (startX, startY, goalX, goalY, isWalkable, minX, minY, maxX, maxY, options = {})
138{
139 const axisTiePreferVertical = !!options.preferVertical;
140 const stepCost = typeof options.stepCost === "function" ? options.stepCost : null;
141 const minStepCost = Math.max(0.001, Number(options.minStepCost) || 1);
142 if (!isWalkable(goalX, goalY) || !isWalkable(startX, startY))
143 { return []; }
144
145 if (startX === goalX && startY === goalY)
146 { return []; }
147
148 const width = maxX - minX + 1;
149 const height = maxY - minY + 1;
150 if (width <= 0 || height <= 0)
151 { return []; }
152
153 function index (x, y)
154 {
155 return (y - minY) * width + (x - minX);
156 }
157
158 const heuristic = (x, y) => (Math.abs(goalX - x) + Math.abs(goalY - y)) * minStepCost;
159
160 const inBounds = (x, y) => x >= minX && y >= minY && x <= maxX && y <= maxY;
161 const cameFrom = new Int32Array(width * height).fill(-1);
162 const gScore = new Float64Array(width * height).fill(Infinity);
163 const closed = new Uint8Array(width * height);
164 const startIndex = index(startX, startY);
165 gScore[startIndex] = 0;
166
167 const open = new MinHeap();
168 open.push({ x: startX, y: startY, f: heuristic(startX, startY) });
169
170 while (open.size > 0)
171 {
172 const current = open.pop();
173 if (!inBounds(current.x, current.y))
174 { continue; }
175
176 const currentIndex = index(current.x, current.y);
177 if (closed[currentIndex])
178 { continue; }
179 closed[currentIndex] = 1;
180
181 if (current.x === goalX && current.y === goalY)
182 { return reconstruct(cameFrom, current.x, current.y, minX, minY, width); }
183
184 const preferVertical = preferVerticalAxis(
185 current.x,
186 current.y,
187 goalX,
188 goalY,
189 axisTiePreferVertical
190 );
191 for (const dir of orderedCardinals(current.x, current.y, goalX, goalY, axisTiePreferVertical))
192 {
193 const nx = current.x + dir.x;
194 const ny = current.y + dir.y;
195 if (!inBounds(nx, ny) || !isWalkable(nx, ny))
196 { continue; }
197
198 const neighborIndex = index(nx, ny);
199 if (closed[neighborIndex])
200 { continue; }
201
202 const cost = stepCost ? Math.max(minStepCost, Number(stepCost(nx, ny)) || 1) : 1;
203 const tentative = gScore[currentIndex] + cost;
204 if (tentative >= gScore[neighborIndex])
205 { continue; }
206
207 cameFrom[neighborIndex] = currentIndex;
208 gScore[neighborIndex] = tentative;
209 const h = heuristic(nx, ny);
210 const stepIsVertical = dir.y !== 0;
211 const preferredStep = preferVertical ? stepIsVertical : !stepIsVertical;
212 const bias = preferredStep ? 0 : AXIS_TIE_BIAS * minStepCost;
213 open.push({ x: nx, y: ny, f: tentative + h + bias });
214 }
215 }
216
217 return [];
218}
219
220function reconstruct (cameFrom, x, y, minX, minY, width)
221{
222 const path = [];
223 let cx = x;
224 let cy = y;
225 while (true)
226 {
227 path.push({ x: cx, y: cy });
228 const idx = (cy - minY) * width + (cx - minX);
229 const prev = cameFrom[idx];
230 if (prev < 0)
231 { break; }
232 cx = minX + (prev % width);
233 cy = minY + Math.floor(prev / width);
234 }
235 path.reverse();
236 if (path.length > 0)
237 { path.shift(); }
238 return path;
239}
240
241export function chunkBoundsAround (tileX, tileY, chunkRadius)
242{
243 const chunkX = tileToChunk(tileX);
244 const chunkY = tileToChunk(tileY);
245 const minChunkX = chunkX - chunkRadius;
246 const minChunkY = chunkY - chunkRadius;
247 const maxChunkX = chunkX + chunkRadius;
248 const maxChunkY = chunkY + chunkRadius;
249 return {
250 minX: minChunkX * CHUNK_SIZE,
251 minY: minChunkY * CHUNK_SIZE,
252 maxX: (maxChunkX + 1) * CHUNK_SIZE - 1,
253 maxY: (maxChunkY + 1) * CHUNK_SIZE - 1
254 };
255}
256
257export { tileToLocal };