How to Implement the A* Search Algorithm in Python

The A* (A-Star) search algorithm is one of the most powerful and widely used pathfinding algorithms in computer science. From video games to robotics and navigation systems, A* is the go-to choice for finding the shortest path efficiently.

This guide explains how the A* algorithm works and provides a complete, optimized Python implementation.

Understanding the A* Search Algorithm

A* is an informed search algorithm that finds the shortest path between a start node and a goal node in a weighted graph. It extends Dijkstra's algorithm by using a heuristic function to guide the search towards the goal, making it significantly faster in most scenarios.

The Cost Function

A* makes decisions based on the cost function: f(n) = g(n) + h(n)

Where:

• g(n): The actual cost from the start node to the current node
• h(n): The heuristic estimated cost from the current node to the goal

By combining the actual distance traveled and the estimated distance remaining, A* ensures both optimality and efficiency.

Admissible Heuristics

For A* to guarantee the shortest path, the heuristic must be admissible, meaning it never overestimates the true cost to reach the goal. Common admissible heuristics include Manhattan distance and Euclidean distance.

Open and Closed Lists

The algorithm manages two sets of nodes:

• Open List: Nodes discovered but not yet fully evaluated (the frontier)
• Closed List: Nodes already evaluated

How the Algorithm Works

The A* algorithm follows these steps:

1. Add the start node to the Open List
2. Select the node with the lowest f(n) from the Open List
3. If this node is the goal, reconstruct and return the path
4. Move the current node to the Closed List
5. Evaluate all neighbors of the current node
6. For each valid neighbor, calculate costs and update if a better path is found
7. Repeat until the goal is reached or the Open List is empty

Basic Python Implementation

This implementation works on a 2D grid with 8-directional movement using Python's heapq module for an efficient priority queue.

import heapq
import math


class Node:
    """Represents a node in the pathfinding grid."""

    def __init__(self, parent=None, position=None):
        self.parent = parent
        self.position = position
        self.g = 0
        self.h = 0
        self.f = 0

    def __eq__(self, other):
        return self.position == other.position

    def __lt__(self, other):
        return self.f < other.f

    def __hash__(self):
        return hash(self.position)


def heuristic(node_position, goal_position):
    """Calculate the Euclidean distance heuristic."""
    return math.sqrt(
        (node_position[0] - goal_position[0]) ** 2 +
        (node_position[1] - goal_position[1]) ** 2
    )


def get_neighbors(position, grid):
    """Generate valid neighboring positions."""
    rows = len(grid)
    cols = len(grid[0])
    directions = [
        (0, -1), (0, 1), (-1, 0), (1, 0),
        (-1, -1), (-1, 1), (1, -1), (1, 1)
    ]

    neighbors = []
    for direction in directions:
        new_row = position[0] + direction[0]
        new_col = position[1] + direction[1]

        if 0 <= new_row < rows and 0 <= new_col < cols:
            if grid[new_row][new_col] == 0:
                neighbors.append((new_row, new_col))

    return neighbors


def reconstruct_path(current_node):
    """Trace back from goal to start to build the path."""
    path = []
    while current_node is not None:
        path.append(current_node.position)
        current_node = current_node.parent
    return path[::-1]


def astar(grid, start, goal):
    """
    Find the shortest path using the A* algorithm.

    Args:
        grid: 2D list where 0 represents walkable cells and 1 represents walls
        start: Tuple (row, col) for the starting position
        goal: Tuple (row, col) for the goal position

    Returns:
        List of tuples representing the path, or None if no path exists
    """
    start_node = Node(None, start)
    goal_node = Node(None, goal)

    open_list = []
    closed_set = set()
    open_set = {start}

    heapq.heappush(open_list, start_node)

    while open_list:
        current_node = heapq.heappop(open_list)
        open_set.discard(current_node.position)
        closed_set.add(current_node.position)

        if current_node.position == goal_node.position:
            return reconstruct_path(current_node)

        for neighbor_pos in get_neighbors(current_node.position, grid):
            if neighbor_pos in closed_set:
                continue

            neighbor_node = Node(current_node, neighbor_pos)
            neighbor_node.g = current_node.g + 1
            neighbor_node.h = heuristic(neighbor_pos, goal)
            neighbor_node.f = neighbor_node.g + neighbor_node.h

            if neighbor_pos not in open_set:
                heapq.heappush(open_list, neighbor_node)
                open_set.add(neighbor_pos)

    return None

