A*

This is the one. Every pathfinding tutorial builds toward this moment. A* (pronounced “A-star”) is the algorithm used in more shipped games than any other — from Age of Empires to Stardew Valley to AAA blockbusters. It’s optimal like Dijkstra’s and fast like Greedy Best-First, because it’s actually both of them fused together.

The insight is elegant: Dijkstra’s tracks the real cost from start to each tile (g). Greedy Best-First estimates the remaining cost to the goal (h). A* simply adds them together: f = g + h. Prioritise by f, and you’re guaranteed to find the shortest (or cheapest) path while exploring far fewer tiles than either algorithm alone.

What You’ll Master:

• The f = g + h formula and what each term actually means
• Why A* beats Dijkstra’s on speed without sacrificing correctness
• Where Best-First can fail and how A* fixes it
• Weighted terrain in an optimal algorithm
• The open/closed list pattern

Prerequisites:

• Dijkstra’s (you understand g cost)
• Greedy Best-First (you understand heuristics)

The Formula That Changes Everything

Watch the tile counts in the status bar. A* almost always explores fewer tiles than Greedy Best-First while guaranteeing the optimal path — something Greedy can’t promise.

On some maps Greedy will find the right answer anyway, but on others (especially with concave obstacles like the spiral above) it gets lured down dead ends and can’t recover. A* doesn’t have this problem because it balances the actual cost already paid against the estimated cost remaining.

The formula is three letters:

f = g + h

• g — the real, proven cost to reach this tile from the start (Dijkstra’s part)
• h — the heuristic estimate of cost from here to the goal (Best-First’s part)
• f — the best-guess total cost of a path through this tile

A* always expands the node with the lowest f. Tiles that are genuinely close to the start and close to the goal get processed first. Tiles far in the wrong direction have high g and high h, so they wait at the back of the queue — often never processed at all.

The Implementation

A* is Dijkstra’s with one extra field on each node:

class AStarNode {
    constructor(x, y, parent = null, g = 0, targetX = 0, targetY = 0) {
        this.x = x;
        this.y = y;
        this.parent = parent;
        this.g = g;                                  // actual cost from start
        this.h = manhattan(x, y, targetX, targetY);  // heuristic estimate
        this.f = this.g + this.h;                    // total score
    }
    key() { return `${this.x},${this.y}`; }
}

function manhattan(x1, y1, x2, y2) {
    return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}

function findPathAStar(startX, startY, targetX, targetY, map) {
    const startNode = new AStarNode(startX, startY, null, 0, targetX, targetY);
    const openList = [startNode];
    const closedSet = new Set();
    const bestG = {};
    bestG[startNode.key()] = 0;

    while (openList.length > 0) {
        // Always process the node with the lowest f score
        openList.sort((a, b) => a.f - b.f);
        const current = openList.shift();

        // Skip if we already found a better route here
        if (closedSet.has(current.key())) continue;
        closedSet.add(current.key());

        // Arrived!
        if (current.x === targetX && current.y === targetY) {
            return buildPath(current);
        }

        for (const dir of DIRECTIONS) {
            const nx = current.x + dir.x;
            const ny = current.y + dir.y;
            if (!isWalkable(nx, ny, map)) continue;

            const newG = current.g + terrainCost(nx, ny, map);
            const key = `${nx},${ny}`;

            // Only queue this neighbour if we've found a new best route to it
            if (bestG[key] === undefined || newG < bestG[key]) {
                bestG[key] = newG;
                openList.push(new AStarNode(nx, ny, current, newG, targetX, targetY));
            }
        }
    }

    return null; // unreachable
}

function buildPath(endNode) {
    const path = [];
    let cur = endNode;
    while (cur.parent) { path.unshift({ x: cur.x, y: cur.y }); cur = cur.parent; }
    return path;
}

That’s it. The only differences from Dijkstra’s are the h and f fields and the fact that you sort by f instead of g.

Choosing the Right Heuristic

The heuristic must never overestimate the real cost — if it does, A* loses its guarantee of finding the optimal path. A heuristic that never overestimates is called admissible.

Manhattan distance — the standard for 4-directional grid movement:

function manhattan(x1, y1, x2, y2) {
    return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}

Chebyshev distance — for 8-directional movement (including diagonals):

function chebyshev(x1, y1, x2, y2) {
    return Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2));
}

Euclidean distance — also admissible, slightly better for open maps but slower to compute:

function euclidean(x1, y1, x2, y2) {
    return Math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2);
}

Weighted heuristic — trade optimality for speed by multiplying h:

// w > 1 makes the search faster but potentially suboptimal
// w = 1 is standard A*
// w = 0 degenerates to Dijkstra's
const f = g + w * h; // where w is your weight factor

For most games, w = 1.2 gives paths that are “good enough” and run noticeably faster on crowded maps.

Combining A* with Terrain Costs

Add terrain costs to the g calculation and you get the best of all worlds — optimal paths that respect both terrain difficulty and heuristic direction:

const TERRAIN_COST = { floor: 1, road: 0.5, mud: 4 };

function terrainCost(x, y, map) {
    return TERRAIN_COST[map[y][x]] ?? 1;
}

// In the main loop, just change the g calculation:
const newG = current.g + terrainCost(nx, ny, map);

A* with terrain costs will prefer roads to reach a distant target even if the direct tile-count path goes through mud. Dijkstra’s does this too, but A* gets there faster.

Tie-Breaking for Cleaner Paths

When many tiles share the same f score, the order they’re processed can make paths look jagged. A small tie-breaking nudge produces neater results:

// Add a tiny bias toward tiles closer to the target
// This breaks ties in favour of more "direct" routes
this.f = this.g + this.h + this.h * 0.001;

The 0.001 is small enough to never overestimate, but enough to guide A* toward cleaner diagonals when f values are equal.

When to Use Each Algorithm

You now have the whole family:

A* is the default choice for tile-based pathfinding. Reach for the others only when you have a specific reason.

Next up: Bringing it Together — we’ll build a full stealth game demo where a guard uses A* to hunt you down.