A* search

August 4, 2026

A planner searching a grid has to decide which cell to look at next. Dijkstra’s algorithm always takes the cheapest cell reached so far. That is correct, and it spreads outward in every direction, including directly away from the goal.

A* adds one thing: an estimate of the distance still to go.

Click anywhere below to move the goal.

Shaded cells were examined. The path is the same path Dijkstra would find. The difference is how much of the map had to be looked at to find it.

The ordering rule

Both algorithms keep a frontier of cells waiting to be examined and always take the best one. They differ only in what counts as best.

Dijkstra orders by cost so far:

A* orders by cost so far plus estimated cost remaining:

Set the heuristic to None and the tool becomes Dijkstra exactly, because $h(n) = 0$ makes $f(n) = g(n)$. That is the whole relationship between the two algorithms.

What the estimate has to satisfy

$h$ must never overestimate the true remaining cost. A heuristic with that property is admissible, and it is what makes the path optimal.

The argument is short. A* stops when it takes the goal off the frontier. If some other route were cheaper, one of its cells would still be waiting with

and a smaller $f$ would have been taken first. So no cheaper route can be outstanding when the goal is reached.

Overestimating breaks that. The search becomes confident about a direction it has no right to be confident about, and it can commit to a worse route.

A stronger condition, consistency, requires

for every step from $n$ to $n'$. Consistency implies admissibility and adds a guarantee: $f$ never decreases along the search, so once a cell is examined its cost is final and it never needs revisiting.

Choosing $h$ for the grid

The right heuristic depends on which moves are legal, and getting this wrong is the most common way to break A* by accident.

With four-way movement, the true distance ignoring obstacles is the Manhattan distance:

With eight-way movement, a diagonal covers one row and one column at a cost of $\sqrt{2}$ instead of $2$. The exact obstacle-free distance is the octile distance:

Turn diagonals on and switch to Manhattan. It now counts a diagonal as $2$ when it costs $\sqrt{2}$, so it overestimates, and the path is no longer guaranteed optimal. The readout compares against the true cost whenever that happens.

Euclidean distance is always admissible, but on a grid it underestimates badly, because no vehicle restricted to eight directions can travel the hypotenuse. Underestimating is safe and slow: more cells get examined for the same answer.

Weighting the estimate

The weight slider multiplies $h$:

At $w = 1$ this is ordinary A*. Above that it is weighted A*, which examines dramatically fewer cells and gives up the optimality guarantee in a bounded way. The path it returns costs at most $w$ times the best one.

Push the weight up and watch the shaded region collapse toward a narrow corridor running at the goal, while the path cost creeps above the optimum. That is the trade in its clearest form: a planner that is sure looks at less.

Real planners use this deliberately. When a robot must replan every control cycle, a route five percent long that arrives in time beats an optimal one that misses the deadline.

What the shape of the search tells you

Set the heuristic to None. The examined region is a disc: Dijkstra has no idea where the goal is, so it grows evenly.

Switch to Octile. The disc collapses into an ellipse elongated toward the goal.

Now draw a wall between start and goal. The search spills along the barrier and pools against it, because every cell near the wall looks good to the heuristic and is expensive to actually reach. Straight-line estimates cannot see walls, and that gap between the estimate and reality is exactly where the extra work goes.

That failure is why planners in cluttered spaces often precompute better estimates than a straight line.

The code

The same search in C++, including the tolerance that stops it doing the work twice:

// Straight moves cost 1, diagonals cost the hypotenuse.
constexpr double kStraight = 1.0;
const double kDiagonal = std::sqrt(2.0);

// Costs are sums of 1 and sqrt(2), so two routes that are equal in exact
// arithmetic can differ in the last bit. Without a tolerance that
// difference reads as an improvement, and the search reopens a cell it
// had already settled, expanding it twice for no reason.
constexpr double kEps = 1e-9;

struct Grid {
    int width, height;
    std::vector<char> wall;      // wall[y * width + x]

    bool open(int x, int y) const {
        return x >= 0 && y >= 0 && x < width && y < height && !wall[y * width + x];
    }
};

struct Edge { int index; double cost; };

