A* Pathfinding Algorithm
A* (A-star) is a best-first search algorithm that efficiently finds the shortest path between two nodes using both actual cost and a heuristic estimate. Developed by Peter Hart, Nils Nilsson, and Bertram Raphael in 1968, it combines the strengths of Dijkstra's Algorithm (guaranteed shortest path) with Greedy Best-First Search (speed using heuristics). Widely used in game AI, robotics, GPS navigation, and puzzle solving.
Visualization
Interactive visualization for A* Pathfinding Algorithm
A* Pathfinding Visualization
Optimal pathfinding using heuristic-guided search with f(n) = g(n) + h(n)
Click cells to add/remove walls
Time Complexity: O(E log V) with binary heap
Formula: f(n) = g(n) + h(n)
- g(n): cost from start to current node
- h(n): heuristic estimate to goal (Manhattan distance)
- Always expands lowest f-score node
- Optimal if heuristic is admissible
Interactive visualization with step-by-step execution
Implementation
1function aStar(graph: Map<string, Array<{node: string; cost: number}>>,
2 start: string, goal: string,
3 heuristic: (node: string) => number): string[] {
4 const openSet = new Set([start]);
5 const cameFrom = new Map<string, string>();
6 const gScore = new Map<string, number>();
7 const fScore = new Map<string, number>();
8
9 gScore.set(start, 0);
10 fScore.set(start, heuristic(start));
11
12 while (openSet.size > 0) {
13 let current = Array.from(openSet).reduce((a, b) =>
14 (fScore.get(a) ?? Infinity) < (fScore.get(b) ?? Infinity) ? a : b
15 );
16
17 if (current === goal) {
18 const path = [current];
19 while (cameFrom.has(current)) {
20 current = cameFrom.get(current)!;
21 path.unshift(current);
22 }
23 return path;
24 }
25
26 openSet.delete(current);
27
28 for (const {node, cost} of graph.get(current) || []) {
29 const tentativeG = (gScore.get(current) ?? Infinity) + cost;
30
31 if (tentativeG < (gScore.get(node) ?? Infinity)) {
32 cameFrom.set(node, current);
33 gScore.set(node, tentativeG);
34 fScore.set(node, tentativeG + heuristic(node));
35 openSet.add(node);
36 }
37 }
38 }
39 return [];
40}Deep Dive
Theoretical Foundation
A* evaluates nodes using f(n) = g(n) + h(n), where g(n) is the actual cost from start to node n, and h(n) is the heuristic estimated cost from n to goal. The algorithm maintains an open set (priority queue) of nodes to explore, always selecting the node with lowest f(n). If the heuristic is admissible (never overestimates) and consistent (satisfies triangle inequality), A* guarantees finding the optimal path. Common heuristics include Manhattan distance (grid with 4 directions), Euclidean distance (any direction), and Diagonal distance (8 directions). A* is complete and optimal when h(n) is admissible. With a perfect heuristic, A* expands minimal nodes; with h(n)=0, it becomes Dijkstra.
Complexity
Time
O(E)
O(E)
O(b^d)
Space
O(V)
Applications
Industry Use
Video game AI pathfinding (NPCs, enemies, RTS units)
GPS navigation and route planning with traffic
Robot motion planning and obstacle avoidance
Puzzle solving (15-puzzle, Rubik's cube, Sokoban)
Network packet routing with QoS
Path planning in autonomous vehicles
Maze solving and procedural generation
AI planning systems and decision making
Logistics and delivery route optimization
Use Cases
Related Algorithms
Depth-First Search (DFS)
Graph traversal exploring as deep as possible before backtracking. DFS is a fundamental algorithm that uses a stack (either implicitly through recursion or explicitly) to explore graph vertices. It's essential for cycle detection, topological sorting, and pathfinding problems.
Breadth-First Search (BFS)
Level-by-level graph traversal guaranteeing shortest paths in unweighted graphs. BFS uses a queue to explore vertices level by level, making it optimal for finding shortest paths and solving problems that require exploring nearest neighbors first.
Dijkstra's Algorithm
Finds shortest path from source to all vertices in weighted graph with non-negative edges. Uses greedy approach with priority queue.
Floyd-Warshall Algorithm
Floyd-Warshall is an all-pairs shortest path algorithm that finds shortest distances between every pair of vertices in a weighted graph. Unlike Dijkstra (single-source), it computes shortest paths from all vertices to all other vertices simultaneously. The algorithm can handle negative edge weights but not negative cycles. Developed independently by Robert Floyd, Bernard Roy, and Stephen Warshall in the early 1960s.