A* Search
Dijkstra + a heuristic to guide search toward the goal.
How it works
A* (pronounced "A-star") is an informed search algorithm that finds the shortest path between two nodes in a weighted graph. Unlike Dijkstra's algorithm, which expands nodes in all directions based solely on their distance from the source, A* uses a heuristic function h(n) to estimate the remaining cost to the goal. At each step it picks the node that minimises f(n) = g(n) + h(n), where g(n) is the actual cost from the start and h(n) is the heuristic estimate to the goal.
On a grid with Manhattan distance as the heuristic, A* focuses its search toward the goal and typically visits far fewer nodes than Dijkstra. The algorithm is admissible (guaranteed to find the optimal path) as long as the heuristic never overestimates the true cost — a condition the Manhattan distance satisfies on a grid where movement is restricted to four directions.
The key insight is the open set (priority queue ordered by f) and the closed set (already-expanded nodes). When a node is popped from the open set, it has the lowest tentative total cost; its neighbours are relaxed if a shorter path is found. Once the goal is popped, the shortest path is reconstructed by following parent pointers back to the start. The trade-off versus Dijkstra is that A* requires a good heuristic — a poor or inadmissible one can produce sub-optimal paths.
Complexity
Visualizer
Where it's used in the real world
Google Maps / Apple Maps navigation
Real-time turn-by-turn route planningRoad networks are huge weighted graphs. A* with a geographic distance heuristic focuses the search toward the destination, making route computation fast enough to run on a phone. Bidirectional A* and preprocessing techniques like contraction hierarchies extend this to continent-scale maps.
Game AI pathfinding (Unity, Unreal Engine)
NPC movement on tile maps and NavMeshesA* is the de-facto standard for game pathfinding. Unity's NavMesh agent and most tile-based game engines ship A* as the built-in path planner. The heuristic is tunable: tie-breaking and weighted variants let designers balance optimality against compute budget per frame.
Robotics motion planning (ROS)
Collision-free path planning in 2D/3D occupancy gridsThe ROS navigation stack uses A* (or Dijkstra as a fallback) on a costmap to find paths for wheeled robots. Obstacle inflation and terrain cost layers make the heuristic inadmissible in practice, so the implementation often uses weighted A* to trade slight sub-optimality for speed.
Implementation
// A* on a grid with Manhattan distance heuristic
type Pos = [number, number];
function aStar(
grid: string[][], // "." = passable, "#" = wall
start: Pos,
end: Pos
): Pos[] | null {
const rows = grid.length;
const cols = grid[0].length;
const key = ([r, c]: Pos) => `${r},${c}`;
const h = ([r, c]: Pos) => Math.abs(r - end[0]) + Math.abs(c - end[1]);
const DIRS: Pos[] = [[0,1],[1,0],[0,-1],[-1,0]];
const g = new Map<string, number>([[key(start), 0]]);
const parent = new Map<string, Pos | null>([[key(start), null]]);
// Open set as sorted array — swap for a real min-heap in production
let open: Array<{ pos: Pos; f: number }> = [{ pos: start, f: h(start) }];
const closed = new Set<string>();
while (open.length > 0) {
open.sort((a, b) => a.f - b.f);
const { pos: cur } = open.shift()!;
const ck = key(cur);
if (ck === key(end)) {
// Reconstruct path
const path: Pos[] = [];
let c: Pos | null = end;
while (c) { path.unshift(c); c = parent.get(key(c)) ?? null; }
return path;
}
closed.add(ck);
const gc = g.get(ck)!;
for (const [dr, dc] of DIRS) {
const nb: Pos = [cur[0] + dr, cur[1] + dc];
const [nr, nc] = nb;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (grid[nr][nc] === "#") continue;
const nk = key(nb);
if (closed.has(nk)) continue;
const tg = gc + 1;
if (!g.has(nk) || tg < g.get(nk)!) {
g.set(nk, tg);
parent.set(nk, cur);
const f = tg + h(nb);
const idx = open.findIndex(e => key(e.pos) === nk);
if (idx === -1) open.push({ pos: nb, f });
else open[idx] = { pos: nb, f };
}
}
}
return null; // no path
}