Table of Contents
Introduction
The A* (A-star) algorithm is a highly efficient pathfinding method widely used in artificial intelligence, robotics, and game development. First described in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael, A* improves on Dijkstra’s algorithm by using a heuristic to focus the search on promising routes rather than exploring every possible path.
At its core, A* is a best-first search algorithm that evaluates paths using two components:
- g(n): The actual cost from the start node to node n.
- h(n): A heuristic estimate of the cost from node n to the goal.
- f(n) = g(n) + h(n): The total estimated cost of reaching the goal via n.
Key Features of A*
- Optimality: It finds the shortest path when an admissible heuristic is used.
- Efficiency: Heuristic guidance reduces the number of nodes explored compared to Dijkstra’s algorithm.
- Flexibility: The heuristic can be tailored to fit different scenarios.
- Completeness: It will find a solution if one exists.
Core Concepts
A* Algorithm Components
A* evaluates nodes using:
- g(n): The cumulative cost from the start node to the current node.
- h(n): The estimated cost from the current node to the goal.
- f(n) = g(n) + h(n): The total estimated cost for a path through the current node.
By combining these, A* prioritizes nodes that appear to lead to an optimal path.
How A* Works
In each iteration, A* selects the node with the lowest f(n) from the open set, expands it, and updates its neighbors’ costs. If a neighbor’s tentative cost is lower than a previously recorded value, it is updated (and linked via a parent pointer for path reconstruction) and added to the open set. This process continues until the goal is reached or no path exists.
A* Algorithm Pseudocode
The following pseudocode provides a high-level overview of the A* algorithm. It initializes an open set for nodes to be evaluated and a closed set for nodes that have been explored. At each iteration, the node with the lowest estimated total cost (f(n) = g(n) + h(n)) is selected. The algorithm then updates the costs of neighboring nodes, maintaining parent pointers for path reconstruction. If the goal is reached, the optimal path is reconstructed; otherwise, the search continues until no nodes remain.
# A* Algorithm - High-Level Overview
1. Initialize:
- openSet = {start} # Nodes to be evaluated
- closedSet = {} # Nodes already evaluated
- g_score[start] = 0 # Cost from start to node
- f_score[start] = heuristic(start, goal)
2. While openSet is not empty:
a. Select current = node in openSet with lowest f_score
b. If current is the goal:
Return reconstructed path via parent pointers
c. Remove current from openSet and add it to closedSet
d. For each neighbor of current:
- tentative_g = g_score[current] + distance(current, neighbor)
- If tentative_g < g_score[neighbor]:
- Set parent[neighbor] = current # For path reconstruction
- Update g_score[neighbor] = tentative_g
- Update f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)
- If neighbor is not in openSet:
Add neighbor to openSet
3. If openSet is empty and goal not reached:
Return failure # No path exists
Interactive Demonstration
The visualization below shows how A* explores paths by prioritizing nodes based on their estimated total cost (f(n)). Unlike Dijkstra’s algorithm, which expands all nodes uniformly, A* uses heuristics to focus on promising paths and reach the goal more efficiently.
| Node | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| g(n) | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| h(n) | 3 | 3 | 3 | 2 | 2 | 0 |
| f(n) | 3 | ∞ | ∞ | ∞ | ∞ | ∞ |
In this demonstration, the heuristic values (h(n)) are computed using the Manhattan distance. This method calculates the distance between two nodes as the sum of the absolute differences of their grid coordinates. For example, consider node E with grid coordinates (2, 1) and the goal node F with grid coordinates (3, 0). The Manhattan distance is calculated as follows:
h(E) = |3 - 2| + |0 - 1| = 1 + 1 = 2
Notice that node D retains a g(n) value of ∞. This is because the algorithm never updates the cost to reach node D—no path that includes D was found to be more efficient than the optimal path discovered (A → C → E → F). As a result, the cost to reach D remains at its initial value of ∞, indicating that it was not part of the final solution.
Time and Space Complexity
- Time Complexity: In the worst case, A* operates in O(b^d) time, where b is the branching factor and d is the depth of the solution.
- Space Complexity: It also requires O(b^d) space to store the nodes in the open and closed sets.
- Optimality: A* is guaranteed to find the optimal path when using an admissible heuristic (one that never overestimates the true cost).
- Practical Performance: In many practical applications, the performance is significantly better than the worst-case scenario because the heuristic effectively guides the search.
The complexity results highlight that while the worst-case behavior of A* can be exponential in both time and space, its intelligent use of heuristics typically leads to faster and more efficient searches. This balance between theoretical complexity and practical efficiency makes A* a popular choice in a wide range of applications.
In the following sections, we will delve deeper into the mathematical principles behind the algorithm, explore the implementation details, and compare A* with other pathfinding algorithms. Whether you are developing games, robotics applications, or navigation systems, understanding these complexity considerations is key to designing efficient pathfinding solutions.
Mathematical Background
This section will go through the formal definition for the A* algorithm, heuristic properties and key properties.
Formal Definition
Imagine you are on a treasure hunt in a maze. The maze is represented by a weighted graph \(G = (V, E)\) where:
- \(V = \{v_1, v_2, ..., v_n\}\): The set of all locations (vertices) in the maze.
- \(E \subset V \times V\): The pathways (edges) connecting these locations.
- \(w: E \to \mathbb{R}_{\geq 0}\): The cost (or time) required to travel each path.
- \(h: V \to \mathbb{R}_{\geq 0}\): A heuristic function that gives an estimated cost from any location to the treasure (goal).
-
\(g: V \to \mathbb{R}_{\geq 0} \cup \{\infty\}\): The actual cost from the start location to each vertex, defined as:
\[ g(v) = \begin{cases} 0 & \text{if } v = s \quad (\text{your starting point})\\[8pt] \infty & \text{otherwise} \end{cases} \] - \(f: V \to \mathbb{R}_{\geq 0} \cup \{\infty\}\): The evaluation function that estimates the total cost of a path going through a vertex, given by: \[ f(v) = g(v) + h(v) \]
At the beginning, you know exactly how far you've come from the start (the g(n) value) and you have an idea of how far the treasure might be (the h(n) value).
As you explore the maze, A* keeps track of two groups:
- OPEN: Locations that have been discovered but not yet fully explored. Think of these as the "frontier" of your search.
- CLOSED: Locations that have been fully explored and for which you know the shortest distance from the start.
The algorithm maintains an important invariant: for every location \(v\) in CLOSED, \[ g(v) = \delta(s,v) \] where \(\delta(s,v)\) is the actual shortest path distance from your starting point \(s\) to \(v\). In other words, once you finish exploring a location, you are certain that you found the best route to get there.
Heuristic Properties
To ensure that A* leads you to the treasure along the best possible path, the heuristic function must satisfy certain properties:
1. Admissibility
Think of the heuristic as an optimistic estimate. A heuristic h(n) is admissible if it never overestimates the true cost to reach the treasure. Formally: \[ \forall n \in V: \quad h(n) \leq h^*(n) \] where \(h^*(n)\) is the actual cost of the optimal path from \(n\) to the goal. It’s like always assuming the best-case scenario for the remaining journey.
2. Consistency (Monotonicity)
Consistency ensures that as you move from one location to a neighbor, the estimated cost to reach the treasure does not suddenly drop unexpectedly. For every location \(n\) and its neighbor \(n'\) with a step cost \(c(n,n')\): \[ h(n) \leq c(n,n') + h(n') \] This property is similar to a "smooth" decline in your estimated remaining distance as you progress toward your goal.
Example Graph Structure
Consider a simple maze where the distances between locations are estimated using the Manhattan distance (like counting city blocks). The table below shows the initial values for each node:
| Node | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| g(n) | 0 | 4 | 2 | ∞ | ∞ | ∞ |
| h(n) | 3 | 2 | 2 | 1 | 1 | 0 |
| f(n) | 3 | 6 | 4 | ∞ | ∞ | ∞ |
The values shown represent an initial state using the Manhattan distance heuristic, where the cost to reach node A is 0 (start), and the costs for other nodes are calculated based on the paths explored so far.
Optimality Proof
The optimality of A* (i.e., its guarantee to find the best path) relies on two key ideas:
1. Optimal Substructure with Consistent Heuristics
Imagine you are following the best possible directions at every step. If a location \(n_1\) is expanded before another location \(n_2\), then the estimated total cost at \(n_1\) must be less than or equal to that at \(n_2\):
\[
f(n_1) \leq f(n_2)
\]
Analogy: This is like always choosing the road that seems to get you closer to the treasure without any unexpected detours.
2. Optimality of Path Selection
If the heuristic is admissible (always optimistic) and \(n^*\) is the goal node reached with the optimal path cost \(C^*\), then for every node \(n\) in the OPEN set:
\[
f(n) \leq C^*
\]
Analogy: Think of it as having a promise that no matter which unexplored road you take, your total estimated journey cost will never exceed the cost of the best-known route to the treasure.
Common Heuristics
For grid-based pathfinding, several heuristics are popular because they are both admissible and consistent:
-
Manhattan Distance: \(h(n) = |x_1 - x_2| + |y_1 - y_2|\)
- Best suited for grids where you can only move horizontally or vertically (like city blocks).
- Simple and effective.
-
Euclidean Distance: \(h(n) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\)
- Appropriate when movement in any direction is allowed.
- Mimics the "straight-line" distance between points.
-
Diagonal Distance: \(h(n) = \max(|x_1 - x_2|, |y_1 - y_2|)\)
- Ideal for grids that allow diagonal movement (like an 8-connected grid), especially when diagonal moves have a cost of \(\sqrt{2}\).
Key Mathematical Properties
-
Completeness:
A* is complete—if there is a path to the goal, A* will find it. This is guaranteed if the graph has positive edge weights, a finite number of paths to explore, and the goal is reachable.
-
Optimality:
A* will always find the optimal path, provided that the heuristic is admissible and consistent, and all edge costs are non-negative.
-
Efficiency:
Among best-first search algorithms using the same heuristic, A* is optimally efficient—it expands the fewest nodes possible to find the optimal solution. If another algorithm expanded fewer nodes, it might risk missing the best path.
The following section will look at how to implement the A* algorithm in Python, Java, JavaScript, and C++ for an example grid-based map.
Implementation
In this section, we explore implementations of the A* algorithm in multiple programming languages. Each implementation demonstrates how heuristic guidance is combined with efficient node selection using a priority queue. We cover essential elements such as comprehensive error handling, complete path reconstruction, and flexible support for custom heuristic functions.
Implementation Strategy
- Priority Queue: Efficient node selection based on f-scores.
- Custom Heuristics: Support for different heuristic functions to tailor the search.
- Path Reconstruction: Rebuild the optimal path from the goal back to the start.
- Set Management: Effective handling of open and closed sets to avoid reprocessing nodes.
In the visualization below, each cell on the grid is represented by a rectangle. Walkable cells appear in white with a light border, while walls are shown in dark gray. The start cell (top-left) and the end cell (bottom-right) are both part of the path, which is highlighted by a semi-transparent green overlay across each cell along the route.
In addition to the visual grid above, our implementations in Python, Java, JavaScript, and C++ demonstrate how the A* algorithm processes this grid to compute an optimal path from start to finish.
Below, you can explore each language-specific implementation by clicking the corresponding tab.
Python Implementation
Uses Python's heapq module for the priority queue implementation and includes customizable heuristic functions.
from typing import Dict, List, Set, Tuple, Callable, Optional
import heapq
class Node:
"""A node in the graph with position and cost information."""
def __init__(self, position: Tuple[int, int],
g_cost: float = float('inf'),
h_cost: float = 0):
self.position = position
self.g_cost = g_cost # Cost from start to this node.
self.h_cost = h_cost # Heuristic estimate to goal.
self.parent: Optional['Node'] = None # Parent node in the path.
@property
def f_cost(self) -> float:
"""Total estimated cost (f = g + h)."""
return self.g_cost + self.h_cost
def __lt__(self, other: 'Node') -> bool:
"""Comparison for priority queue ordering."""
return self.f_cost < other.f_cost
class AStar:
def __init__(self, grid: List[List[int]],
heuristic: Callable[[Tuple[int, int], Tuple[int, int]], float]):
"""
Initialize A* pathfinder.
Args:
grid: 2D grid where 0 represents walkable cells and 1 represents walls.
heuristic: Function that estimates distance between two points.
"""
self.grid = grid
self.rows = len(grid)
self.cols = len(grid[0]) if self.rows > 0 else 0
self.heuristic = heuristic
def get_neighbors(self, pos: Tuple[int, int]) -> List[Tuple[int, int]]:
"""Get valid neighboring positions."""
x, y = pos
neighbors = []
# Check orthogonal neighbors first (up, right, down, left).
for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
new_x, new_y = x + dx, y + dy
if (0 <= new_x < self.rows and 0 <= new_y < self.cols and
self.grid[new_x][new_y] == 0):
neighbors.append((new_x, new_y))
# Check diagonal neighbors.
for dx, dy in [(1, 1), (1, -1), (-1, 1), (-1, -1)]:
new_x, new_y = x + dx, y + dy
# Ensure move is within bounds and walkable.
# Also ensure no "corner cutting" by checking adjacent cells.
if (0 <= new_x < self.rows and 0 <= new_y < self.cols and
self.grid[new_x][new_y] == 0 and
self.grid[x + dx][y] == 0 and
self.grid[x][y + dy] == 0):
neighbors.append((new_x, new_y))
return neighbors
def find_path(self, start: Tuple[int, int],
goal: Tuple[int, int]) -> Optional[List[Tuple[int, int]]]:
"""
Find the shortest path between start and goal positions.
"""
# Initialize the start node.
start_node = Node(start, 0, self.heuristic(start, goal))
# The open set (priority queue) and a dictionary for quick lookup.
open_set = []
heapq.heappush(open_set, start_node)
open_dict: Dict[Tuple[int, int], Node] = {start: start_node}
# The closed set contains positions we’ve finished processing.
closed_set: Set[Tuple[int, int]] = set()
while open_set:
current = heapq.heappop(open_set)
# Skip nodes that have already been expanded.
if current.position in closed_set:
continue
# Goal reached.
if current.position == goal:
return self._reconstruct_path(current)
closed_set.add(current.position)
for neighbor_pos in self.get_neighbors(current.position):
if neighbor_pos in closed_set:
continue
movement_cost = 1.0 # Uniform cost for any move.
tentative_g = current.g_cost + movement_cost
if neighbor_pos in open_dict:
neighbor = open_dict[neighbor_pos]
# If the new path is not better, skip.
if tentative_g >= neighbor.g_cost:
continue
else:
neighbor = Node(neighbor_pos)
open_dict[neighbor_pos] = neighbor
# This path is better—update the neighbor.
neighbor.parent = current
neighbor.g_cost = tentative_g
neighbor.h_cost = self.heuristic(neighbor_pos, goal)
heapq.heappush(open_set, neighbor)
return None # No path found.
def _reconstruct_path(self, node: Node) -> List[Tuple[int, int]]:
"""Reconstruct the path from the goal node to the start."""
path = []
while node:
path.append(node.position)
node = node.parent
return path[::-1] # Reverse to get start-to-goal order.
# Example heuristic function.
def manhattan_distance(p1: Tuple[int, int], p2: Tuple[int, int]) -> float:
"""Manhattan distance heuristic."""
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
Example Usage:
# Example grid (0 = walkable, 1 = wall)
grid = [
[0, 0, 0, 1, 0],
[1, 1, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0]
]
# Create pathfinder with the Manhattan distance heuristic.
pathfinder = AStar(grid, manhattan_distance)
# Find path from (0, 0) to (4, 4)
path = pathfinder.find_path((0, 0), (4, 4))
print(f"Path found: {path}")
# Output: Path found: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4)]Java Implementation
Uses Java's PriorityQueue and implements an interface for custom heuristics.
// AStarDemo.java
import java.util.*;
public class AStarDemo {
// Represents a position in the grid.
public static class Position {
public int row, col;
public Position(int row, int col) {
this.row = row;
this.col = col;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null || getClass() != obj.getClass())
return false;
Position other = (Position) obj;
return row == other.row && col == other.col;
}
@Override
public int hashCode() {
return 31 * row + col;
}
@Override
public String toString() {
return "(" + row + ", " + col + ")";
}
}
// Node class for A* search.
public static class Node implements Comparable<Node> {
public Position pos;
public double gCost; // Cost from start node.
public double hCost; // Heuristic cost to goal.
public Node parent; // Parent node in the path.
public Node(Position pos, double gCost, double hCost) {
this.pos = pos;
this.gCost = gCost;
this.hCost = hCost;
this.parent = null;
}
public double getFCost() {
return gCost + hCost;
}
@Override
public int compareTo(Node other) {
return Double.compare(this.getFCost(), other.getFCost());
}
}
// Interface for heuristic calculation.
public interface Heuristic {
double estimate(Position a, Position b);
}
// Manhattan distance heuristic.
public static class ManhattanHeuristic implements Heuristic {
@Override
public double estimate(Position a, Position b) {
return Math.abs(a.row - b.row) + Math.abs(a.col - b.col);
}
}
// A* algorithm implementation.
public static class AStar {
private int[][] grid;
private int rows;
private int cols;
private Heuristic heuristic;
public AStar(int[][] grid, Heuristic heuristic) {
this.grid = grid;
this.rows = grid.length;
this.cols = grid[0].length;
this.heuristic = heuristic;
}
// Check if a cell is within bounds and walkable.
private boolean isWalkable(int row, int col) {
return row >= 0 && row < rows && col >= 0 && col < cols && grid[row][col] == 0;
}
// Get valid neighboring positions.
public List<Position> getNeighbors(Position pos) {
List<Position> neighbors = new ArrayList<>();
int r = pos.row;
int c = pos.col;
// Orthogonal neighbors: up, right, down, left.
int[][] orthogonal = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
for (int[] d : orthogonal) {
int newRow = r + d[0];
int newCol = c + d[1];
if (isWalkable(newRow, newCol)) {
neighbors.add(new Position(newRow, newCol));
}
}
// Diagonal neighbors.
int[][] diagonal = { {-1, -1}, {-1, 1}, {1, 1}, {1, -1} };
for (int[] d : diagonal) {
int newRow = r + d[0];
int newCol = c + d[1];
if (isWalkable(newRow, newCol)) {
// Prevent corner cutting.
if (isWalkable(r + d[0], c) && isWalkable(r, c + d[1])) {
neighbors.add(new Position(newRow, newCol));
}
}
}
return neighbors;
}
// Find the shortest path using the A* algorithm.
public List<Position> findPath(Position start, Position goal) {
PriorityQueue<Node> openSet = new PriorityQueue<>();
Map<Position, Node> openMap = new HashMap<>();
Set<Position> closedSet = new HashSet<>();
Node startNode = new Node(start, 0, heuristic.estimate(start, goal));
openSet.add(startNode);
openMap.put(start, startNode);
while (!openSet.isEmpty()) {
Node current = openSet.poll();
if (closedSet.contains(current.pos))
continue;
if (current.pos.equals(goal)) {
return reconstructPath(current);
}
closedSet.add(current.pos);
for (Position neighborPos : getNeighbors(current.pos)) {
if (closedSet.contains(neighborPos))
continue;
double tentativeG = current.gCost + 1.0; // Uniform cost.
Node neighbor = openMap.get(neighborPos);
if (neighbor == null) {
neighbor = new Node(neighborPos, Double.POSITIVE_INFINITY, heuristic.estimate(neighborPos, goal));
openMap.put(neighborPos, neighbor);
}
if (tentativeG < neighbor.gCost) {
neighbor.gCost = tentativeG;
neighbor.hCost = heuristic.estimate(neighborPos, goal);
neighbor.parent = current;
openSet.add(neighbor);
}
}
}
return null; // No path found.
}
// Reconstruct the path from goal to start.
private List<Position> reconstructPath(Node node) {
List<Position> path = new ArrayList<>();
while (node != null) {
path.add(node.pos);
node = node.parent;
}
Collections.reverse(path);
return path;
}
}
// Main method for testing the A* implementation.
public static void main(String[] args) {
int[][] grid = {
{0, 0, 0, 1, 0},
{1, 1, 0, 1, 0},
{0, 0, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 0, 0}
};
Position start = new Position(0, 0);
Position goal = new Position(4, 4);
AStar astar = new AStar(grid, new ManhattanHeuristic());
List<Position> path = astar.findPath(start, goal);
if (path != null) {
System.out.println("Path found: " + path);
} else {
System.out.println("No path found.");
}
}
}
// Example Output: Path found: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4)]
JavaScript Implementation
Uses a custom PriorityQueue and ES6 classes for A* pathfinding with custom heuristics.
/* JavaScript Implementation */
class Node {
constructor(position, gCost = Infinity, hCost = 0) {
this.position = position; // [row, col]
this.gCost = gCost;
this.hCost = hCost;
this.parent = null;
}
get fCost() {
return this.gCost + this.hCost;
}
}
class PriorityQueue {
constructor() {
this.heap = [];
}
isEmpty() {
return this.heap.length === 0;
}
push(node) {
this.heap.push(node);
this._siftUp();
}
pop() {
if (this.isEmpty()) return null;
const top = this.heap[0];
const end = this.heap.pop();
if (!this.isEmpty()) {
this.heap[0] = end;
this._siftDown();
}
return top;
}
_siftUp() {
let index = this.heap.length - 1;
const element = this.heap[index];
while (index > 0) {
let parentIndex = Math.floor((index - 1) / 2);
let parent = this.heap[parentIndex];
if (element.fCost >= parent.fCost) break;
this.heap[index] = parent;
this.heap[parentIndex] = element;
index = parentIndex;
}
}
_siftDown() {
let index = 0;
const length = this.heap.length;
const element = this.heap[0];
while (true) {
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
let swapIndex = null;
if (leftChildIndex < length) {
let leftChild = this.heap[leftChildIndex];
if (leftChild.fCost < element.fCost) {
swapIndex = leftChildIndex;
}
}
if (rightChildIndex < length) {
let rightChild = this.heap[rightChildIndex];
if ((swapIndex === null && rightChild.fCost < element.fCost) ||
(swapIndex !== null && rightChild.fCost < this.heap[swapIndex].fCost)) {
swapIndex = rightChildIndex;
}
}
if (swapIndex === null) break;
this.heap[index] = this.heap[swapIndex];
this.heap[swapIndex] = element;
index = swapIndex;
}
}
}
function manhattanDistance(a, b) {
return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
}
class AStar {
constructor(grid, heuristic) {
this.grid = grid;
this.heuristic = heuristic;
this.rows = grid.length;
this.cols = grid[0].length;
}
isWalkable(row, col) {
return row >= 0 && row < this.rows &&
col >= 0 && col < this.cols &&
this.grid[row][col] === 0;
}
getNeighbors(position) {
const [row, col] = position;
const neighbors = [];
// Orthogonal neighbors: up, right, down, left.
const orthogonal = [[-1, 0], [0, 1], [1, 0], [0, -1]];
for (let [dr, dc] of orthogonal) {
const newRow = row + dr, newCol = col + dc;
if (this.isWalkable(newRow, newCol)) {
neighbors.push([newRow, newCol]);
}
}
// Diagonal neighbors.
const diagonal = [[-1, -1], [-1, 1], [1, 1], [1, -1]];
for (let [dr, dc] of diagonal) {
const newRow = row + dr, newCol = col + dc;
if (this.isWalkable(newRow, newCol)) {
// Prevent corner cutting.
if (this.isWalkable(row + dr, col) && this.isWalkable(row, col + dc)) {
neighbors.push([newRow, newCol]);
}
}
}
return neighbors;
}
findPath(start, goal) {
const startNode = new Node(start, 0, this.heuristic(start, goal));
const openSet = new PriorityQueue();
openSet.push(startNode);
// Using string representation of the position as the key.
const openMap = new Map();
openMap.set(start.toString(), startNode);
const closedSet = new Set();
while (!openSet.isEmpty()) {
const current = openSet.pop();
const currentKey = current.position.toString();
if (closedSet.has(currentKey)) continue;
if (current.position[0] === goal[0] && current.position[1] === goal[1]) {
return this._reconstructPath(current);
}
closedSet.add(currentKey);
for (let neighborPos of this.getNeighbors(current.position)) {
const neighborKey = neighborPos.toString();
if (closedSet.has(neighborKey)) continue;
const tentativeG = current.gCost + 1; // Uniform cost.
let neighbor;
if (openMap.has(neighborKey)) {
neighbor = openMap.get(neighborKey);
if (tentativeG >= neighbor.gCost) continue;
} else {
neighbor = new Node(neighborPos, Infinity, this.heuristic(neighborPos, goal));
openMap.set(neighborKey, neighbor);
}
neighbor.gCost = tentativeG;
neighbor.parent = current;
openSet.push(neighbor);
}
}
return null; // No path found.
}
_reconstructPath(node) {
const path = [];
let current = node;
while (current) {
path.push(current.position);
current = current.parent;
}
return path.reverse();
}
}
Example Usage
/* Example Usage */
const grid = [
[0, 0, 0, 1, 0],
[1, 1, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0]
];
const astar = new AStar(grid, manhattanDistance);
const start = [0, 0];
const goal = [4, 4];
const path = astar.findPath(start, goal);
if (path) {
console.log("Path found:", path);
} else {
console.log("No path found.");
}
/* Example output: Path found: [
[ 0, 0 ], [ 0, 1 ],
[ 0, 2 ], [ 1, 2 ],
[ 2, 2 ], [ 2, 3 ],
[ 2, 4 ], [ 3, 4 ],
[ 4, 4 ]
]
*/
C++ Implementation
Uses STL's priority_queue and unordered_map for A* pathfinding with custom heuristics.
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <functional>
struct Position {
int row, col;
bool operator==(const Position &other) const {
return row == other.row && col == other.col;
}
};
// Custom hash for Position
namespace std {
template<>
struct hash<Position> {
std::size_t operator()(const Position &p) const {
return std::hash<int>()(p.row) ^ (std::hash<int>()(p.col) << 1);
}
};
}
struct Node {
Position pos;
double gCost;
double hCost;
Node* parent;
Node(Position pos, double gCost = std::numeric_limits<double>::infinity(), double hCost = 0)
: pos(pos), gCost(gCost), hCost(hCost), parent(nullptr) {}
double fCost() const {
return gCost + hCost;
}
};
struct CompareNode {
bool operator()(const Node* a, const Node* b) const {
// For priority_queue as a min-heap, we want the node with lower fCost to have higher priority.
return a->fCost() > b->fCost();
}
};
class AStar {
public:
AStar(const std::vector<std::vector<int>> &grid,
std::function<double(const Position&, const Position&)> heuristic)
: grid(grid), heuristic(heuristic) {
rows = grid.size();
cols = (rows > 0) ? grid[0].size() : 0;
}
// Returns true if the cell is within bounds and walkable (value 0).
bool isWalkable(int row, int col) const {
return row >= 0 && row < rows &&
col >= 0 && col < cols &&
grid[row][col] == 0;
}
// Returns a vector of valid neighboring positions.
std::vector<Position> getNeighbors(const Position &pos) const {
std::vector<Position> neighbors;
int r = pos.row, c = pos.col;
// Orthogonal neighbors: up, right, down, left.
std::vector<std::pair<int, int>> orthogonal = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
for (auto &d : orthogonal) {
int newRow = r + d.first;
int newCol = c + d.second;
if (isWalkable(newRow, newCol)) {
neighbors.push_back({ newRow, newCol });
}
}
// Diagonal neighbors.
std::vector<std::pair<int, int>> diagonal = { { -1, -1 }, { -1, 1 }, { 1, 1 }, { 1, -1 } };
for (auto &d : diagonal) {
int newRow = r + d.first;
int newCol = c + d.second;
if (isWalkable(newRow, newCol)) {
// Prevent corner cutting.
if (isWalkable(r + d.first, c) && isWalkable(r, c + d.second)) {
neighbors.push_back({ newRow, newCol });
}
}
}
return neighbors;
}
// Finds the shortest path from start to goal.
std::vector<Position> findPath(const Position &start, const Position &goal) {
std::priority_queue<Node*, std::vector<Node*>, CompareNode> openSet;
std::unordered_map<Position, Node*> openMap;
std::unordered_set<Position> closedSet;
Node* startNode = new Node(start, 0, heuristic(start, goal));
openSet.push(startNode);
openMap[start] = startNode;
while (!openSet.empty()) {
Node* current = openSet.top();
openSet.pop();
if (closedSet.find(current->pos) != closedSet.end())
continue;
if (current->pos.row == goal.row && current->pos.col == goal.col) {
std::vector<Position> path = reconstructPath(current);
cleanup(openMap);
return path;
}
closedSet.insert(current->pos);
for (const auto &neighborPos : getNeighbors(current->pos)) {
if (closedSet.find(neighborPos) != closedSet.end())
continue;
double tentativeG = current->gCost + 1.0; // Uniform cost.
Node* neighbor;
if (openMap.find(neighborPos) != openMap.end()) {
neighbor = openMap[neighborPos];
if (tentativeG >= neighbor->gCost)
continue;
} else {
neighbor = new Node(neighborPos, std::numeric_limits<double>::infinity(), heuristic(neighborPos, goal));
openMap[neighborPos] = neighbor;
}
neighbor->gCost = tentativeG;
neighbor->parent = current;
openSet.push(neighbor);
}
}
cleanup(openMap);
return std::vector<Position>(); // No path found.
}
private:
std::vector<std::vector<int>> grid;
int rows, cols;
std::function<double(const Position&, const Position&)> heuristic;
std::vector<Position> reconstructPath(Node* node) {
std::vector<Position> path;
while (node != nullptr) {
path.push_back(node->pos);
node = node->parent;
}
std::reverse(path.begin(), path.end());
return path;
}
void cleanup(std::unordered_map<Position, Node*> &openMap) {
for (auto &pair : openMap) {
delete pair.second;
}
}
};
Example Usage
// Forward declaration for Position (already defined in the implementation snippet)
struct Position;
double manhattanDistance(const Position &a, const Position &b) {
return std::abs(a.row - b.row) + std::abs(a.col - b.col);
}
int main() {
std::vector<std::vector<int>> grid = {
{0, 0, 0, 1, 0},
{1, 1, 0, 1, 0},
{0, 0, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 0, 0}
};
Position start = {0, 0};
Position goal = {4, 4};
AStar astar(grid, manhattanDistance);
std::vector<Position> path = astar.findPath(start, goal);
if (!path.empty()) {
std::cout << "Path found: ";
for (const auto &pos : path) {
std::cout << "(" << pos.row << ", " << pos.col << ") ";
}
std::cout << std::endl;
} else {
std::cout << "No path found." << std::endl;
}
return 0;
}
// Path found: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4)]Implementation Benefits
- Flexibility: Custom heuristic functions and modular design allow tailoring the algorithm to various use cases.
- Efficiency: Priority queues (or custom implementations thereof) ensure optimal node selection during search.
- Maintainability: Code is separated into distinct components (e.g., Node classes, path reconstruction, grid handling) for clarity and easy updates.
- Robustness: The implementations include thorough error checking (such as boundary validation and path existence) and proper resource management (e.g. RAII in C++), ensuring reliability even in edge cases.
Language-Specific Notes
- Python: Leverages the built-in
heapqmodule for a concise and effective priority queue; type hints improve code clarity. - Java: Uses the
PriorityQueueclass and theBiFunctioninterface to allow flexible heuristic functions while ensuring strong type safety. - JavaScript: Features a custom
PriorityQueueclass built with modern ES6+ syntax, and encapsulates functionality to avoid global variable conflicts. - C++: Employs the STL
priority_queuefor high performance and uses RAII (and smart pointers where applicable) to ensure proper memory management.
Key Design Choices
- Memory Management:
- Python: Automatic garbage collection handles object cleanup.
- Java: The JVM manages memory, reducing the need for manual intervention.
- JavaScript: Modern V8 garbage collection, with code encapsulated to prevent global namespace pollution.
- C++: RAII patterns and smart pointers (or careful manual cleanup) ensure that memory is released properly.
- Data Structures:
- Priority Queues for selecting the next node based on the lowest estimated total cost (f-score).
- Hash tables or dictionaries for O(1) lookup of nodes in open/closed sets.
- Sets for efficiently tracking visited nodes.
- Error Handling:
- Each implementation includes boundary checks for grid access and clear handling of unreachable targets.
- C++ implementation explicitly cleans up allocated resources to avoid memory leaks.
Performance Considerations
The implementations focus on optimizing both time and space:
- Space Optimization:
- Efficient storage of node information with minimal overhead.
- Reuse of node objects when appropriate, and proper cleanup of resources.
- Time Optimization:
- O(log n) node selection via priority queues ensures fast extraction of the next candidate.
- O(1) lookup for nodes in the open/closed sets speeds up neighbor checking.
- Efficient path reconstruction avoids unnecessary iterations after reaching the goal.
- Cache Efficiency:
- Contiguous memory layouts (especially in C++ and Python) help maximize CPU cache performance.
- Minimized dynamic allocation during the search process improves overall speed.
- Careful structuring of data traversal ensures that only the necessary nodes are processed.
Now that we have an understanding of the algorithm and how to implement it, let's look at how it compares to other common path-finding algorithms.
Relationship to Other Path-Finding Algorithms
A* represents a significant advancement in pathfinding, as it combines the systematic approach of uniform‑cost search (as seen in Dijkstra’s algorithm) with the informed guidance of best‑first search. By incorporating a heuristic function, A* can focus its search on promising paths and reduce the number of nodes expanded. Understanding how A* compares to other algorithms is key to selecting the best approach for your specific problem.
| Algorithm | Relationship to A* | Key Differences | Trade-offs |
|---|---|---|---|
| Dijkstra's Algorithm |
|
|
|
| Bellman-Ford |
|
|
|
| Floyd-Warshall |
|
|
|
Feature Comparison Matrix
The matrix below provides a structured comparison of key features and characteristics of various pathfinding algorithms, making it easier to choose the right one based on your requirements.
| Feature | A* | Dijkstra's | Bellman-Ford | Floyd-Warshall |
|---|---|---|---|---|
| Time Complexity | O((V + E) log V)* | O((V + E) log V) | O(VE) | O(V³) |
| Space Complexity | O(V) | O(V) | O(V) | O(V²) |
| Negative Edges | ✗ | ✗ | ✓ | ✓ |
| All Pairs | ✗ | ✗ | ✗ | ✓ |
| Heuristic-guided | ✓ | ✗ | ✗ | ✗ |
| Optimality | ✓** | ✓ | ✓ | ✓ |
| Early Termination | ✓ | ✓ | ✗ | ✗ |
| Memory Usage | Medium | Medium | Low | High |
- * A*’s performance depends on the quality of the heuristic (given here for an admissible heuristic).
- ** A* guarantees optimality only with both admissible and consistent heuristics.
- Early termination is possible for A* and Dijkstra’s when the target is reached.
- Memory usage can vary with implementation details and graph size.
Selection Guidelines
When choosing between algorithms, consider:
- Graph Properties:
- If negative weights are present, use Bellman-Ford.
- For dense graphs requiring all-pairs shortest paths, Floyd-Warshall is appropriate.
- If you have domain knowledge to design an effective heuristic, A* is a strong choice.
- For single-source shortest paths without a heuristic, Dijkstra's is reliable.
- Performance Requirements:
- Real-time pathfinding typically favors A* with a good heuristic.
- All-pairs preprocessing problems may be best served by Floyd-Warshall.
- If memory is a constraint, Bellman-Ford may be preferable.
- For general shortest path needs, Dijkstra’s algorithm is robust.
Key Insights
- Performance vs. Applicability: A* offers excellent performance with a well-chosen heuristic, but requires domain-specific knowledge.
- Memory Trade-offs: Floyd-Warshall uses more memory but provides all-pairs solutions, while A* and Dijkstra’s are more memory‑efficient for single‑source queries.
- Flexibility: Bellman-Ford and Floyd-Warshall handle negative edges, though they tend to be slower.
- Optimality: All algorithms yield optimal solutions within their respective constraints.
Conclusion
This guide has examined the A* algorithm from its mathematical foundations to its practical implementations and comparisons with other pathfinding techniques. By blending Dijkstra's systematic exploration with heuristic guidance, A* efficiently reduces search space while guaranteeing optimality (when using admissible and consistent heuristics).
When to Use A*
- Single-source, single-target pathfinding
- Availability of domain-specific heuristics
- Optimality is required
- Sufficient memory for open/closed set maintenance
- Critical performance and search space reduction
Implementation Considerations
- Use priority queues (e.g., binary or Fibonacci heaps) for fast node selection
- Select data structures based on graph size
- Design and validate effective heuristic functions
- Optimize for space in large-scale applications
Best Practices
- Heuristic Design: Ensure admissibility and consistency while balancing accuracy with computational cost.
- Performance Optimization: Use efficient data structures, consider path smoothing, and hierarchical approaches.
- Error Handling: Validate inputs and handle unreachable targets gracefully.
A* exemplifies the power of combining systematic search with informed guidance, making it indispensable for applications ranging from navigation systems to video games.
If you found this guide helpful, please consider citing or sharing it. For additional resources on graph algorithms and practical implementations, check out our Further Reading section.
Happy pathfinding!
Core Concepts
-
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Original 1968 paper by Hart, Nilsson, and Raphael introducing A* and proving its properties.
-
Amit's A* Pages
Comprehensive resource on A* implementation and optimization techniques.
-
Dijkstra's Algorithm: A Comprehensive Guide to Single-Source Shortest Paths
Complete guide to understanding Dijkstra's algorithm, which forms the foundation of A*. Includes detailed explanations, implementations, and visualizations of the base algorithm that A* extends.
Implementation Resources
-
Red Blob Games - A* Implementation
Interactive tutorial on implementing A* with visual explanations.
-
GitHub A* Resources
Collection of A* implementations in various languages with different optimizations.
Advanced Topics
-
Hierarchical Path Planning for Multi-Size Agents in Heterogeneous Environments
Research on applying A* to complex, hierarchical pathfinding problems.
-
Pathfinding Algorithms in Game Development
Comprehensive review of A* variants and optimizations for game development.
Attribution and Citation
If you found this guide and tools helpful, feel free to link back to this page or cite it in your work!
Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.