A* Algorithm

Overview

A* (A-star) is a graph traversal and pathfinding algorithm that finds the shortest path from a start node to a target node. It combines the benefits of Dijkstra's algorithm (guaranteed optimality) with a heuristic function (efficiency) to guide the search toward the goal.

A* uses an evaluation function f(n) = g(n) + h(n), where:

g(n): Cost from start to current node (known)
h(n): Heuristic estimate from current node to goal (estimated)
f(n): Total estimated cost (g + h)

A* is widely used in game development, robotics, GPS navigation, and any application requiring efficient pathfinding with a known goal.

History: Shakey the Robot

A* was developed in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael at the Stanford Research Institute (SRI), specifically for the navigation problems faced by Shakey the Robot. Shakey, built at SRI between 1966 and 1972, was the world's first general-purpose mobile robot capable of reasoning about its own actions, a machine that could observe its environment, formulate a plan, and carry out a sequence of actions to achieve a stated goal. Shakey needed to navigate through rooms full of obstacles, and existing algorithms, plain Dijkstra's, breadth-first search, and various early heuristic-guided searches, either explored too many states or produced suboptimal paths.

Hart, Nilsson and Raphael's insight was to combine the guaranteed optimality of Dijkstra's algorithm (which explores nodes in order of their known distance from the start) with the goal-directed efficiency of best-first search (which explores nodes in order of their estimated distance to the goal). Their evaluation function f(n) = g(n) + h(n) reads as "total path cost through n = known cost-so-far + estimated cost-to-go," and the priority queue picks whichever open node has the lowest estimated total cost.

The paper "A Formal Basis for the Heuristic Determination of Minimum Cost Paths" was published in IEEE Transactions on Systems Science and Cybernetics in 1968. Hart, Nilsson and Raphael proved that A* is optimal when the heuristic never overestimates (admissibility), and that A* is optimally efficient among admissible algorithms, no algorithm using the same heuristic can find the optimal path while expanding fewer nodes. This second property is remarkable and specific to A*: any algorithm that achieves the same optimality guarantees using the same heuristic must do at least as much work.

Nils Nilsson later became one of the founders of the field of artificial intelligence; his textbook "Principles of Artificial Intelligence" (1980) was a standard reference for a generation of AI researchers, and A* has been a fixture of AI courses ever since.

Designing a Good Heuristic

A*'s performance is dominated by the quality of the heuristic function h(n). A trivial heuristic h(n) = 0 turns A* into pure Dijkstra's (correct but slow). A perfect heuristic that returns the true shortest-path distance turns A* into a single-shot algorithm that never explores a suboptimal node. Real heuristics fall between these extremes, and choosing one is one of the more consequential engineering decisions in a pathfinding system.

The Two Correctness Conditions

Admissibility. The heuristic must never overestimate the true remaining cost. If h(n) ≤ true distance from n to goal for every n, A* is guaranteed to find an optimal path, but only if you allow nodes to be re-opened when a better path is found. Without re-opening, admissibility alone can fail to give optimality.

