/**
 * 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;
}