Using the Implementation

def main():
    grid = [
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    ]

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

    path = astar(grid, start, goal)

    if path:
        print(f"Path found: {path}")
        print(f"Path length: {len(path)} steps")
    else:
        print("No path found")


if __name__ == "__main__":
    main()

Output:

Path found: [(0, 0), (1, 1), (2, 2), (3, 3), (4, 3), (5, 4), (6, 5), (7, 6)]
Path length: 8 steps

Choosing the Right Heuristic

The heuristic function significantly impacts A* performance. Different heuristics suit different movement rules.

Heuristic Selection

Choose your heuristic based on allowed movement directions. Using the wrong heuristic can result in suboptimal paths or reduced performance.

Manhattan Distance

Best for 4-directional movement (no diagonals):

def manhattan_distance(node_position, goal_position):
    return (
        abs(node_position[0] - goal_position[0]) +
        abs(node_position[1] - goal_position[1])
    )

Euclidean Distance

Best for 8-directional or free movement:

def euclidean_distance(node_position, goal_position):
    return math.sqrt(
        (node_position[0] - goal_position[0]) ** 2 +
        (node_position[1] - goal_position[1]) ** 2
    )

Diagonal Distance

Optimal for 8-directional movement with uniform costs:

def diagonal_distance(node_position, goal_position):
    dx = abs(node_position[0] - goal_position[0])
    dy = abs(node_position[1] - goal_position[1])
    return max(dx, dy)

Handling Diagonal Movement Costs

When diagonal movement should cost more than cardinal movement, adjust the g-cost calculation:

def get_movement_cost(current_pos, neighbor_pos):
    """Calculate movement cost based on direction."""
    dx = abs(current_pos[0] - neighbor_pos[0])
    dy = abs(current_pos[1] - neighbor_pos[1])

    if dx == 1 and dy == 1:
        return 1.414  # Diagonal movement (sqrt of 2)
    return 1.0  # Cardinal movement

Update the neighbor evaluation in the main algorithm:

neighbor_node.g = current_node.g + get_movement_cost(
    current_node.position,
    neighbor_pos
)

Visualizing the Path

Add a function to display the grid with the computed path:

def visualize_path(grid, path):
    """Display the grid with the path marked."""
    display = [row[:] for row in grid]

    for row, col in path:
        display[row][col] = 2

    if path:
        start = path[0]
        goal = path[-1]
        display[start[0]][start[1]] = 3
        display[goal[0]][goal[1]] = 4

    symbols = {0: ".", 1: "#", 2: "*", 3: "S", 4: "G"}

    for row in display:
        print(" ".join(symbols[cell] for cell in row))

Output:

S . . . # . . . . .
. * . . # . . . . .
. . * . # . . . . .
. . . * # . . . . .
. . . * # . . . . .
. . . . * . . . . .
. . . . # * . . . .
. . . . # . G . . .
. . . . # . . . . .
. . . . . . . . . .

Complexity Analysis

Aspect	Complexity	Notes
Time	O(E log V)	E = edges, V = vertices; priority queue operations dominate
Space	O(V)	Storage for open and closed lists

Performance Consideration

The actual performance depends heavily on heuristic quality. A well-chosen heuristic dramatically reduces the number of nodes explored compared to uninformed search algorithms.

Comparison with Other Algorithms

Algorithm	Use Case	Guarantees Shortest Path
A*	Known goal location with good heuristic	Yes (with admissible heuristic)
Dijkstra	Unknown goal or no useful heuristic	Yes
BFS	Unweighted graphs	Yes
Greedy Best-First	Speed over optimality	No

Common Pitfalls to Avoid

Implementation Mistakes

These common errors can cause incorrect results or poor performance:

• Overestimating heuristic: Breaks optimality guarantee
• Forgetting the closed set: Causes infinite loops
• Not using a priority queue: Degrades performance to O(V²)
• Incorrect neighbor validation: Allows invalid paths through walls

Summary

The A* search algorithm combines the completeness of Dijkstra's algorithm with heuristic guidance for improved efficiency. Key implementation considerations include:

• Choosing an admissible heuristic appropriate for your movement rules
• Using efficient data structures like heap-based priority queues
• Properly handling diagonal movement costs when applicable
• Maintaining both open and closed sets for correctness

These qualities make A* indispensable for game development, robotics, and any application requiring optimal pathfinding.