A* Search Algorithm: Heuristic Pathfinding

Key Insights

A* combines the completeness of Dijkstra’s algorithm with the speed of greedy best-first search through its f(n) = g(n) + h(n) formula, guaranteeing optimal paths when using an admissible heuristic.
Your heuristic choice determines everything: Manhattan distance for grid movement without diagonals, Euclidean for any-angle movement, and Chebyshev when diagonal moves cost the same as cardinal ones.
A* excels on small to medium maps, but for large-scale pathfinding, you’ll need optimizations like Jump Point Search or hierarchical approaches to keep performance acceptable.

Introduction to A* Search

A* (pronounced “A-star”) is the pathfinding algorithm you’ll reach for in 90% of cases. Developed by Peter Hart, Nils Nilsson, and Bertram Raphael at Stanford Research Institute in 1968, it’s become the de facto standard for finding shortest paths in games, robotics, GPS navigation, and network routing.

What makes A* special is its elegant combination of two simpler algorithms. Dijkstra’s algorithm explores outward uniformly, guaranteeing the shortest path but wasting time checking nodes in the wrong direction. Greedy best-first search rushes toward the goal but often finds suboptimal paths. A* takes the best of both: it uses actual path costs like Dijkstra while also considering estimated distance to the goal like greedy search.

The result is an algorithm that finds optimal paths while typically exploring far fewer nodes than Dijkstra. In game development, this translates to NPCs that navigate intelligently without melting your frame rate.

The Core Formula: f(n) = g(n) + h(n)

A* evaluates each node using three values:

g(n): The actual cost from the start node to node n. This is known and exact.
h(n): The heuristic estimate from node n to the goal. This is estimated and must never overestimate.
f(n): The total estimated cost of the path through node n. A* always expands the node with the lowest f(n).

The magic happens because g(n) keeps the algorithm honest about actual costs, while h(n) guides it toward the goal. If your heuristic never overestimates the true cost (a property called “admissibility”), A* guarantees finding the optimal path.

from dataclasses import dataclass, field
from typing import Optional, Tuple

@dataclass
class Node:
    position: Tuple[int, int]
    g: float = float('inf')  # Cost from start
    h: float = 0.0           # Heuristic estimate to goal
    parent: Optional['Node'] = field(default=None, repr=False)
    
    @property
    def f(self) -> float:
        """Total estimated cost through this node."""
        return self.g + self.h
    
    def __lt__(self, other: 'Node') -> bool:
        """For priority queue comparison."""
        return self.f < other.f
    
    def __hash__(self) -> int:
        return hash(self.position)
    
    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Node):
            return False
        return self.position == other.position

Choosing the Right Heuristic

Your heuristic must satisfy two properties for A* to work correctly:

Admissibility: Never overestimate the cost to reach the goal. Overestimating can cause A* to miss the optimal path.
Consistency (optional but preferred): For any node n and successor n’, h(n) ≤ cost(n, n’) + h(n’). This prevents A* from re-expanding nodes.

For grid-based pathfinding, three heuristics cover most use cases:

import math
from typing import Tuple

def manhattan_distance(a: Tuple[int, int], b: Tuple[int, int]) -> float:
    """
    Use when movement is restricted to 4 directions (no diagonals).
    Exact for uniform-cost grids with cardinal movement only.
    """
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def euclidean_distance(a: Tuple[int, int], b: Tuple[int, int]) -> float:
    """
    Use for any-angle movement or when diagonal cost is sqrt(2).
    Always admissible but may underestimate on restricted grids.
    """
    return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)

def chebyshev_distance(a: Tuple[int, int], b: Tuple[int, int]) -> float:
    """
    Use when diagonal movement costs the same as cardinal movement.
    Common in strategy games where units move 8 directions equally.
    """
    return max(abs(a[0] - b[0]), abs(a[1] - b[1]))

def octile_distance(a: Tuple[int, int], b: Tuple[int, int]) -> float:
    """
    Use when diagonal costs sqrt(2) and cardinal costs 1.
    Most accurate for typical 8-direction grid movement.
    """
    dx = abs(a[0] - b[0])
    dy = abs(a[1] - b[1])
    return max(dx, dy) + (math.sqrt(2) - 1) * min(dx, dy)

