BlueGit

timfa questward

Files

questward / server / src / navigation / astar.js

astar.js

astar.js 5.5 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 */
117export function findPath (startX, startY, goalX, goalY, isWalkable, minX, minY, maxX, maxY, options = {})
118{
119 const preferVertical = !!options.preferVertical;
120 if (!isWalkable(goalX, goalY) || !isWalkable(startX, startY))
121 { return []; }
122
123 if (startX === goalX && startY === goalY)
124 { return []; }
125
126 const width = maxX - minX + 1;
127 const height = maxY - minY + 1;
128 if (width <= 0 || height <= 0)
129 { return []; }
130
131 function index (x, y)
132 {
133 return (y - minY) * width + (x - minX);
134 }
135
136 const inBounds = (x, y) => x >= minX && y >= minY && x <= maxX && y <= maxY;
137 const cameFrom = new Int32Array(width * height).fill(-1);
138 const gScore = new Float64Array(width * height).fill(Infinity);
139 const closed = new Uint8Array(width * height);
140 const startIndex = index(startX, startY);
141 gScore[startIndex] = 0;
142
143 const open = new MinHeap();
144 open.push({ x: startX, y: startY, f: Math.abs(goalX - startX) + Math.abs(goalY - startY) });
145
146 while (open.size > 0)
147 {
148 const current = open.pop();
149 if (!inBounds(current.x, current.y))
150 { continue; }
151
152 const currentIndex = index(current.x, current.y);
153 if (closed[currentIndex])
154 { continue; }
155 closed[currentIndex] = 1;
156
157 if (current.x === goalX && current.y === goalY)
158 { return reconstruct(cameFrom, current.x, current.y, minX, minY, width); }
159
160 for (const dir of orderedCardinals(current.x, current.y, goalX, goalY, preferVertical))
161 {
162 const nx = current.x + dir.x;
163 const ny = current.y + dir.y;
164 if (!inBounds(nx, ny) || !isWalkable(nx, ny))
165 { continue; }
166
167 const neighborIndex = index(nx, ny);
168 if (closed[neighborIndex])
169 { continue; }
170
171 const tentative = gScore[currentIndex] + 1;
172 if (tentative >= gScore[neighborIndex])
173 { continue; }
174
175 cameFrom[neighborIndex] = currentIndex;
176 gScore[neighborIndex] = tentative;
177 const h = Math.abs(goalX - nx) + Math.abs(goalY - ny);
178 const stepIsVertical = dir.y !== 0;
179 const preferredStep = preferVertical ? stepIsVertical : !stepIsVertical;
180 const bias = preferredStep ? 0 : AXIS_TIE_BIAS;
181 open.push({ x: nx, y: ny, f: tentative + h + bias });
182 }
183 }
184
185 return [];
186}
187
188function reconstruct (cameFrom, x, y, minX, minY, width)
189{
190 const path = [];
191 let cx = x;
192 let cy = y;
193 while (true)
194 {
195 path.push({ x: cx, y: cy });
196 const idx = (cy - minY) * width + (cx - minX);
197 const prev = cameFrom[idx];
198 if (prev < 0)
199 { break; }
200 cx = minX + (prev % width);
201 cy = minY + Math.floor(prev / width);
202 }
203 path.reverse();
204 if (path.length > 0)
205 { path.shift(); }
206 return path;
207}
208
209export function chunkBoundsAround (tileX, tileY, chunkRadius)
210{
211 const chunkX = tileToChunk(tileX);
212 const chunkY = tileToChunk(tileY);
213 const minChunkX = chunkX - chunkRadius;
214 const minChunkY = chunkY - chunkRadius;
215 const maxChunkX = chunkX + chunkRadius;
216 const maxChunkY = chunkY + chunkRadius;
217 return {
218 minX: minChunkX * CHUNK_SIZE,
219 minY: minChunkY * CHUNK_SIZE,
220 maxX: (maxChunkX + 1) * CHUNK_SIZE - 1,
221 maxY: (maxChunkY + 1) * CHUNK_SIZE - 1
222 };
223}
224
225export { tileToLocal };