/** * 4-connected path to the nearest walkable goal. * Uniform costs use BFS; optional stepCost uses Dijkstra (same API). */ const CARDINALS = Object.freeze([ Object.freeze({ x: 0, y: -1 }), Object.freeze({ x: 1, y: 0 }), Object.freeze({ x: 0, y: 1 }), Object.freeze({ x: -1, y: 0 }) ]); /** * @param {number} startX * @param {number} startY * @param {(x: number, y: number) => boolean} isGoal * @param {(x: number, y: number) => boolean} isWalkable * @param {number} minX * @param {number} minY * @param {number} maxX * @param {number} maxY * @param {{ stepCost?: (x: number, y: number) => number }} [options] * @returns {{ x: number, y: number }[]} path tiles after start (empty if already at goal or unreachable) */ export function findPathToNearestGoal (startX, startY, isGoal, isWalkable, minX, minY, maxX, maxY, options = {}) { if (!isWalkable(startX, startY)) { return []; } if (isGoal(startX, startY)) { return []; } const width = maxX - minX + 1; const height = maxY - minY + 1; if (width <= 0 || height <= 0) { return []; } const stepCost = typeof options.stepCost === "function" ? options.stepCost : null; if (stepCost) { return findPathToNearestGoalWeighted( startX, startY, isGoal, isWalkable, minX, minY, maxX, maxY, width, height, stepCost ); } const inBounds = (x, y) => x >= minX && y >= minY && x <= maxX && y <= maxY; const index = (x, y) => (y - minY) * width + (x - minX); const cameFrom = new Int32Array(width * height).fill(-1); const visited = new Uint8Array(width * height); const startIndex = index(startX, startY); visited[startIndex] = 1; const queue = [{ x: startX, y: startY }]; let head = 0; while (head < queue.length) { const current = queue[head++]; for (const dir of CARDINALS) { const nx = current.x + dir.x; const ny = current.y + dir.y; if (!inBounds(nx, ny) || !isWalkable(nx, ny)) { continue; } const neighborIndex = index(nx, ny); if (visited[neighborIndex]) { continue; } visited[neighborIndex] = 1; cameFrom[neighborIndex] = index(current.x, current.y); if (isGoal(nx, ny)) { return reconstruct(cameFrom, nx, ny, minX, minY, width); } queue.push({ x: nx, y: ny }); } } return []; } /** * Dijkstra to nearest goal when tile step costs are non-uniform. * @param {(x: number, y: number) => number} stepCost */ function findPathToNearestGoalWeighted ( startX, startY, isGoal, isWalkable, minX, minY, maxX, maxY, width, height, stepCost ) { const inBounds = (x, y) => x >= minX && y >= minY && x <= maxX && y <= maxY; const index = (x, y) => (y - minY) * width + (x - minX); const cameFrom = new Int32Array(width * height).fill(-1); const gScore = new Float64Array(width * height).fill(Infinity); const closed = new Uint8Array(width * height); const startIndex = index(startX, startY); gScore[startIndex] = 0; /** @type {{ x: number, y: number, g: number }[]} */ const heap = [{ x: startX, y: startY, g: 0 }]; const siftUp = (i) => { while (i > 0) { const p = (i - 1) >> 1; if (heap[p].g <= heap[i].g) { break; } const tmp = heap[p]; heap[p] = heap[i]; heap[i] = tmp; i = p; } }; const siftDown = (i) => { for (;;) { const left = i * 2 + 1; const right = left + 1; let best = i; if (left < heap.length && heap[left].g < heap[best].g) { best = left; } if (right < heap.length && heap[right].g < heap[best].g) { best = right; } if (best === i) { break; } const tmp = heap[i]; heap[i] = heap[best]; heap[best] = tmp; i = best; } }; const pop = () => { const root = heap[0]; const last = heap.pop(); if (heap.length > 0 && last) { heap[0] = last; siftDown(0); } return root; }; while (heap.length > 0) { const current = pop(); if (!inBounds(current.x, current.y)) { continue; } const currentIndex = index(current.x, current.y); if (closed[currentIndex]) { continue; } closed[currentIndex] = 1; if (isGoal(current.x, current.y) && !(current.x === startX && current.y === startY)) { return reconstruct(cameFrom, current.x, current.y, minX, minY, width); } for (const dir of CARDINALS) { const nx = current.x + dir.x; const ny = current.y + dir.y; if (!inBounds(nx, ny) || !isWalkable(nx, ny)) { continue; } const neighborIndex = index(nx, ny); if (closed[neighborIndex]) { continue; } const cost = Math.max(0.001, Number(stepCost(nx, ny)) || 1); const tentative = gScore[currentIndex] + cost; if (tentative >= gScore[neighborIndex]) { continue; } cameFrom[neighborIndex] = currentIndex; gScore[neighborIndex] = tentative; heap.push({ x: nx, y: ny, g: tentative }); siftUp(heap.length - 1); } } return []; } function reconstruct (cameFrom, x, y, minX, minY, width) { const path = []; let cx = x; let cy = y; while (true) { path.push({ x: cx, y: cy }); const idx = (cy - minY) * width + (cx - minX); const prev = cameFrom[idx]; if (prev < 0) { break; } cx = minX + (prev % width); cy = minY + Math.floor(prev / width); } path.reverse(); if (path.length > 0) { path.shift(); } return path; }