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:

1. Initialize: Add start node to open set with f(start) = h(start)
2. 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
3. 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 overestimate the true cost (h(n) ≤ actual cost)
• Consistent: h(n) ≤ cost(n, n') + h(n') for all neighbors n'

Common Heuristics

• Manhattan Distance: For grid-based pathfinding

  h(n) = |x₁ - x₂| + |y₁ - y₂|

• Euclidean Distance: Straight-line distance

  h(n) = √((x₁ - x₂)² + (y₁ - y₂)²)

• Chebyshev Distance: For 8-directional movement

  h(n) = max(|x₁ - x₂|, |y₁ - y₂|)

Complexity Analysis

• Time Complexity: O(b^d) worst case, where b is branching factor and d is depth. With good heuristic, much better than Dijkstra's.
• Space Complexity: O(b^d) - stores all nodes in open and closed sets

The actual performance depends heavily on the heuristic quality. With a perfect heuristic (h(n) = actual cost), A* only explores nodes on the optimal path. With a poor heuristic, it degrades to Dijkstra's algorithm.

Optimality

A* is guaranteed to find the optimal path if:

• The heuristic is admissible (never overestimates)
• The heuristic is consistent (satisfies triangle inequality)

If the heuristic is not admissible, A* may find a suboptimal path. If it's not consistent, nodes may be re-expanded, reducing efficiency.

Example

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

Grid (0 = free, 1 = obstacle):
0 0 0 0
0 1 1 0
0 0 0 0
0 0 0 0

Start: (0, 0)
Goal: (3, 3)

Step 1: Start at (0,0), f = 0 + 6 = 6
Step 2: Explore neighbors, choose best f
Step 3: Continue until goal reached

Path: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (3,2) → (3,3)
                

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

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

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