A* Search

The problem

A game character must walk to a target; a delivery app must route a driver. We want the shortest path from a start to a goal, and we want to find it fast.

Dijkstra’s algorithm finds the shortest path but explores in every direction like ripples — even directly away from the goal. A* adds a sense of direction.

f = g + h

For every cell n, A* computes:

• g(n) — the exact cost of the best path found so far from the start to n.
• h(n) — a heuristic: an estimate of the cost from n to the goal.
• f(n) = g(n) + h(n) — the estimated total length of a path through n.

It always expands the cell with the smallest f. Cells that move towards the goal get small f values and are explored first.

The algorithm

open   ← {start}        (cells waiting to be explored)
closed ← {}             (cells already explored)
g[start] ← 0
while open is not empty:
    current ← the cell in open with the smallest f
    if current is the goal: follow the parent pointers back → path
    move current from open to closed
    for each neighbour n of current:
        if n is a wall or in closed: skip
        if g[current] + cost < g[n]:
            g[n] ← g[current] + cost
            parent[n] ← current
            add n to open

In the 3D model: cyan cells are in the open set, purple cells are closed (explored), the yellow raised cell is the current one, and the final path is orange.

Heuristics

On a grid where you can move up, down, left and right, the classic heuristic is the Manhattan distance:

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

A heuristic is admissible if it never overestimates the true remaining cost. With an admissible heuristic, A* is guaranteed to return a shortest path. Manhattan distance is admissible here because walls can only make the real path longer.

A* vs Dijkstra vs greedy

Try all three in the model on the same maze.

Code

import heapq

def a_star(grid, start, goal):
    """grid: list of strings, '#' = wall. start/goal: (row, col)."""
    rows, cols = len(grid), len(grid[0])
    h = lambda p: abs(p[0] - goal[0]) + abs(p[1] - goal[1])
    g = {start: 0}
    parent = {}
    open_heap = [(h(start), 0, start)]
    closed = set()
    while open_heap:
        f, cost, cur = heapq.heappop(open_heap)
        if cur in closed:
            continue
        if cur == goal:
            path = [cur]
            while cur in parent:
                cur = parent[cur]
                path.append(cur)
            return path[::-1]
        closed.add(cur)
        r, c = cur
        for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != '#':
                ng = cost + 1
                if ng < g.get((nr, nc), float('inf')):
                    g[(nr, nc)] = ng
                    parent[(nr, nc)] = cur
                    heapq.heappush(open_heap, (ng + h((nr, nc)), ng, (nr, nc)))
    return None

maze = ["S..#....",
        ".#.#.##.",
        ".#...#..",
        ".####.#.",
        "......#G"]
print(a_star(maze, (0, 0), (4, 7)))

Where is A* used?

Video games (NPC movement), robot navigation, GPS routing (with extra speed-ups), puzzle solving (8-puzzle, Rubik’s cube with pattern-database heuristics) and AI planning.

Common mistakes

• Using a heuristic that overestimates (e.g. Euclidean distance × 2) — faster, but no longer guaranteed optimal.
• Forgetting the closed set, so cells are expanded again and again.
• Using Manhattan distance when diagonal moves are allowed (it then overestimates).