

 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.


code Ran=1, CrLf=9, Text=12;            \intrinsic routines
def  Cols=20, Rows=6;                   \dimensions of maze (cells)
int  Cell(Cols+1, Rows+1, 3);           \cells (plus right and bottom borders)
def  LeftWall, Ceiling, Connected;      \attributes of each cell (= 0, 1 and 2)
 
proc ConnectFrom(X, Y);         \Connect cells starting from cell X,Y
int  X, Y;
int  Dir, Dir0;
[Cell(X, Y, Connected):= true;  \mark current cell as connected
Dir:= Ran(4);                   \randomly choose a direction
Dir0:= Dir;                     \save this initial direction
repeat  case Dir of             \try to connect to cell at Dir
          0: if X+1<Cols & not Cell(X+1, Y, Connected) then     \go right
                [Cell(X+1, Y, LeftWall):= false; ConnectFrom(X+1, Y)];
          1: if Y+1<Rows & not Cell(X, Y+1, Connected) then     \go down
                [Cell(X, Y+1, Ceiling):= false;  ConnectFrom(X, Y+1)];
          2: if X-1>=0 & not Cell(X-1, Y, Connected) then       \go left
                [Cell(X, Y, LeftWall):= false;   ConnectFrom(X-1, Y)];
          3: if Y-1>=0 & not Cell(X, Y-1, Connected) then       \go up
                [Cell(X, Y, Ceiling):= false;    ConnectFrom(X, Y-1)]
        other   [];             \(never occurs)
        Dir:= Dir+1 & $03;      \next direction
until   Dir = Dir0;
];
 
int  X, Y;
[for Y:= 0 to Rows do
    for X:= 0 to Cols do
        [Cell(X, Y, LeftWall):= true;           \start with all walls and
         Cell(X, Y, Ceiling):= true;            \ ceilings in place
         Cell(X, Y, Connected):= false;         \ and all cells disconnected
        ];
Cell(0, 0, LeftWall):= false;                   \make left and right doorways
Cell(Cols, Rows-1, LeftWall):= false;
ConnectFrom(Ran(Cols), Ran(Rows));              \randomly pick a starting cell
for Y:= 0 to Rows do                            \display the maze
        [CrLf(0);
        for X:= 0 to Cols do
                Text(0, if X#Cols & Cell(X, Y, Ceiling)  then "+--" else "+  ");
        CrLf(0);
        for X:= 0 to Cols do
                Text(0, if Y#Rows & Cell(X, Y, LeftWall) then "|  " else "   ");
        ];
]