Maze pathfinding – BFS, DFS and A*
Computer ScienceAlgorithms & Problem SolvingAges 17–18
Loading…
Sign in to playA grid with walls, a start cell and a goal cell. Students choose breadth-first search (BFS, using a queue), depth-first search (DFS, using a stack) or A*, then watch step by step: the waiting cells are numbered in the order they will be taken out, explored cells are shaded by distance, and finally the route found appears. Draw or erase walls, drag the start and goal, generate new mazes and compare the cells explored and the path length of each algorithm.
Lesson: Pathfinding algorithms on a grid: breadth-first search (BFS), depth-first search (DFS) and A*
What it shows
A maze is modelled as a grid of cells; each move goes to a neighbouring cell up, down, left or right, and every move costs the same. Breadth-first search keeps waiting cells in a queue, so it explores all cells one step away, then two steps, and the first time it reaches the goal it has a shortest path. Depth-first search uses a stack and follows one direction until it is stuck, so its path is often longer. A* orders cells by f = g + h, where h is the Manhattan distance to the goal.
How to use
Pick BFS, DFS or A* and press Step to watch the numbered waiting cells, or Run for an animation. Compare the results table after each run. Use Draw walls, Erase walls, Set start and Set goal to change the grid, or choose a Grid type and press New grid.
Parameters you can change
- Algorithm BFS – breadth-first search, DFS – depth-first search, A* – guided by a distance estimate
- Grid type Maze with loops, Random obstacles, Empty grid
- Number of grid columns 11–41 cells
- Extra walls removed (maze) 0–60 %
- Obstacle density 0–45 %
- Run speed 1–100 steps/s
Questions to explore
- Why is the path found by BFS always a shortest one, while the DFS path often is not?
- On an empty grid, which algorithm explores the fewest cells, and why?
- Can you build a maze where DFS reaches the goal after exploring fewer cells than BFS?