The trade-off is accuracy versus computation. Manhattan distance is fastest but may significantly underestimate for diagonal movement, causing A* to explore more nodes. Octile distance is more expensive to compute but provides tighter estimates, reducing node expansions.

The A* Algorithm Step-by-Step

A* maintains two sets: the open set containing nodes to evaluate (implemented as a priority queue) and the closed set containing already-evaluated nodes. The algorithm repeatedly extracts the lowest-f node from the open set, checks if it’s the goal, and if not, expands its neighbors.

import heapq
from typing import List, Set, Dict, Callable, Optional, Tuple

def astar(
    start: Tuple[int, int],
    goal: Tuple[int, int],
    get_neighbors: Callable[[Tuple[int, int]], List[Tuple[Tuple[int, int], float]]],
    heuristic: Callable[[Tuple[int, int], Tuple[int, int]], float]
) -> Optional[List[Tuple[int, int]]]:
    """
    A* pathfinding algorithm.
    
    Args:
        start: Starting position
        goal: Target position
        get_neighbors: Function returning list of (neighbor_pos, move_cost) tuples
        heuristic: Function estimating cost from position to goal
    
    Returns:
        List of positions from start to goal, or None if no path exists
    """
    start_node = Node(position=start, g=0, h=heuristic(start, goal))
    
    # Priority queue: (f_score, node)
    open_set: List[Node] = [start_node]
    heapq.heapify(open_set)
    
    # Track best g-score for each position
    g_scores: Dict[Tuple[int, int], float] = {start: 0}
    
    # Track nodes in open set for O(1) lookup
    open_positions: Set[Tuple[int, int]] = {start}
    
    # Closed set
    closed: Set[Tuple[int, int]] = set()
    
    # For path reconstruction
    came_from: Dict[Tuple[int, int], Tuple[int, int]] = {}
    
    while open_set:
        current = heapq.heappop(open_set)
        open_positions.discard(current.position)
        
        if current.position == goal:
            return reconstruct_path(came_from, current.position)
        
        closed.add(current.position)
        
        for neighbor_pos, move_cost in get_neighbors(current.position):
            if neighbor_pos in closed:
                continue
            
            tentative_g = current.g + move_cost
            
            if tentative_g < g_scores.get(neighbor_pos, float('inf')):
                # This path is better
                came_from[neighbor_pos] = current.position
                g_scores[neighbor_pos] = tentative_g
                
                neighbor = Node(
                    position=neighbor_pos,
                    g=tentative_g,
                    h=heuristic(neighbor_pos, goal)
                )
                
                if neighbor_pos not in open_positions:
                    heapq.heappush(open_set, neighbor)
                    open_positions.add(neighbor_pos)
    
    return None  # No path found

def reconstruct_path(
    came_from: Dict[Tuple[int, int], Tuple[int, int]],
    current: Tuple[int, int]
) -> List[Tuple[int, int]]:
    """Reconstruct path by following parent pointers."""
    path = [current]
    while current in came_from:
        current = came_from[current]
        path.append(current)
    return list(reversed(path))

Practical Implementation: Grid-Based Pathfinding

Let’s build a complete grid pathfinder that handles obstacles, weighted terrain, and diagonal movement:

from typing import List, Tuple, Optional
from enum import IntEnum

class Terrain(IntEnum):
    OPEN = 1
    FOREST = 2
    SWAMP = 3
    WALL = -1  # Impassable

