A*

AStar.ts

type Node = {
    x: number;
    y: number;
    g: number;
    h: number;
    f: number;
    parent: Node | null;
};

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

function aStar(grid: number[][], start: [number, number], end: [number, number]): [number, number][] | null {
    const openSet: Node[] = [];
    const closedSet: boolean[][] = Array.from({ length: grid.length }, () =>
        Array(grid[0].length).fill(false)
    );

    const startNode: Node = {
        x: start[0],
        y: start[1],
        g: 0,
        h: heuristic({ x: start[0], y: start[1], g: 0, h: 0, f: 0, parent: null }, { x: end[0], y: end[1], g: 0, h: 0, f: 0, parent: null }),
        f: 0,
        parent: null,
    };

    startNode.f = startNode.g + startNode.h;

    openSet.push(startNode);

    const directions = [
        [0, -1],
        [1, 0],
        [0, 1],
        [-1, 0],
    ];

    while (openSet.length > 0) {
        openSet.sort((a, b) => a.f - b.f);
        const current = openSet.shift()!;

        if (current.x === end[0] && current.y === end[1]) {
            const path: [number, number][] = [];
            let temp: Node | null = current;

            while (temp) {
                path.push([temp.x, temp.y]);
                temp = temp.parent;
            }

            return path.reverse();
        }

        closedSet[current.y][current.x] = true;

        for (const [dx, dy] of directions) {
            const nx = current.x + dx;
            const ny = current.y + dy;

            if (
                ny < 0 || ny >= grid.length ||
                nx < 0 || nx >= grid[0].length ||
                grid[ny][nx] === 1 || closedSet[ny][nx]
            ) {
                continue;
            }

            const neighbor: Node = {
                x: nx,
                y: ny,
                g: current.g + 1,
                h: heuristic({ x: nx, y: ny, g: 0, h: 0, f: 0, parent: null }, { x: end[0], y: end[1], g: 0, h: 0, f: 0, parent: null }),
                f: 0,
                parent: current,
            };

            neighbor.f = neighbor.g + neighbor.h;

            const existing = openSet.find(n => n.x === nx && n.y === ny);

            if (!existing || neighbor.g < existing.g) {
                openSet.push(neighbor);
            }
        }
    }

    return null;
}

// Test

const grid = [
    [0, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 0, 0, 0],
    [0, 1, 1, 0]
];

const start: [number, number] = [0, 0];
const end: [number, number] = [3, 2];

const path = aStar(grid, start, end);

console.log("Path:", path);