Pathfinding Algorithm

A* Search

“The Smart Navigator”

Time: O((V + E) log V)

Space: O(V)

Shortest Path: Guaranteed

History

A* (A-Star) was developed in 1968 for Shakey the Robot at Stanford. The researchers wanted Shakey to navigate a room without bumping into things, but Dijkstra's algorithm was too slow for the hardware of the time.

They added a "heuristic" (a best guess) to guide the search. The result was an algorithm that combines the precision of Dijkstra with the speed of a greedy approach. It is widely considered the crown jewel of pathfinding in game development.

How It Works

A* is Dijkstra with a cheat sheet. It decides which node to explore next based on two numbers: 1. g(n): The cost to get here (same as Dijkstra). 2. h(n): The estimated cost to get to the goal (the heuristic).

The Magic Formula

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

The Algorithm Step-by-Step

Initialize: Add start node to the open set with its f-score.
Select Best: Choose the node with the lowest f-score.
Check Goal: If we are there, trace the path.
Evaluate: For each neighbor, calculate the cost to get there. If it's a better path than we knew before, record it, calculate the heuristic, and add it to the open set.
Repeat: Until the goal is found.

The Heuristic

This is the "educated guess." In a grid, we usually use the Manhattan Distance (counting tiles) or Euclidean Distance (straight line) to estimate how far the goal is. This acts as a magnet, pulling the search toward the finish line.

Time ComplexityO((V + E) log V)

The worst case is the same as Dijkstra, but in practice, A* visits significantly fewer nodes because it doesn't waste time exploring the wrong direction.

Space ComplexityO(V)

It still needs to store the open and closed lists. Memory is usually the bottleneck for A* on massive maps.

Data StructurePriority Queue (ordered by f-score)

The core data structure powering A* Search.

Visual PatternDirected beam that expands specifically toward the target

How this algorithm appears during visualization.

Code Walkthrough

Real implementations in multiple programming languages. Select a language to view idiomatic code.

1import heapq
2
3def heuristic(a: tuple[int, int], b: tuple[int, int]) -> int:
4    """Manhattan distance heuristic."""
5    return abs(a[0] - b[0]) + abs(a[1] - b[1])
6
7def astar(grid: list[list[int]], start: tuple[int, int], end: tuple[int, int]) -> list[tuple[int, int]] | None:
8    """Find shortest path using A* with Manhattan heuristic."""
9    rows, cols = len(grid), len(grid[0])
10    g_score = {start: 0}
11    f_score = {start: heuristic(start, end)}
12    parents = {start: None}
13    open_set = [(f_score[start], start)]
14    closed_set = set()
15    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
16
17    while open_set:
18        _, current = heapq.heappop(open_set)
19
20        if current in closed_set:
21            continue
22        closed_set.add(current)
23
24        if current == end:
25            path = []
26            while current:
27                path.append(current)
28                current = parents[current]
29            return path[::-1]
30
31        row, col = current
32        for dr, dc in directions:
33            neighbor = (row + dr, col + dc)
34            nr, nc = neighbor
35
36            if (0 <= nr < rows and 0 <= nc < cols
37                    and grid[nr][nc] == 0
38                    and neighbor not in closed_set):
39                tentative_g = g_score[current] + 1
40
41                if neighbor not in g_score or tentative_g < g_score[neighbor]:
42                    g_score[neighbor] = tentative_g
43                    f = tentative_g + heuristic(neighbor, end)
44                    f_score[neighbor] = f
45                    parents[neighbor] = current
46                    heapq.heappush(open_set, (f, neighbor))
47
48    return None