class GridPathfinder:
    # Cardinal and diagonal directions
    DIRECTIONS = [
        (0, 1), (1, 0), (0, -1), (-1, 0),  # Cardinal
        (1, 1), (1, -1), (-1, 1), (-1, -1)  # Diagonal
    ]
    
    def __init__(self, grid: List[List[int]], allow_diagonal: bool = True):
        self.grid = grid
        self.height = len(grid)
        self.width = len(grid[0]) if grid else 0
        self.allow_diagonal = allow_diagonal
    
    def is_valid(self, pos: Tuple[int, int]) -> bool:
        x, y = pos
        return (0 <= x < self.width and 
                0 <= y < self.height and 
                self.grid[y][x] != Terrain.WALL)
    
    def get_neighbors(
        self, pos: Tuple[int, int]
    ) -> List[Tuple[Tuple[int, int], float]]:
        x, y = pos
        neighbors = []
        directions = self.DIRECTIONS if self.allow_diagonal else self.DIRECTIONS[:4]
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            new_pos = (nx, ny)
            
            if not self.is_valid(new_pos):
                continue
            
            # Prevent corner cutting through walls
            if dx != 0 and dy != 0:  # Diagonal move
                if not self.is_valid((x + dx, y)) or not self.is_valid((x, y + dy)):
                    continue
            
            # Calculate move cost
            base_cost = 1.414 if (dx != 0 and dy != 0) else 1.0
            terrain_cost = self.grid[ny][nx]
            total_cost = base_cost * terrain_cost
            
            neighbors.append((new_pos, total_cost))
        
        return neighbors
    
    def find_path(
        self, 
        start: Tuple[int, int], 
        goal: Tuple[int, int]
    ) -> Optional[List[Tuple[int, int]]]:
        if not self.is_valid(start) or not self.is_valid(goal):
            return None
        
        return astar(start, goal, self.get_neighbors, octile_distance)
    
    def visualize(
        self, 
        path: Optional[List[Tuple[int, int]]] = None
    ) -> str:
        symbols = {
            Terrain.OPEN: '.',
            Terrain.FOREST: 'F',
            Terrain.SWAMP: '~',
            Terrain.WALL: '#'
        }
        path_set = set(path) if path else set()
        
        lines = []
        for y in range(self.height):
            row = []
            for x in range(self.width):
                if (x, y) in path_set:
                    row.append('*')
                else:
                    row.append(symbols.get(self.grid[y][x], '?'))
            lines.append(''.join(row))
        return '\n'.join(lines)

# Usage example
if __name__ == "__main__":
    grid = [
        [1, 1, 1, 1, 1, 1, 1, 1],
        [1, 1, 1,-1,-1, 1, 1, 1],
        [1, 1, 1,-1, 1, 1, 2, 1],
        [1, 1, 1,-1, 1, 2, 2, 1],
        [1, 1, 1, 1, 1, 1, 1, 1],
    ]
    
    pathfinder = GridPathfinder(grid)
    path = pathfinder.find_path((0, 0), (7, 2))
    print(pathfinder.visualize(path))

Performance Optimization Techniques

A* works well for small to medium maps, but performance degrades on large grids. Here are practical optimizations:

Jump Point Search (JPS) eliminates symmetrical paths on uniform-cost grids by “jumping” over intermediate nodes. It can be 10-30x faster than vanilla A* but only works when all walkable tiles have equal cost.

Hierarchical Pathfinding divides large maps into regions. First, find a path between regions using a coarse graph, then refine within each region. This is essential for open-world games.

Memory-Bounded Variants like IDA* (Iterative Deepening A*) trade time for memory, useful when RAM is constrained. SMA* (Simplified Memory-Bounded A*) drops the least promising nodes when memory fills up.

When to skip A* entirely:

For very small grids (under 100 nodes), BFS is simpler and fast enough
For single-source all-destinations, use Dijkstra’s algorithm
For unweighted graphs, BFS guarantees shortest paths with less overhead
For real-time constraints with acceptable suboptimality, consider greedy best-first or weighted A* (f = g + w*h where w > 1)

Conclusion

A* remains the workhorse of pathfinding because it’s correct, efficient, and adaptable. Master these fundamentals: implement the algorithm with a proper priority queue, choose heuristics that match your movement model, and know when to reach for optimizations like JPS or hierarchical approaches.

Start with the vanilla implementation, profile it in your actual use case, and optimize only when needed. Most games and applications never need anything beyond basic A* with a binary heap.