Introduction

A* is a shortest-path algorithm that combines the exact path cost so far with a heuristic estimate of the remaining distance. It is popular because it is much more directed than Dijkstra’s algorithm while still producing optimal paths when the heuristic is admissible.

Core Idea of A*

For each node n, A* tracks:

• 'g(n): the exact cost from the start to n'
• 'h(n): the heuristic estimate from n to the goal'
• 'f(n) = g(n) + h(n)'

The algorithm always expands the open node with the lowest f score.

If h never overestimates the true remaining cost, A* is optimal. In grid pathfinding, Manhattan distance is a common heuristic when movement is limited to four directions.

Data Structures You Need

A practical implementation uses:

• a priority queue for the open set
• a map of best-known g scores
• a came_from map for path reconstruction
• a closed set or stale-entry check to avoid useless work

Here is a compact Python implementation for a 2D grid:

1import heapq
2
3
4def heuristic(a, b):
5    return abs(a[0] - b[0]) + abs(a[1] - b[1])
6
7
8def astar(grid, start, goal):
9    rows, cols = len(grid), len(grid[0])
10    open_heap = [(0, start)]
11    came_from = {}
12    g_score = {start: 0}
13
14    while open_heap:
15        _, current = heapq.heappop(open_heap)
16
17        if current == goal:
18            return reconstruct_path(came_from, current)
19
20        r, c = current
21        for nr, nc in neighbors(r, c, rows, cols):
22            if grid[nr][nc] == 1:
23                continue
24
25            neighbor = (nr, nc)
26            tentative_g = g_score[current] + 1
27
28            if tentative_g < g_score.get(neighbor, float("inf")):
29                came_from[neighbor] = current
30                g_score[neighbor] = tentative_g
31                f_score = tentative_g + heuristic(neighbor, goal)
32                heapq.heappush(open_heap, (f_score, neighbor))
33
34    return None
35
36
37def neighbors(r, c, rows, cols):
38    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
39        nr, nc = r + dr, c + dc
40        if 0 <= nr < rows and 0 <= nc < cols:
41            yield nr, nc
42
43
44def reconstruct_path(came_from, current):
45    path = [current]
46    while current in came_from:
47        current = came_from[current]
48        path.append(current)
49    path.reverse()
50    return path

Here 0 means walkable and 1 means blocked.

Example Usage

1grid = [
2    [0, 0, 0, 0],
3    [1, 1, 0, 1],
4    [0, 0, 0, 0],
5    [0, 1, 1, 0],
6]
7
8path = astar(grid, (0, 0), (3, 3))
9print(path)

The output is the shortest path if one exists.

Choosing the Heuristic

The heuristic is what makes A* efficient. Good heuristics point the search toward the goal without overestimating.

Common choices:

• Manhattan distance for four-direction grids
• Euclidean distance for continuous or eight-direction movement
• domain-specific lower bounds in routing or planning systems

If the heuristic is always zero, A* collapses into Dijkstra’s algorithm.

Why Path Reconstruction Matters

Many beginners get the search to reach the goal but forget to store how each node was reached. Without came_from, you know the cost but not the actual path.

That is why every time a better route to a neighbor is found, the predecessor mapping must be updated.

Common Pitfalls

The biggest mistake is using a heuristic that overestimates the true remaining cost. That can make A* faster, but it can also destroy optimality.

Another issue is failing to update a node when a cheaper path is found later. A* correctness depends on keeping the best-known g score.

People also often ignore stale priority-queue entries. In simple implementations this is acceptable, but you must still rely on the best g score rather than trusting every popped queue entry blindly.

Finally, choose movement costs and heuristic units consistently. If they do not measure the same thing, the search behavior becomes distorted.

Summary

• A* combines exact path cost and heuristic estimate through f(n) = g(n) + h(n).
• Use a priority queue, g scores, and a predecessor map.
• Choose an admissible heuristic if you need optimal paths.
• Store predecessors so you can reconstruct the final route.
• Keep the heuristic and movement cost model aligned with the problem domain.