Consistency (also called monotonicity). The heuristic must satisfy h(n) ≤ cost(n, n') + h(n') for every edge (n, n'). Consistency implies admissibility and additionally guarantees that A* never needs to re-open a node, the first time A* takes a node out of the priority queue, its distance is final. Every heuristic based on a physical distance (Manhattan, Euclidean, octile) on a grid is consistent because distance is a metric and satisfies the triangle inequality.

Standard Heuristics for Grid Pathfinding

Manhattan distance for 4-directional grids: |x₂−x₁| + |y₂−y₁|. Admissible when diagonal movement is not allowed.
Chebyshev distance for 8-directional grids where diagonals cost the same as cardinal moves: max(|x₂−x₁|, |y₂−y₁|).
Octile distance for 8-directional grids where diagonals cost √2: max + (√2 − 1) · min of the axis differences. This is the admissible heuristic for the common "queens-move" grid.
Euclidean distance for grids allowing arbitrary movement directions: √((Δx)² + (Δy)²). Admissible for any pathfinding where the underlying space is metric.

Heuristics for Non-Grid Problems

In A* applied to state-space search, solving Rubik's cubes, 15-puzzles, Sokoban, planning problems, heuristics require more creativity. Common approaches:

Relaxation heuristics. Solve a simpler version of the problem exactly, and use that solution's cost as the heuristic. For the 15-puzzle, ignore the fact that tiles collide with each other and count only the moves each tile individually needs (this is called the "sum of Manhattan distances" heuristic and is the standard for the 15-puzzle).
Pattern databases. Precompute exact solution costs for subproblems (say, solving just 8 of the 15 tiles), store them in a table, and combine them at query time. Pattern databases can give near-perfect heuristics for many puzzles, at the cost of large lookup tables.
Learned heuristics. Train a neural network to predict remaining cost. Recent work at DeepMind and elsewhere has shown that learned heuristics can outperform hand-crafted ones on many domains. The catch is that learned heuristics are usually inadmissible, they overestimate sometimes, so A* using them finds near-optimal but not guaranteed optimal paths.

Variants and Improvements

Weighted A* (WA*)

Multiply the heuristic by a weight w ≥ 1: f(n) = g(n) + w · h(n). Larger w makes the search more goal-directed at the cost of optimality, the solution is guaranteed to be at most w times the optimal cost. In practice a small weight (like w = 1.5) often gives near-optimal solutions with dramatic speed improvements. Used in many game AIs where "fast" beats "optimal."

Iterative Deepening A* (IDA*)

A memory-efficient variant that avoids A*'s worst weakness: memory. Instead of maintaining a large open set, IDA* performs depth-first search with a cost threshold, increasing the threshold when no solution is found. It uses O(depth) memory instead of O(b^d), at the cost of revisiting nodes multiple times. Standard for large state-space searches where memory is more limiting than time.

Bidirectional A*

Run A* simultaneously from start and from goal (with the roles of "start" and "goal" reversed for the backward search) and terminate when the two frontiers meet. On typical graphs this reduces node expansions by roughly the square root of what plain A* would do, a real win on continent-scale routing. The tricky part is the termination condition: the naive "they touch, we're done" is wrong, and getting it right is subtle.

Jump Point Search (JPS)

A dramatically faster A* variant specifically for uniform-cost grids (Harabor and Grastien 2011). JPS uses the grid's symmetry to skip over long uninteresting stretches in a single jump, reducing the number of nodes A* actually expands by an order of magnitude on typical maps. It is now the standard pathfinding algorithm in real-time strategy games and open-world games where the terrain is grid-based.

Contraction Hierarchies + A*

For road networks where the graph is static but queries are frequent, contraction hierarchies preprocess the graph to add "shortcut" edges that let A* skip past entire regions. Real GPS routing systems use combinations of contraction hierarchies, A* with landmark-based heuristics (ALT), and bidirectional search to answer coast-to-coast queries in a few milliseconds.

How It Works

The algorithm follows these steps:

Initialize: Add start node to open set with f(start) = h(start)
Iterate: While open set is not empty:
- Select node with lowest f(n) from open set
- Move it to closed set
- If it's the goal, reconstruct and return path
- For each neighbor:
  - Calculate tentative g(n) = g(current) + cost(current, neighbor)
  - If neighbor not in open set or new path is better, update it
  - Calculate f(n) = g(n) + h(n) and add to open set
Result: Shortest path from start to goal (if exists)

A* Algorithm Pseudocode


AStar(graph, start, goal, heuristic):
    open_set = priority_queue containing (f(start), start)
    closed_set = set()
    g_score[start] = 0
    f_score[start] = heuristic(start, goal)
    parent = {}
    
    while open_set is not empty:
        current = node in open_set with lowest f_score
        if current == goal:
            return reconstruct_path(parent, goal)
        
        open_set.remove(current)
        closed_set.add(current)
        
        for each neighbor of current:
            if neighbor in closed_set:
                continue
            
            tentative_g = g_score[current] + cost(current, neighbor)
            
            if neighbor not in open_set:
                open_set.add(neighbor)
            else if tentative_g >= g_score[neighbor]:
                continue  # Not a better path
            
            parent[neighbor] = current
            g_score[neighbor] = tentative_g
            f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)
    
    return failure  // No path exists

Implementation


import heapq

def heuristic(node, goal):
    """Heuristic function - Manhattan distance for grid"""
    return abs(node[0] - goal[0]) + abs(node[1] - goal[1])

