Maze generation: Difference between revisions

Content added Content deleted

Inline

Revision as of 18:04, 6 January 2011

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.

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.

Ada

Works with: Ada 2005

Works with: GNAT

mazes.ads: <lang Ada>generic

  Height : Positive;
  Width : Positive;

package Mazes is

  type Maze_Grid is private;

  procedure Initialize (Maze : in out Maze_Grid);

  procedure Put (Item : Maze_Grid);

private

  type Directions is (North, South, West, East);

  type Cell_Walls is array (Directions) of Boolean;
  type Cells is record
     Walls   : Cell_Walls := (others => True);
     Visited : Boolean    := False;
  end record;

  subtype Height_Type is Positive range 1 .. Height;
  subtype Width_Type is Positive range 1 .. Width;

  type Maze_Grid is array (Height_Type, Width_Type) of Cells;

end Mazes;</lang>

mazes.adb: <lang Ada>with Ada.Numerics.Discrete_Random; with Ada.Text_IO;

package body Mazes is

  package RNG is new Ada.Numerics.Discrete_Random (Positive);
  package Random_Direction is new Ada.Numerics.Discrete_Random (Directions);

  Generator     : RNG.Generator;
  Dir_Generator : Random_Direction.Generator;

  function "-" (Dir : Directions) return Directions;

  procedure Depth_First_Algorithm
    (Maze   : in out Maze_Grid;
     Row    : Height_Type;
     Column : Width_Type);

  function Has_Unvisited_Neighbours
    (Maze   : Maze_Grid;
     Row    : Height_Type;
     Column : Width_Type)
     return   Boolean;

  procedure Move
    (Row        : in out Height_Type;
     Column     : in out Width_Type;
     Direction  : Directions;
     Valid_Move : out Boolean);

  function "-" (Dir : Directions) return Directions is
  begin
     case Dir is
        when North =>
           return South;
        when South =>
           return North;
        when East =>
           return West;
        when West =>
           return East;
     end case;
  end "-";

  procedure Depth_First_Algorithm
    (Maze   : in out Maze_Grid;
     Row    : Height_Type;
     Column : Width_Type)
  is
     Next_Row        : Height_Type;
     Next_Column     : Width_Type;
     Next_Direction  : Directions;
     Valid_Direction : Boolean;
  begin
     -- mark as visited
     Maze (Row, Column).Visited := True;
     -- continue as long as there are unvisited neighbours left
     while Has_Unvisited_Neighbours (Maze, Row, Column) loop
        -- use random direction
        Next_Direction := Random_Direction.Random (Dir_Generator);
        Next_Row       := Row;
        Next_Column    := Column;
        Move (Next_Row, Next_Column, Next_Direction, Valid_Direction);
        if Valid_Direction then
           -- connect the two cells
           if not Maze (Next_Row, Next_Column).Visited then
              Maze (Row, Column).Walls (Next_Direction)              :=
                False;
              Maze (Next_Row, Next_Column).Walls (-Next_Direction)   :=
                False;
              Depth_First_Algorithm (Maze, Next_Row, Next_Column);
           end if;
        end if;
     end loop;
  end Depth_First_Algorithm;

  function Has_Unvisited_Neighbours
    (Maze   : Maze_Grid;
     Row    : Height_Type;
     Column : Width_Type)
     return   Boolean
  is
     Neighbour_Row    : Height_Type;
     Neighbour_Column : Width_Type;
     Is_Valid         : Boolean;
  begin
     for Dir in Directions loop
        Neighbour_Row    := Row;
        Neighbour_Column := Column;
        Move
          (Row        => Neighbour_Row,
           Column     => Neighbour_Column,
           Direction  => Dir,
           Valid_Move => Is_Valid);
        if Is_Valid
          and then not Maze (Neighbour_Row, Neighbour_Column).Visited
        then
           return True;
        end if;
     end loop;
     return False;
  end Has_Unvisited_Neighbours;

  procedure Initialize (Maze : in out Maze_Grid) is
     Row, Column : Positive;
  begin
     -- initialize random generators
     RNG.Reset (Generator);
     Random_Direction.Reset (Dir_Generator);
     -- choose starting cell
     Row    := RNG.Random (Generator) mod Height + 1;
     Column := RNG.Random (Generator) mod Width + 1;
     Ada.Text_IO.Put_Line
       ("Starting generation at " &
        Positive'Image (Row) &
        " x" &
        Positive'Image (Column));
     Depth_First_Algorithm (Maze, Row, Column);
  end Initialize;

  procedure Move
    (Row        : in out Height_Type;
     Column     : in out Width_Type;
     Direction  : Directions;
     Valid_Move : out Boolean)
  is
  begin
     Valid_Move := False;
     case Direction is
        when North =>
           if Row > Height_Type'First then
              Valid_Move := True;
              Row        := Row - 1;
           end if;
        when East =>
           if Column < Width_Type'Last then
              Valid_Move := True;
              Column     := Column + 1;
           end if;
        when West =>
           if Column > Width_Type'First then
              Valid_Move := True;
              Column     := Column - 1;
           end if;
        when South =>
           if Row < Height_Type'Last then
              Valid_Move := True;
              Row        := Row + 1;
           end if;
     end case;
  end Move;

  procedure Put (Item : Maze_Grid) is
  begin
     for Row in Item'Range (1) loop
        if Row = Item'First (1) then
           for Col in Item'Range (2) loop
              if Col = Item'First (2) then
                 Ada.Text_IO.Put ('+');
              end if;
              if Item (Row, Col).Walls (North) then
                 Ada.Text_IO.Put ("---");
              else
                 Ada.Text_IO.Put ("   ");
              end if;
              Ada.Text_IO.Put ('+');
           end loop;
           Ada.Text_IO.New_Line;
        end if;
        for Col in Item'Range (2) loop
           if Col = Item'First (2) then
              if Item (Row, Col).Walls (West) then
                 Ada.Text_IO.Put ('|');
              else
                 Ada.Text_IO.Put (' ');
              end if;
           elsif Item (Row, Col).Walls (West)
             and then Item (Row, Col - 1).Walls (East)
           then
              Ada.Text_IO.Put ('|');
           elsif Item (Row, Col).Walls (West)
             or else Item (Row, Col - 1).Walls (East)
           then
              Ada.Text_IO.Put ('>');
           else
              Ada.Text_IO.Put (' ');
           end if;
           if Item (Row, Col).Visited then
              Ada.Text_IO.Put ("   ");
           else
              Ada.Text_IO.Put ("???");
           end if;
           if Col = Item'Last (2) then
              if Item (Row, Col).Walls (East) then
                 Ada.Text_IO.Put ('|');
              else
                 Ada.Text_IO.Put (' ');
              end if;
           end if;
        end loop;
        Ada.Text_IO.New_Line;
        for Col in Item'Range (2) loop
           --for Col in Item'Range (2) loop
           if Col = Item'First (2) then
              Ada.Text_IO.Put ('+');
           end if;
           if Item (Row, Col).Walls (South) then
              Ada.Text_IO.Put ("---");
           else
              Ada.Text_IO.Put ("   ");
           end if;
           Ada.Text_IO.Put ('+');
           --end loop;
        end loop;
        Ada.Text_IO.New_Line;
     end loop;
  end Put;

end Mazes;</lang>

Example main.adb: <lang Ada>with Mazes; procedure Main is

  package Small_Mazes is new Mazes (Height => 8, Width => 11);
  My_Maze : Small_Mazes.Maze_Grid;

begin

  Small_Mazes.Initialize (My_Maze);
  Small_Mazes.Put (My_Maze);

end Main;</lang>

Output:

Starting generation at  3 x 7
+---+---+---+---+---+---+---+---+---+---+---+
|   |               |   |                   |
+   +   +   +---+   +   +   +---+---+---+   +
|       |       |       |   |       |       |
+   +---+---+   +---+---+   +   +   +   +---+
|           |           |   |   |   |   |   |
+   +---+---+---+---+   +---+   +   +   +   +
|   |           |       |       |       |   |
+   +   +---+   +   +   +   +---+---+---+   +
|   |   |           |   |       |           |
+   +   +---+---+---+---+---+   +---+   +   +
|   |   |                   |           |   |
+---+   +   +---+---+---+   +---+---+---+   +
|       |   |           |                   |
+   +---+   +---+---+   +---+---+---+---+---+
|                                           |
+---+---+---+---+---+---+---+---+---+---+---+

D

Works with: D version 2

Translation of: Python

<lang d>import std.stdio, std.string, std.random, std.algorithm;

int[][] makeMaze(const int height, const int width) {

   int[] getCandidateNeighbors(const int[][] maze, const int i) {
       int[] neighbors;
       int n = i - width;
       if (n >= 0 && !maze[n].length)
           neighbors ~= n;
       int s = i + width;
       if (s < (height * width) && !maze[s].length)
           neighbors ~= s;
       int e = i + 1;
       if (e >= 0 && e / width == i / width && !maze[e].length)
           neighbors ~= e;
       int w = i - 1;
       if (w >= 0 && w / width == i / width && !maze[w].length)
           neighbors ~= w;
       return neighbors;
   }

   int totalCells = height * width;
   auto maze = new int[][](totalCells);
   int currentCell = uniform(0, totalCells);
   int visited = 1;
   int[] cellstack;

   while (visited < totalCells) {
       int[] neighbors = getCandidateNeighbors(maze, currentCell);
       if (neighbors.length) {
           int ne = neighbors[uniform(0, neighbors.length)];
           maze[currentCell] ~= ne;
           maze[ne] ~= currentCell;
           cellstack ~= currentCell;
           currentCell = ne;
           visited++;
       } else {
           currentCell = cellstack[$ - 1];
           cellstack.length -= 1;
       }
   }

   return maze;

}

void showMaze(int[][] maze, const int height, const int width) {

   string s1, s2;
   foreach (i; 0 .. height * width) {
       if (i % width == 0) {
           writeln(s1);
           writeln(s2);
           s1 = "+";
           s2 = "|";
       }
       s1 ~= (indexOf(maze[i], i - width) != -1) ? "  +" : "--+";
       s2 ~= (indexOf(maze[i], i + 1) != -1) ? "   " : "  |";
   }
   writeln("+", repeat("--+", width));

}

void main() {

   enum int height = 8, width = 11;
   showMaze(makeMaze(height, width), height, width);

}</lang> Output example:


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

Alternative version

See Maze_solving#D

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:

x,y -- dimensions of maze
n -- number of openings to be generated
horiz -- two dimensional array of locations of horizontal openings (true means wall is open)
verti -- two dimensional array of locations of vertical openings (true means wall is open)
here -- current location under consideration
path -- history (stack) of locations that might need to be revisited
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)
potential -- locations adjacent to here
neighbors -- unvisited locations adjacent to here

