/**
 * Поиск пути A* по тайловой сетке.
 * Движение 4-стороннее; диагонали опциональны (с запретом «среза углов» через блокеры).
 */

export interface Grid {
    width: number;
    height: number;
    /** Проходим ли тайл. */
    isWalkable(x: number, y: number): boolean;
}

interface Node {
    x: number;
    y: number;
    g: number;
    f: number;
    parent: Node | null;
}

function heuristic(a: { x: number; y: number }, b: { x: number; y: number }): number {
    return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}

/**
 * Возвращает путь (без стартового тайла, включая конечный) или null, если пути нет.
 * Включение диагоналей добавляет шаги (±1, ±1), но только если оба ортогональных
 * соседа проходимы (без среза углов).
 */
export function findPath(
    grid: Grid,
    start: { x: number; y: number },
    goal: { x: number; y: number },
    allowDiagonal = false
): { x: number; y: number }[] | null {
    if (!grid.isWalkable(goal.x, goal.y)) return null;
    if (start.x === goal.x && start.y === goal.y) return [];

    const key = (x: number, y: number) => y * grid.width + x;
    const open: Node[] = [];
    const best = new Map<number, number>();
    const startNode: Node = { x: start.x, y: start.y, g: 0, f: heuristic(start, goal), parent: null };
    open.push(startNode);
    best.set(key(start.x, start.y), 0);

    const dirs4 = [
        { x: 1, y: 0 },
        { x: -1, y: 0 },
        { x: 0, y: 1 },
        { x: 0, y: -1 }
    ];

    while (open.length > 0) {
        // Извлекаем узел с минимальным f (карты маленькие, линейного поиска достаточно).
        let idx = 0;
        for (let i = 1; i < open.length; i++) {
            if (open[i].f < open[idx].f) idx = i;
        }
        const cur = open.splice(idx, 1)[0];

        if (cur.x === goal.x && cur.y === goal.y) {
            const path: { x: number; y: number }[] = [];
            for (let n: Node | null = cur; n !== null; n = n.parent) {
                path.unshift({ x: n.x, y: n.y });
            }
            path.shift(); // убираем стартовый тайл
            return path;
        }

        const neighbors = allowDiagonal
            ? [...dirs4, { x: 1, y: 1 }, { x: 1, y: -1 }, { x: -1, y: 1 }, { x: -1, y: -1 }]
            : dirs4;

        for (const d of neighbors) {
            const nx = cur.x + d.x;
            const ny = cur.y + d.y;
            if (nx < 0 || ny < 0 || nx >= grid.width || ny >= grid.height) continue;
            if (!grid.isWalkable(nx, ny)) continue;
            if (d.x !== 0 && d.y !== 0) {
                // Диагональ разрешена только без среза углов.
                if (!grid.isWalkable(cur.x + d.x, cur.y) || !grid.isWalkable(cur.x, cur.y + d.y)) continue;
            }

            const g = cur.g + 1;
            const k = key(nx, ny);
            if (best.has(k) && best.get(k)! <= g) continue;
            best.set(k, g);
            open.push({ x: nx, y: ny, g, f: g + heuristic({ x: nx, y: ny }, goal), parent: cur });
        }
    }

    return null;
}
/**
 * Путь к ближайшей проходимой клетке, соседней с goal (8-соседство).
 * Идём к краю цели: goal может быть непроходим (тайл NPC/объекта) или занят —
 * стоять на нём не нужно. Пути нет — null.
 */
export function findPathToNeighbor(
    grid: Grid,
    start: { x: number; y: number },
    goal: { x: number; y: number }
): { x: number; y: number }[] | null {
    let best: { x: number; y: number }[] | null = null;
    for (let dy = -1; dy <= 1; dy++) {
        for (let dx = -1; dx <= 1; dx++) {
            if (dx === 0 && dy === 0) continue;
            const tx = goal.x + dx;
            const ty = goal.y + dy;
            if (tx < 0 || ty < 0 || tx >= grid.width || ty >= grid.height) continue;
            if (!grid.isWalkable(tx, ty)) continue;
            const p = findPath(grid, start, { x: tx, y: ty });
            if (p && (best === null || p.length < best.length)) best = p;
        }
    }
    return best;
}