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.
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:
- Add the start node to the Open List
- Select the node with the lowest f(n) from the Open List
- If this node is the goal, reconstruct and return the path
- Move the current node to the Closed List
- Evaluate all neighbors of the current node
- For each valid neighbor, calculate costs and update if a better path is found
- 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 NoneUsing 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 stepsChoosing the Right Heuristic
The heuristic function significantly impacts A* performance. Different heuristics suit different movement rules.
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 movementUpdate 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 |
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
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.