Variable meanings in function display:

m -- maze to be drawn
text -- lines of text representing maze
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:

</body></html>

produced:

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

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:

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

PureBasic

<lang PureBasic>Enumeration

 ;indexes for types of offsets from maze coordinates (x,y)
 #visited ;used to index visited(x,y) in a given direction from current maze cell
 #maze    ;used to index maze() in a given direction from current maze cell
 #wall    ;used to index walls in maze() in a given direction from current maze cell
 #numOffsets = #wall 
 ;direction indexes
 #dir_ID = 0 ;identity value, produces no changes
 #firstDir
 #dir_N = #firstDir
 #dir_E
 #dir_S
 #dir_W
 #numDirs = #dir_W

EndEnumeration

DataSection

 ;maze(x,y) offsets for visited, maze, & walls for each direction
 Data.i 1, 1,  0,  0, 0, 0 ;ID
 Data.i 1, 0,  0, -1, 0, 0 ;N
 Data.i 2, 1,  1,  0, 1, 0 ;E
 Data.i 1, 2,  0,  1, 0, 1 ;S
 Data.i 0, 1, -1,  0, 0, 0 ;W
 Data.i %00, %01, %10, %01, %10 ;wall values for ID, N, E, S, W

EndDataSection

cellDWidth = 4

Structure mazeOutput

 vWall.s
 hWall.s

