A* Search Algorithm: Heuristic Pathfinding Explained

A* (A-star) is the gold standard for pathfinding in games, robotics, and navigation systems. It finds the shortest path like Dijkstra but explores far fewer nodes by using a heuristic to guide the search toward the goal. The result is an algorithm that is both optimal (finds the true shortest path) and efficient (skips irrelevant areas of the graph).

The Core Formula

A* evaluates each node using three values:

• g(n): The actual cost from the start node to node n. This is what Dijkstra tracks.
• h(n): The heuristic estimate of the cost from node n to the goal. This is the intelligence A* adds.
• f(n) = g(n) + h(n): The total estimated cost of the cheapest path through node n.

A* always expands the node with the lowest f(n) value. By combining the known cost g(n) with the estimated remaining cost h(n), A* prioritizes nodes that are likely on the shortest path.

Why A* Works

If the heuristic h(n) never overestimates the true cost to the goal (admissible heuristic), A* is guaranteed to find the optimal path. Here is the intuition: if h(n) underestimates, then f(n) = g(n) + h(n) is an optimistic estimate. A* will never skip a node that could be on the shortest path because its f-value will always be at most the true shortest path cost.

Admissible Heuristics

A heuristic h(n) is admissible if h(n) <= h*(n) for all nodes n, where h*(n) is the true shortest distance from n to the goal.

Common admissible heuristics for grids:

• Manhattan Distance (L1): |x1-x2| + |y1-y2|. Admissible for 4-directional movement.
• Euclidean Distance (L2): sqrt((x1-x2)^2 + (y1-y2)^2). Admissible for any movement, but weaker for 4-directional grids.
• Chebyshev Distance (L-infinity): max(|x1-x2|, |y1-y2|). Admissible for 8-directional movement.

Consistent (Monotone) Heuristics

A heuristic is consistent if for every node n and neighbor n’ with edge cost c: h(n) <= c(n, n’) + h(n’). Consistent heuristics are always admissible. Manhattan distance is consistent for 4-directional grids. Consistency ensures that once A* expands a node, it has found the shortest path to that node (like Dijkstra).

A* Implementation for Grid Pathfinding

import heapq

def a_star_grid(grid, start, goal):
    """
    A* search on a 2D grid.
    grid: 2D list where 0 = walkable, 1 = wall
    start: (row, col) tuple
    goal: (row, col) tuple
    Returns: shortest path as list of (row, col), or empty list
    """
    rows, cols = len(grid), len(grid[0])

    def heuristic(pos):
        """Manhattan distance heuristic."""
        return abs(pos[0] - goal[0]) + abs(pos[1] - goal[1])

    def neighbors(pos):
        """4-directional neighbors."""
        r, c = pos
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
                yield (nr, nc)

    # g_score[pos] = cost of cheapest known path from start to pos
    g_score = {start: 0}

    # f_score[pos] = g_score[pos] + heuristic(pos)
    f_score = {start: heuristic(start)}

    # Priority queue: (f_score, position)
    open_set = [(f_score[start], start)]

    # For path reconstruction
    came_from = {}

    # Track expanded nodes
    closed_set = set()

    while open_set:
        current_f, current = heapq.heappop(open_set)

        if current == goal:
            return reconstruct_path(came_from, current)

        if current in closed_set:
            continue
        closed_set.add(current)

        for neighbor in neighbors(current):
            if neighbor in closed_set:
                continue

            tentative_g = g_score[current] + 1  # Cost 1 per step

            if tentative_g < g_score.get(neighbor, float('inf')):
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f = tentative_g + heuristic(neighbor)
                f_score[neighbor] = f
                heapq.heappush(open_set, (f, neighbor))

    return []  # No path found


def reconstruct_path(came_from, current):
    """Reconstruct the path from start to current."""
    path = [current]
    while current in came_from:
        current = came_from[current]
        path.append(current)
    path.reverse()
    return path

Example Usage

grid = [
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
]

start = (0, 0)
goal = (5, 7)

path = a_star_grid(grid, start, goal)
print(f"Path length: {len(path) - 1} steps")
print(f"Path: {path}")
# Path navigates around walls efficiently

A* with Weighted Edges

For grids with varying terrain costs:

def a_star_weighted_grid(grid, start, goal):
    """
    A* on a weighted grid where grid[r][c] = movement cost.
    0 means impassable wall.
    """
    rows, cols = len(grid), len(grid[0])

    def heuristic(pos):
        return abs(pos[0] - goal[0]) + abs(pos[1] - goal[1])

    g_score = {start: 0}
    open_set = [(heuristic(start), start)]
    came_from = {}
    closed_set = set()

    while open_set:
        _, current = heapq.heappop(open_set)

        if current == goal:
            return reconstruct_path(came_from, current), g_score[goal]

        if current in closed_set:
            continue
        closed_set.add(current)

        r, c = current
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > 0:
                neighbor = (nr, nc)
                if neighbor in closed_set:
                    continue

                move_cost = grid[nr][nc]
                tentative_g = g_score[current] + move_cost

                if tentative_g < g_score.get(neighbor, float('inf')):
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g
                    f = tentative_g + heuristic(neighbor)
                    heapq.heappush(open_set, (f, neighbor))

    return [], float('inf')

