Sketch · 2026-06-12
A*, on a 48 by 28 grid.
A* picks the next cell to look at by adding two numbers: how far it has already walked to get there, and how far it guesses the goal still is. The cell with the smallest sum is always popped next. Draw a wall, drag an endpoint, watch the frontier sweep around the obstacle and settle on a path.
How to use it
Click and drag on an empty cell to paint a wall. Click and drag on a wall to erase. Grab the green start dot or the red goal dot to move it around the board. Any edit restarts the search from scratch. The speed slider controls how many expansions happen per animation frame; push it to the top and the search resolves in two or three frames. The heuristic switch changes the third number A* uses, so the frontier reaches the goal by a different route even when the optimal path stays the same.
What you are seeing
Each cell carries two scores. g is the cheapest path A* has actually found from the start to this cell. h is the guess for how far the goal still is, computed by the heuristic and never allowed to overshoot the truth. The cell with the smallest g plus h gets popped off the open set next. Cells in the open set show up in bright blue. Cells already popped and finished with show up in dim teal. When the goal cell finally pops, the path is reconstructed by walking the parent pointers backward, and the trail lights up in amber.
On heuristics
Manhattan adds the horizontal and vertical distance. It matches 4-way movement perfectly, which is why the frontier under Manhattan tends to stay tight against the optimal path. Chebyshev takes the larger of the two distances and lines up with 8-way movement. Euclidean uses the straight-line distance. On 4-way movement Euclidean underestimates more than Manhattan, so the frontier grows wider before finding the goal. Mismatch the heuristic to the movement and you can see the cost: more cells popped, more work done, same answer.
Source
P. E. Hart, N. J. Nilsson and B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems Science and Cybernetics 4:2 (1968), pages 100 to 107. The diagonal cost on 8-way movement is the square root of two, so a corner step costs the same as the hypotenuse of the unit square it crosses.