EndStructure

setup reference values indexed by type and direction from current map cell

Global Dim offset.POINT(#numOffsets, #numDirs) Define i, j For i = 0 To #numDirs

 For j = 0 To #numOffsets
   Read.i offset(j, i)\x: Read.i offset(j, i)\y
 Next

Procedure makeDisplayMazeRow(Array mazeRow.mazeOutput(1), Array maze(2), y)

 ;modify mazeRow() to produce output of 2 strings showing the vertical walls above and horizontal walls across a given maze row
 Protected x, vWall.s, hWall.s
 Protected mazeWidth = ArraySize(maze(), 1), mazeHeight = ArraySize(maze(), 2)
 
 vWall = "": hWall = ""
 For x = 0 To mazeWidth
   If maze(x, y) & wallvalue(#dir_N): vWall + "+   ": Else: vWall + "+---": EndIf 
   If maze(x, y) & wallvalue(#dir_W): hWall + "    ": Else: hWall + "|   ": EndIf 
 Next
 mazeRow(0)\vWall = Left(vWall, mazeWidth * #cellDWidth + 1)
 If y <> mazeHeight: mazeRow(0)\hWall = Left(hWall, mazeWidth * #cellDWidth + 1): Else: mazeRow(0)\hWall = "": EndIf

EndProcedure

Procedure displayMaze(Array maze(2))

 Protected x, y, vWall.s, hWall.s, mazeHeight = ArraySize(maze(), 2)
 Protected Dim mazeRow.mazeOutput(0)
 
 For y = 0 To mazeHeight
   makeDisplayMazeRow(mazeRow(), maze(), y)
   PrintN(mazeRow(0)\vWall): PrintN(mazeRow(0)\hWall)
 Next

EndProcedure

Procedure generateMaze(Array maze(2), mazeWidth, mazeHeight)

 Dim maze(mazeWidth, mazeHeight) ;Each cell specifies walls present above and to the left of it,
                                 ;array includes an extra row and column for the right and bottom walls
 Dim visited(mazeWidth + 1, mazeHeight + 1) ;Each cell represents a cell of the maze, an extra line of cells are included
                                            ;as padding around the representative cells for easy border detection
 
 Protected i
 ;mark outside border as already visited (off limits)
 For i = 0 To mazeWidth
   visited(i + offset(#visited, #dir_N)\x, 0 + offset(#visited, #dir_N)\y) = #True
   visited(i + offset(#visited, #dir_S)\x, mazeHeight - 1 + offset(#visited, #dir_S)\y) = #True
 Next
 For i = 0 To mazeHeight
   visited(0 + offset(#visited, #dir_W)\x, i + offset(#visited, #dir_W)\y) = #True
   visited(mazeWidth - 1 + offset(#visited, #dir_E)\x, i + offset(#visited, #dir_E)\y) = #True
 Next
 
 ;generate maze
 Protected x = Random(mazeWidth - 1), y = Random (mazeHeight - 1), cellCount, nextCell
 visited(x + offset(#visited, #dir_ID)\x, y + offset(#visited, #dir_ID)\y) = #True
 PrintN("Maze of size " + Str(mazeWidth) + " x " + Str(mazeHeight) + ", generation started at " + Str(x) + " x " + Str(y))
 
 NewList stack.POINT()
 Dim unvisited(#numDirs - #firstDir)
 Repeat
   cellCount = 0
   For i = #firstDir To #numDirs
     If Not visited(x + offset(#visited, i)\x, y + offset(#visited, i)\y)
       unvisited(cellCount) = i: cellCount + 1
     EndIf 
   Next 
   
   If cellCount
     nextCell = unvisited(Random(cellCount - 1))
     visited(x + offset(#visited, nextCell)\x, y + offset(#visited, nextCell)\y) = #True
     maze(x + offset(#wall, nextCell)\x, y + offset(#wall, nextCell)\y) | wallvalue(nextCell)
     
     If cellCount > 1
       AddElement(stack())
       stack()\x = x: stack()\y = y
     EndIf 
     x + offset(#maze, nextCell)\x: y + offset(#maze, nextCell)\y
   ElseIf ListSize(stack()) > 0
     x = stack()\x: y = stack()\y
     DeleteElement(stack())
   Else 
     Break  ;end maze generation
   EndIf 
 ForEver
 
 ; ;mark random entry and exit point
 ; x = Random(mazeWidth - 1): y = Random(mazeHeight - 1)
 ; maze(x, 0) | wallvalue(#dir_N): maze(mazeWidth, y) | wallvalue(#dir_E)
 ProcedureReturn

EndProcedure

If OpenConsole()

 Dim maze(0, 0)
 Define mazeWidth = Random(5) + 7: mazeHeight = Random(5) + 3
 generateMaze(maze(), mazeWidth, mazeHeight)
 displayMaze(maze())
 
 Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
 CloseConsole()

EndIf</lang> The maze is represented by an array of cells where each cell indicates the walls present above (#dir_N) and to its left (#dir_W). Maze generation is done with a additional array marking the visited cells. Neither an entry nor an exit are created, these were not part of the task. A simple means of doing so is included but has been commented out.

Sample output:

Maze of size 11 x 8, generation started at 9 x 3
+---+---+---+---+---+---+---+---+---+---+---+
|   |           |           |               |
+   +   +---+   +   +---+   +   +---+   +   +
|   |       |       |       |   |       |   |
+   +---+   +---+---+   +---+   +   +---+---+
|   |       |       |           |           |
+   +   +---+---+   +---+---+---+---+---+   +
|       |           |       |       |       |
+   +---+   +---+   +   +---+   +   +---+---+
|           |   |   |           |           |
+---+---+---+   +   +   +---+---+   +---+   +
|           |       |           |       |   |
+   +---+---+   +---+   +---+---+   +   +---+
|       |       |       |       |   |       |
+   +   +   +---+---+---+   +   +---+---+   +
|   |                       |               |
+---+---+---+---+---+---+---+---+---+---+---+

Python

<lang Python>from random import randrange, choice

def make_maze(height, width):

   def get_candidate_neighbors(cells, i):
       neighbors = []

       n = i - width
       s = i + width
       e = i + 1
       w = i - 1

       if n >= 0 and not cells[n]:
           neighbors.append(n)
       if (s < height * width) and (not cells[s]):
           neighbors.append(s)
       if (e // width == i // width) and (not cells[e]):
           neighbors.append(e)
       if (w // width == i // width) and (not cells[w]):
           neighbors.append(w)

       return neighbors

   # cells data structure is simply a list of lists. Each cell
   # has a list of the neighbors where there is a connection
   # so an empty list means that a cell has all walls remaining.
   total_cells = height * width
   cells = [[] for i in xrange(total_cells)]
   cur_cell = randrange(total_cells)
   visited = 1
   cellstack = []

   while visited < total_cells:
       neighbors = get_candidate_neighbors(cells, cur_cell)
       if len(neighbors):
           new = choice(neighbors)

           # breakdown the wall
           cells[cur_cell].append(new)
           cells[new].append(cur_cell)
           cellstack.append(cur_cell)
           cur_cell = new
           visited += 1
       else:
           cur_cell = cellstack.pop()

   return cells

def show_maze(cells, height, width):

   s1, s2 = "", ""
   for i in xrange(height * width):
       if i % width == 0:
           print s1
           print s2
           s1 = "+"
           s2 = "|"
       s1 += "  +" if (i - width) in cells[i] else "--+"
       s2 += "   " if (i + 1) in cells[i] else "  |"
   print "+" + "--+" * width

height, width = 8, 11 show_maze(make_maze(height, width), height, width)</lang> Sample Output:

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

Tcl

Translation of: Javascript

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

Helper to pick a random number

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

Helper to pick a random element of a list

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

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]

}

Demonstration

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

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