

 This page uses content from Wikipedia. The original article was at Maze generation algorithm. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)




Task

Generate and show a maze, using the simple Depth-first search algorithm.

Start at a random cell.
Mark the current cell as visited, and get a list of its neighbors. For each neighbor, starting with a randomly selected neighbor:
If that neighbor hasn't been visited, remove the wall between this cell and that neighbor, and then recurse with that neighbor as the current cell.


 Related tasks
 Maze solving.


program MazeGen
 
    // First and last columns/rows are "dead" cells. Makes generating
    // a maze with border walls much easier. Therefore, a visible
    // 20x20 maze has a maze size of 22. 	
    mazeSize int = 22;
 
    south boolean[][];
    west boolean[][];
    visited boolean[][];
 
    function main()
        initMaze();
        generateMaze();
        drawMaze();
    end
 
    private function initMaze()
 
        visited = createBooleanArray(mazeSize, mazeSize, false);
 
        // Initialize border cells as already visited
        for(col int from 1 to mazeSize)
            visited[col][1] = true;
            visited[col][mazeSize] = true;
        end
        for(row int from 1 to mazeSize)
            visited[1][row] = true;
            visited[mazeSize][row] = true;
        end
 
        // Initialize all walls as present
        south = createBooleanArray(mazeSize, mazeSize, true);
        west = createBooleanArray(mazeSize, mazeSize, true);
 
    end
 
    private function createBooleanArray(col int in, row int in, initialState boolean in) returns(boolean[][])
 
        newArray boolean[][] = new boolean[0][0];
 
        for(i int from 1 to col)
            innerArray boolean[] = new boolean[0];
            for(j int from 1 to row)
                innerArray.appendElement(initialState);
            end
            newArray.appendElement(innerArray);
        end
 
        return(newArray);
 
    end
 
    private function createIntegerArray(col int in, row int in, initialValue int in) returns(int[][])
 
        newArray int[][] = new int[0][0];
 
        for(i int from 1 to col)
            innerArray int[] = new int[0];
            for(j int from 1 to row)
                innerArray.appendElement(initialValue);
            end
            newArray.appendElement(innerArray);
        end
 
        return(newArray);
 
    end
 
    private function generate(col int in, row int in)
 
        // Mark cell as visited
        visited[col][row] = true;
 
        // Keep going as long as there is an unvisited neighbor
        while(!visited[col][row + 1] || !visited[col + 1][row] ||
                !visited[col][row - 1] || !visited[col - 1][row])
 
            while(true)
                r float = MathLib.random(); // Choose a random direction
 
                case
                    when(r < 0.25 && !visited[col][row + 1]) // Go south
                        south[col][row] = false; // South wall down
                        generate(col, row + 1);
                        exit while;
                    when(r >= 0.25 && r < 0.50 && !visited[col + 1][row]) // Go east 
                        west[col + 1][row] = false; // West wall of neighbor to the east down
                        generate(col + 1, row);
                        exit while;
                    when(r >= 0.5 && r < 0.75 && !visited[col][row - 1]) // Go north
                        south[col][row - 1] = false; // South wall of neighbor to the north down
                        generate(col, row - 1);
                        exit while;
                    when(r >= 0.75 && r < 1.00 && !visited[col - 1][row]) // Go west
                        west[col][row] = false; // West wall down
                        generate(col - 1, row);
                        exit while;
                end
            end
        end
 
    end
 
    private function generateMaze()
 
        // Pick random start position (within the visible maze space)
        randomStartCol int = MathLib.floor((MathLib.random() *(mazeSize - 2)) + 2);
        randomStartRow int = MathLib.floor((MathLib.random() *(mazeSize - 2)) + 2);
 
        generate(randomStartCol, randomStartRow);
 
    end
 
    private function drawMaze()
 
        line string;
 
        // Iterate over wall arrays (skipping dead border cells as required). 
        // Construct a line at a time and output to console.
        for(row int from 1 to mazeSize - 1)
 
            if(row > 1)
                line = "";
                for(col int from 2 to mazeSize)
                    if(west[col][row])
                        line ::= "|   ";
                    else
                        line ::= "    ";
                    end
                end
                Syslib.writeStdout(line);
            end
 
            line = "";
            for(col int from 2 to mazeSize - 1)
                if(south[col][row])
                    line ::= "+---";
                else
                    line ::= "+   ";
                end
            end
            line ::= "+";
            SysLib.writeStdout(line);
 
        end
 
    end
 
end