Maze Generator + Solver
Kruskal generation · BFS / DFS search
Generates a perfect maze with one MST pass, then puts BFS and DFS side by side so you can watch the frontier spread and compare how many cells each search visits to reach the same goal.
Arrow keys (or W A S D) walk the player from the start, top-left, to the goal, bottom-right, through carved passages only. Or run a search and watch the explored frontier spread before the path is highlighted.
- Search
- not run
- Visited
- not run
- Path
- not run
New maze generated. Walk it with the arrow keys, or run a search.
Generate a maze with Kruskal's algorithm, then race BFS against DFS and compare how many cells each one explores.
The source for this course project is kept private. Request access through the contact form and I will gladly share the code and walk through it.
Request accessMaze Generator + Solver, a Fundamentals of Computer Science 2 course project co-authored with a classmate, models a grid as a graph of cell vertices joined by weighted edges. To generate a maze it assigns each wall a random weight, sorts the edges, and runs Kruskal's algorithm over a union-find (a HashMap-based find and union) so an edge is carved into a passage only when it connects two cells that are not yet in the same set. The result is a perfect maze: exactly one path between any two cells, with a spanning tree of height by width minus one passages over the 35 by 25 grid. Solving is a single polymorphic search routine over a mutable collection: hand it a stack and it explores depth-first, hand it a queue and it explores breadth-first, in both cases marking cells seen, recording a came-from edge for each, and reconstructing the route once the goal is reached. The maze world animates the search frontier one cell per tick and you can also play it yourself, walking from the top-left start to the bottom-right goal with the arrow keys.
- Java
- Kruskal's MST
- Union-Find
- BFS
- DFS
- Graphs
- javalib (impworld)
- Generation
- Kruskal MST + union-find
- Grid
- 35 x 25 (874 passages)
- Solvers
- BFS + DFS (one search routine)
- Play
- arrow-key manual solve
What I'd improve
The generator and both searches are correct and visualized, but the original ran on a fixed grid with a single random layout per reset. With more time I would add adjustable dimensions and seedable generation, surface the visited-cell counts and path length as a live readout, and add A* with a Manhattan heuristic so the demo contrasts an informed search against the uninformed BFS and DFS baselines.