A* Pathfinding Visualizer

Goal

Explain and visualize how A* finds the shortest path between two points on a grid.

Concept

• › Heuristic function $h(n)$ estimates cost from $n$ to the goal.
• › g(n) is the actual cost from the start to $n$.
• › A* minimizes $f(n)=g(n)+h(n)$ in its priority queue.

$$f(n)=g(n)+h(n)$$

Manhattan distance is a common admissible heuristic on grids:

$$h(n)=|x_n-x_g|+|y_n-y_g|$$

A* is optimal when the heuristic is admissible (never overestimates).

How it works

1. › Initialize open set with the start node ($f=g+h$).
2. › Pop the node with lowest $f$.
3. › If it is the goal, reconstruct the path via parent pointers.
4. › Otherwise expand neighbors, skip walls, and relax edges when a cheaper $g$ is found.
5. › Repeat until the open set is empty (no path) or the goal is reached.

Observations

• › Why A* is optimal: With an admissible heuristic, the first time we pop the goal it has minimum $f$.
• › When it struggles: Dense mazes with a misleading heuristic can explore many nodes before finding the goal.
• › Compared to Dijkstra: A* is Dijkstra + heuristic guidance toward the target.

Source

GitHub — portfolio & experiments