This simulation visualises how five graph-search algorithms find a route across a grid of cells. Each open cell becomes a node linked to its four orthogonal neighbours, while walls block travel. A* ranks cells by f(n) = g(n) + h(n), where g is the real cost from the start and h is a heuristic estimate to the goal. Dijkstra sets h to zero, Greedy Best-First uses h alone, and BFS expands a plain queue layer by layer.
The algorithm selector switches between A* (Manhattan), A* (Euclidean), Dijkstra, Greedy Best-First and BFS. Draw modes let you place walls, the start and end, or erase, and a speed slider sets how many search steps run per animation frame. You can also step manually, clear the search, reset the grid, or generate a recursive-backtracker maze. Pathfinding powers GPS navigation, video-game movement and warehouse-robot routing.
What does this pathfinding simulation actually show?
It treats the grid as a graph and animates how a chosen algorithm searches outward from the start cell to the end cell, colouring the open set, the visited (closed) cells, and the final shortest path. The live counters report cells visited and the resulting path length so you can compare efficiency against optimality.
How does the A* algorithm work here?
A* keeps a priority queue ordered by f(n) = g(n) + h(n). The g value is the number of steps taken from the start, and h estimates the remaining distance to the goal. At each step it expands the cell with the lowest f, which steers the search toward the target while still guaranteeing the shortest path when the heuristic never overestimates.
What is the difference between Manhattan and Euclidean A*?
Both use the same f = g + h formula but a different heuristic. Manhattan distance sums the horizontal and vertical gaps (|dr| + |dc|), which matches the 4-directional grid exactly. Euclidean distance uses the straight-line hypotenuse, which underestimates more on a grid that cannot move diagonally, so it can explore slightly more cells.
Dijkstra is A* with h set to zero, so it explores purely by accumulated cost and expands evenly in all directions. Greedy Best-First uses f = h, racing toward the goal by estimate alone, which is fast but can be tricked by walls into a longer route. BFS uses a simple first-in-first-out queue rather than a priority queue.
A* (with an admissible heuristic), Dijkstra and BFS all return a guaranteed shortest path on this uniform-cost grid, because every step costs one. Greedy Best-First does not guarantee optimality; it often finds a route quickly but may take a longer detour around obstacles since it ignores the cost already paid.
The Wall, Start, End and Erase chips set what clicking or dragging on the grid does. Wall blocks cells, Start and End relocate the green and red endpoints, and Erase clears walls. The speed slider chooses how many search steps run per animation frame, from one step up to a hundred, letting you watch slowly or solve instantly.
Blue translucent cells are the open set still queued for exploration, dark-blue cells are the closed set already visited, and yellow marks the reconstructed shortest path. Comparing the size of the closed region between algorithms makes their efficiency visible: A* usually visits far fewer cells than Dijkstra to reach the same goal.
The Generate maze button fills the grid with walls and then runs a recursive backtracker. Starting from a corner cell, it carves passages two cells at a time in a randomly shuffled order, knocking down the wall between cells it links. The result is a perfect maze with exactly one path between any two open cells.
Yes. Each time a cell is reached for the first time, the algorithm records which neighbour it came from in a came-from map. When the end cell is popped, the route is rebuilt by walking those parent links backwards from the goal to the start, then reversed to give the forward path that is highlighted in yellow.
A* and Dijkstra underpin GPS and mapping route planners, the movement of non-player characters in video games, and the navigation of warehouse and delivery robots. The same graph-search ideas extend to network routing, puzzle solving and logistics. A* was first developed in 1968 at Stanford Research Institute for the robot Shakey.
Pathfinding algorithms find the shortest route between two points across a grid of cells, working around obstacles along the way. They are the engine behind GPS turn-by-turn navigation, the movement of characters in video games, and the route planning of warehouse robots. What makes them fascinating is watching how different strategies trade off speed against optimality: some explore widely and guarantee the best path, while others race toward the goal but can be fooled by dead ends.
f(n) = g(n) + h(n) — A* ranks each cell by f, where g(n) is the actual cost from the start and h(n) is a heuristic estimate of the distance to the goal. Dijkstra uses h = 0 (cost only), while Greedy Best-First uses f = h (estimate only).
A* was invented in 1968 by Peter Hart, Nils Nilsson and Bertram Raphael at Stanford Research Institute while working on Shakey, one of the first mobile robots that could reason about its own actions.
Draw walls, generate mazes and watch four algorithms explore the grid: A* (fastest with heuristic), Dijkstra (optimal but slow), Greedy Best-First (fast but not optimal) and BFS (guaranteed shortest).
Each algorithm uses different strategies: BFS explores layer by layer, Dijkstra by cumulative cost, Greedy by estimated distance, A* by cost + estimate. Explored cells are visualised.
Draw walls with mouse. Place start and end points. Choose an algorithm and click Run. Compare the explored area (efficiency) and path quality (optimality).
A* was invented by Peter Hart, Nils Nilsson and Bertram Raphael in 1968 at Stanford Research Institute. It's widely used in video games, GPS navigation and robotic path planning.