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