def a_star(graph, start, goal, heuristic_func):
    """
    graph: dict mapping node -> list of (neighbor, cost) tuples
    start: start node
    goal: target node
    heuristic_func: function(node, goal) -> estimated cost
    """
    open_set = [(0, start)]  # (f_score, node)
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic_func(start, goal)}
    closed_set = set()
    
    while open_set:
        current_f, current = heapq.heappop(open_set)
        
        if current == goal:
            # Reconstruct path
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]
        
        closed_set.add(current)
        
        for neighbor, cost in graph.get(current, []):
            if neighbor in closed_set:
                continue
            
            tentative_g = g_score[current] + cost
            
            if neighbor not in g_score or tentative_g < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score[neighbor] = tentative_g + heuristic_func(neighbor, goal)
                heapq.heappush(open_set, (f_score[neighbor], neighbor))
    
    return None  # No path found

# Example: Grid pathfinding
def grid_heuristic(node, goal):
    """Manhattan distance for grid"""
    return abs(node[0] - goal[0]) + abs(node[1] - goal[1])

def a_star_grid(grid, start, goal):
    """A* for 2D grid with obstacles"""
    rows, cols = len(grid), len(grid[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    def get_neighbors(node):
        r, c = node
        neighbors = []
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != 1:
                neighbors.append(((nr, nc), 1))  # Cost 1 for each step
        return neighbors
    
    graph = {}
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1:  # Not an obstacle
                graph[(r, c)] = get_neighbors((r, c))
    
    return a_star(graph, start, goal, grid_heuristic)

Heuristic Functions

The quality of the heuristic function determines A*'s efficiency. A good heuristic should be:

Admissible: never overestimates the true remaining cost, h(n) ≤ h*(n).
Consistent (monotone): h(n) ≤ cost(n, n') + h(n') for every neighbour n', and h(goal) = 0. This is a triangle inequality on the heuristic.

Consistency is the stronger property: every consistent heuristic is admissible, but not every admissible heuristic is consistent. In practice almost all natural heuristics, Manhattan, Euclidean, octile, are consistent, so the distinction rarely bites. It matters enormously when it does; see Optimality below.

Common Heuristics

A heuristic is admissible only with respect to a particular movement model. Matching them up wrongly is the most common way to break A* in practice:

Manhattan Distance, for 4-directional grid movement:
```
h(n) = |x₁ - x₂| + |y₁ - y₂|
```
Not admissible for 8-directional movement, where a diagonal step covers both axes at once and Manhattan overestimates.
Chebyshev Distance, for 8-directional movement where a diagonal costs the same as a straight step:
```
h(n) = max(|x₁ - x₂|, |y₁ - y₂|)
```
Octile Distance, for 8-directional movement where a diagonal costs √2, which is the usual game setup:
```
dx, dy = |x₁ - x₂|, |y₁ - y₂|
h(n) = (dx + dy) + (√2 - 2) × min(dx, dy)
```
Chebyshev underestimates here (still admissible, just weaker); Manhattan overestimates and breaks optimality.
Euclidean Distance, for movement at any angle:
```
h(n) = √((x₁ - x₂)² + (y₁ - y₂)²)
```
Admissible on any grid, but loose for 4- or 8-way movement, so A* explores more than it needs to.

h(n) = 0 is always admissible, and reduces A* to exactly Dijkstra's algorithm. That is the useful mental model: A* is Dijkstra's plus a hint about which direction the goal lies in. Scale matters too: if edge costs are in metres, the heuristic must be in metres.

Complexity Analysis

Time Complexity: O(b^d) for tree search, where b is the branching factor and d the solution depth. On a graph with a closed set, it is bounded by the number of reachable states, O(V + E log V) with a binary heap, the same as Dijkstra's, since A* is Dijkstra's with a modified priority. A good heuristic reduces the constant enormously but does not change the worst-case bound.
Space Complexity: O(b^d), usually the binding constraint. A* stores every generated node, and running out of memory is the typical failure mode on large searches, well before running out of time. IDA* and SMA* trade time for bounded memory.

Performance depends almost entirely on heuristic quality. With h(n) = 0 A* is exactly Dijkstra's. With a perfect heuristic h(n) = h*(n) it walks straight to the goal, though only if ties are broken in favour of larger g, otherwise it can still wander among equal-f nodes. Between those extremes, a heuristic that dominates another (is closer to h* everywhere while staying admissible) never expands more nodes.

Optimality

The two properties guarantee different things, and conflating them is a common source of subtle bugs:

Admissibility alone guarantees optimality, but only if the search is allowed to reopen closed nodes. If a shorter route to an already-expanded node is discovered later, it must be moved back into the open set and expanded again.
Consistency additionally guarantees that the first time A* expands a node, it has already found the optimal path to it. No node is ever expanded twice, so the closed set can be final and you can safely skip anything in it.

This has a direct consequence for the code above. The implementation does if neighbor in closed_set: continue and never reopens, which is the standard graph-search formulation. That is correct and efficient with a consistent heuristic. With a heuristic that is merely admissible, it can return a suboptimal path, not merely run slower. So: use a consistent heuristic (all of the standard ones above are), or remove the closed-set skip and allow reopening.

If the heuristic is not even admissible, if it can overestimate. A* gives up optimality entirely, though it may still find a good path quickly. That trade is sometimes deliberate; see Weighted A* under Optimizations.

Example

Finding path from (0,0) to (3,3) on a grid:

Grid (0 = free, 1 = obstacle), rows are (r, c) with r downward:

        c=0  c=1  c=2  c=3
  r=0    0    0    0    0
  r=1    0    1    1    0        <- (1,1) and (1,2) are walls
  r=2    0    0    0    0
  r=3    0    0    0    0

Start: (0, 0)     Goal: (3, 3)     4-directional movement, cost 1 per step
Heuristic: Manhattan, h((0,0)) = |0-3| + |0-3| = 6

Step 1: expand (0,0)    g=0, h=6, f=6
Step 2: expand the open node with lowest f, tie-breaking on larger g
Step 3: repeat until (3,3) is expanded

Two optimal paths of length 6, either side of the wall:

  down the left column     (0,0) -> (1,0) -> (2,0) -> (3,0) -> (3,1) -> (3,2) -> (3,3)
  across the top row       (0,0) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (2,3) -> (3,3)

Manhattan distance from (0,0) to (3,3) is 6 and both routes take exactly 6 steps,
so the heuristic is exact here and A* expands almost nothing off the path.

When to Use A*

A* is ideal when:

You have a known goal/target
You can design a good heuristic function
You need optimal or near-optimal paths
Graph is large but heuristic can guide search
Game development, robotics, navigation

Consider alternatives when:

No good heuristic available → Use Dijkstra's
Need all shortest paths → Use Dijkstra's or Floyd-Warshall
Unweighted graph → Use BFS (simpler)
Negative weights → Use Bellman-Ford

A* vs Other Algorithms

Algorithm	Heuristic	Optimal	Best For
BFS	No	Yes (unweighted)	Unweighted graphs
Dijkstra's	No	Yes	Weighted graphs, no heuristic
A*	Yes	Yes (with good heuristic)	Pathfinding with known goal

Optimizations

Bidirectional A*: Search from both start and goal simultaneously
Weighted A*: Use f(n) = g(n) + ε × h(n) for faster (but suboptimal) paths
Jump Point Search: Optimize A* for uniform-cost grids
Hierarchical A*: Use multiple abstraction levels
IDA*: iterative-deepening A*, O(d) memory instead of O(b^d), at the cost of re-expanding nodes. The standard choice for puzzles like the 15-puzzle.
D* Lite / LPA*: incremental replanning when the map changes. Repairs the existing search rather than restarting, the standard approach in robotics, where obstacles appear as sensors discover them.
Theta* / any-angle: allows paths that are not constrained to grid edges, producing shorter, more natural routes.
ARA*: anytime A*, returns a suboptimal path quickly, then improves it while time remains.

For road networks specifically, A* has largely been superseded by preprocessing-based methods, contraction hierarchies and hub labeling answer queries orders of magnitude faster after an offline build step.

Real-World Applications

Game Development: NPC pathfinding, enemy AI
Robotics: Navigation and obstacle avoidance
GPS Navigation: Route planning and optimization
Network Routing: Finding optimal network paths
Puzzle Solving: 15-puzzle, sliding puzzles

Related Algorithms

Explore other searching algorithms:

Dijkstra's Algorithm - Without heuristic
Breadth-First Search - Unweighted graphs
Depth-First Search - Graph traversal
Back to Searching Algorithms Overview