How to use it
The page starts with a maze and A* already searching. Cells that the algorithm has finished with are marked with a dot, cells waiting in its to-do list (the frontier) with a ring, and the final path is the pink line. Press Reset, change the algorithm and press Play to watch another one solve the same maze. Use Step to advance one cell at a time and read the numbers under the grid: the current cell, its cost so far (g), the estimate to the goal (h), and the size of the frontier.
Draw walls with the Wall tool, add Mud (cost 5 instead of 1) and drag the green S and the orange G anywhere. Once a search has finished, everything you change is solved again instantly, so you can drag the goal around and see the path follow. After a search, hover a cell (or tap it with the Inspect tool) to see its g, h, f and an arrow to its parent.
Controls
- Mouse: drag on the grid to draw with the chosen tool. Starting on a wall with the Wall tool erases walls instead. Right-drag always erases. Drag S or G to move them.
- Touch: the same by finger. The page does not scroll while you touch the grid, so scroll using the area around it.
- Keyboard: Space plays or pauses, N steps, R resets. With the grid focused, the arrow keys move a cursor, Enter applies the tool, W, M, E pick Wall, Mud, Eraser, and S or G place the start or goal at the cursor.
- Settings: 4 or 8 directions, heuristic, heuristic weight, tie-breaking, cell size, maze density. Your grid and settings are saved in this browser.
How it works
A grid is a graph: every open cell is a node and every allowed move to a neighbour is an edge. The cost of a move is the cost of the cell you enter (1, or 5 for mud), multiplied by √2 for a diagonal step. Diagonal moves are not allowed to cut a wall’s corner. Every algorithm here keeps a set of cells waiting to be expanded (the frontier), picks one, and adds its neighbours. They differ only in which cell they pick next.
- Breadth-first search uses a first-in, first-out queue and spreads out in rings. It finds the path with the fewest steps, which is the cheapest path only when every step costs the same. It ignores mud.
- Depth-first search uses a stack and dives as deep as it can before backing up. It finds some path, usually a long winding one.
- Dijkstra always expands the frontier cell with the smallest cost so far, g. It respects mud and diagonal costs and is guaranteed to find the cheapest path, but it explores in all directions.
- A* picks the smallest f = g + w · h, where h is a heuristic guess of the remaining cost and w is the weight. If h never overestimates (it is admissible) and w ≤ 1, A* still finds the cheapest path while expanding far fewer cells. With w = 0 it becomes Dijkstra; a large w makes it greedy.
- Greedy best-first looks only at h. It is fast when the way is clear, but dead ends fool it: in the U-shaped trap it dives into the cup, has to flood it before it gets out, and returns a slightly longer path.
- Bidirectional BFS grows two searches, one from the start and one from the goal, and stops when they meet. It uses the same rules as BFS but explores far less area in open spaces.
The heuristics: Manhattan is |dx| + |dy|, Euclidean is the straight-line distance, and octile is the exact cost on an empty grid with diagonals: (|dx| + |dy|) + (√2 − 2) · min(|dx|, |dy|). Manhattan is admissible with 4 directions but overestimates with diagonals, so A* with Manhattan can return a slightly longer path there; the page warns you when this can happen. Mud never makes the estimate wrong, because the cheapest step costs 1.
| Algorithm | Shortest path? | Uses costs? | Typical work |
|---|---|---|---|
| BFS | Fewest steps | No | Everything closer than the goal |
| DFS | No | No | Varies a lot |
| Dijkstra | Yes | Yes | Everything cheaper than the goal |
| A* | Yes, with an admissible h and w ≤ 1 | Yes | Often far less than Dijkstra |
| Greedy | No | Only in h | Very little, if lucky |
| Bidirectional BFS | Fewest steps | No | Two small areas instead of one big one |
Searches like these are used for route finding on maps, for characters and units in video games, and for robots moving around obstacles. Real systems add many refinements. This demo is simplified: it is a small square grid, the cost values are only 1 and 5, and the timings in the comparison are measured in your browser, so use them only to compare algorithms with each other.
Things to try
- Load Open field and run Dijkstra, then A*. Dijkstra fills a disc around the start; A* heads straight for the goal. Compare the “cells expanded” numbers.
- Set the heuristic weight to 0 and watch A* behave exactly like Dijkstra. Slide it to 3 and watch it turn greedy.
- Load U-shaped trap and run Greedy. It dives into the cup, floods it, and returns a slightly longer path. Then run A*: it may look at more cells here, but its path is the shortest possible.
- Load Mud shortcut and run BFS and Dijkstra. BFS walks straight through the mud because that is fewer steps, and pays more.
- Switch to 8 directions and set the heuristic to Manhattan. Use Compare all and look for a case where A* is no longer shortest.
- Load No way through and see how each algorithm decides there is no path.
- Generate a Backtracker maze and a Rooms maze and compare how many cells A* needs in each.
- Finish a search, then drag the goal across the grid and watch the explored area change live.
Frequently asked questions
Why does BFS ignore the mud?
BFS counts steps, not costs. It treats a mud cell like any other, so its path can be cheaper in steps and more expensive in cost. Dijkstra and A* add up real costs.
Why does A* sometimes expand as many cells as Dijkstra?
When walls force a long detour, the heuristic points the wrong way and A* has to explore the same area. A good heuristic helps most in open spaces.
Is depth-first search ever useful for shortest paths?
Not for shortest paths. It is great for other jobs, such as generating mazes or checking whether two places are connected at all.
What is “Guaranteed?” in the comparison?
It says whether the algorithm is guaranteed to return the cheapest path under the current settings. “Shortest?” says whether it actually did on this grid. A non-guaranteed algorithm can be lucky.
Why can’t diagonals cut corners?
Squeezing between two diagonal wall cells would pass through a gap with no width. The rule is that both neighbouring cells of a diagonal move must be open.
Does it work offline?
Yes. Everything runs in your browser and nothing is sent anywhere.