A* Algorithm

Overview

A* (A-star) is a graph traversal and pathfinding algorithm that finds the shortest path from a start node to a target node. It combines the benefits of Dijkstra's algorithm (guaranteed optimality) with a heuristic function (efficiency) to guide the search toward the goal.

A* uses an evaluation function f(n) = g(n) + h(n), where:

g(n): Cost from start to current node (known)
h(n): Heuristic estimate from current node to goal (estimated)
f(n): Total estimated cost (g + h)

A* is widely used in game development, robotics, GPS navigation, and any application requiring efficient pathfinding with a known goal.

How It Works

The algorithm follows these steps:

Initialize: Add start node to open set with f(start) = h(start)
Iterate: While open set is not empty:
- Select node with lowest f(n) from open set
- Move it to closed set
- If it's the goal, reconstruct and return path
- For each neighbor:
  - Calculate tentative g(n) = g(current) + cost(current, neighbor)
  - If neighbor not in open set or new path is better, update it
  - Calculate f(n) = g(n) + h(n) and add to open set
Result: Shortest path from start to goal (if exists)

A* Algorithm Pseudocode


AStar(graph, start, goal, heuristic):
    open_set = priority_queue containing (f(start), start)
    closed_set = set()
    g_score[start] = 0
    f_score[start] = heuristic(start, goal)
    parent = {}
    
    while open_set is not empty:
        current = node in open_set with lowest f_score
        if current == goal:
            return reconstruct_path(parent, goal)
        
        open_set.remove(current)
        closed_set.add(current)
        
        for each neighbor of current:
            if neighbor in closed_set:
                continue
            
            tentative_g = g_score[current] + cost(current, neighbor)
            
            if neighbor not in open_set:
                open_set.add(neighbor)
            else if tentative_g >= g_score[neighbor]:
                continue  # Not a better path
            
            parent[neighbor] = current
            g_score[neighbor] = tentative_g
            f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)
    
    return failure  // No path exists

Implementation


import heapq

def heuristic(node, goal):
    """Heuristic function - Manhattan distance for grid"""
    return abs(node[0] - goal[0]) + abs(node[1] - goal[1])

def a_star(graph, start, goal, heuristic_func):
    """
    graph: dict mapping node -> list of (neighbor, cost) tuples
    start: start node
    goal: target node
    heuristic_func: function(node, goal) -> estimated cost
    """
    open_set = [(0, start)]  # (f_score, node)
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic_func(start, goal)}
    closed_set = set()
    
    while open_set:
        current_f, current = heapq.heappop(open_set)
        
        if current == goal:
            # Reconstruct path
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]
        
        closed_set.add(current)
        
        for neighbor, cost in graph.get(current, []):
            if neighbor in closed_set:
                continue
            
            tentative_g = g_score[current] + cost
            
            if neighbor not in g_score or tentative_g < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score[neighbor] = tentative_g + heuristic_func(neighbor, goal)
                heapq.heappush(open_set, (f_score[neighbor], neighbor))
    
    return None  # No path found

# Example: Grid pathfinding
def grid_heuristic(node, goal):
    """Manhattan distance for grid"""
    return abs(node[0] - goal[0]) + abs(node[1] - goal[1])

