Algorithms/Graph/A* Search

A* Search

Best-first shortest path on a grid using f = g + h. Click cells to draw walls, set start/end, or change the heuristic.

GraphHeuristicShortest PathAI PathfindingO(E log V)

Grid(20×12)

1,1 → 18,10

Heuristic:

StartGoalWallCurrentOpenClosedPathf = g + h (top / left / right)

1 / 0

Speed

astar.js

1function aStar(grid, start, goal, heuristic) {

2 const open = new MinHeap();

3 const closed = new Set();

4 const g = {}; // cost from start

5 const h = {}; // heuristic estimate to goal

6 const f = {}; // f = g + h

7 const parent = {};

9 g[start] = 0;

10 h[start] = heuristic(start, goal);

11 f[start] = g[start] + h[start];

12 open.push(start, f[start]);

14 while (!open.isEmpty()) {

15 const current = open.pop(); // lowest f

16 if (current === goal) return reconstructPath(parent);

17 closed.add(current);

19 for (const neighbor of getNeighbors(grid, current)) {

20 if (closed.has(neighbor)) continue;

21 const tentativeG = g[current] + 1;

22 if (!g[neighbor] || tentativeG < g[neighbor]) {

23 parent[neighbor] = current;

24 g[neighbor] = tentativeG;

25 h[neighbor] = heuristic(neighbor, goal);

26 f[neighbor] = g[neighbor] + h[neighbor];

27 open.push(neighbor, f[neighbor]);

28 }

29 }

30 }

31 return null; // no path

32}

Algorithm Explanation

A* Search is a best-first graph search algorithm that finds the shortest path from a start node to a goal node using a heuristic to guide which node to expand next. It is often faster than Dijkstra because it uses the heuristic to look "in the right direction."

⚙️ How It Works

Initialize — Add the start node to the open set with g = 0 and compute f = g + h where h is the heuristic estimate to the goal.
Expand — Repeatedly dequeue the open-set node with the lowest f-score. Move it to the closed set.
Relax neighbors — For each unvisited neighbor, compute a tentative g via the current node. If it's better than any known g, update parent and f, then push to the open set.
Stop — When the goal is dequeued, A* terminates and reconstructs the path from parent pointers.

🔑 Why Three Scores?

g(n) — exact cost paid so far from the start (like Dijkstra).
h(n) — heuristic guess of remaining cost to the goal.
f(n) = g(n) + h(n) — estimated total cost through n. A* always expands the node with the smallest f.

💡 Optimality: A* returns the optimal (shortest) path when the heuristic is admissible — i.e., it never overestimates the true cost. All three heuristics on this page (Manhattan, Euclidean, Chebyshev) are admissible on a grid with unit-cost moves.

📊 Open vs Closed Set

Open Set (Frontier)

Cells discovered but not yet expanded. Ordered by f-score via a min-heap. Think of it as the "candidate" nodes.

Closed Set (Visited)

Cells already dequeued and expanded. Their optimal g-score is final. A node moves from open → closed exactly once.

Click cells to draw walls, set start/goal, or change the heuristic · Use Random Walls to generate a maze · Step through to see how A* expands