A* Search Algorithm
Informed search algorithm combining best-first search with Dijkstra's algorithm using heuristics. Widely used in pathfinding and graph traversal, A* is optimal and complete when using admissible heuristic. Used in games, GPS navigation, and robotics. Invented by Peter Hart, Nils Nilsson, and Bertram Raphael in 1968.
Visualization
Interactive visualization for A* Search 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
1interface Node {
2 x: number;
3 y: number;
4}
5
6function aStar(grid: number[][], start: Node, goal: Node): Node[] | null {
7 const rows = grid.length;
8 const cols = grid[0].length;
9
10 const heuristic = (a: Node, b: Node) =>
11 Math.abs(a.x - b.x) + Math.abs(a.y - b.y); // Manhattan distance
12
13 const openSet: Node[] = [start];
14 const cameFrom: Map<string, Node> = new Map();
15
16 const gScore: Map<string, number> = new Map();
17 const fScore: Map<string, number> = new Map();
18
19 const key = (n: Node) => `${n.x},${n.y}`;
20
21 gScore.set(key(start), 0);
22 fScore.set(key(start), heuristic(start, goal));
23
24 while (openSet.length > 0) {
25 openSet.sort((a, b) => (fScore.get(key(a)) || Infinity) - (fScore.get(key(b)) || Infinity));
26 const current = openSet.shift()!;
27
28 if (current.x === goal.x && current.y === goal.y) {
29 // Reconstruct path
30 const path: Node[] = [current];
31 let curr = current;
32 while (cameFrom.has(key(curr))) {
33 curr = cameFrom.get(key(curr))!;
34 path.unshift(curr);
35 }
36 return path;
37 }
38
39 const neighbors = [
40 {x: current.x + 1, y: current.y},
41 {x: current.x - 1, y: current.y},
42 {x: current.x, y: current.y + 1},
43 {x: current.x, y: current.y - 1}
44 ];
45
46 for (const neighbor of neighbors) {
47 if (neighbor.x < 0 || neighbor.x >= rows || neighbor.y < 0 || neighbor.y >= cols) continue;
48 if (grid[neighbor.x][neighbor.y] === 1) continue; // obstacle
49
50 const tentativeG = (gScore.get(key(current)) || Infinity) + 1;
51
52 if (tentativeG < (gScore.get(key(neighbor)) || Infinity)) {
53 cameFrom.set(key(neighbor), current);
54 gScore.set(key(neighbor), tentativeG);
55 fScore.set(key(neighbor), tentativeG + heuristic(neighbor, goal));
56
57 if (!openSet.some(n => n.x === neighbor.x && n.y === neighbor.y)) {
58 openSet.push(neighbor);
59 }
60 }
61 }
62 }
63
64 return null; // No path found
65}Deep Dive
Theoretical Foundation
A* uses f(n) = g(n) + h(n) where g(n) is cost from start to n, h(n) is heuristic estimate from n to goal. With admissible heuristic (never overestimates), A* is optimal. Common heuristics: Manhattan distance, Euclidean distance, Diagonal distance. A* explores most promising paths first, pruning search space significantly.
Complexity
Time
O(b^d)
O(b^d)
O(b^d)
Space
O(b^d)
Applications
Industry Use
GPS navigation and route planning
Video game pathfinding (NPCs, AI)
Robot motion planning
Puzzle solving (15-puzzle, Rubik's cube)
Network routing
Supply chain optimization
Use Cases
Related Algorithms
Convex Hull (Graham Scan)
Find smallest convex polygon containing all points. Graham Scan invented by Ronald Graham in 1972, runs in O(n log n). Essential in computational geometry, computer graphics, and pattern recognition.
Line Segment Intersection
Determine if two line segments intersect. Fundamental geometric primitive used in graphics, CAD, GIS. Uses orientation and collinearity tests.
Caesar Cipher
The Caesar Cipher is one of the oldest and simplest encryption techniques, named after Julius Caesar who used it to protect military messages around 100 BC. It works by shifting each letter in the plaintext by a fixed number of positions down the alphabet. For example, with a shift of 3, A becomes D, B becomes E, and so on. Despite being used for over 2000 years, it's extremely weak by modern standards with only 25 possible keys, making it trivially breakable by brute force or frequency analysis.
Vigenère Cipher
Polyalphabetic substitution cipher using keyword. Invented by Giovan Battista Bellaso in 1553, misattributed to Blaise de Vigenère. More secure than Caesar, resists simple frequency analysis.