Pathfinding & Heuristic Search Lab
Draw walls on a grid and run pathfinding algorithms to compare their behavior. See how BFS guarantees shortest paths, DFS explores deeply, and A* uses heuristics to search efficiently. Generate mazes and analyze their structure.
Guided Experiment: BFS vs DFS vs A*
On the same grid with walls, which algorithm will explore the fewest nodes? Which will find the shortest path? Can an algorithm be fast but non-optimal?
Write your hypothesis in the Lab Report panel, then click Next.
Controls
Click to draw walls. Drag start (S) or end (E) to reposition.
Results
Draw walls on the grid, select algorithms, and click "Run Comparison" to see results.
Data Table
(0 rows)| # | Algorithm | Nodes Explored | Path Length | Path Cost | Optimal? | Heuristic |
|---|
Reference Guide
Breadth-First Search (BFS)
BFS explores all nodes at the current depth before moving to the next level. It uses a queue (FIFO) data structure.
On unweighted graphs, BFS always finds the shortest path because it explores nodes in order of their distance from the start.
- Time complexity: O(V + E)
- Space complexity: O(V)
- Guarantees shortest path on unweighted graphs
Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path in weighted graphs by always expanding the node with the lowest cumulative cost.
It uses a priority queue to efficiently select the next node. On unweighted graphs, it behaves identically to BFS.
- Time complexity: O((V + E) log V) with a binary heap
- Handles non-negative edge weights
- Guarantees optimal path in weighted graphs
A* Search
A* combines Dijkstra's actual cost g(n) with a heuristic estimate h(n) to prioritize nodes, giving f(n) = g(n) + h(n).
With an admissible heuristic (one that never overestimates), A* is guaranteed to find the optimal path while often exploring far fewer nodes than BFS or Dijkstra.
- Time complexity: O((V + E) log V)
- Manhattan distance is tight for 4-directional grids
- Optimal with admissible heuristic
Maze Generation
Recursive backtracking uses a randomized DFS to carve passages, producing mazes with long corridors and fewer branches.
Prim's algorithm grows the maze from a random frontier, creating more branching paths. Kruskal's algorithm randomly joins cells using a union-find structure, producing even, well-distributed passages.
- DFS mazes have long winding paths with many dead ends
- Prim's mazes tend to have shorter, more branching corridors
- All algorithms produce perfect mazes (exactly one path between any two cells)