BlueGit

timfa questward

Files

questward / shared / navigation / bfs.js

bfs.js

bfs.js 2.3 KiB Download Raw
1/**
2 * 4-connected BFS from the start tile to the nearest walkable goal.
3 * First goal reached is shortest path length (no top-left Chebyshev bias).
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 * @returns {{ x: number, y: number }[]} path tiles after start (empty if already at goal or unreachable)
23 */
24export function findPathToNearestGoal (startX, startY, isGoal, isWalkable, minX, minY, maxX, maxY)
25{
26 if (!isWalkable(startX, startY))
27 { return []; }
28 if (isGoal(startX, startY))
29 { return []; }
30
31 const width = maxX - minX + 1;
32 const height = maxY - minY + 1;
33 if (width <= 0 || height <= 0)
34 { return []; }
35
36 const inBounds = (x, y) => x >= minX && y >= minY && x <= maxX && y <= maxY;
37 const index = (x, y) => (y - minY) * width + (x - minX);
38
39 const cameFrom = new Int32Array(width * height).fill(-1);
40 const visited = new Uint8Array(width * height);
41 const startIndex = index(startX, startY);
42 visited[startIndex] = 1;
43
44 const queue = [{ x: startX, y: startY }];
45 let head = 0;
46
47 while (head < queue.length)
48 {
49 const current = queue[head++];
50 for (const dir of CARDINALS)
51 {
52 const nx = current.x + dir.x;
53 const ny = current.y + dir.y;
54 if (!inBounds(nx, ny) || !isWalkable(nx, ny))
55 { continue; }
56 const neighborIndex = index(nx, ny);
57 if (visited[neighborIndex])
58 { continue; }
59 visited[neighborIndex] = 1;
60 cameFrom[neighborIndex] = index(current.x, current.y);
61 if (isGoal(nx, ny))
62 { return reconstruct(cameFrom, nx, ny, minX, minY, width); }
63 queue.push({ x: nx, y: ny });
64 }
65 }
66
67 return [];
68}
69
70function reconstruct (cameFrom, x, y, minX, minY, width)
71{
72 const path = [];
73 let cx = x;
74 let cy = y;
75 while (true)
76 {
77 path.push({ x: cx, y: cy });
78 const idx = (cy - minY) * width + (cx - minX);
79 const prev = cameFrom[idx];
80 if (prev < 0)
81 { break; }
82 cx = minX + (prev % width);
83 cy = minY + Math.floor(prev / width);
84 }
85 path.reverse();
86 if (path.length > 0)
87 { path.shift(); }
88 return path;
89}