BlueGit

timfa questward

Files

questward / shared / navigation / bfs.js

bfs.js

bfs.js 5.1 KiB Download Raw
1/**
2 * 4-connected path to the nearest walkable goal.
3 * Uniform costs use BFS; optional stepCost uses Dijkstra (same API).
4 */
5
6const CARDINALS = Object.freeze([
7 Object.freeze({ x: 0, y: -1 }),
8 Object.freeze({ x: 1, y: 0 }),
9 Object.freeze({ x: 0, y: 1 }),
10 Object.freeze({ x: -1, y: 0 })
11]);
12
13/**
14 * @param {number} startX
15 * @param {number} startY
16 * @param {(x: number, y: number) => boolean} isGoal
17 * @param {(x: number, y: number) => boolean} isWalkable
18 * @param {number} minX
19 * @param {number} minY
20 * @param {number} maxX
21 * @param {number} maxY
22 * @param {{ stepCost?: (x: number, y: number) => number }} [options]
23 * @returns {{ x: number, y: number }[]} path tiles after start (empty if already at goal or unreachable)
24 */
25export function findPathToNearestGoal (startX, startY, isGoal, isWalkable, minX, minY, maxX, maxY, options = {})
26{
27 if (!isWalkable(startX, startY))
28 { return []; }
29 if (isGoal(startX, startY))
30 { return []; }
31
32 const width = maxX - minX + 1;
33 const height = maxY - minY + 1;
34 if (width <= 0 || height <= 0)
35 { return []; }
36
37 const stepCost = typeof options.stepCost === "function" ? options.stepCost : null;
38 if (stepCost)
39 {
40 return findPathToNearestGoalWeighted(
41 startX,
42 startY,
43 isGoal,
44 isWalkable,
45 minX,
46 minY,
47 maxX,
48 maxY,
49 width,
50 height,
51 stepCost
52 );
53 }
54
55 const inBounds = (x, y) => x >= minX && y >= minY && x <= maxX && y <= maxY;
56 const index = (x, y) => (y - minY) * width + (x - minX);
57
58 const cameFrom = new Int32Array(width * height).fill(-1);
59 const visited = new Uint8Array(width * height);
60 const startIndex = index(startX, startY);
61 visited[startIndex] = 1;
62
63 const queue = [{ x: startX, y: startY }];
64 let head = 0;
65
66 while (head < queue.length)
67 {
68 const current = queue[head++];
69 for (const dir of CARDINALS)
70 {
71 const nx = current.x + dir.x;
72 const ny = current.y + dir.y;
73 if (!inBounds(nx, ny) || !isWalkable(nx, ny))
74 { continue; }
75 const neighborIndex = index(nx, ny);
76 if (visited[neighborIndex])
77 { continue; }
78 visited[neighborIndex] = 1;
79 cameFrom[neighborIndex] = index(current.x, current.y);
80 if (isGoal(nx, ny))
81 { return reconstruct(cameFrom, nx, ny, minX, minY, width); }
82 queue.push({ x: nx, y: ny });
83 }
84 }
85
86 return [];
87}
88
89/**
90 * Dijkstra to nearest goal when tile step costs are non-uniform.
91 * @param {(x: number, y: number) => number} stepCost
92 */
93function findPathToNearestGoalWeighted (
94 startX,
95 startY,
96 isGoal,
97 isWalkable,
98 minX,
99 minY,
100 maxX,
101 maxY,
102 width,
103 height,
104 stepCost
105)
106{
107 const inBounds = (x, y) => x >= minX && y >= minY && x <= maxX && y <= maxY;
108 const index = (x, y) => (y - minY) * width + (x - minX);
109
110 const cameFrom = new Int32Array(width * height).fill(-1);
111 const gScore = new Float64Array(width * height).fill(Infinity);
112 const closed = new Uint8Array(width * height);
113 const startIndex = index(startX, startY);
114 gScore[startIndex] = 0;
115
116 /** @type {{ x: number, y: number, g: number }[]} */
117 const heap = [{ x: startX, y: startY, g: 0 }];
118
119 const siftUp = (i) =>
120 {
121 while (i > 0)
122 {
123 const p = (i - 1) >> 1;
124 if (heap[p].g <= heap[i].g)
125 { break; }
126 const tmp = heap[p];
127 heap[p] = heap[i];
128 heap[i] = tmp;
129 i = p;
130 }
131 };
132 const siftDown = (i) =>
133 {
134 for (;;)
135 {
136 const left = i * 2 + 1;
137 const right = left + 1;
138 let best = i;
139 if (left < heap.length && heap[left].g < heap[best].g)
140 { best = left; }
141 if (right < heap.length && heap[right].g < heap[best].g)
142 { best = right; }
143 if (best === i)
144 { break; }
145 const tmp = heap[i];
146 heap[i] = heap[best];
147 heap[best] = tmp;
148 i = best;
149 }
150 };
151 const pop = () =>
152 {
153 const root = heap[0];
154 const last = heap.pop();
155 if (heap.length > 0 && last)
156 {
157 heap[0] = last;
158 siftDown(0);
159 }
160 return root;
161 };
162
163 while (heap.length > 0)
164 {
165 const current = pop();
166 if (!inBounds(current.x, current.y))
167 { continue; }
168 const currentIndex = index(current.x, current.y);
169 if (closed[currentIndex])
170 { continue; }
171 closed[currentIndex] = 1;
172
173 if (isGoal(current.x, current.y) && !(current.x === startX && current.y === startY))
174 { return reconstruct(cameFrom, current.x, current.y, minX, minY, width); }
175
176 for (const dir of CARDINALS)
177 {
178 const nx = current.x + dir.x;
179 const ny = current.y + dir.y;
180 if (!inBounds(nx, ny) || !isWalkable(nx, ny))
181 { continue; }
182 const neighborIndex = index(nx, ny);
183 if (closed[neighborIndex])
184 { continue; }
185 const cost = Math.max(0.001, Number(stepCost(nx, ny)) || 1);
186 const tentative = gScore[currentIndex] + cost;
187 if (tentative >= gScore[neighborIndex])
188 { continue; }
189 cameFrom[neighborIndex] = currentIndex;
190 gScore[neighborIndex] = tentative;
191 heap.push({ x: nx, y: ny, g: tentative });
192 siftUp(heap.length - 1);
193 }
194 }
195
196 return [];
197}
198
199function reconstruct (cameFrom, x, y, minX, minY, width)
200{
201 const path = [];
202 let cx = x;
203 let cy = y;
204 while (true)
205 {
206 path.push({ x: cx, y: cy });
207 const idx = (cy - minY) * width + (cx - minX);
208 const prev = cameFrom[idx];
209 if (prev < 0)
210 { break; }
211 cx = minX + (prev % width);
212 cy = minY + Math.floor(prev / width);
213 }
214 path.reverse();
215 if (path.length > 0)
216 { path.shift(); }
217 return path;
218}