| 1 | /** |
| 2 | * 4-connected path to the nearest walkable goal. |
| 3 | * Uniform costs use BFS; optional stepCost uses Dijkstra (same API). |
| 4 | */ |
| 5 | |
| 6 | const 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 | */ |
| 25 | export 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 | */ |
| 93 | function 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 | |
| 199 | function 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 | } |