/** * 4-connected BFS from the start tile to the nearest walkable goal. * First goal reached is shortest path length (no top-left Chebyshev bias). */ 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 * @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) { 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 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 []; } 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; }