Here is a Maze Generator/Solver written in Java
This jar file is an executable. In windows, where you have
Java installed, download the file, then just click on it with the mouse to run
it. Or to run it in place, right click and choose to open the file where it
is.
I developed this generator because I wanted to investigate an
algorithm for maze generation. The algorithm is this:
- create a matrix of cells - in this case 30x30 or 900 cells
- put each of the cells into a set - here I used a vector to hold the sets
- Since Set is not instantable, I used HashSet
- randomly choose a cell and randomly choose a contiguous (nsew) neighbor
- if the 2 cells are are in the same set reject
- if the 2 cells are in seperate sets, join them and join their sets
- repeat until the upper left and lower right are in the same set
The solution is the standard maze recursive solution recursiveSolve(x,y)
- if (x,y outside maze) return false
- if (x,y is goal) return true
- if (x,y not open) return false
- mark x,y as part of solution path
- if (recursiveSolveMaze(North of x,y) == true) return true
- if (recursiveSolveMaze(East of x,y) == true) return true
- if (recursiveSolveMaze(South of x,y) == true) return true
- if (recursiveSolveMaze(West of x,y) == true) return true
- unmark x,y as part of solution path
- return false
Maze