A* on General Graphs

A* is not limited to grids. It works on any weighted graph:

def a_star_graph(graph, start, goal, heuristic_fn):
    """
    A* search on a general weighted graph.
    graph: dict mapping node -> list of (neighbor, weight)
    heuristic_fn: function(node) -> estimated cost to goal
    """
    g_score = {start: 0}
    open_set = [(heuristic_fn(start), start)]
    came_from = {}
    closed_set = set()

    while open_set:
        _, current = heapq.heappop(open_set)

        if current == goal:
            return reconstruct_path(came_from, current), g_score[goal]

        if current in closed_set:
            continue
        closed_set.add(current)

        for neighbor, weight in graph[current]:
            if neighbor in closed_set:
                continue

            tentative_g = g_score[current] + weight

            if tentative_g < g_score.get(neighbor, float('inf')):
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f = tentative_g + heuristic_fn(neighbor)
                heapq.heappush(open_set, (f, neighbor))

    return [], float('inf')

Comparing A*, Dijkstra, and BFS

A* vs Dijkstra

Dijkstra is A* with h(n) = 0 for all nodes. Without a heuristic, Dijkstra expands nodes in all directions equally. A* focuses the search toward the goal, exploring fewer nodes.

def compare_expansion(grid, start, goal):
    """
    Compare nodes expanded by Dijkstra vs A* on the same grid.
    """
    # Dijkstra (h = 0)
    dijkstra_expanded = set()
    g = {start: 0}
    pq = [(0, start)]
    while pq:
        d, node = heapq.heappop(pq)
        if node in dijkstra_expanded:
            continue
        dijkstra_expanded.add(node)
        if node == goal:
            break
        r, c = node
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if (0 <= nr < len(grid) and 0 <= nc < len(grid[0])
                    and grid[nr][nc] == 0):
                nd = d + 1
                if nd < g.get((nr, nc), float('inf')):
                    g[(nr, nc)] = nd
                    heapq.heappush(pq, (nd, (nr, nc)))

    # A* (Manhattan heuristic)
    astar_expanded = set()
    g = {start: 0}
    h = lambda p: abs(p[0] - goal[0]) + abs(p[1] - goal[1])
    pq = [(h(start), start)]
    while pq:
        _, node = heapq.heappop(pq)
        if node in astar_expanded:
            continue
        astar_expanded.add(node)
        if node == goal:
            break
        r, c = node
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if (0 <= nr < len(grid) and 0 <= nc < len(grid[0])
                    and grid[nr][nc] == 0):
                nd = g[node] + 1
                if nd < g.get((nr, nc), float('inf')):
                    g[(nr, nc)] = nd
                    f = nd + h((nr, nc))
                    heapq.heappush(pq, (f, (nr, nc)))

    print(f"Dijkstra expanded: {len(dijkstra_expanded)} nodes")
    print(f"A* expanded: {len(astar_expanded)} nodes")
    print(f"A* saved: {len(dijkstra_expanded) - len(astar_expanded)} nodes")

A* vs BFS

BFS finds shortest paths in unweighted graphs and expands nodes level by level. A* can be thought of as “informed BFS” that prioritizes promising directions. On a large open grid, BFS explores a growing circle while A* explores a narrow corridor toward the goal.

When A* Degrades to Dijkstra

If the heuristic h(n) = 0 for all nodes, A* becomes Dijkstra. This happens when you have no useful way to estimate the remaining distance. For example, in a social network graph, there is no spatial heuristic.

When A* is Not the Right Choice

• Unweighted graph with no goal node: Use BFS.
• Negative edge weights: A* does not handle them. Use Bellman-Ford.
• All-pairs shortest paths: Use Floyd-Warshall.
• No admissible heuristic available: Use Dijkstra to guarantee optimality.

8-Directional Movement

For grids where diagonal movement is allowed:

import math

def a_star_8dir(grid, start, goal):
    """
    A* with 8-directional movement.
    Diagonal moves cost sqrt(2), cardinal moves cost 1.
    """
    rows, cols = len(grid), len(grid[0])
    SQRT2 = math.sqrt(2)

    def heuristic(pos):
        """Chebyshev distance for 8-directional grids."""
        dx = abs(pos[0] - goal[0])
        dy = abs(pos[1] - goal[1])
        return max(dx, dy) + (SQRT2 - 1) * min(dx, dy)

    directions = [
        (0, 1, 1), (0, -1, 1), (1, 0, 1), (-1, 0, 1),
        (1, 1, SQRT2), (1, -1, SQRT2), (-1, 1, SQRT2), (-1, -1, SQRT2)
    ]

    g_score = {start: 0}
    open_set = [(heuristic(start), start)]
    came_from = {}
    closed_set = set()

    while open_set:
        _, current = heapq.heappop(open_set)

        if current == goal:
            return reconstruct_path(came_from, current)

        if current in closed_set:
            continue
        closed_set.add(current)

        r, c = current
        for dr, dc, cost in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
                neighbor = (nr, nc)
                if neighbor in closed_set:
                    continue

                tentative_g = g_score[current] + cost
                if tentative_g < g_score.get(neighbor, float('inf')):
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g
                    heapq.heappush(open_set, (tentative_g + heuristic(neighbor), neighbor))

    return []

