Why A*? From BFS to Heuristics

Enemies need to walk from Start to Goal around whatever walls are on the grid, and recompute that route the instant a tower blocks their way. That's a pathfinding problem, and the algorithm this course builds, A* (pronounced "A-star"), is the industry-standard answer for exactly this situation.

Starting point: breadth-first search

BFS explores outward from the start, one ring of neighbors at a time, and is guaranteed to find the shortest path on an unweighted grid like this one. The problem: it explores equally in every direction, including straight away from the goal, wasting a lot of work checking cells that were never going to lead anywhere useful.

BFS explores a growing circle around the start,
even the parts pointing away from the goal:

        ░░░░░░░
      ░░░░░░░░░░░
    ░░░░S░░░░░░░░░   G
      ░░░░░░░░░░░
        ░░░░░░░

A*'s idea: let the goal pull the search toward it

A* keeps BFS's guarantee of finding the shortest path, but adds a heuristic, an estimate of "how far is this cell from the goal", to prioritize exploring cells that are actually making progress. Every cell A* considers gets a score:

f(n) = g(n) + h(n)

• g(n): the actual cost to reach cell n from the start, along the best path found so far.
• h(n): the heuristic, an estimate of the remaining cost from n to the goal.
• f(n): the combined score, "total estimated cost of a path through this cell." A* always explores the cell with the lowest f next.

The heuristic for a grid: Manhattan distance

On a grid where movement is only up/down/left/right (no diagonals), the natural heuristic is Manhattan distance, the number of grid steps between two cells ignoring any obstacles:

float heuristic(GridPos a, GridPos b) {
    return std::abs(a.row - b.row) + std::abs(a.col - b.col);
}

This heuristic is admissible, it never overestimates the true remaining cost (walls can only make the real path longer, never shorter than the straight-line grid distance), and that's the one property A* needs to guarantee it still finds the truly shortest path, not just a plausible-looking one.

Open set and closed set

A* tracks two collections while it searches:

Each step: pull the lowest-f cell out of the open set, mark it closed, look at its neighbors, and for each one either add it to the open set or update its score if a cheaper path to it was just found. The search ends the moment the goal itself is pulled from the open set.