A-Star

A* is a widely used graph traversal and pathfinding algorithm that finds the path from a given initial node to a given final node while minimizing the total cost (distance plus any other costs). It uses a combination of Best First Search and Dijkstra’s algorithm.

Demo

See this Jupyter notebook for an example of A* in action:

Basics of A*

\(g(n)\): the exact cost of the path from the starting point to any vertex \(n\).
\(h(n)\): the estimated cost from vertex \(n\) to the goal. This is the heuristic part of the algorithm.
\(f(n)\): the estimated total cost of the cheapest path from the start to the goal that goes through \(n\). It's computed as: \(f(n) = g(n) + h(n)\)

How A* works:

Initialize the open set with the starting node.
While the open set is not empty:
- Find the node with the lowest \(f(n)\) in the open set.
- Pop the node from the open set.
- Generate the node's successors and set their parents to the current node.
- For each successor:
  - If successor is the goal, reconstruct and return the path.
  - Else, compute its \(f(n)\) value and place it in the open set.
If the open set is empty and we haven't found the goal, a path doesn't exist.

Pseudocode

OPEN_SET = {start node}
CLOSED_SET = {}
for each iteration:
    current = node with lowest f(n) in OPEN_SET

if current is the goal:
    return reconstructed path

move current from OPEN_SET → CLOSED_SET

for each successor of current:
    if successor in CLOSED_SET:
        skip

    compute f(n) = g(n) + h(n)
    set successor's parent = current

    if successor not in OPEN_SET:
        add successor to OPEN_SET

if OPEN_SET is empty:
    return no path exists

Try It Yourself

Click and drag on the grid to draw walls. Drag the S (start) or E (end) node to reposition them, then hit Run A* to watch the algorithm explore and find the shortest path.

Start End Wall Open Set Closed Set Path

Click and drag to draw walls. Drag S or E to move them.