A* Pathfinding Algorithm Explained (Python, Grid Example)

Dijkstra's algorithm explores outward in every direction equally, like a ripple in a pond. When you only need the route to one goal, that wastes effort on directions that lead away from it. A* (A-star) adds a guess of the remaining distance, so it searches towards the goal first. It is the standard pathfinding algorithm in games, robots and route planners.

f = g + h#

For each vertex, A* combines:

• g: the real cost from the start to this vertex (what Dijkstra uses);
• h: a heuristic, an estimate of the cost from this vertex to the goal;
• f = g + h: the estimated cost of the whole route through this vertex.

It always expands the vertex with the smallest f. With h = 0 for every vertex, A* is exactly Dijkstra.

Heuristics#

A good heuristic is fast to compute and never overestimates the true remaining cost. Such a heuristic is called admissible, and with it A* is guaranteed to find a shortest path.

On a 4-direction grid you can never reach the goal in fewer steps than the Manhattan distance, so it is admissible.

A* on a grid#

The search below also counts how many cells it expands, so we can compare it with Dijkstra (the same function with h = 0):

import heapq

GRID = [
    "S.........",
    ".########.",
    ".#......#.",
    ".#.####.#.",
    ".#....#...",
    ".####.#.#.",
    "......#.#G",
]

def find(ch):
    for r, row in enumerate(GRID):
        if ch in row:
            return r, row.index(ch)

def search(use_heuristic):
    start, goal = find("S"), find("G")
    def h(cell):
        if not use_heuristic:
            return 0
        return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])   # Manhattan
    g = {start: 0}
    parent = {start: None}
    heap = [(h(start), 0, start)]
    expanded = 0
    while heap:
        f, cost, cell = heapq.heappop(heap)
        if cost > g[cell]:
            continue
        expanded += 1
        if cell == goal:
            path = []
            while cell:
                path.append(cell)
                cell = parent[cell]
            return cost, expanded, path[::-1]
        r, c = cell
        for nr, nc in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
            if 0 <= nr < len(GRID) and 0 <= nc < len(GRID[0]) and GRID[nr][nc] != "#":
                new = cost + 1
                if new < g.get((nr, nc), float("inf")):
                    g[(nr, nc)] = new
                    parent[(nr, nc)] = cell
                    heapq.heappush(heap, (new + h((nr, nc)), new, (nr, nc)))
    return None

cost_d, expanded_d, _ = search(use_heuristic=False)
cost_a, expanded_a, path = search(use_heuristic=True)
print(f"Dijkstra: path length {cost_d}, cells expanded {expanded_d}")
print(f"A*:       path length {cost_a}, cells expanded {expanded_a}")

picture = [list(row) for row in GRID]
for r, c in path[1:-1]:
    picture[r][c] = "*"
print("\n".join("".join(row) for row in picture))

Dijkstra: path length 15, cells expanded 33
A*:       path length 15, cells expanded 27
S*********
.########*
.#......#*
.#.####.#*
.#....#..*
.####.#.#*
......#.#G

Both find a path of the same length (A* with an admissible heuristic is still optimal), but A* expands fewer cells because the heuristic steers it away from cells that lead away from the goal. On large open maps the saving is usually much bigger.

The heap holds (f, g, cell) tuples. Tuples compare item by item, so f decides the order and, when two entries have the same f, the one with the smaller g comes first. Either tie-break gives a shortest path; some implementations prefer the larger g so the search dives towards the goal.

Weighted grids and games#

Real game maps give terrain different costs (road 1, grass 2, swamp 5). The only change is new = cost + terrain_cost(next_cell). The heuristic must then use the cheapest possible step cost, or it may overestimate and lose the optimality guarantee.

Games also use tricks on top of A*: precomputed navigation meshes instead of tiny grid cells, and hierarchical search (plan a route between regions first, then within each region).

Common mistakes#

Practice#

import heapq

def king_path(rows, cols, start, goal):
    def h(cell):
        return max(abs(cell[0] - goal[0]), abs(cell[1] - goal[1]))
    moves = [(dr, dc) for dr in (-1, 0, 1) for dc in (-1, 0, 1) if (dr, dc) != (0, 0)]
    g = {start: 0}
    heap = [(h(start), 0, start)]
    while heap:
        f, cost, (r, c) = heapq.heappop(heap)
        if (r, c) == goal:
            return cost
        if cost > g[(r, c)]:
            continue
        for dr, dc in moves:
            nxt = (r + dr, c + dc)
            if 0 <= nxt[0] < rows and 0 <= nxt[1] < cols and cost + 1 < g.get(nxt, float("inf")):
                g[nxt] = cost + 1
                heapq.heappush(heap, (cost + 1 + h(nxt), cost + 1, nxt))

print(king_path(5, 5, (0, 0), (4, 4)))
print(king_path(5, 5, (0, 0), (2, 4)))

4
4

Key takeaway#

Next: tracking groups that merge, with Union-Find.