Maze generation

Maze generation
You are encouraged to solve this task according to the task description, using any language you may know.

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)

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

1. Start at a random cell.
2. 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.

See also Maze solving.

D

Works with: D version 2

<lang d>import std.stdio, std.random, std.array;

enum {visited = 1, north = 2, east = 4, south = 8, west = 16}; struct cell { int c, r, m; } const w = 11, h = 8; cell[][] maze;

void main() {

   build();
   print();

}

void build() {

   void breakWall(ref cell c, ref cell n) {
       if (c.c == n.c) {
           if (c.r < n.r) {
               c.m &= ~south; n.m &= ~north;
           } else if (c.r > n.r) {
               c.m &= ~north; n.m &= ~south;
           }
       } else if (c.r == n.r) {
           if (c.c < n.c) { 
               c.m &= ~east; n.m &= ~west;
           } else if (c.c > n.c) {
               c.m &= ~west; n.m &= ~east;
           }
       }
   }
   
   bool deadEnd(cell[] nbrs) {
       foreach (n; nbrs) {
           if ((n.m & visited) == 0)
               return false;
       }
       return true;
   }

   void setNeighbors(cell c, ref cell[] nbrs) {
       nbrs.length = 0;
       if (c.r != 0) {
           nbrs ~= maze[c.c][c.r - 1]; // n
       }
       if (c.c != 0) {
           nbrs ~= maze[c.c - 1][c.r]; // w
       }
       if (c.r != h - 1) {
           nbrs ~= maze[c.c][c.r + 1]; // s
       }
       if (c.c != w - 1) {
           nbrs ~= maze[c.c + 1][c.r]; // e
       }
   }
   
   void dig(ref cell c, ref cell[] stack, ref cell[] nbrs) {
       cell n;
       do {
           n = nbrs[uniform(0, nbrs.length)];
       } while ((n.m & visited) != 0)

       n.m |= visited; 
       breakWall(c, n);
       maze[c.c][c.r] = c;
       maze[n.c][n.r] = n;
       stack ~= c;
       c = n;
       setNeighbors(c, nbrs);
   }

   // setup
   maze = new cell[][](w, h);
   for (int r = 0; r < h; r++)
       for (int c = 0; c < w; c++)
           maze[c][r] = cell(c, r, north|east|south|west);
   cell[] nbrs;
   cell[] stack;
   
   cell c = maze[uniform(0, w)][uniform(0, h)];
   c.m |= visited;
   setNeighbors(c, nbrs);
   dig(c, stack, nbrs); 

   // go
   while (stack.length > 0) {
       if (deadEnd(nbrs)) {
           c = stack.back; 
           stack.popBack;
           setNeighbors(c, nbrs);
       } else {
           dig(c, stack, nbrs);
       }
   }

}

void print() {

   for (int r = 0; r < h; r++) {
       auto hori = appender("");
       auto vert = appender("");
       for (int c; c < w; c++) {
           if (maze[c][r].m & north) {
               if (c == w - 1) hori.put("+---+"); else hori.put("+---");
           } else {
               if (c == w - 1) hori.put("+   +"); else hori.put("+   ");
           }
           if (maze[c][r].m & west) {
               if (c == w - 1) vert.put("|   |"); else vert.put("|   ");
           } else {
               if (c == w - 1) vert.put("    |"); else vert.put("    ");
           }
       }
       writeln(hori.data, "\n", vert.data); 
   }
   for (int c; c < w; c++) 
       write("+---");
   writeln("+");

}</lang>

+---+---+---+---+---+---+---+---+---+---+---+
|                       |               |   |
+---+---+---+   +---+   +   +---+---+   +   +
|               |       |           |       |
+   +---+---+---+   +---+---+---+   +---+   +
|       |                       |   |   |   |
+---+   +---+---+---+---+---+   +   +   +   +
|       |           |       |   |   |       |
+   +   +   +---+   +---+   +   +   +---+---+
|   |   |   |   |   |       |   |           |
+   +   +---+   +   +   +   +   +---+---+   +
|   |   |           |   |   |       |       |
+   +---+   +---+---+   +---+---+   +   +   +
|       |       |   |           |       |   |
+   +   +---+   +   +   +---+   +---+---+   +
|   |           |           |               |
+---+---+---+---+---+---+---+---+---+---+---+

J

This algorithm allows almost no parallelism. So, while it might be "simple", generating very large mazes this way will not be necessarily efficient to implement on future (highly parallel) systems. That said, perhaps mazes with millions of cells are not very likely to be needed to be generated quickly.

