The algorithm consists of 3 parts, a function and 2 scripts and was split for convenience in writing and troubleshooting. The generator works by creating a matrix of 0's, picking a location at random and turning the 0 into a 1, then creating branches of 1's outwards in random directions until no further branches can be made.
This script is the first one called in the function and is simply used to move the active coordinate 2 units in a random direction. By moving 2 units, a grid of coordinates is rendered incapable of turning into 1's. These coordinates become the maze walls.
This is the second script called in the function. It detects if the new active coordinate has already been activated (if it is a 1), and if so moves back along the path the active coordinate followed until an unactivated coordinate is available. When this condition is met, it activates the coordinate (changes a 0 to a 1) as well as the coordinate in between both the current and the last active coordinates.
The is the command window of MATLAB. From here, the function is called using an x and y dimension for the maze. This dimension is the size of the maze without walls. The matrix it generates is (2x-1) in size. The 10x10 maze generated here uses a 19x19 matrix.
When the maze can grow no farther, the generator stops. The matrix can then be copy pasted into excel.
Using an Excel macro I wrote, each cell is filled with either black for 0 or white for 1.
This is the matrix after being filled. The matrix is then given a border, the text removed, and the maze printed.
The maze at the time of printing. (Note the maze has been rotated 90deg clockwise)
A second finished maze.
A third finished maze.
gLike
Maze Generator
As a side project for the maze solving robot, I wrote a program to randomly generate a black and white maze that the robot could solve. I developed this algorithm to form a "perfect maze" (only one solution) using MATLAB and Excel with VBA.