Optimizing A* Performance

Tie-Breaking

When multiple nodes have the same f-value, breaking ties can significantly affect performance. Preferring nodes with higher g-values (closer to the goal) often helps.

# Instead of (f, position), use (f, -g, position) to break ties
# This prefers nodes closer to the goal
heapq.heappush(open_set, (f, -tentative_g, neighbor))

Bidirectional A*

Run A* from both start and goal simultaneously. When the two searches meet, combine the paths.

def bidirectional_a_star(grid, start, goal):
    """
    Bidirectional A* that searches from both ends.
    Meets in the middle for ~2x speedup.
    """
    rows, cols = len(grid), len(grid[0])

    def h_forward(pos):
        return abs(pos[0] - goal[0]) + abs(pos[1] - goal[1])

    def h_backward(pos):
        return abs(pos[0] - start[0]) + abs(pos[1] - start[1])

    g_fwd = {start: 0}
    g_bwd = {goal: 0}
    pq_fwd = [(h_forward(start), start)]
    pq_bwd = [(h_backward(goal), goal)]
    came_fwd = {}
    came_bwd = {}
    closed_fwd = set()
    closed_bwd = set()
    best_cost = float('inf')
    meeting_point = None

    def expand(pq, g, came, closed, other_g, h_fn):
        nonlocal best_cost, meeting_point
        if not pq:
            return False

        _, current = heapq.heappop(pq)
        if current in closed:
            return True
        closed.add(current)

        # Check if this node was reached by the other search
        if current in other_g:
            total = g[current] + other_g[current]
            if total < best_cost:
                best_cost = total
                meeting_point = current

        r, c = current
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
                nb = (nr, nc)
                if nb in closed:
                    continue
                new_g = g[current] + 1
                if new_g < g.get(nb, float('inf')):
                    came[nb] = current
                    g[nb] = new_g
                    heapq.heappush(pq, (new_g + h_fn(nb), nb))
        return True

    while pq_fwd or pq_bwd:
        expand(pq_fwd, g_fwd, came_fwd, closed_fwd, g_bwd, h_forward)
        expand(pq_bwd, g_bwd, came_bwd, closed_bwd, g_fwd, h_backward)

        # Termination check
        if meeting_point is not None:
            min_f = float('inf')
            if pq_fwd:
                min_f = min(min_f, pq_fwd[0][0])
            if pq_bwd:
                min_f = min(min_f, pq_bwd[0][0])
            if best_cost <= min_f:
                break

    if meeting_point is None:
        return []

    # Reconstruct path
    path_fwd = []
    node = meeting_point
    while node in came_fwd:
        path_fwd.append(node)
        node = came_fwd[node]
    path_fwd.append(node)
    path_fwd.reverse()

    path_bwd = []
    node = came_bwd.get(meeting_point)
    while node is not None:
        path_bwd.append(node)
        node = came_bwd.get(node)

    return path_fwd + path_bwd

Complexity Analysis

• Time: O(E log V) in the worst case, same as Dijkstra. But in practice, a good heuristic makes A* much faster.
• Space: O(V) for the open and closed sets.
• With perfect heuristic (h(n) = h*(n)): A* expands only nodes on the shortest path, achieving O(path_length * log(path_length)).

The quality of the heuristic determines performance. A stronger (higher, still admissible) heuristic means fewer nodes expanded.

Practice Problems

1. Shortest Path in Binary Matrix (LeetCode 1091) - BFS or A* on grid
2. Path With Minimum Effort (LeetCode 1631) - A* or Dijkstra on grid
3. Minimum Cost to Make at Least One Valid Path (LeetCode 1368) - Modified A*
4. Sliding Puzzle (LeetCode 773) - A* on state space
5. 8-Puzzle / 15-Puzzle - Classic A* application
6. Maze Solving - Direct grid A*

Key Takeaways

A* is Dijkstra with intelligence. The heuristic function h(n) guides the search toward the goal, dramatically reducing the number of nodes explored compared to uninformed algorithms. With an admissible heuristic, A* guarantees optimal paths. Manhattan distance works for 4-directional grids, Chebyshev for 8-directional, and Euclidean for free movement. When no heuristic is available, fall back to Dijkstra. A* is the standard for game pathfinding, robot navigation, and any problem where you know the goal location.