Learn · Pathfinding
A* pathfinding
How does a game character, or a satnav, find its way? A* explores outward from the start, but uses a heuristic — a straight-line guess of the remaining distance — to head toward the goal instead of searching blindly. Draw some walls and watch it work.
Click or drag to draw / erase walls.
Cells explored
0
Path length
—
Status
ready
■ start · ■ goal · ■ explored · ■ frontier · ■ shortest path
A* vs Dijkstra
Both guarantee the shortest path. Each step, A* expands the frontier cell with the lowest f = g + h — where g is the distance travelled so far and h is the heuristic guess to the goal (Manhattan distance here). Dijkstra is just A* with h = 0: no guess, so it explores in all directions equally. Switch between them and compare "cells explored" — the heuristic is what makes A* efficient.