def a_star_grid(grid, start, goal):
    """A* for 2D grid with obstacles"""
    rows, cols = len(grid), len(grid[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    def get_neighbors(node):
        r, c = node
        neighbors = []
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != 1:
                neighbors.append(((nr, nc), 1))  # Cost 1 for each step
        return neighbors
    
    graph = {}
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1:  # Not an obstacle
                graph[(r, c)] = get_neighbors((r, c))
    
    return a_star(graph, start, goal, grid_heuristic)

Heuristic Functions

The quality of the heuristic function determines A*'s efficiency. A good heuristic should be:

Admissible: never overestimates the true remaining cost, h(n) ≤ h*(n).
Consistent (monotone): h(n) ≤ cost(n, n') + h(n') for every neighbour n', and h(goal) = 0. This is a triangle inequality on the heuristic.

Consistency is the stronger property: every consistent heuristic is admissible, but not every admissible heuristic is consistent. In practice almost all natural heuristics — Manhattan, Euclidean, octile — are consistent, so the distinction rarely bites. It matters enormously when it does; see Optimality below.

Common Heuristics

A heuristic is admissible only with respect to a particular movement model. Matching them up wrongly is the most common way to break A* in practice:

Manhattan Distance — for 4-directional grid movement:
```
h(n) = |x₁ - x₂| + |y₁ - y₂|
```
Not admissible for 8-directional movement, where a diagonal step covers both axes at once and Manhattan overestimates.
Chebyshev Distance — for 8-directional movement where a diagonal costs the same as a straight step:
```
h(n) = max(|x₁ - x₂|, |y₁ - y₂|)
```
Octile Distance — for 8-directional movement where a diagonal costs √2, which is the usual game setup:
```
dx, dy = |x₁ - x₂|, |y₁ - y₂|
h(n) = (dx + dy) + (√2 - 2) × min(dx, dy)
```
Chebyshev underestimates here (still admissible, just weaker); Manhattan overestimates and breaks optimality.
Euclidean Distance — for movement at any angle:
```
h(n) = √((x₁ - x₂)² + (y₁ - y₂)²)
```
Admissible on any grid, but loose for 4- or 8-way movement, so A* explores more than it needs to.

h(n) = 0 is always admissible — and reduces A* to exactly Dijkstra's algorithm. That is the useful mental model: A* is Dijkstra's plus a hint about which direction the goal lies in. Scale matters too: if edge costs are in metres, the heuristic must be in metres.

Complexity Analysis

Time Complexity: O(b^d) for tree search, where b is the branching factor and d the solution depth. On a graph with a closed set, it is bounded by the number of reachable states, O(V + E log V) with a binary heap — the same as Dijkstra's, since A* is Dijkstra's with a modified priority. A good heuristic reduces the constant enormously but does not change the worst-case bound.
Space Complexity: O(b^d) — usually the binding constraint. A* stores every generated node, and running out of memory is the typical failure mode on large searches, well before running out of time. IDA* and SMA* trade time for bounded memory.

Performance depends almost entirely on heuristic quality. With h(n) = 0 A* is exactly Dijkstra's. With a perfect heuristic h(n) = h*(n) it walks straight to the goal — though only if ties are broken in favour of larger g, otherwise it can still wander among equal-f nodes. Between those extremes, a heuristic that dominates another (is closer to h* everywhere while staying admissible) never expands more nodes.

Optimality

The two properties guarantee different things, and conflating them is a common source of subtle bugs:

Admissibility alone guarantees optimality — but only if the search is allowed to reopen closed nodes. If a shorter route to an already-expanded node is discovered later, it must be moved back into the open set and expanded again.
Consistency additionally guarantees that the first time A* expands a node, it has already found the optimal path to it. No node is ever expanded twice, so the closed set can be final and you can safely skip anything in it.

This has a direct consequence for the code above. The implementation does if neighbor in closed_set: continue and never reopens, which is the standard graph-search formulation. That is correct and efficient with a consistent heuristic. With a heuristic that is merely admissible, it can return a suboptimal path — not merely run slower. So: use a consistent heuristic (all of the standard ones above are), or remove the closed-set skip and allow reopening.

If the heuristic is not even admissible — if it can overestimate — A* gives up optimality entirely, though it may still find a good path quickly. That trade is sometimes deliberate; see Weighted A* under Optimizations.

Example

Finding path from (0,0) to (3,3) on a grid:

Grid (0 = free, 1 = obstacle), rows are (r, c) with r downward:

        c=0  c=1  c=2  c=3
  r=0    0    0    0    0
  r=1    0    1    1    0        <- (1,1) and (1,2) are walls
  r=2    0    0    0    0
  r=3    0    0    0    0

Start: (0, 0)     Goal: (3, 3)     4-directional movement, cost 1 per step
Heuristic: Manhattan, h((0,0)) = |0-3| + |0-3| = 6

Step 1: expand (0,0)    g=0, h=6, f=6
Step 2: expand the open node with lowest f, tie-breaking on larger g
Step 3: repeat until (3,3) is expanded

Two optimal paths of length 6, either side of the wall:

  down the left column     (0,0) -> (1,0) -> (2,0) -> (3,0) -> (3,1) -> (3,2) -> (3,3)
  across the top row       (0,0) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (2,3) -> (3,3)

Manhattan distance from (0,0) to (3,3) is 6 and both routes take exactly 6 steps,
so the heuristic is exact here and A* expands almost nothing off the path.

When to Use A*

A* is ideal when:

You have a known goal/target
You can design a good heuristic function
You need optimal or near-optimal paths
Graph is large but heuristic can guide search
Game development, robotics, navigation

Consider alternatives when:

No good heuristic available → Use Dijkstra's
Need all shortest paths → Use Dijkstra's or Floyd-Warshall
Unweighted graph → Use BFS (simpler)
Negative weights → Use Bellman-Ford

A* vs Other Algorithms

Algorithm	Heuristic	Optimal	Best For
BFS	No	Yes (unweighted)	Unweighted graphs
Dijkstra's	No	Yes	Weighted graphs, no heuristic
A*	Yes	Yes (with good heuristic)	Pathfinding with known goal

Optimizations

Bidirectional A*: Search from both start and goal simultaneously
Weighted A*: Use f(n) = g(n) + ε × h(n) for faster (but suboptimal) paths
Jump Point Search: Optimize A* for uniform-cost grids
Hierarchical A*: Use multiple abstraction levels
IDA*: iterative-deepening A* — O(d) memory instead of O(b^d), at the cost of re-expanding nodes. The standard choice for puzzles like the 15-puzzle.
D* Lite / LPA*: incremental replanning when the map changes. Repairs the existing search rather than restarting — the standard approach in robotics, where obstacles appear as sensors discover them.
Theta* / any-angle: allows paths that are not constrained to grid edges, producing shorter, more natural routes.
ARA*: anytime A* — returns a suboptimal path quickly, then improves it while time remains.

For road networks specifically, A* has largely been superseded by preprocessing-based methods — contraction hierarchies and hub labeling answer queries orders of magnitude faster after an offline build step.

Real-World Applications

Game Development: NPC pathfinding, enemy AI
Robotics: Navigation and obstacle avoidance
GPS Navigation: Route planning and optimization
Network Routing: Finding optimal network paths
Puzzle Solving: 15-puzzle, sliding puzzles

Related Algorithms

Explore other searching algorithms:

Dijkstra's Algorithm - Without heuristic
Breadth-First Search - Unweighted graphs
Depth-First Search - Graph traversal
Back to Searching Algorithms Overview