Find the shortest path using artificial intelligence
A* (pronounced "A-star") is one of the most efficient and widely-used pathfinding algorithms in computer science. It intelligently navigates from a start point to a goal by evaluating which path is most promising at each step — guaranteed to find the optimal solution.
The core formula that drives every decision A* makes
Google Maps, Waze and GPS systems use A* variants to find the fastest route between two locations in real time.
NPCs and enemy AI in games like StarCraft and Warcraft III use A* for intelligent movement and pathfinding.
Autonomous robots and drones rely on A* to navigate real environments while avoiding obstacles.
A* is used to solve complex puzzles like the 15-puzzle and sliding tile games with optimal solutions.
Configure the grid, define start and end nodes, place obstacles, then execute the A* algorithm to observe optimal pathfinding in real time.
A deep dive into how A* manages its open and closed lists to systematically discover the globally optimal path through any configuration.
A* begins by adding the start node to the Open List with f(start) = 0 + h(start). The Closed List is empty. All other nodes are unvisited.
At each step, A* picks the node with the lowest f(n) value from the Open List. This is the most promising node to explore next.
For each neighbor, A* calculates g(n) + h(n). If a better path is found or the node is new, it's added or updated in the Open List.
Once fully explored, the current node moves to the Closed List. Nodes here won't be re-evaluated — they have their optimal cost.
When the goal node is dequeued from the Open List, A* traces back through parent pointers to reconstruct the shortest path.
If the Open List becomes empty before reaching the goal, no valid path exists. The grid is fully blocked or disconnected.
Candidates sorted by f(n). The lowest f(n) is always explored next.
Nodes with confirmed optimal cost. Never revisited.
↑ Lists update in real time when the algorithm executes in the game above ↑
A clean, fully-commented JavaScript implementation of A* — the exact logic powering this visualizer.
// ─── A* Search Algorithm ───────────────────────────────────────── // f(n) = g(n) + h(n) // g(n) = actual cost from start to n // h(n) = heuristic estimate from n to goal function aStar(grid, start, end) { const openList = []; // Nodes to be explored const closedSet = new Set(); // Already explored nodes // Initialise start node start.g = 0; start.h = heuristic(start, end); start.f = start.g + start.h; start.parent = null; openList.push(start); while (openList.length > 0) { // Pick node with lowest f(n) openList.sort((a, b) => a.f - b.f); const current = openList.shift(); // Goal reached → reconstruct path if (current === end) return buildPath(current); closedSet.add(`${current.row},${current.col}`); // Explore each neighbor (up, down, left, right) for (const neighbor of getNeighbors(grid, current)) { if (neighbor.isWall) continue; if (closedSet.has(`${neighbor.row},${neighbor.col}`)) continue; const tentativeG = current.g + 1; const inOpen = openList.find(n => n.row === neighbor.row && n.col === neighbor.col ); if (!inOpen) { // New node — add to open list neighbor.g = tentativeG; neighbor.h = heuristic(neighbor, end); neighbor.f = neighbor.g + neighbor.h; neighbor.parent = current; openList.push(neighbor); } else if (tentativeG < inOpen.g) { // Better path found — update existing node inOpen.g = tentativeG; inOpen.f = inOpen.g + inOpen.h; inOpen.parent = current; } } } return null; // No path found } // Manhattan distance heuristic function heuristic(a, b) { return Math.abs(a.row - b.row) + Math.abs(a.col - b.col); } // Trace back from goal to start via parent pointers function buildPath(node) { const path = []; let current = node; while (current) { path.unshift(current); current = current.parent; } return path; }
A* combines the completeness of Dijkstra's algorithm with the speed of Greedy Best-First Search — delivering guaranteed optimal results with maximum efficiency.
A* always guarantees the shortest possible path when an admissible (non-overestimating) heuristic is used.
By using h(n), A* intelligently focuses its search toward the goal, exploring far fewer nodes than blind search.
Configure custom grids, place obstacles, and observe A* navigate them in real time with step-by-step animation.
Track nodes explored, path length, open/closed list sizes, and algorithm performance as it runs.
Switch between Manhattan, Euclidean, and Chebyshev distance heuristics to see how they affect the search.
Engineered for any viewport — desktop, tablet, or mobile — with adaptive layout and touch-optimized controls.