// A diagonal is only legal when both straight moves bracketing it are
// clear, so a path never clips the corner of an obstacle.
std::vector<Edge> neighbours(const Grid& grid, int index) {
    static constexpr int kStraightDirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static constexpr int kDiagonalDirs[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

    const int x = index % grid.width, y = index / grid.width;
    std::vector<Edge> out;

    for (const auto& d : kStraightDirs) {
        const int nx = x + d[0], ny = y + d[1];
        if (grid.open(nx, ny)) out.push_back({ny * grid.width + nx, kStraight});
    }
    for (const auto& d : kDiagonalDirs) {
        const int nx = x + d[0], ny = y + d[1];
        if (!grid.open(nx, ny)) continue;
        if (!grid.open(nx, y) || !grid.open(x, ny)) continue;
        out.push_back({ny * grid.width + nx, kDiagonal});
    }
    return out;
}

// The exact obstacle-free distance under eight-way movement: as many
// diagonals as both axes allow, then straight moves for the remainder.
double octile(int dx, int dy) {
    const int lo = std::min(dx, dy), hi = std::max(dx, dy);
    return kDiagonal * lo + (hi - lo);
}

struct Node { int index; double g, f; };

// Ordering on f, breaking ties toward the larger g. std::priority_queue
// pops the greatest element, so the comparison is inverted: true means
// "goes later". The tie-break drives the search at the goal instead of
// letting it fan out across every equally scored cell. It changes the
// picture completely and changes the answer not at all.
struct Worse {
    bool operator()(const Node& a, const Node& b) const {
        if (a.f != b.f) return a.f > b.f;
        return a.g < b.g;
    }
};

// weight = 1 is ordinary A*. Above that it is weighted A*.
std::vector<int> astar(const Grid& grid, int start, int goal, double weight = 1.0) {
    const int count = grid.width * grid.height;
    if (!grid.open(start % grid.width, start / grid.width)) return {};
    if (!grid.open(goal % grid.width, goal / grid.width)) return {};

    std::vector<double> g(count, std::numeric_limits<double>::infinity());
    std::vector<int> cameFrom(count, -1);
    std::vector<char> closed(count, 0);

    const int gx = goal % grid.width, gy = goal / grid.width;
    auto h = [&](int i) {
        return weight * octile(std::abs(i % grid.width - gx),
                               std::abs(i / grid.width - gy));
    };

    std::priority_queue<Node, std::vector<Node>, Worse> frontier;
    g[start] = 0.0;
    frontier.push({start, 0.0, h(start)});       // f = g + h, and g is 0 here

    while (!frontier.empty()) {
        const Node current = frontier.top();
        frontier.pop();

        // Stale entry: a cheaper route to this cell was found after this
        // one was queued. Lazy deletion, because a binary heap cannot
        // cheaply update a key in place.
        if (current.g > g[current.index] + kEps) continue;
        if (closed[current.index]) continue;
        closed[current.index] = 1;

        if (current.index == goal) {
            std::vector<int> path;
            for (int at = goal; at != -1; at = cameFrom[at]) path.push_back(at);
            std::reverse(path.begin(), path.end());
            return path;
        }

        for (const Edge& edge : neighbours(grid, current.index)) {
            const double tentative = current.g + edge.cost;

            // The tolerance again, and the one that matters most: an
            // improvement has to be a real one, not the last bit of
            // difference between two routes that cost the same.
            if (tentative >= g[edge.index] - kEps) continue;

            // An inconsistent heuristic can make a closed cell look
            // cheaper later. Reopening it keeps the result correct.
            closed[edge.index] = 0;

            g[edge.index] = tentative;
            cameFrom[edge.index] = current.index;
            frontier.push({edge.index, tentative, tentative + h(edge.index)});
        }
    }

    return {};   // no route
}

Where this leaves you

A* is optimal, complete, and optimally efficient: no algorithm using the same heuristic can examine fewer cells and still guarantee the best path. That is about as strong as guarantees get.

The cost is that it searches a discrete graph. A grid fine enough to plan smooth motion has enormous numbers of cells, and a robot arm’s configuration space has one dimension per joint. Sampling-based planners exist for that case, and they give up completeness in exchange for not enumerating the space at all.

Between the two sits the question this tool is really about: how much does your estimate know, and how much work does that knowledge save?