

 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.


OPTION BASE 0
RANDOMIZE TIMER
 
REM must be even
width% = 40
height% = 20
 
REM make array and fill
DIM maze$(width%, height%)
FOR x% = 0 TO width%
    FOR y% = 0 TO height%
        maze$(x%, y%) = "#"
    NEXT y%
NEXT x%
 
REM initial start location
currentx% = INT(RND * (width% - 1))
currenty% = INT(RND * (height% - 1))
REM value must be odd
IF currentx% MOD 2 = 0 THEN currentx% = currentx% + 1
IF currenty% MOD 2 = 0 THEN currenty% = currenty% + 1
maze$(currentx%, currenty%) = " "
 
REM generate maze
done% = 0
DO WHILE done% = 0
    FOR i% = 0 TO 99
        oldx% = currentx%
        oldy% = currenty%
 
        REM move in random direction
        SELECT CASE INT(RND * 4)
            CASE 0
                IF currentx% + 2 < width% THEN currentx% = currentx% + 2
            CASE 1
                IF currenty% + 2 < height% THEN currenty% = currenty% + 2
            CASE 2
                IF currentx% - 2 > 0 THEN currentx% = currentx% - 2
            CASE 3
                IF currenty% - 2 > 0 THEN currenty% = currenty% - 2
        END SELECT
 
        REM if cell is unvisited then connect it
        IF maze$(currentx%, currenty%) = "#" THEN
            maze$(currentx%, currenty%) = " "
            maze$(INT((currentx% + oldx%) / 2), ((currenty% + oldy%) / 2)) = " "
        END IF
    NEXT i%
 
    REM check if all cells are visited
    done% = 1
    FOR x% = 1 TO width% - 1 STEP 2
        FOR y% = 1 TO height% - 1 STEP 2
            IF maze$(x%, y%) = "#" THEN done% = 0
        NEXT y%
    NEXT x%
LOOP
 
REM draw maze
FOR y% = 0 TO height%
    FOR x% = 0 TO width%
        PRINT maze$(x%, y%);
    NEXT x%
    PRINT
NEXT y%
 
REM wait
DO: LOOP WHILE INKEY$ = ""