BlueGit

timfa questward

Files

questward / server / src / navigation / astar.js

astar.js

astar.js 5.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 caller's axis. */
77const AXIS_TIE_BIAS = 0.001;
78
79/**
80 * Neighbour order: most distance-to-goal reduction first, then preferred axis
81 * (horizontal for mobs, vertical for players) so opposing pathfinders diverge.
82 */
83export function orderedCardinals (fromX, fromY, goalX, goalY, preferVertical = false)
84{
85 const currentDist = Math.abs(goalX - fromX) + Math.abs(goalY - fromY);
86 return CARDINALS
87 .map((dir) =>
88 {
89 const nx = fromX + dir.x;
90 const ny = fromY + dir.y;
91 const nextDist = Math.abs(goalX - nx) + Math.abs(goalY - ny);
92 return {
93 dir,
94 reduction: currentDist - nextDist,
95 vertical: dir.y !== 0
96 };
97 })
98 .sort((a, b) =>
99 {
100 if (b.reduction !== a.reduction)
101 { return b.reduction - a.reduction; }
102 if (a.vertical !== b.vertical)
103 {
104 if (preferVertical)
105 { return a.vertical ? -1 : 1; }
106 return a.vertical ? 1 : -1;
107 }
108 return 0;
109 })
110 .map((entry) => entry.dir);
111}
112
113/**
114 * @param {object} [options]
115 * @param {boolean} [options.preferVertical] players prefer vertical; mobs (default) prefer horizontal
116 * @param {(x: number, y: number) => number} [options.stepCost] movement cost into a tile (default 1)
117 */
118export function findPath (startX, startY, goalX, goalY, isWalkable, minX, minY, maxX, maxY, options = {})
119{
120 const preferVertical = !!options.preferVertical;
121 const stepCost = typeof options.stepCost === "function" ? options.stepCost : null;
122 if (!isWalkable(goalX, goalY) || !isWalkable(startX, startY))
123 { return []; }
124
125 if (startX === goalX && startY === goalY)
126 { return []; }
127
128 const width = maxX - minX + 1;
129 const height = maxY - minY + 1;
130 if (width <= 0 || height <= 0)
131 { return []; }
132
133 function index (x, y)
134 {
135 return (y - minY) * width + (x - minX);
136 }
137
138 const inBounds = (x, y) => x >= minX && y >= minY && x <= maxX && y <= maxY;
139 const cameFrom = new Int32Array(width * height).fill(-1);
140 const gScore = new Float64Array(width * height).fill(Infinity);
141 const closed = new Uint8Array(width * height);
142 const startIndex = index(startX, startY);
143 gScore[startIndex] = 0;
144
145 const open = new MinHeap();
146 open.push({ x: startX, y: startY, f: Math.abs(goalX - startX) + Math.abs(goalY - startY) });
147
148 while (open.size > 0)
149 {
150 const current = open.pop();
151 if (!inBounds(current.x, current.y))
152 { continue; }
153
154 const currentIndex = index(current.x, current.y);
155 if (closed[currentIndex])
156 { continue; }
157 closed[currentIndex] = 1;
158
159 if (current.x === goalX && current.y === goalY)
160 { return reconstruct(cameFrom, current.x, current.y, minX, minY, width); }
161
162 for (const dir of orderedCardinals(current.x, current.y, goalX, goalY, preferVertical))
163 {
164 const nx = current.x + dir.x;
165 const ny = current.y + dir.y;
166 if (!inBounds(nx, ny) || !isWalkable(nx, ny))
167 { continue; }
168
169 const neighborIndex = index(nx, ny);
170 if (closed[neighborIndex])
171 { continue; }
172
173 const cost = stepCost ? Math.max(0.001, Number(stepCost(nx, ny)) || 1) : 1;
174 const tentative = gScore[currentIndex] + cost;
175 if (tentative >= gScore[neighborIndex])
176 { continue; }
177
178 cameFrom[neighborIndex] = currentIndex;
179 gScore[neighborIndex] = tentative;
180 const h = Math.abs(goalX - nx) + Math.abs(goalY - ny);
181 const stepIsVertical = dir.y !== 0;
182 const preferredStep = preferVertical ? stepIsVertical : !stepIsVertical;
183 const bias = preferredStep ? 0 : AXIS_TIE_BIAS;
184 open.push({ x: nx, y: ny, f: tentative + h + bias });
185 }
186 }
187
188 return [];
189}
190
191function reconstruct (cameFrom, x, y, minX, minY, width)
192{
193 const path = [];
194 let cx = x;
195 let cy = y;
196 while (true)
197 {
198 path.push({ x: cx, y: cy });
199 const idx = (cy - minY) * width + (cx - minX);
200 const prev = cameFrom[idx];
201 if (prev < 0)
202 { break; }
203 cx = minX + (prev % width);
204 cy = minY + Math.floor(prev / width);
205 }
206 path.reverse();
207 if (path.length > 0)
208 { path.shift(); }
209 return path;
210}
211
212export function chunkBoundsAround (tileX, tileY, chunkRadius)
213{
214 const chunkX = tileToChunk(tileX);
215 const chunkY = tileToChunk(tileY);
216 const minChunkX = chunkX - chunkRadius;
217 const minChunkY = chunkY - chunkRadius;
218 const maxChunkX = chunkX + chunkRadius;
219 const maxChunkY = chunkY + chunkRadius;
220 return {
221 minX: minChunkX * CHUNK_SIZE,
222 minY: minChunkY * CHUNK_SIZE,
223 maxX: (maxChunkX + 1) * CHUNK_SIZE - 1,
224 maxY: (maxChunkY + 1) * CHUNK_SIZE - 1
225 };
226}
227
228export { tileToLocal };