A* (A-Star) Algorithm
Description
A* is an informed search algorithm that finds the shortest path between nodes in a graph. Unlike Dijkstra's algorithm, A* uses heuristics to guide its search, making it more efficient for many practical applications.
History
The A* (pronounced "A-star") algorithm was created in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael at the Stanford Research Institute (now SRI International). It was developed as part of the Shakey robotics project, which aimed to build a mobile robot that could plan its own actions. A* was a significant improvement over existing pathfinding algorithms like Dijkstra's algorithm because it incorporated heuristics to guide the search process more efficiently. The algorithm was first described in their 1968 paper "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," which has become one of the most cited papers in computer science. The key innovation of A* was combining Dijkstra's algorithm with heuristic estimation (similar to what was used in Breadth-First Search) to create an algorithm that was both optimal and efficient. The name "A*" was chosen because it was an improvement over their previous algorithm called "A1", and the asterisk represented that it was optimal under appropriate conditions. Since its introduction, A* has become the foundation for many pathfinding applications, from video games to robotics. Its influence extends beyond just pathfinding - the principles behind A* have inspired many other informed search algorithms and continue to influence artificial intelligence research today.
How It Works
- Initialize the open list with the starting node
- For each node, maintain:
- g(n): Cost from start to current node
- h(n): Estimated cost from current node to goal
- f(n) = g(n) + h(n): Total estimated cost
- While the open list is not empty:
- Get node with lowest f(n) from open list
- If current node is goal, reconstruct path
- Generate successors and calculate their scores
- Add successors to open list if better path found
Visualization
Click on the grid to set start and end points
Implementation
from heapq import heappush, heappop
from dataclasses import dataclass, field
from typing import List, Set, Dict, Tuple
@dataclass
class Node:
x: int
y: int
f: float = 0.0
g: float = 0.0
h: float = 0.0
parent: 'Node' = None
def __eq__(self, other):
return self.x == other.x and self.y == other.y
def __lt__(self, other):
return self.f < other.f
def __hash__(self):
return hash((self.x, self.y))
class AStar:
@staticmethod
def heuristic(a: Node, b: Node) -> float:
# Manhattan distance
return abs(a.x - b.x) + abs(a.y - b.y)
@staticmethod
def is_valid(x: int, y: int, rows: int, cols: int) -> bool:
return 0 <= x < rows and 0 <= y < cols
@staticmethod
def find_path(grid: List[List[bool]], start_pos: Tuple[int, int],
end_pos: Tuple[int, int]) -> List[Tuple[int, int]]:
"""
Find the shortest path using A* algorithm
Args:
grid: 2D grid where True represents walls/obstacles
start_pos: Starting position (x, y)
end_pos: Target position (x, y)
Returns:
List of coordinates representing the path
"""
rows, cols = len(grid), len(grid[0])
start_x, start_y = start_pos
end_x, end_y = end_pos
# Create start and end nodes
start_node = Node(start_x, start_y)
end_node = Node(end_x, end_y)
# Initialize open and closed sets
open_set: List[Node] = []
closed_set: Set[Node] = set()
# Add start node to open set
heappush(open_set, start_node)
# Define possible movements (up, down, left, right)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while open_set:
current = heappop(open_set)
if current == end_node:
path = []
while current:
path.append((current.x, current.y))
current = current.parent
return path[::-1]
closed_set.add(current)
# Check all neighboring nodes
for dx, dy in directions:
new_x, new_y = current.x + dx, current.y + dy
# Skip if position is invalid or is a wall
if not AStar.is_valid(new_x, new_y, rows, cols) or grid[new_x][new_y]:
continue
neighbor = Node(new_x, new_y)
# Skip if node has been evaluated
if neighbor in closed_set:
continue
# Calculate g, h, and f values
tentative_g = current.g + 1
# Check if this path is better than previous ones
if neighbor not in open_set or tentative_g < neighbor.g:
neighbor.parent = current
neighbor.g = tentative_g
neighbor.h = AStar.heuristic(neighbor, end_node)
neighbor.f = neighbor.g + neighbor.h
if neighbor not in open_set:
heappush(open_set, neighbor)
return [] # No path found
@staticmethod
def print_path(path: List[Tuple[int, int]]):
"""Print the path coordinates"""
print(" -> ".join(f"({x},{y})" for x, y in path))
# Example usage
if __name__ == "__main__":
# Create a sample grid (False = empty, True = wall)
grid = [
[False, False, False, False, False],
[True, True, False, True, False],
[False, False, False, False, False],
[False, True, True, True, False],
[False, False, False, False, False]
]
start = (0, 0)
end = (4, 4)
path = AStar.find_path(grid, start, end)
if path:
print("Path found:")
AStar.print_path(path)
else:
print("No path found!")
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <unordered_set>
class AStar {
private:
struct Node {
int x, y;
double f, g, h;
Node* parent;
Node(int x, int y) : x(x), y(y), f(0), g(0), h(0), parent(nullptr) {}
bool operator==(const Node& other) const {
return x == other.x && y == other.y;
}
};
struct NodeCompare {
bool operator()(const Node* a, const Node* b) const {
return a->f > b->f;
}
};
static double heuristic(const Node* a, const Node* b) {
// Manhattan distance
return std::abs(a->x - b->x) + std::abs(a->y - b->y);
}
static bool isValid(int x, int y, int rows, int cols) {
return x >= 0 && x < rows && y >= 0 && y < cols;
}
static void printPath(const std::vector>& path) {
for (const auto& [x, y] : path) {
std::cout << "(" << x << "," << y << ") ";
}
std::cout << std::endl;
}
public:
static std::vector> findPath(
const std::vector>& grid,
int startX, int startY,
int endX, int endY
) {
const int rows = grid.size();
const int cols = grid[0].size();
std::priority_queue, NodeCompare> openSet;
std::unordered_set closedSet;
Node* startNode = new Node(startX, startY);
Node* endNode = new Node(endX, endY);
openSet.push(startNode);
const std::vector> directions = {
{-1, 0}, {1, 0}, {0, -1}, {0, 1}
};
while (!openSet.empty()) {
Node* current = openSet.top();
openSet.pop();
if (*current == *endNode) {
std::vector> path;
while (current != nullptr) {
path.push_back({current->x, current->y});
current = current->parent;
}
std::reverse(path.begin(), path.end());
return path;
}
closedSet.insert(current);
for (const auto& [dx, dy] : directions) {
int newX = current->x + dx;
int newY = current->y + dy;
if (!isValid(newX, newY, rows, cols) || grid[newX][newY]) {
continue;
}
Node* neighbor = new Node(newX, newY);
if (closedSet.find(neighbor) != closedSet.end()) {
delete neighbor;
continue;
}
double tentativeG = current->g + 1;
neighbor->parent = current;
neighbor->g = tentativeG;
neighbor->h = heuristic(neighbor, endNode);
neighbor->f = neighbor->g + neighbor->h;
openSet.push(neighbor);
}
}
return std::vector>();
}
};
using System;
using System.Collections.Generic;
using System.Linq;
public class AStar
{
private class Node
{
public int X { get; }
public int Y { get; }
public double F { get; set; }
public double G { get; set; }
public double H { get; set; }
public Node Parent { get; set; }
public Node(int x, int y)
{
X = x;
Y = y;
F = G = H = 0;
Parent = null;
}
public override bool Equals(object obj)
{
if (obj is Node other)
{
return X == other.X && Y == other.Y;
}
return false;
}
public override int GetHashCode()
{
return HashCode.Combine(X, Y);
}
}
private static double Heuristic(Node a, Node b)
{
// Manhattan distance
return Math.Abs(a.X - b.X) + Math.Abs(a.Y - b.Y);
}
private static bool IsValid(int x, int y, int rows, int cols)
{
return x >= 0 && x < rows && y >= 0 && y < cols;
}
public static List<(int, int)> FindPath(
bool[,] grid,
int startX, int startY,
int endX, int endY)
{
var rows = grid.GetLength(0);
var cols = grid.GetLength(1);
var openSet = new SortedSet(Comparer.Create((a, b) =>
a.F != b.F ? a.F.CompareTo(b.F) : a.GetHashCode().CompareTo(b.GetHashCode())));
var closedSet = new HashSet();
var startNode = new Node(startX, startY);
var endNode = new Node(endX, endY);
openSet.Add(startNode);
var directions = new[]
{
(-1, 0), (1, 0), (0, -1), (0, 1)
};
while (openSet.Count > 0)
{
var current = openSet.Min;
openSet.Remove(current);
if (current.Equals(endNode))
{
var path = new List<(int, int)>();
while (current != null)
{
path.Add((current.X, current.Y));
current = current.Parent;
}
path.Reverse();
return path;
}
closedSet.Add(current);
foreach (var (dx, dy) in directions)
{
var newX = current.X + dx;
var newY = current.Y + dy;
if (!IsValid(newX, newY, rows, cols) || grid[newX, newY])
{
continue;
}
var neighbor = new Node(newX, newY);
if (closedSet.Contains(neighbor))
{
continue;
}
var tentativeG = current.G + 1;
neighbor.Parent = current;
neighbor.G = tentativeG;
neighbor.H = Heuristic(neighbor, endNode);
neighbor.F = neighbor.G + neighbor.H;
openSet.Add(neighbor);
}
}
return new List<(int, int)>();
}
public static void PrintPath(List<(int, int)> path)
{
foreach (var (x, y) in path)
{
Console.Write($"({x},{y}) ");
}
Console.WriteLine();
}
}
Complexity Analysis
Time Complexity
O((V + E) log V) where:
- V is the number of vertices (nodes)
- E is the number of edges
- log V comes from the priority queue operations
Note: In a grid-based implementation, where each cell connects to its neighbors, the complexity can be expressed as O(n log n) where n is the number of cells.
Space Complexity
O(V) where:
- V is the number of vertices (nodes)
- Space is needed for the open and closed sets
- Additional space for the path reconstruction
Best Case
O(1) when the target is the starting node or immediately adjacent.
Worst Case
O((V + E) log V) when the algorithm needs to explore most of the graph before finding the target.
Advantages and Disadvantages
Advantages
- More efficient than Dijkstra's algorithm for most pathfinding scenarios
- Guarantees the shortest path when using an admissible heuristic
- Can be optimized with different heuristics for specific use cases
- Widely used in games and robotics
- Can handle both weighted and unweighted graphs
- Easy to modify for different movement patterns
Disadvantages
- Memory intensive for large graphs
- Performance depends heavily on the heuristic function
- May not perform well in maze-like environments with many obstacles
- Can be slower than other algorithms when the heuristic is poor
- More complex to implement than simpler algorithms like BFS
- May explore unnecessary nodes if the heuristic overestimates
Common Applications
- Video game pathfinding (NPCs, navigation)
- Robotics and autonomous navigation
- GPS and navigation systems
- Network routing
- Puzzle solving (8-puzzle, sliding puzzles)
- Automated planning systems