/**
 * Поиск пути 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;
    /** Порядок вставки: при равном f выбираем ранее вставленный (детерминизм обхода). */
    seq: number;
}

interface Vec2 {
    x: number;
    y: number;
}

/** Соседство 4/8 (диагонали без среза углов проверяются отдельно). */
const DIRS4: readonly Vec2[] = [
    { x: 1, y: 0 },
    { x: -1, y: 0 },
    { x: 0, y: 1 },
    { x: 0, y: -1 }
];
const DIRS8: readonly Vec2[] = [...DIRS4, { x: 1, y: 1 }, { x: 1, y: -1 }, { x: -1, y: 1 }, { x: -1, y: -1 }];

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

/** a важнее b в куче: меньшее f, при равном — более ранней вставки. */
function before(a: Node, b: Node): boolean {
    return a.f < b.f || (a.f === b.f && a.seq < b.seq);
}

/** Мин-куча открытых узлов по f — вместо линейного скана (O(log n) на операцию). */
class OpenHeap {
    private nodes: Node[] = [];

    get size(): number {
        return this.nodes.length;
    }

    push(n: Node): void {
        const a = this.nodes;
        a.push(n);
        let i = a.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (!before(a[i]!, a[p]!)) break;
            a[i] = a[p]!;
            a[p] = n;
            i = p;
        }
    }

    pop(): Node | null {
        const a = this.nodes;
        const top = a[0] ?? null;
        const last = a.pop()!;
        if (a.length > 0) {
            a[0] = last;
            let i = 0;
            for (;;) {
                const l = 2 * i + 1;
                const r = l + 1;
                let m = i;
                if (l < a.length && before(a[l]!, a[m]!)) m = l;
                if (r < a.length && before(a[r]!, a[m]!)) m = r;
                if (m === i) break;
                const t = a[i]!;
                a[i] = a[m]!;
                a[m] = t;
                i = m;
            }
        }
        return top;
    }
}

/**
 * Общий каркас A*: цель и эвристика — параметры (многоцелевой прогон
 * findPathToNeighbor переиспользует тот же цикл). Возвращает конечный узел
 * (путь — по цепочке parent) или null.
 */
function astar(
    grid: Grid,
    start: Vec2,
    dirs: readonly Vec2[],
    isGoal: (x: number, y: number) => boolean,
    h: (x: number, y: number) => number
): Node | null {
    const key = (x: number, y: number) => y * grid.width + x;
    const open = new OpenHeap();
    const best = new Map<number, number>();
    let seq = 0;
    open.push({ x: start.x, y: start.y, g: 0, f: h(start.x, start.y), parent: null, seq: seq++ });
    best.set(key(start.x, start.y), 0);

    while (open.size > 0) {
        const cur = open.pop()!;
        if (isGoal(cur.x, cur.y)) return cur;

        for (const d of dirs) {
            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 + h(nx, ny), parent: cur, seq: seq++ });
        }
    }

    return null;
}

/** Путь из цепочки parent (без стартового тайла, включая конечный). */
function tracePath(node: Node): { x: number; y: number }[] {
    const path: { x: number; y: number }[] = [];
    for (let n: Node | null = node; n !== null; n = n.parent) {
        path.unshift({ x: n.x, y: n.y });
    }
    path.shift(); // убираем стартовый тайл
    return path;
}

/**
 * Возвращает путь (без стартового тайла, включая конечный) или null, если пути нет.
 * Включение диагоналей добавляет шаги (±1, ±1), но только если оба ортогональных
 * соседа проходимы (без среза углов).
 */
export function findPath(
    grid: Grid,
    start: Vec2,
    goal: Vec2,
    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 node = astar(
        grid,
        start,
        allowDiagonal ? DIRS8 : DIRS4,
        (x, y) => x === goal.x && y === goal.y,
        (x, y) => manhattan({ x, y }, goal)
    );
    return node ? tracePath(node) : null;
}

/**
 * Путь к ближайшей проходимой клетке, соседней с goal (8-соседство).
 * Идём к краю цели: goal может быть непроходим (тайл NPC/объекта) или занят —
 * стоять на нём не нужно. Один прогон A* со всеми 8 соседями как целями
 * (эвристика — минимум манхэттена по целям); пути нет — null.
 */
export function findPathToNeighbor(
    grid: Grid,
    start: Vec2,
    goal: Vec2
): { x: number; y: number }[] | null {
    const goals: Vec2[] = [];
    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)) goals.push({ x: tx, y: ty });
        }
    }
    if (goals.length === 0) return null;
    if (goals.some((g) => g.x === start.x && g.y === start.y)) return [];

    const goalKeys = new Set(goals.map((g) => g.y * grid.width + g.x));
    const node = astar(
        grid,
        start,
        DIRS4,
        (x, y) => goalKeys.has(y * grid.width + x),
        (x, y) => {
            let min = Infinity;
            for (const g of goals) {
                const d = Math.abs(x - g.x) + Math.abs(y - g.y);
                if (d < min) min = d;
            }
            return min;
        }
    );
    return node ? tracePath(node) : null;
}