A* Pathfinding Algorithm | Game AI Tutorial

Why A*?

Moving straight towards a target is easy. Moving around walls? Not so much.

A* is the industry standard because it's both fast (like Greedy Best-First) and accurate (like Dijkstra). It finds the shortest path while intelligently guessing which direction is promising.

Interactive A* Solver

Click to place walls. Drag the Green (Start) or Red (End) points. The algorithm updates instantly.

Blue = Path

How It Works (The Math)

A* analyzes cells (nodes) using three values:

G Cost: Distance from Start Node to current node.
H Cost (Heuristic): Estimated distance from current node to End Node (ignoring walls).
F Cost: G + H. The algorithm always explores the node with the lowest F cost first.

a-star-logic.js

function findPath(start, end) {
    let openSet = [start];
    let closedSet = [];

    while (openSet.length > 0) {
        // 1. Get node with lowest F cost
        let current = getLowestFCost(openSet);
        
        if (current === end) {
            return retracePath(start, end);
        }

        openSet.remove(current);
        closedSet.push(current);

        // 2. Check neighbors
        for (let neighbor of current.neighbors) {
            if (closedSet.includes(neighbor) || !neighbor.walkable) {
                continue;
            }

            let newCostToNeighbor = current.gCost + getDistance(current, neighbor);
            
            if (newCostToNeighbor < neighbor.gCost || !openSet.includes(neighbor)) {
                neighbor.gCost = newCostToNeighbor;
                neighbor.hCost = getDistance(neighbor, end);
                neighbor.parent = current;

                if (!openSet.includes(neighbor)) {
                    openSet.push(neighbor);
                }
            }
        }
    }
}