Chapters

On this page

All lessons

Intro to Search
soon
Depth-First Search
soon
Breadth-First Search
soon
Dijkstra's Algorithm
soon
A* Algorithmcurrent
Anytime Weighted A*
Chapter 1

The A* Algorithm

A* (pronounced "A-star") is the most widely used pathfinding algorithm in computer science and game development. It finds the shortest path from a start to a goal by combining the actual distance travelled with a smart estimate of the remaining distance.

1. What is pathfinding?

Imagine you need to get from your house to a coffee shop in a city you've never visited. You open a map app, tap your destination, and — almost instantly — it draws a route. Under the hood, the app is running a pathfinding algorithm: a procedure that searches through a graph of intersections and roads to find the shortest or fastest route between two points.

We model this problem as a grid(or graph): nodes represent locations, and edges connect adjacent locations. The algorithm's job is to find the least-cost sequence of edges that gets from a start node to a goal node.

Many algorithms can solve this — Breadth-First Search, Dijkstra's, Greedy Best-First — but A* is the one that achieves optimality while remaining efficient by using a heuristic to guide the search.

2. The Grid

We represent the world as a 2D grid. Each cell is either passable (the algorithm can walk through it) or a wall(impassable). Try drawing walls below to create a maze — you'll run the algorithm through this very map in the next sections.

Try it
Left-click and drag to paint walls. Right-click to erase. Use the toolbar to move the start (green flag) or goal (red target).
Tool:

The algorithm needs two special cells: a start and a goal. It will explore adjacent cells outward from the start, tracking the cost so far and an estimate of what's left, until it reaches the goal.

3. The cost function: g(n)

Every time the algorithm steps from one cell to a neighbour, it incurs a cost. On a uniform grid with no terrain, this is simply 1 per step.

We call the total cost of the path from the start to a node n its g-score, written g(n). The algorithm always knows the exact g-score for every node it has visited — because it got there and tracked every step.

The node with the lowest final g-score is on the optimal path.

g-scores from the start

4
3
2
3
4
5
6
3
2
1
2
3
4
5
2
1
★
1
2
3
4
3
2
1
2
3
4
5
4
3
2
3
4
5
6

Each number = steps from start (★). Cells further away cost more.

4. The heuristic: h(n)

g(n) tells us how far we've come. But the algorithm also needs to guess how far it still needs to go. This guess is the heuristic, written h(n).

The most common heuristic on a grid is Manhattan distance: the number of horizontal + vertical steps between two cells, ignoring obstacles.

h(n) = |n.row − goal.row| + |n.col − goal.col|

For A* to guarantee an optimal path, the heuristic must never overestimatethe true remaining cost. A heuristic with this property is called admissible. Manhattan distance is always admissible on a grid where each step costs ≥ 1.

A* combines both scores: f(n) = g(n) + h(n). The node with the lowest f-score is always expanded next.

h-scores toward the goal

10
9
8
7
6
5
4
9
8
7
6
5
4
3
8
7
6
5
4
3
★
9
8
7
6
5
4
3
10
9
8
7
6
5
4

Each number = Manhattan distance to goal (★). Cells closer to goal have lower h.

Why not just use h(n)?
A purely heuristic search (Greedy Best-First) picks the node that looks closest to the goal — but it can take long, winding paths because it ignores the actual cost travelled. A* balances both to guarantee the shortest path.

5. A* in action

Now for the main event. A* maintains two sets of nodes:

  • Open set — nodes discovered but not yet fully explored.
  • Closed set — nodes already expanded; we know their optimal cost.
  • Current node — the node being expanded this step.
  • Path — the final optimal route (shown once goal is reached).

Draw your map, then click Run A*. Use the slider to scrub through every step, or press Play to animate. The pseudocode panel highlights the exact line executing at each step.

Heuristic:
Tool:

Draw your map above, then click Run A* to generate the step trace.

a-star.pseudo
1function aStar(start, goal, grid):
2  openSet ← {start}
3  gScore[start] ← 0;  fScore[start] ← h(start, goal)
4  while openSet is not empty:
5    current ← node in openSet with lowest fScore
6    if current = goal: return reconstruct_path(cameFrom, current)
7    move current from openSet → closedSet
8    for each neighbour of current:
9      if neighbour in closedSet: continue
10      tentative_g ← gScore[current] + cost(current, neighbour)
11      if tentative_g < gScore[neighbour]:
12        cameFrom[neighbour] ← current
13        gScore[neighbour] ← tentative_g
14        fScore[neighbour] ← tentative_g + h(neighbour, goal)
15        add neighbour to openSet if not already there
16  return failure  // no path found
Things to try
  • Draw a wall corridor — watch A* navigate around it.
  • Switch between Manhattan and Euclidean heuristic and compare node counts.
  • Place the goal inside a completely closed wall ring — A* will exhaust the open set and report no path.
  • Move the start or goal and hit Run again — the grid is re-solved instantly.

6. Terrain costs and weighted grids

In the real world, not all paths cost the same. Moving through a forest is slower than a road; crossing water might cost even more. We model this by giving each cell a movement cost:

Empty / Grass×1
Forest×3
Water×10
Wallimpassable

A* handles this seamlessly — terrain cost is factored into the g-score. The algorithm will prefer to go around expensive terrain if the detour costs less overall. Try running A* on the weighted grid below and observe how the path avoids water.

Tool:

Draw your map above, then click Run A* to generate the step trace.

7. Tips, pitfalls & variants

Admissibility
If your heuristic overestimates the true distance, A* is no longer guaranteed to find the optimal path. Always make sure h(n) ≤ true remaining cost.
Diagonal movement
If you allow diagonal moves, use Chebyshev distance or Euclidean distance as your heuristic — Manhattan distance underestimates too aggressively, slowing things down.
Tie-breaking
When many nodes have the same f-score, A* can explore them in any order — leading to unnecessary work. A small tie-breaking nudge (e.g. slightly scaling h) dramatically reduces explored nodes.
Weighted A* (WA*)
Multiplying h by a weight w > 1 makes A* faster but potentially sub-optimal (the path cost is at most w times the optimal). This is a common game-dev trade-off.

8. What's next?

You've seen how A* balances explored cost and estimated remaining cost to efficiently find optimal paths. A great next step is to compare it against Dijkstra's algorithm, which is essentially A* with h(n) = 0— no heuristic at all. It's guaranteed optimal but explores far more nodes. Understanding the difference will solidify your intuition for why heuristics matter.

Back to Home
Dijkstra's Algorithm Soon

Continue your Learning

Deepen your understanding of A* with these video walkthroughs.

A* in a nutshell

Understanding the A* Algorithm

Found this helpful?

These resources are free — if they saved you time, a coffee keeps them going.

Buy me a coffee