This Java Script calculator generates a random perfect maze given the desired number of rows and columns. To operate the calculator, enter values for rows and columns. Then press the Compute button to obtain a random maze. On invalid entries, a popup window will display an error message.
Return to Contents
The Java Script source code for this program can be viewed by using the View|Source command of your web browser.
You may use or modify this source code in any way you find useful, provided that you agree that the author has no warranty, obligations or liability. You must determine the suitability of this source code for your use.
Return to Contents
Definition
In a perfect maze, there is one and only one path from any point in the maze to any other point. That is, there are no inaccessible sections, no circular paths, and no open regions. A perfect maze can be generated easily with a computer using a depth first search algorithm.
Maze data structures
A two dimensional maze can be represented as a rectangular array of square cells. Each cell has four walls. The state of each wall (north, south, east, and west) of each cell is maintained in a data structure consisting of an array of records. Each record stores a bit value that represents the state of each wall in a cell. To create a path between adjacent cells, the exit wall from the current cell and the entry wall to the next cell are removed. For example, if the next cell is to the right (east) of the current cell, remove the right (east) wall of the current cell and the left (west) wall of the next cell.
Algorithm
Depth first search assumes that, initially, all cell walls are in place. Then these operations are executed:
When the algorithm is completed, every cell will have been visited and therefore no cell is inaccessible. Since each cell is visited once (backtracking doesn't count), creation of any open areas or paths that circle back on themselves is prevented. Because one and only one path will exist between any two cells in the maze, the start and end points can be placed anywhere.
- Select any cell in the array as the current cell. Set the count of cells visited to one.
- If one or more neighbor cells exist that have not been visited,
else, if none exist
- Pick one at random as the next cell.
- Remove the walls between the cells.
- Make the next cell the current cell.
- Increment count of cells visited.
- make the previous cell the current cell (backtrack).
- Repeat step 2 until the count of cells visited equals total number of cells.
Return to Contents
AbCd Classics - free on-line books