Anyways, based on the picolisp implementation, except without any relevant grid support:

<lang j>maze=:4 :0

 assert.0<:n=.<:x*y
 horiz=. 0$~x,y-1
 verti=. 0$~(x-1),y
 path=.,:here=. ?x,y
 unvisited=.0 (<here+1)} 0,0,~|:0,0,~1$~y,x
 while.n do.
   neighbors=. here+"1 (,-)=0 1
   neighbors=. neighbors #~ (<"1 neighbors+1) {unvisited
   if.#neighbors do.
     n=.n-1
     next=. ({~ ?@#) neighbors
     unvisited=.0 (<next+1)} unvisited
     if.{.next=here
     do. horiz=.1 (<-:here+next-0 1)} horiz
     else. verti=. 1 (<-:here+next-1 0)} verti end.
     path=.path,here=.next
   else.
     here=.{:path
     path=.}:path
   end.
 end.
 horiz;verti

)

display=:3 :0

 size=. >.&$&>/y
 text=. (}:1 3$~2*1+{:size)#"1":size$<' '
 'hdoor vdoor'=. 2 4&*&.>&.> (#&,{@;&i./@$)&.> y
 ' ' (a:-.~0 1;0 2; 0 3;(2 1-~$text);(1 4&+&.> hdoor),,vdoor+&.>"0/2 1;2 2;2 3)} text

)</lang>

The result of maze is a pair of arrays: one for open "doors" in the horizontal direction and the other for open "doors" in the vertical direction. The entry and exit doors are not represented by maze -- they are implicitly defined and are implemented in display.

Example use (with ascii box drawing enabled):

<lang j> display 8 maze 11 + +---+---+---+---+---+---+---+---+---+---+ | | | | | + + + + +---+ + +---+---+ + + | | | | | | | | + +---+---+ + +---+---+---+ + + + | | | | | | | +---+ +---+ + + +---+ + +---+---+ | | | | | | | + + +---+---+ +---+ + +---+---+ + | | | | | | | | | + +---+ + + + + +---+---+ + + | | | | | + +---+---+---+---+---+---+---+ +---+ + | | | | | | | | | + + + + + + + + +---+ + + | | | | | +---+---+---+---+---+---+---+---+---+---+---+</lang>

JavaScript

Translation of: J

<lang javascript>function maze(x,y) { var n=x*y-1; if (n<0) {alert("illegal maze dimensions");return;} var horiz=[]; for (var j= 0; j<x+1; j++) horiz[j]= []; var verti=[]; for (var j= 0; j<x+1; j++) verti[j]= []; var here= [Math.floor(Math.random()*x), Math.floor(Math.random()*y)]; var path= [here]; var unvisited= []; for (var j= 0; j<x+2; j++) { unvisited[j]= []; for (var k= 0; k<y+1; k++) unvisited[j].push(j>0 && j<x+1 && k>0 && (j != here[0]+1 || k != here[1]+1)); } while (0<n) { var potential= [[here[0]+1, here[1]], [here[0],here[1]+1], [here[0]-1, here[1]], [here[0],here[1]-1]]; var neighbors= []; for (var j= 0; j < 4; j++) if (unvisited[potential[j][0]+1][potential[j][1]+1]) neighbors.push(potential[j]); if (neighbors.length) { n= n-1; next= neighbors[Math.floor(Math.random()*neighbors.length)]; unvisited[next[0]+1][next[1]+1]= false; if (next[0] == here[0]) horiz[next[0]][(next[1]+here[1]-1)/2]= true; else verti[(next[0]+here[0]-1)/2][next[1]]= true; path.push(here= next); } else here= path.pop(); } return ({x: x, y: y, horiz: horiz, verti: verti}); }

function display(m) { var text= []; for (var j= 0; j<m.x*2+1; j++) { var line= []; if (0 == j%2) for (var k=0; k<m.y*4+1; k++) if (0 == k%4) line[k]= '+'; else if (j>0 && m.verti[j/2-1][Math.floor(k/4)]) line[k]= ' '; else line[k]= '-'; else for (var k=0; k<m.y*4+1; k++) if (0 == k%4) if (k>0 && m.horiz[(j-1)/2][k/4-1]) line[k]= ' '; else line[k]= '|'; else line[k]= ' '; if (0 == j) line[1]= line[2]= line[3]= ' '; if (m.x*2-1 == j) line[4*m.y]= ' '; text.push(line.join()+'\r\n'); } return text.join(); }</lang>

Variable meanings in function maze:

1. x,y -- dimensions of maze
2. n -- number of openings to be generated
3. horiz -- two dimensional array of locations of horizontal openings (true means wall is open)
4. verti -- two dimensional array of locations of vertical openings (true means wall is open)
5. here -- current location under consideration
6. path -- history (stack) of locations that might need to be revisited
7. unvisited -- two dimensional array of locations that have not been visited, padded to avoid need for boundary tests (true means location needs to be visited)
8. potential -- locations adjacent to here
9. neighbors -- unvisited locations adjacent to here

Variable meanings in function display:

1. m -- maze to be drawn
2. text -- lines of text representing maze
3. line -- characters of current line

Note that this implementation relies on javascript arrays being treatable as infinite in size with false (null) values springing into existence as needed, to support referenced array locations. (This significantly reduces the bulk of the necessary initialization code.)

Example use:

<lang html><html><head><title></title></head><body>

</body></html>

<script type="text/javascript"> /* ABOVE CODE GOES HERE */ document.getElementById('out').innerHTML= display(maze(8,11)); </script></lang>

produced:

<lang>+ +---+---+---+---+---+---+---+---+---+---+ | | | | +---+---+ + +---+ + +---+---+ + + | | | | | | | | + + + +---+ +---+ +---+---+ + + | | | | | | | + +---+ +---+---+---+---+---+ + + + | | | | | | +---+ +---+ +---+---+ + +---+---+ + | | | | | | | + + + +---+---+---+---+---+ + + + | | | | | | + +---+---+ +---+---+ + +---+---+ + | | | | | | | + + + +---+ +---+---+ + + +---+ | | | | +---+---+---+---+---+---+---+---+---+---+---+</lang>

For an animated presentation of the progress of this maze creation process, you can use display in each iteration of the main loop. You would also need to take steps to make sure you could see each intermediate result.

For example, change replace the line while (0<n) { with:

<lang javascript> function step() { if (0<n) {</lang>

And replace the closing brace for this while loop with:

<lang javascript> document.getElementById('out').innerHTML= display({x: x, y: y, horiz: horiz, verti: verti, here: here}); setTimeout(step, 100); } } step();</lang>

To better see the progress, you might want a marker in place, showing the position being considered. To do that, replace the line which reads if (0 == k%4) { with

<lang javascript> if (m.here && m.here[0]*2+1 == j && m.here[1]*4+2 == k) line[k]= '#' else if (0 == k%4) {</lang>

Note however that this leaves the final '#' in place on maze completion, and that the function maze no longer returns a result which represents a generated maze.

Note also that this display suggests an optimization. You can replace the line reading path.push(here= next); with:

<lang javascript> here= next; if (1 < neighbors.length) path.push(here);</lang>

And this does indeed save a negligible bit of processing, but the maze algorithm will still be forced to backtrack through a number of locations which have no unvisited neighbors.

PicoLisp

This solution uses 'grid' from "lib/simul.l" to generate the two-dimensional structure. <lang PicoLisp>(load "@lib/simul.l")

(de maze (DX DY)

  (let Maze (grid DX DY)
     (let Fld (get Maze (rand 1 DX) (rand 1 DY))
        (recur (Fld)
           (for Dir (shuffle '((west . east) (east . west) (south . north) (north . south)))
              (with ((car Dir) Fld)
                 (unless (or (: west) (: east) (: south) (: north))
                    (put Fld (car Dir) This)
                    (put This (cdr Dir) Fld)
                    (recurse This) ) ) ) ) )
     (for (X . Col) Maze
        (for (Y . This) Col
           (set This
              (cons
                 (cons
                    (: west)
                    (or
                       (: east)
                       (and (= Y 1) (= X DX)) ) )
                 (cons
                    (: south)
                    (or
                       (: north)
                       (and (= X 1) (= Y DY)) ) ) ) ) ) )
     Maze ) )

(de display (Maze)

  (disp Maze 0 '((This) "   ")) )</lang>

Output:

: (display (maze 11 8))
   +   +---+---+---+---+---+---+---+---+---+---+
 8 |           |       |                       |
   +   +   +   +   +   +   +---+   +---+---+   +
 7 |   |   |       |   |   |       |       |   |
   +---+   +---+---+   +   +   +---+   +   +   +
 6 |   |       |       |   |           |   |   |
   +   +---+   +---+   +---+---+---+   +   +---+
 5 |       |       |               |   |       |
   +---+   +---+   +---+---+---+   +---+---+   +
 4 |   |       |       |       |   |           |
   +   +---+   +---+   +---+   +   +   +---+   +
 3 |       |       |   |       |   |       |   |
   +   +---+---+   +   +   +   +   +---+   +   +
 2 |       |       |   |   |   |   |       |   |
   +   +   +   +---+   +   +---+   +   +---+   +
 1 |   |               |               |
   +---+---+---+---+---+---+---+---+---+---+---+
     a   b   c   d   e   f   g   h   i   j   k

Tcl

Translation of: Javascript

<lang tcl>package require TclOO; # Or Tcl 8.6

1. Helper to pick a random number

proc rand n {expr {int(rand() * $n)}}

1. Helper to pick a random element of a list

proc pick list {lindex $list [rand [llength $list]]}

1. Helper _function_ to index into a list of lists

proc tcl::mathfunc::idx {v x y} {lindex $v $x $y}

oo::class create maze {

   variable x y horiz verti content
   constructor {width height} {

set y $width set x $height

set n [expr {$x * $y - 1}] if {$n < 0} {error "illegal maze dimensions"} set horiz [set verti [lrepeat $x [lrepeat $y 0]]] # This matrix holds the output for the Maze Solving task; not used for generation set content [lrepeat $x [lrepeat $y " "]] set unvisited [lrepeat [expr {$x+2}] [lrepeat [expr {$y+2}] 0]] # Helper to write into a list of lists (with offsets) proc unvisited= {x y value} { upvar 1 unvisited u lset u [expr {$x+1}] [expr {$y+1}] $value }

lappend stack [set here [list [rand $x] [rand $y]]] for {set j 0} {$j < $x} {incr j} { for {set k 0} {$k < $y} {incr k} { unvisited= $j $k [expr {$here ne [list $j $k]}] } }

while {0 < $n} { lassign $here hx hy set neighbours {} foreach {dx dy} {1 0 0 1 -1 0 0 -1} { if {idx($unvisited, $hx+$dx+1, $hy+$dy+1)} { lappend neighbours [list [expr {$hx+$dx}] [expr {$hy+$dy}]] } } if {[llength $neighbours]} { lassign [set here [pick $neighbours]] nx ny unvisited= $nx $ny 0 if {$nx == $hx} { lset horiz $nx [expr {min($ny, $hy)}] 1 } else { lset verti [expr {min($nx, $hx)}] $ny 1 } lappend stack $here incr n -1 } else { set here [lindex $stack end] set stack [lrange $stack 0 end-1] } }

rename unvisited= {}

   }

   # Maze displayer; takes a maze dictionary, returns a string
   method view {} {

set text {} for {set j 0} {$j < $x*2+1} {incr j} { set line {} for {set k 0} {$k < $y*4+1} {incr k} { if {$j%2 && $k%4==2} { # At the centre of the cell, put the "content" of the cell append line [expr {idx($content, $j/2, $k/4)}] } elseif {$j%2 && ($k%4 || $k && idx($horiz, $j/2, $k/4-1))} { append line " " } elseif {$j%2} { append line "|" } elseif {0 == $k%4} { append line "+" } elseif {$j && idx($verti, $j/2-1, $k/4)} { append line " " } else { append line "-" } } if {!$j} { lappend text [string replace $line 1 3 " "] } elseif {$x*2-1 == $j} { lappend text [string replace $line end end " "] } else { lappend text $line } } return [join $text \n]

   }

}

1. Demonstration

maze create m 11 8 puts [m view]</lang> Output:

+   +---+---+---+---+---+---+---+---+---+---+
|                   |               |       |
+---+---+   +---+---+   +   +---+   +---+   +
|           |           |   |       |       |
+   +   +---+   +---+---+   +---+   +   +   +
|   |   |               |       |   |   |   |
+   +---+   +---+---+---+   +   +   +   +   +
|       |   |           |   |   |       |   |
+   +   +   +   +---+---+   +   +---+---+   +
|   |       |       |       |   |   |       |
+---+---+---+---+   +   +---+   +   +   +---+
|               |   |   |   |   |   |       |
+   +---+---+   +   +   +   +   +   +---+   +
|       |   |       |       |   |       |   |
+---+   +   +---+---+---+---+   +   +---+   +
|                               |            
+---+---+---+---+---+---+---+---+---+---+---+