Pathfinding

A* Search

Heuristic-driven shortest pathfinding algorithm for grids and navigation graphs.

What is A* Search?

A* (A-Star) is a popular and efficient heuristic-based pathfinding algorithm. It is used to find the shortest path from a start node to a goal node. It combines the actual distance from the start node (g-score) with an estimated heuristic distance to the goal node (h-score) using the function f(n) = g(n) + h(n) to prioritize node exploration.

Key Characteristics:

  • Uses heuristics (e.g. Manhattan or Euclidean distance) to guide search.
  • Guarantees the shortest path if the heuristic is admissible (never overestimates).
  • Maintains Open and Closed lists of candidate nodes.
  • Widely used in game AI, robotics, and mapping applications.

Complexity Analysis

Avg Time Complexity: O(E * log V) where E is edges and V is vertices
Space Complexity: O(V) node queue allocation
Best Case: O(V) (heuristic leads directly to target)
Worst Case: O(E) (exploring all nodes in graph)

How it Works Step-by-Step

  1. Initialize Lists: Create an Open list (min-priority queue) containing the start node, and an empty Closed list.
  2. Extract Best Node: Pop the node n with the lowest f(n) from the Open list.
  3. Target Check: If n is the goal, reconstruct the path and terminate.
  4. Relax Neighbors: For each neighbor, calculate its tentative g-score. If it's lower than recorded, update its parent, g-score, f-score, and add to Open list.
  5. Iterate: Mark node n as closed and repeat steps 2-4 until target found or Open list empty.

Code Implementation

Worked Trace Example

A* Search on grid from (0,0) to (2,2) with obstacle at (1,1):
1. Start node (0,0): g=0, h=4 (Manhattan to (2,2)), f=4.
2. Open neighbors (1,0) and (0,1): both have g=1, h=3, f=4.
3. Pop (1,0): check neighbors. (2,0) has g=2, h=2, f=4. Obstacle at (1,1) skipped.
4. Pop (2,0): check neighbors. (2,1) has g=3, h=1, f=4.
5. Pop (2,1): neighbor (2,2) is goal! Path found: (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2).

Ready to Understand A* Search Visually?

Don't just read about it. Launch our interactive, premium algorithm visualizer to step through calculations in real-time.

Launch A* Search Visualizer →