Maze generation: Difference between revisions

From Rosetta Code
Content added Content deleted
(Updated D entry)
Line 1,015: Line 1,015:
}
}
walk(uniform(0, w), uniform(0, h));
walk(uniform(0, w), uniform(0, h));
foreach (a, b; lockstep(hor, ver ~ []))
foreach (a, b; hor.zip(ver ~ []))
writeln(join(a ~ ["+\n"] ~ b));
writeln(join(a ~ ["+\n"] ~ b));
}</lang>
}</lang>

Revision as of 20:56, 27 May 2012

Task
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.

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
+---+---+---+---+---+---+---+---+---+---+---+
|   |               |   |                   |
+   +   +   +---+   +   +   +---+---+---+   +
|       |       |       |   |       |       |
+   +---+---+   +---+---+   +   +   +   +---+
|           |           |   |   |   |   |   |
+   +---+---+---+---+   +---+   +   +   +   +
|   |           |       |       |       |   |
+   +   +---+   +   +   +   +---+---+---+   +
|   |   |           |   |       |           |
+   +   +---+---+---+---+---+   +---+   +   +
|   |   |                   |           |   |
+---+   +   +---+---+---+   +---+---+---+   +
|       |   |           |                   |
+   +---+   +---+---+   +---+---+---+---+---+
|                                           |
+---+---+---+---+---+---+---+---+---+---+---+

Aime

<lang aime>void grid_maze(data b, integer N) { 

   data d;
   integer i, j;

   j = N;
   while (j) {

b_suffix(d, "+---"); j -= 1; 

   }
   {

b_suffix(d, "+\n"); 

   }

   j = N;
   while (j) {

b_suffix(d, "| * "); j -= 1; 

   }
   {

b_suffix(d, "|\n"); 

   }

   i = N;
   while (i) {

b_extend(b, d);

i -= 1; 

   }

   b_size(d, N * 4 + 2);

   {

b_extend(b, d); 

   }

}

void walk_cell(data b, integer N, integer line_size, integer x, integer y, list x_offsets, list y_offsets) { 

   integer i, r;

   b_replace(b, y + x, ' ');

   r = drand(3);

   i = 0;
   while (i < 4) {

integer p, q;

p = x + l_q_integer(x_offsets, (r + i) & 3); q = y + l_q_integer(y_offsets, (r + i) & 3);

if (-1 < p && p < line_size && -1 < q && q < line_size * (N * 2 + 1)) { if (b_text(b, q + p) == '*') { walk_cell(b, N, line_size, p, q, x_offsets, y_offsets); b_replace(b, (q + y) / 2 + (p + x) / 2, ' '); if (p == x) { b_replace(b, (q + y) / 2 + p - 1, ' '); b_replace(b, (q + y) / 2 + p + 1, ' '); } } }

i += 1; 

   }

}

void walk_maze(data b, integer N) { 

   integer line_size, x, y;
   list x_offsets, y_offsets;

   line_size = N * 4 + 1 + 1;

   lb_p_integer(x_offsets, 4);
   lb_p_integer(y_offsets, 0);
   lb_p_integer(x_offsets, 0);
   lb_p_integer(y_offsets, line_size * 2);
   lb_p_integer(x_offsets, -4);
   lb_p_integer(y_offsets, 0);
   lb_p_integer(x_offsets, 0);
   lb_p_integer(y_offsets, line_size * -2);

   x = drand(N - 1) * 4 + 2;
   y = line_size * (drand(N - 1) * 2 + 1);

   walk_cell(b, N, line_size, x, y, x_offsets, y_offsets);

}

integer main(void) { 

   data b;
   integer N;

   N = 10;

   grid_maze(b, N);

   walk_maze(b, N);

   o_text(b_string(b));

   return 0;

}</lang>

Output:
+---+---+---+---+---+---+---+---+---+---+
|                       |               |
+   +---+---+---+---+   +   +---+---+   +
|   |       |       |   |   |           |
+   +   +   +   +   +   +   +   +---+   +
|   |   |       |       |   |   |   |   |
+   +---+---+   +---+---+---+   +   +   +
|           |               |   |   |   |
+---+---+---+---+---+---+   +   +   +   +
|                       |   |   |       |
+   +---+---+---+---+   +   +   +---+---+
|   |               |   |   |           |
+   +---+---+---+   +   +   +---+   +   +
|       |       |       |       |   |   |
+   +   +   +   +   +---+---+   +---+   +
|   |       |   |           |       |   |
+---+---+---+   +---+---+---+---+   +   +
|               |       |       |       |
+   +---+---+---+   +   +   +   +---+   +
|                   |       |           |
+---+---+---+---+---+---+---+---+---+---+

AutoHotkey

For a challenge, this maze generation is entirely string based. That is to say, all operations including the wall removal and retrieval of cell states are done on the output string. <lang AHK>; Initially build the board Width := 11 Height := 8 Loop % height*2+1 { Outer := A_Index Loop % Width maze .= Outer & 1 ? "+-" : "|0" maze .= (Outer & 1 ? "+" : "|") "`n" } StringTrimRight, maze, maze, 1 ; removes trailing newline Clipboard := Walk(maze)

Walk(S, x=0, y=0){ If !x{ ; --Start at a random cell... StringReplace, junk, S, `n,,UseErrorLevel ; Calculate rows Random, y, 1, ErrorLevel//2 Random, x, 1, InStr(S, "`n")//2-1  ; Calculate height }

; --Obtain a list of its neighbors... neighbors := x "," y+1 "`n" x "," y-1 "`n" x+1 "," y "`n" x-1 "," y ; --Randomize the list... Sort neighbors, random

; --Then for each neighbor... Loop Parse, neighbors, `n { pC := InStr(A_LoopField, ","), x2 := SubStr(A_LoopField, 1, pC-1), y2 := SubStr(A_LoopField, pC+1) ; If it has not been visited... If GetChar(S, 2*x2, 2*y2) = "0"{ ; Mark it as visited... S := ChangeChar(s, 2*x2, 2*y2, " ") ; Remove the wall between this cell and the neighbor... S := ChangeChar(S, x+x2, y+y2, " ") ; Then recurse with the neighbor as the current cell S := Walk(S, x2, y2) } } return S }

Change a character in a string using x and y coordinates

ChangeChar(s, x, y, c){ Loop Parse, s, `n { If (A_Index = Y) Loop Parse, A_LoopField If (A_Index = x) out .= c Else out .= A_LoopField Else out .= A_LoopField out .= "`n" } StringTrimRight, out, out, 1 return out }

retrieve a character in a string using x and y coordinates

GetChar(s, x, y, n=1){ x*=n, y*=n Loop Parse, s, `n If (A_Index = Y) return SubStr(A_LoopField, x, 1) }</lang>

Sample output:
+-+-+-+-+-+-+-+-+-+-+-+
|         |     |     |
+-+ +-+-+ +-+ + + +-+-+
|   |         | |     |
+ +-+ +-+ +-+-+ +-+ + +
| |     | |   |   | | |
+ + +-+-+ + + +-+ +-+ +
| |   |   | |     |   |
+ +-+ + +-+-+-+ +-+ + +
| |   |       |     | |
+ +-+-+-+-+-+ +-+-+-+ +
| |   |       |   |   |
+ + + + +-+-+-+ + + +-+
|   |   |   |   | |   |
+-+-+-+-+ +-+ + +-+-+ +
|             |       |
+-+-+-+-+-+-+-+-+-+-+-+

C

Generation/solver in one. Requires UTF8 locale and unicode capable console. If your console font line-drawing chars are single width, define DOUBLE_SPACE to 0. <lang c>#include <stdio.h>

  1. include <stdlib.h>
  2. include <string.h>
  3. include <locale.h>
  1. define DOUBLE_SPACE 1
  1. if DOUBLE_SPACE
  2. define SPC "　"
  3. else
  4. define SPC " "
  5. endif

wchar_t glyph[] = L""SPC"│││─┘┐┤─└┌├─┴┬┼"SPC"┆┆┆┄╯╮ ┄╰╭ ┄";

typedef unsigned char byte; enum { N = 1, S = 2, W = 4, E = 8, V = 16 };

byte **cell; int w, h, avail;

  1. define each(i, x, y) for (i = x; i <= y; i++)

int irand(int n) { int r, rmax = n * (RAND_MAX / n); while ((r = rand()) >= rmax); return r / (RAND_MAX/n); }

void show() { int i, j, c; each(i, 0, 2 * h) { each(j, 0, 2 * w) { c = cell[i][j]; if (c > V) printf("\033[31m"); printf("%lc", glyph[c]); if (c > V) printf("\033[m"); } putchar('\n'); } }

inline int max(int a, int b) { return a >= b ? a : b; } inline int min(int a, int b) { return b >= a ? a : b; }

static int dirs[4][2] = {{-2, 0}, {0, 2}, {2, 0}, {0, -2}}; void walk(int x, int y) { int i, t, x1, y1, d[4] = { 0, 1, 2, 3 };

cell[y][x] |= V; avail--;

for (x1 = 3; x1; x1--) if (x1 != (y1 = irand(x1 + 1))) i = d[x1], d[x1] = d[y1], d[y1] = i;

for (i = 0; avail && i < 4; i++) { x1 = x + dirs[ d[i] ][0], y1 = y + dirs[ d[i] ][1];

if (cell[y1][x1] & V) continue;

/* break walls */ if (x1 == x) { t = (y + y1) / 2; cell[t][x+1] &= ~W, cell[t][x] &= ~(E|W), cell[t][x-1] &= ~E; } else if (y1 == y) { t = (x + x1)/2; cell[y-1][t] &= ~S, cell[y][t] &= ~(N|S), cell[y+1][t] &= ~N; } walk(x1, y1); } }

int solve(int x, int y, int tox, int toy) { int i, t, x1, y1;

cell[y][x] |= V; if (x == tox && y == toy) return 1;

each(i, 0, 3) { x1 = x + dirs[i][0], y1 = y + dirs[i][1]; if (cell[y1][x1]) continue;

/* mark path */ if (x1 == x) { t = (y + y1)/2; if (cell[t][x] || !solve(x1, y1, tox, toy)) continue;

cell[t-1][x] |= S, cell[t][x] |= V|N|S, cell[t+1][x] |= N; } else if (y1 == y) { t = (x + x1)/2; if (cell[y][t] || !solve(x1, y1, tox, toy)) continue;

cell[y][t-1] |= E, cell[y][t] |= V|E|W, cell[y][t+1] |= W; } return 1; }

/* backtrack */ cell[y][x] &= ~V; return 0; }

void make_maze() { int i, j; int h2 = 2 * h + 2, w2 = 2 * w + 2; byte **p;

p = calloc(sizeof(byte*) * (h2 + 2) + w2 * h2 + 1, 1);

p[1] = (byte*)(p + h2 + 2) + 1; each(i, 2, h2) p[i] = p[i-1] + w2; p[0] = p[h2]; cell = &p[1];

each(i, -1, 2 * h + 1) cell[i][-1] = cell[i][w2 - 1] = V; each(j, 0, 2 * w) cell[-1][j] = cell[h2 - 1][j] = V; each(i, 0, h) each(j, 0, 2 * w) cell[2*i][j] |= E|W; each(i, 0, 2 * h) each(j, 0, w) cell[i][2*j] |= N|S; each(j, 0, 2 * w) cell[0][j] &= ~N, cell[2*h][j] &= ~S; each(i, 0, 2 * h) cell[i][0] &= ~W, cell[i][2*w] &= ~E;

avail = w * h; walk(irand(2) * 2 + 1, irand(h) * 2 + 1);

/* reset visited marker (it's also used by path finder) */ each(i, 0, 2 * h) each(j, 0, 2 * w) cell[i][j] &= ~V; solve(1, 1, 2 * w - 1, 2 * h - 1);

show(); }

int main(int c, char **v) { setlocale(LC_ALL, ""); if (c < 2 || (w = atoi(v[1])) <= 0) w = 16; if (c < 3 || (h = atoi(v[2])) <= 0) h = 8;

make_maze();

return 0; }</lang>

Sample output:
┌───┬─────┬─────────┬───────┬───┐
│┄┄╮│╭┄┄┄╮│　　╭┄┄┄┄┄╮│　　╭┄┄┄╮│╭┄╮│
│　│┆│┆──┐┆│　│┆──┬─┐┆└──┆┌─┐┆│┆│┆│
│　│┆│╰┄╮│┆│　│╰┄╮│　│╰┄┄┄╯│　│╰┄╯│┆│
│　│┆└──┆│┆└─┼──┆│　└─────┤　└─┬─┘┆│
│　│╰┄┄┄╯│╰┄╮│╭┄╯│　　　　　　　│　　　│╭┄╯│
│　└─────┴─┐┆│┆┌─┴───┐　│　│　│　│┆──┤
│　　　　　　　　　│┆│┆│╭┄┄┄╮│　│　　　│　│╰┄╮│
│　──────┐　│┆│┆│┆──┐┆└─┤　┌─┘　└─┐┆│
│　　　　　　　│　│┆│╰┄╯　　│╰┄╮│　│　　　　　│┆│
│　┌─────┘　│┆├─────┴─┐┆│　│　──┬─┘┆│
│　│　　　　　　　│┆│╭┄┄┄┄┄╮│┆│　│　　　│╭┄╯│
├─┤　──┬─┬─┘┆│┆┌─┬──┆│┆└─┴─┐　│┆┌─┤
│　│　　　│　│╭┄╯│┆│　│╭┄╯│╰┄┄┄╮│　│┆│　│
│　└──　│　│┆──┘┆│　│┆──┴────┆│　│┆│　│
│　　　　　│　　╰┄┄┄╯│　　╰┄┄┄┄┄┄┄╯│　　╰┄┄│
└─────┴───────┴───────────┴─────┘

The very alternative version

Invoke as ./maze [width] [depth] [height], and output is in maze.pgm, which you can print out and cut to fold into a cuboid. Sample output with 15, 10 and 20 sizes.

<lang c>#include <stdio.h>

  1. include <stdlib.h>
  2. include <string.h>
  1. define CW 10 /* cell width. This decides how big the output is */

typedef struct cell_t cell_t, *cell;

enum { N, E, S, W, V }; struct cell_t { unsigned int flags; cell prev, next, nei[4]; /* neighbors */ };

int sx, sy, sz, w, h;

  1. define C(y, x) c[(y) * w + x]
  2. define P(y, x) pix[(y) * w2 + x]

void draw_maze(cell *c) {

  1. define FOR(a, b) for(a = 0; a < b; a++)

FILE *fp; int w2 = w * CW + 8, h2 = h * CW + 7; char *pix = malloc(w2 * h2); memset(pix, 200, w2 * h2);

void draw_face(int x, int y, int ww, int hh, int px, int py) { int i, j, k, l; cell t;

px += 2, py += 2; for (i = py; i <= py + hh * CW; i++) memset(&P(i, px), 0, ww * CW+1);

px++, py++;

  1. define mark(y, x) P(py + CW*i + y, px + CW*j + x) = 255

FOR (i, hh) FOR (j, ww) { FOR(k, CW - 1) FOR(l, CW - 1) mark(k, l);

t = C(y + i, x + j); if (t->flags & (1 << N)) FOR (l, CW - 1) mark(-1, l); if (t->flags & (1 << S)) FOR (l, CW - 1) mark(CW - 1, l); if (t->flags & (1 << E)) FOR (l, CW - 1) mark(l, CW - 1); if (t->flags & (1 << W)) FOR (l, CW - 1) mark(l, -1); } }

draw_face(0, 0, sx, sy, 0, 0); draw_face(0, sy, sx, sz, 0, CW*sy + 1); draw_face(sx, sy, sy, sz, CW*sx + 1, CW*sy + 1); draw_face(sx + sy, sy, sx, sz, CW*(sx + sy) + 2, CW*sy + 1); draw_face(sx + sy + sx, sy, sy, sz, CW*(sx + sy + sx) + 3, CW*sy + 1); draw_face(sx + sy, sy + sz, sx, sy, CW*(sx + sy) + 2, CW*(sy + sz) + 2);

fp = fopen("maze.pgm", "w+"); fprintf(fp, "P5\n%d %d\n255\n", w2, h2); fwrite(pix, 1, w2 * h2, fp); fclose(fp); }

cell rand_neighbor(cell x) { cell r = 0; int i, c = 1; for (i = N; i <= W; i++) { if (!x->nei[i] || (x->nei[i]->flags & (1 << V))) continue; if (rand() % c++ == 0) r = x->nei[i]; } return r; }

void link_cells(cell a, cell b) { int i; for (i = N; i <= W; i++) { if (a->nei[i] != b) continue; a->flags |= 1 << i; break; } for (i = N; i <= W; i++) { if (b->nei[i] != a) continue; b->flags |= 1 << i; break; } }

void walk(cell head) { cell tail = head, p, n;

while (head) { for (p = head; p; p = n) { p->flags |= 1 << V; n = rand_neighbor(p); if (!n) break; tail->next = n; n->prev = tail;

tail = n; link_cells(p, n); } while (head && !rand_neighbor(head)) head = head->next; } }

void make_maze(void) { int i, j; int n = (sx * sy + sx * sz + sy * sz) * 2; cell t, *c; cell_t * cells;

w = 2 * sx + 2 * sy, h = sy * 2 + sz; cells = calloc(sizeof(cell_t), n); c = calloc(sizeof(cell), w * h);

for (i = 0; i < sy; i++) for (j = 0; j < sx; j++) C(i, j) = cells + --n; for (; i < sy + sz; i++) for (j = 0; j < w; j++) C(i, j) = cells + --n; for (; i < h; i++) for (j = sx + sy; j < w - sy; j++) C(i, j) = cells + --n;

for (i = 0; i < h; i++) { for (j = 0; j < w; j++) { t = C(i, j); if (!t) continue; if (i) t->nei[N] = C(i - 1, j); if (i < h - 1) t->nei[S] = C(i + 1, j); if (j) t->nei[W] = C(i, j - 1); if (j < w - 1) t->nei[E] = C(i, j + 1); } }

for (j = 0; j < sx; j++) { C(0, j)->nei[N] = C(sy, w - sy - j - 1); C(sy, w - sy - j - 1)->nei[N] = C(0, j);

C(h - sy - 1, j)->nei[S] = C(h - 1, w - sy - j - 1); C(h - 1, w - sy - j - 1)->nei[S] = C(h - sy - 1, j); }

for (i = sy; i < sy + sz; i++) { C(i, 0)->nei[W] = C(i, w - 1); C(i, w - 1)->nei[E] = C(i, 0); }

for (i = 0; i < sy; i++) { C(i, 0)->nei[W] = C(sy, w - sy + i); C(sy, w - sy + i)->nei[N] = C(i, 0);

C(i, sx - 1)->nei[E] = C(sy, sx + sy - i - 1); C(sy, sx + sy - i - 1)->nei[N] = C(i, sx - 1);

C(h - sy - 1, sx + i)->nei[S] = C(h - 1 - i, sx + sy); C(h - 1 - i, sx + sy)->nei[W] = C(h - sy - 1, sx + i);

C(sy + sz + i, w - sy - 1)->nei[E] = C(sy + sz - 1, w - sy + i); C(sy + sz - 1, w - sy + i)->nei[S] = C(sy + sz + i, w - sy - 1); }

walk(C(0, 0)); draw_maze(c); }

int main(int c, char **v) { if (c < 2 || (sx = atoi(v[1])) <= 0) sx = 10; if (c < 3 || (sy = atoi(v[2])) <= 0) sy = sx; if (c < 4 || (sz = atoi(v[3])) <= 0) sz = sy;

make_maze();

return 0; }</lang>

Common Lisp

The remove-wall function has been written so as to be as close as possible to the specification. The walls are made from a single unicode character, specified by the block keyword, e. g. (maze 20 6 :block #\X). The BOX_DRAWINGS_LIGHT_DIAGONAL_CROSS character is used by default. <lang lisp>(defun shuffle (list)  ;; Z not uniform 

 (sort list '> :key (lambda(x) (random 1.0))))

(defun neighbors (x y maze) 

 (remove-if-not
  (lambda (x-y) (and (< -1 (first x-y) (array-dimension maze 0))
                (< -1 (second x-y) (array-dimension maze 1))))
  `((,x ,(+ y 2)) (,(- x 2) ,y) (,x ,(- y 2)) (,(+ x 2) ,y))))

(defun remove-wall (maze x y &optional visited) 

 (labels ((walk (maze x y)
            (push (list x y) visited)
            (loop for (u v) in (shuffle (neighbors x y maze))
               unless (member (list u v) visited :test 'equal)
               do (setf (aref maze u v) #\space
                        (aref maze (/ (+ x u) 2) (/ (+ y v) 2)) #\space)
                  (walk maze u v))))
   (setf (aref maze x y) #\space)
   (walk maze x y)))

(defun draw-maze (width height &key (block #\BOX_DRAWINGS_LIGHT_DIAGONAL_CROSS)) 

 (let ((maze (make-array (list (1+ (* 2 height)) (1+ (* 2 width)))
                         :element-type 'character :initial-element block)))
   (remove-wall maze (1+ (* 2 (random height))) (1+ (* 2 (random width))))
   (loop for i below (array-dimension maze 0)
         do (fresh-line)
            (loop for j below (array-dimension maze 1)
                  do (princ (aref maze i j))))))

(draw-maze 20 6)</lang>

Output:
╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳
╳         ╳       ╳     ╳         ╳     ╳
╳ ╳╳╳╳╳╳╳ ╳ ╳╳╳ ╳ ╳╳╳ ╳ ╳╳╳╳╳ ╳╳╳ ╳ ╳╳╳╳╳
╳ ╳     ╳   ╳ ╳ ╳     ╳       ╳ ╳ ╳     ╳
╳ ╳╳╳ ╳ ╳╳╳╳╳ ╳ ╳╳╳ ╳╳╳╳╳╳╳╳╳╳╳ ╳ ╳ ╳╳╳ ╳
╳   ╳ ╳ ╳     ╳ ╳   ╳     ╳     ╳ ╳   ╳ ╳
╳╳╳ ╳ ╳ ╳╳╳ ╳ ╳ ╳╳╳ ╳╳╳╳╳ ╳ ╳╳╳ ╳ ╳╳╳ ╳ ╳
╳ ╳ ╳ ╳     ╳ ╳   ╳   ╳   ╳   ╳ ╳   ╳ ╳ ╳
╳ ╳ ╳ ╳╳╳╳╳╳╳ ╳╳╳ ╳╳╳ ╳ ╳╳╳╳╳ ╳╳╳╳╳ ╳╳╳ ╳
╳   ╳   ╳ ╳   ╳ ╳   ╳ ╳     ╳     ╳   ╳ ╳
╳ ╳╳╳╳╳ ╳ ╳ ╳╳╳ ╳╳╳ ╳╳╳╳╳╳╳ ╳ ╳ ╳╳╳╳╳ ╳ ╳
╳       ╳         ╳         ╳ ╳         ╳
╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳

Another solution using unicode line drawing chars. Assumes they are single width on console. Code pretty horribly unreadable. <lang lisp>(setf *random-state* (make-random-state t))

(defun 2d-array (w h) 

 (make-array (list h w) :initial-element 0))

(defmacro or-and (v a b c) 

 `(if (or ,a (and ,b (= 1 ,c))) 0 ,v))

(defun make-maze (w h) 

 (let ((vis (2d-array w h))

(ver (2d-array w h)) (hor (2d-array w h))) 

   (labels
     ((walk (y x)

(setf (aref vis y x) 1) (loop (let (x2 y2) (loop for (dx dy) in '((-1 0) (1 0) (0 -1) (0 1)) with cnt = 0 do (let ((xx (+ x dx)) (yy (+ y dy))) (if (and (array-in-bounds-p vis yy xx) (zerop (aref vis yy xx)) (zerop (random (incf cnt)))) (setf x2 xx y2 yy)))) (if (not x2) (return-from walk)) (if (= x x2) (setf (aref hor (min y y2) x) 1) (setf (aref ver y (min x x2)) 1)) (walk y2 x2)))) 

     (show ()

(let ((g " │││─┘┐┤─└┌├─┴┬┼")) (loop for i from 0 to h do (loop for j from 0 to w do (format t "~c~a" (char g (+ (or-and 1 (= i 0) (> j 0) (aref ver (1- i) (1- j))) (or-and 2 (= i h) (> j 0) (aref ver i (1- j))) (or-and 4 (= j 0) (> i 0) (aref hor (1- i) (1- j))) (or-and 8 (= j w) (> i 0) (aref hor (1- i) j )))) (if (and (< j w) (or (= i 0) (= 0 (aref hor (1- i) j)))) "───" " "))) (terpri) (when (< i h) (loop for j from 0 below w do (format t (if (or (= j 0) (= 0 (aref ver i (1- j)))) "│ " " "))) (format t "│~%")))))) 

     (walk (random h) (random w))
     (show))))

(make-maze 20 20)</lang>

Output:
┼───┴───┼───┴───┴───┼───┴───┴───┼
│       │           │           │
┼────   │   │   │   │   ┌───┐   ├
│       │   │   │   │   │   │   │
┤   ┌───┘   │   │   │   │   │   ├
│   │       │   │       │   │   │
┤   │   ┌───┘   ├───────┤   │   ├
│   │   │       │       │       │
┤   │   │   ────┤   │   │   ────┼
│       │       │   │   │       │
┤   ────┼───┐   │   │   └───┐   ├
│       │   │       │       │   │
┼───┐   │   └───────┼───┐   └───┼
│   │               │   │       │
┤   └────────────   │   └───┐   ├
│                           │   │
┼───┬───┬───┬───┬───┬───┬───┼───┼

D

Translation of: Python

<lang d>import std.stdio, std.algorithm, std.range, std.random, 

      std.string, std.typecons;

void main() { 

   enum int w = 16, h = 8;
   alias std.array.replicate R;
   auto vis = new bool[][](h, w),
        hor = iota(h + 1).map!(_=> R(["+--"], w))().array(),
        ver = iota(h).map!(_=> R(["|  "], w) ~ "|")().array();

   void walk(in int x, in int y) /*nothrow*/ {
       vis[y][x] = true;
       alias Tuple!(uint,"x", uint,"y") P; // will wrap-around
       auto d = [P(x-1, y), P(x, y+1), P(x+1, y), P(x, y-1)];
       d.randomShuffle();
       foreach (p; d) {
           if (p.x >= w || p.y >= h || vis[p.y][p.x]) continue;
           if (p.x == x) hor[max(y, p.y)][x] = "+  ";
           if (p.y == y) ver[y][max(x, p.x)] = "   ";
           walk(p.x, p.y);
       }
   }
   walk(uniform(0, w), uniform(0, h));
   foreach (a, b; hor.zip(ver ~ []))
       writeln(join(a ~ ["+\n"] ~ b));

}</lang>

Output:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|        |           |           |              |
+  +--+  +  +--+--+  +  +  +--+  +--+  +  +--+--+
|  |  |  |  |     |     |  |        |  |        |
+  +  +  +  +--+  +--+--+  +--+--+  +--+  +--+  +
|  |     |              |        |     |     |  |
+  +--+  +--+--+  +--+--+  +--+  +--+  +--+--+  +
|     |     |     |     |  |     |           |  |
+--+  +--+  +--+--+  +  +--+  +  +--+--+--+  +  +
|     |     |     |  |     |  |  |     |  |     |
+  +--+  +--+  +  +  +--+  +  +--+--+  +  +--+  +
|     |        |     |        |        |  |     |
+--+  +--+--+--+--+--+--+--+--+  +--+--+  +  +--+
|     |                 |     |  |        |  |  |
+  +--+  +--+--+--+--+  +  +  +  +  +--+--+  +  +
|                    |     |     |              |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

Alternative version

See Maze_solving#D

F#

Using mutable state in the form of 2D arrays: <lang fsharp>let rnd : int -> int = 

 let gen = new System.Random()
 fun max -> gen.Next(max)

// randomly choose an element of a list let choose (xs:_ list) = xs.[rnd xs.Length]

type Maze(width, height) = 

 // (x,y) -> have we been here before?
 let visited = Array2D.create width height false
 // (x,y) -> is there a wall between (x,y) and (x+1,y)?
 let horizWalls = Array2D.create width height true
 // (x,y) -> is there a wall between (x,y) and (x,y+1)?
 let vertWalls = Array2D.create width height  true
 
 let isLegalPoint (x,y) =
   x >= 0 && x < width && y >= 0 && y < height
 
 let neighbours (x,y) = 
   [(x-1,y);(x+1,y);(x,y-1);(x,y+1)] |> List.filter isLegalPoint
   
 let removeWallBetween (x1,y1) (x2,y2) =
   if x1 <> x2 then
     horizWalls.[min x1 x2, y1] <- false
   else
     vertWalls.[x1, min y1 y2] <- false

 let rec visit (x,y as p) = 
   let rec loop ns =
     let (nx,ny) as n = choose ns
     if not visited.[nx,ny] then
       removeWallBetween p n
       visit n
     match List.filter ((<>) n) ns with
     | [] -> ()
     | others -> loop others

   visited.[x,y] <- true
   loop (neighbours p)

 do visit (rnd width, rnd height)

 member x.Print() =
   ("+" + (String.replicate width "-+")) ::
   [for y in 0..(height-1) do
      yield "\n|"
      for x in 0..(width-1) do 
        yield if horizWalls.[x,y] then " |" else "  "
      yield "\n+"
      for x in 0..(width-1) do 
        yield if vertWalls.[x,y] then "-+" else " +"
   ]
   |> String.concat ""
   |> printfn "%s"

let m = new Maze(10,10) m.Print()</lang>

Output example:
+-+-+-+-+-+-+-+-+-+-+
|         |     |   |
+ +-+-+-+-+ +-+ + + +
|       |   |   | | |
+ +-+-+ + +-+-+ +-+ +
|     | |     |     |
+-+ +-+ +-+-+ +-+-+ +
|   |   |     |     |
+ +-+ +-+ +-+-+-+ +-+
| | |   |       |   |
+ + +-+ +-+ +-+ +-+ +
| |   | | |   |   | |
+ + +-+ + +-+-+-+ + +
|   |   |         | |
+-+ + +-+-+-+-+-+-+ +
|   |     |       | |
+ +-+-+ +-+ +-+-+ + +
| |   |   |     |   |
+ +-+ +-+ +-+-+ +-+-+
|       |           |
+-+-+-+-+-+-+-+-+-+-+

Go

<lang go>package main

import ( 

   "bytes"
   "fmt"
   "math/rand"
   "time"

)

type maze struct { 

   c  []byte   // cell contents
   h  []byte   // horizontal walls above cells
   v  []byte   // vertical walls to the left of cells
   c2 [][]byte // cells by row
   h2 [][]byte // horizontal walls by row (ignore first row)
   v2 [][]byte // vertical walls by row (ignore first of each column)

}

func newMaze(rows, cols int) *maze { 

   c := make([]byte, rows*cols)              // all cells
   h := bytes.Repeat([]byte{'-'}, rows*cols) // all horizontal walls
   v := bytes.Repeat([]byte{'|'}, rows*cols) // all vertical walls
   c2 := make([][]byte, rows)                // cells by row
   h2 := make([][]byte, rows)                // horizontal walls by row
   v2 := make([][]byte, rows)                // vertical walls by row
   for i := range h2 {
       c2[i] = c[i*cols : (i+1)*cols]
       h2[i] = h[i*cols : (i+1)*cols]
       v2[i] = v[i*cols : (i+1)*cols]
   }
   return &maze{c, h, v, c2, h2, v2}

}

func (m *maze) String() string { 

   hWall := []byte("+---")
   hOpen := []byte("+   ")
   vWall := []byte("|   ")
   vOpen := []byte("    ")
   rightCorner := []byte("+\n") 
   rightWall := []byte("|\n")
   var b []byte
   // for all rows 
   for r, hw := range m.h2 {
       // draw h walls
       for _, h := range hw { 
           if h == '-' || r == 0 {
               b = append(b, hWall...)
           } else {
               b = append(b, hOpen...)
           }
       }
       b = append(b, rightCorner...)
       // draw v walls
       for c, vw := range m.v2[r] {
           if vw == '|' || c == 0 {
               b = append(b, vWall...)
           } else {
               b = append(b, vOpen...)
           }
           // draw cell contents
           if m.c2[r][c] != 0 {
               b[len(b)-2] = m.c2[r][c]
           }
       }
       b = append(b, rightWall...)
   }
   // draw bottom edge of maze
   for _ = range m.h2[0] {
       b = append(b, hWall...)
   }
   b = append(b, rightCorner...)
   return string(b)

}

func (m *maze) gen() { 

   m.g2(rand.Intn(len(m.c2)), rand.Intn(len(m.c2[0])))

}

const ( 

   up = iota
   dn
   rt
   lf

)

func (m *maze) g2(r, c int) { 

   m.c2[r][c] = ' '
   for _, dir := range rand.Perm(4) {
       switch dir {
       case up:
           if r > 0 && m.c2[r-1][c] == 0 {
               m.h2[r][c] = 0
               m.g2(r-1, c)
           }
       case lf:
           if c > 0 && m.c2[r][c-1] == 0 {
               m.v2[r][c] = 0
               m.g2(r, c-1)
           }
       case dn:
           if r < len(m.c2)-1 && m.c2[r+1][c] == 0 {
               m.h2[r+1][c] = 0
               m.g2(r+1, c)
           }
       case rt:
           if c < len(m.c2[0])-1 && m.c2[r][c+1] == 0 {
               m.v2[r][c+1] = 0
               m.g2(r, c+1)
           }
       }
   }

}

func main() { 

   rand.Seed(time.Now().UnixNano())
   m := newMaze(4, 6)
   m.gen()
   fmt.Print(m)

}</lang>

Output:
+---+---+---+---+---+---+
|   |           |       |
+   +   +   +---+   +---+
|   |   |           |   |
+   +   +---+---+---+   +
|   |   |               |
+   +   +   +---+---+   +
|           |           |
+---+---+---+---+---+---+

Haskell

<lang haskell>import Control.Monad import Control.Monad.ST import Data.Array import Data.Array.ST import Data.STRef import System.Random

rand :: Random a => (a, a) -> STRef s StdGen -> ST s a rand range gen = do 

   (a, g) <- liftM (randomR range) $ readSTRef gen
   gen `writeSTRef` g
   return a

data Maze = Maze {rightWalls, belowWalls :: Array (Int, Int) Bool}

maze :: Int -> Int -> StdGen -> ST s Maze maze width height gen = do 

   visited <- mazeArray False
   rWalls <- mazeArray True
   bWalls <- mazeArray True
   gen <- newSTRef gen
   liftM2 (,) (rand (0, maxX) gen) (rand (0, maxY) gen) >>=
       visit gen visited rWalls bWalls
   liftM2 Maze (freeze rWalls) (freeze bWalls)
 where visit gen visited rWalls bWalls here = do
           writeArray visited here True
           let ns = neighbors here
           i <- rand (0, length ns - 1) gen
           forM_ (ns !! i : take i ns ++ drop (i + 1) ns) $ \there -> do
               seen <- readArray visited there
               unless seen $ do
                   removeWall here there
                   visit gen visited rWalls bWalls there
         where removeWall (x1, y1) (x2, y2) = writeArray 
                   (if x1 == x2 then bWalls else rWalls)
                   (min x1 x2, min y1 y2)
                   False

       neighbors (x, y) = 
           (if x == 0    then [] else [(x - 1, y    )]) ++
           (if x == maxX then [] else [(x + 1, y    )]) ++
           (if y == 0    then [] else [(x,     y - 1)]) ++
           (if y == maxY then [] else [(x,     y + 1)])

       maxX = width - 1
       maxY = height - 1

       mazeArray = newArray ((0, 0), (maxX, maxY))
           :: Bool -> ST s (STArray s (Int, Int) Bool)

printMaze :: Maze -> IO () printMaze (Maze rWalls bWalls) = do 

   putStrLn $ '+' : (concat $ replicate (maxX + 1) "---+")
   forM_ [0 .. maxY] $ \y -> do
       putStr "|"
       forM_ [0 .. maxX] $ \x -> do
           putStr "   "
           putStr $ if rWalls ! (x, y) then "|" else " "
       putStrLn ""
       forM_ [0 .. maxX] $ \x -> do
           putStr "+"
           putStr $ if bWalls ! (x, y) then "---" else "   "
       putStrLn "+"
 where maxX = fst (snd $ bounds rWalls)
       maxY = snd (snd $ bounds rWalls)

main = getStdGen >>= stToIO . maze 11 8 >>= printMaze</lang>

Sample output:
 +---+---+---+---+---+---+---+---+---+---+---+
 |               |                           |
 +   +---+---+---+   +---+---+---+---+---+   +
 |               |           |   |       |   |
 +   +---+---+   +---+---+   +   +   +   +   +
 |   |   |       |           |       |   |   |
 +   +   +   +---+---+---+---+   +---+   +   +
 |       |   |                   |   |       |
 +---+---+   +   +---+---+---+---+   +---+---+
 |       |   |   |                       |   |
 +   +   +   +   +---+---+---+   +---+   +   +
 |   |       |   |               |       |   |
 +   +---+---+   +   +---+---+---+   +---+   +
 |               |       |           |       |
 +   +---+---+---+---+   +   +---+---+   +   +
 |                       |               |   |
 +---+---+---+---+---+---+---+---+---+---+---+

Icon and Unicon

20x30 with two random openings
20x30 with opposite openings

<lang Icon>link printf

procedure main(A) # generate rows x col maze 

  /mh := \A[1] | 12                            # or take defaults 12 x 16
  /mw := \A[2] | 16
  mz := DisplayMaze(GenerateMaze(mh,mw))
  WriteImage(mz.filename)                      # save file
  WAttrib(mz.window,"canvas=normal")           # show maze in hidden window
  until Event() == &lpress                     # wait for left mouse press
  close(mz.window)

end

$define FINISH 64 # exit $define START 32 # entrance $define PATH 128 $define SEEN 16 # bread crumbs for generator $define NORTH 8 # sides ... $define EAST 4 $define SOUTH 2 $define WEST 1 $define EMPTY 0 # like new

procedure GenerateMaze(r,c) #: Depth First Maze Generation static maze,h,w,rd 

  if /maze then {                              # BEGING - No maze yet
     /h := integer(1 < r) | runerr(r,205)      # valid size 2x2 or better
     /w := integer(1 < c) | runerr(r,205)
     every !(maze := list(h)) := list(w,EMPTY) # shinny new empty maze
     start  := [?h,?w,?4-1,START]              # random [r,c] start & finish                 
     finish := [?h,?w,(start[3]+2)%4,FINISH]   # w/ opposite side exponent
     every x := start | finish do {
        case x[3] := 2 ^ x[3] of {             # get side from exponent and 
           NORTH : x[1] := 1                   # project r,c to selected edge
           EAST  : x[2] := w
           SOUTH : x[1] := h         
           WEST  : x[2] := 1
           }   
        maze[x[1],x[2]] +:= x[3] + x[4]        # transcribe s/f to maze
        }
     rd := [NORTH, EAST, SOUTH, WEST]          # initial list of directions     
     GenerateMaze(start[1],start[2])           # recurse through maze     
     return 1(.maze,maze := &null)             # return maze, reset for next
  }
  else {         # ----------------------- recursed to clear insize of maze
     if iand(maze[r,c],SEEN) = 0 then {        # in bounds and not SEEN yet?
        maze[r,c] +:= SEEN                     # Mark current cell as visited   
        every !rd :=: ?rd                      # randomize list of directions
        every d := !rd do
           case d of {                         # try all, succeed & clear wall
              NORTH :  maze[r,c] +:= ( GenerateMaze(r-1,c), NORTH)
              EAST  :  maze[r,c] +:= ( GenerateMaze(r,c+1),  EAST)
              SOUTH :  maze[r,c] +:= ( GenerateMaze(r+1,c), SOUTH)
              WEST  :  maze[r,c] +:= ( GenerateMaze(r,c-1),  WEST)   
              }
        return                                 # signal success to caller
        }
  }

end

$define CELL 20 # cell size in pixels $define BORDER 30 # border size in pixels

record mazeinfo(window,maze,filename) # keepers

procedure DisplayMaze(maze) #: show it off if CELL < 8 then runerr(205,CELL) # too small

wh := (ch := (mh := *maze ) * CELL) + 2 * BORDER # win, cell, maze height ww := (cw := (mw := *maze[1]) * CELL) + 2 * BORDER # win, cell, maze width

wparms := [ sprintf("Maze %dx%d",*maze,*maze[1]), # window parameters 

           "g","bg=white","canvas=hidden",      
           sprintf("size=%d,%d",ww,wh),
           sprintf("dx=%d",BORDER),
           sprintf("dy=%d",BORDER)]

&window := open!wparms | stop("Unable to open Window")

Fg("black") # Draw full grid every DrawLine(x := 0 to cw by CELL,0,x,ch+1) # . verticals every DrawLine(0,y := 0 to ch by CELL,cw+1,y) # . horizontals

Fg("white") # Set to erase lines every y := CELL*((r := 1 to mh)-1) & x := CELL*((c := 1 to mw)-1) do { 

  WAttrib("dx="||x+BORDER,"dy="||y+BORDER)         # position @ cell r,c
  if iand(maze[r,c],NORTH) > 0 then DrawLine(2,0,CELL-1,0)            
  if iand(maze[r,c],EAST)  > 0 then DrawLine(CELL,2,CELL,CELL-1)        
  if iand(maze[r,c],SOUTH) > 0 then DrawLine(2,CELL,CELL-1,CELL)                
  if iand(maze[r,c],WEST)  > 0 then DrawLine(0,2,0,CELL-1)            
  }

return mazeinfo(&window,maze,sprintf("maze-%dx%d-%d.gif",r,c,&now)) end</lang> Note: The underlying maze structure (matrix) is uni-directional from the start

Library: Icon Programming Library

printf.icn provides formatting

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.

Translation of: PicoLisp

But 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>

Java

Works with: Java version 1.5+

<lang java5>package org.rosettacode;

import java.util.Random; import java.util.Collections; import java.util.Arrays;

/* 

* recursive backtracking algorithm
* shamelessly borrowed from the ruby at
* http://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking
*/

public class MazeGenerator { private final int x; private final int y; private final int[][] maze; private static final Random rand = new Random();

public MazeGenerator(int x, int y) { this.x = x; this.y = y; maze = new int[this.x][this.y]; generateMaze(0, 0); }

public void display() { for (int i = 0; i < y; i++) { // draw the north edge for (int j = 0; j < x; j++) { System.out.print((maze[j][i] & 1) == 0 ? "+---" : "+ "); } System.out.println("+"); // draw the west edge for (int j = 0; j < x; j++) { System.out.print((maze[j][i] & 8) == 0 ? "| " : " "); } System.out.println("|"); } // draw the bottom line for (int j = 0; j < x; j++) { System.out.print("+---"); } System.out.println("+"); }

private void generateMaze(int cx, int cy) { DIR[] dirs = DIR.values(); Collections.shuffle(Arrays.asList(dirs)); for (DIR dir : dirs) { int nx = cx + dir.dx; int ny = cy + dir.dy; if (between(nx, x) && between(ny, y) && (maze[nx][ny] == 0)) { maze[cx][cy] |= dir.bit; maze[nx][ny] |= dir.opposite.bit; generateMaze(nx, ny); } } }

private static boolean between(int v, int upper) { return (v >= 0) && (v < upper); }

private enum DIR { N(1, 0, -1), S(2, 0, 1), E(4, 1, 0), W(8, -1, 0); private final int bit; private final int dx; private final int dy; private DIR opposite;

// use the static initializer to resolve forward references static { N.opposite = S; S.opposite = N; E.opposite = W; W.opposite = E; }

private DIR(int bit, int dx, int dy) { this.bit = bit; this.dx = dx; this.dy = dy; } };

public static void main(String[] args) { int x = args.length >= 1 ? (Integer.parseInt(args[0])) : 8; int y = args.length == 2 ? (Integer.parseInt(args[1])) : 8; MazeGenerator maze = new MazeGenerator(x, y); maze.display(); }

}</lang>

Output:
+---+---+---+---+---+---+---+---+---+---+
|   |                           |       |
+   +---+---+   +---+---+   +   +   +---+
|           |   |   |       |   |       |
+---+---+   +   +   +   +---+   +---+   +
|           |       |   |   |       |   |
+   +---+---+   +---+   +   +---+   +   +
|   |       |   |       |           |   |
+   +   +   +---+   +---+---+---+   +   +
|   |   |       |               |       |
+   +   +---+   +   +---+---+   +---+---+
|   |       |   |   |           |       |
+   +---+   +   +---+   +---+---+   +   +
|       |   |       |               |   |
+---+   +   +---+   +   +---+---+---+   +
|   |   |       |   |       |           |
+   +   +---+   +   +---+---+   +---+   +
|   |       |   |           |   |   |   |
+   +---+   +   +---+---+   +   +   +   +
|               |               |       |
+---+---+---+---+---+---+---+---+---+---+

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<y+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 output:



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


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.



HTML Table


Using HTML, CSS and table cells for maze.
<lang html><html><head><title>Maze maker</title>
<style type="text/css">
table { border-collapse: collapse }
td { width: 1em; height: 1em; border: 1px solid }
td.s { border-bottom: none }
td.n { border-top: none }
td.w { border-left: none }
td.e { border-right: none }
td.v { background: skyblue}
</style>
<script type="application/javascript">
Node.prototype.add = function(tag, cnt, txt) {
	for (var i = 0; i < cnt; i++)
		this.appendChild(ce(tag, txt));
}
Node.prototype.ins = function(tag) {
	this.insertBefore(ce(tag), this.firstChild)
}
Node.prototype.kid = function(i) { return this.childNodes[i] }
Node.prototype.cls = function(t) { this.className += ' ' + t }

NodeList.prototype.map = function(g) {
	for (var i = 0; i < this.length; i++) g(this[i]);
}

function ce(tag, txt) {
	var x = document.createElement(tag);
	if (txt !== undefined) x.innerHTML = txt;
	return x
}

function gid(e) { return document.getElementById(e) }
function irand(x) { return Math.floor(Math.random() * x) }

function make_maze() {
	var w = parseInt(gid('rows').value || 8, 10);
	var h = parseInt(gid('cols').value || 8, 10);
	var tbl = gid('maze');
	tbl.innerHTML = ;
	tbl.add('tr', h);
	tbl.childNodes.map(function(x) {
			x.add('th', 1);
			x.add('td', w, '*');
			x.add('th', 1)});
	tbl.ins('tr');
	tbl.add('tr', 1);
	tbl.firstChild.add('th', w + 2);
	tbl.lastChild.add('th', w + 2);
	for (var i = 1; i <= h; i++) {
		for (var j = 1; j <= w; j++) {
			tbl.kid(i).kid(j).neighbors = [
				tbl.kid(i + 1).kid(j),
				tbl.kid(i).kid(j + 1),
				tbl.kid(i).kid(j - 1),
				tbl.kid(i - 1).kid(j)
			];
		}
	}
	walk(tbl.kid(irand(h) + 1).kid(irand(w) + 1));
	gid('solve').style.display='inline';
}

function shuffle(x) {
	for (var i = 3; i > 0; i--) {
		j = irand(i + 1);
		if (j == i) continue;
		var t = x[j]; x[j] = x[i]; x[i] = t;
	}
	return x;
}

var dirs = ['s', 'e', 'w', 'n'];
function walk(c) {
	c.innerHTML = ' ';
	var idx = shuffle([0, 1, 2, 3]);
	for (var j = 0; j < 4; j++) {
		var i = idx[j];
		var x = c.neighbors[i];
		if (x.textContent != '*') continue;
		c.cls(dirs[i]), x.cls(dirs[3 - i]);
		walk(x);
	}
}

function solve(c, t) {
	if (c === undefined) {
		c = gid('maze').kid(1).kid(1);
		c.cls('v');
	}
	if (t === undefined)
		t = gid('maze')	.lastChild.previousSibling
				.lastChild.previousSibling;

	if (c === t) return 1;
	c.vis = 1;
	for (var i = 0; i < 4; i++) {
		var x = c.neighbors[i];
		if (x.tagName.toLowerCase() == 'th') continue;
		if (x.vis || !c.className.match(dirs[i]) || !solve(x, t))
			continue;

		x.cls('v');
		return 1;
	}
	c.vis = null;
	return 0;
}

</script></head>
<body><form><fieldset>
<label>rows </label><input id='rows' size="3"/>
<label>colums </label><input id='cols' size="3"/>
<a href="javascript:make_maze()">Generate</a>
<a id='solve' style='display:none' href='javascript:solve(); void(0)'>Solve</a>


</fieldset></form>
</body></html></lang>


MATLAB
<lang Matlab>function M = makeMaze(n)

   showProgress = false;

   colormap([1,1,1;1,1,1;0,0,0]);
   set(gcf,'color','w');

   NoWALL      = 0;
   WALL        = 2;
   NotVISITED  = -1;
   VISITED     = -2;

   m = 2*n+3;
   M = NotVISITED(ones(m));
   offsets = [-1, m, 1, -m];

   M([1 2:2:end end],:) = WALL;
   M(:,[1 2:2:end end]) = WALL;

   currentCell = sub2ind(size(M),3,3);
   M(currentCell) = VISITED;
   
   S = currentCell;
   
   while (~isempty(S))
       moves = currentCell + 2*offsets;
       unvistedNeigbors = find(M(moves)==NotVISITED);

       if (~isempty(unvistedNeigbors))
           next = unvistedNeigbors(randi(length(unvistedNeigbors),1));
           M(currentCell + offsets(next)) = NoWALL;

           newCell = currentCell + 2*offsets(next);
           if (any(M(newCell+2*offsets)==NotVISITED))
               S = [S newCell];
           end
           
           currentCell = newCell;
           M(currentCell) = VISITED;
       else
           currentCell = S(1);
           S = S(2:end);
       end

       if (showProgress)
           image(M-VISITED);
           axis equal off;
           drawnow;
           pause(.01);
       end
   end

   image(M-VISITED);
   axis equal off;</lang>

Perl
<lang perl>use List::Util 'max';

my ($w, $h) = @ARGV;
$w ||= 26;
$h ||= 127;
my $avail = $w * $h;

  1. cell is padded by sentinel col and row, so I don't check array bounds
my @cell = (map([(('1') x $w), 0], 1 .. $h), [() x ($w + 1)]);
my @ver = map([("|  ") x $w], 1 .. $h);
my @hor = map([("+--") x $w], 0 .. $h);

sub walk {
	my ($x, $y) = @_;
	$cell[$y][$x] = ;
	$avail-- or return;	# no more bottles, er, cells

	my @d = ([-1, 0], [0, 1], [1, 0], [0, -1]);
	while (@d) {
		my $i = splice @d, int(rand @d), 1;
		my ($x1, $y1) = ($x + $i->[0], $y + $i->[1]);

		$cell[$y1][$x1] or next;

		if ($x == $x1) { $hor[ max($y1, $y) ][$x] = '+  ' }
		if ($y == $y1) { $ver[$y][ max($x1, $x) ] = '   ' }
		walk($x1, $y1);
	}
}

walk(int rand $w, int rand $h);	# generate

for (0 .. $h) {			# display
	print @{$hor[$_]}, "+\n";
	print @{$ver[$_]}, "|\n" if $_ < $h;
}</lang>
Run as maze.pl [width] [height] or use default dimensions.



Sample 4 x 1 output:
+--+--+--+--+
|           |
+--+--+--+--+
Perl 6
Works with: Rakudo version 2011.01
Supply a width and height and optionally the x,y grid coords for the starting cell. If no starting cell is supplied, a random one will be selected automatically. 0,0 is the top left corner.
<lang perl6>display( gen_maze( 11, 8 ) );

sub gen_maze ( $x_size,

              $y_size,
              $start_x = (^$x_size).pick,
              $start_y = (^$y_size).pick )

{

   my %walls;
   my @maze;
   for ^$y_size -> $x {
       @maze[$x]        = [ 1    xx $x_size];
       %walls{'y'}[$x]  = ['|'   xx $x_size];
       %walls{'x'}[$x]  = ['---' xx $x_size];
   }
   my @stack;
   my @current = $start_y, $start_x;
   loop {
        if my @next = get_unvisited_neighbors( @maze, @current ) {
            @stack.push: [@current];
            move( @maze, @next, @current, %walls );
            @current := @next;
        }
        else {
            last unless @stack;
            @current := @stack.pop;
        }
   }
   return %walls;

}

sub get_unvisited_neighbors(@maze, @current) {

   my ($x, $y) = @current;
   my @neighbors;
   @neighbors.push([ $x-1, $y ]) if $x > 0        and @maze[$x-1][$y];
   @neighbors.push([ $x+1, $y ]) if $x < @maze    and @maze[$x+1][$y];
   @neighbors.push([ $x, $y-1 ]) if $y > 0        and @maze[$x][$y-1];
   @neighbors.push([ $x, $y+1 ]) if $y < @maze[0] and @maze[$x][$y+1];
   return |@neighbors.roll(1) if @neighbors;

}

sub move ($maze, $next, $current, $walls) {

   $maze[$next[0]][$next[1]] = 0;
   given () {
       when $next[0] < $current[0] { $walls{'x'}[$next[0]][$current[1]]    = '   '}
       when $next[0] > $current[0] { $walls{'x'}[$current[0]][$current[1]] = '   '}
       when $next[1] < $current[1] { $walls{'y'}[$current[0]][$current[1]] = ' ' }
       when $next[1] > $current[1] { $walls{'y'}[$current[0]][$next[1]]    = ' ' }
   } 

}

sub display ($walls) {

   say '+' ~ ('---' xx $walls{'y'}[0]).join('+') ~ '+';
   for ^$walls{'x'} -> $i {
       say ~$walls{'y'}[$i].join('   ') ~ '   |';
       say '+' ~ $walls{'x'}[$i].join('+') ~ '+';
   }

}</lang>



Output:
+---+---+---+---+---+---+---+---+---+---+---+
|           |       |       |               |
+---+---+   +   +   +   +---+---+---+---+   +
|           |   |       |                   |
+   +---+---+   +---+---+   +---+---+---+---+
|           |       |                       |
+   +---+   +---+   +---+   +---+---+---+   +
|       |       |       |   |               |
+   +---+---+   +---+   +---+   +   +---+---+
|   |       |       |       |   |   |       |
+---+   +   +   +---+---+   +   +---+   +   +
|       |       |       |   |           |   |
+   +---+---+---+   +   +   +   +---+---+   +
|   |               |       |   |           |
+   +   +---+---+---+---+---+---+   +---+   +
|                                   |       |
+---+---+---+---+---+---+---+---+---+---+---+

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
Prolog
Works with SWI-Prolog and XPCE.
<lang Prolog>:- dynamic cell/2.

maze(Lig,Col) :-
	retractall(cell(_,_)),

	new(D, window('Maze')),

	% creation of the grid
	forall(between(0,Lig, I),
	       (XL is  50, YL is I * 30 + 50,
		XR is Col * 30 + 50,
		new(L, line(XL, YL, XR, YL)),
		send(D, display, L))),

	forall(between(0,Col, I),
	       (XT is  50 + I * 30, YT is 50,
		YB is Lig * 30 + 50,
		new(L, line(XT, YT, XT, YB)),
		send(D, display, L))),

	SX is Col * 30 + 100,
	SY is Lig * 30 + 100,
	send(D, size, new(_, size(SX, SY))),

	% choosing a first cell
	L0 is random(Lig),
	C0 is random(Col),
	assert(cell(L0, C0)),
	\+search(D, Lig, Col, L0, C0),
	send(D, open).

search(D, Lig, Col, L, C) :-
	Dir is random(4),
	nextcell(Dir, Lig, Col, L, C, L1, C1),
	assert(cell(L1,C1)),
	assert(cur(L1,C1)),
	erase_line(D, L, C, L1, C1),
	search(D, Lig, Col, L1, C1).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
erase_line(D, L, C, L, C1) :-
	(   C < C1 -> C2 = C1; C2 = C),
	XT is C2  * 30 + 50,
	YT is L * 30 + 51, YR is (L+1) * 30 + 50,
	new(Line, line(XT, YT, XT, YR)),
	send(Line, colour, white),
	send(D, display, Line).

erase_line(D, L, C, L1, C) :-
	XT is  51 + C * 30, XR is 50 + (C + 1) * 30,
	(   L < L1 -> L2 is L1; L2 is L),
	YT is L2 * 30 + 50,
	new(Line, line(XT, YT, XR, YT)),
	send(Line, colour, white),
	send(D, display, Line).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
nextcell(Dir, Lig, Col, L, C, L1, C1) :-
	next(Dir, Lig, Col, L, C, L1, C1);
	(   Dir1 is (Dir+3) mod 4,
	    next(Dir1, Lig, Col, L, C, L1, C1));
	(   Dir2 is (Dir+1) mod 4,
	    next(Dir2, Lig, Col, L, C, L1, C1));
	(   Dir3 is (Dir+2) mod 4,
	    next(Dir3, Lig, Col, L, C, L1, C1)).

% 0 => northward
next(0, _Lig, _Col, L, C, L1, C) :-
	L > 0,
	L1 is L - 1,
	\+cell(L1, C).

% 1 => rightward
next(1, _Lig, Col, L, C, L, C1) :-
	C < Col - 1,
	C1 is C + 1,
	\+cell(L, C1).

% 2 => southward
next(2, Lig, _Col, L, C, L1, C) :-
	L < Lig - 1,
	L1 is L + 1,
	\+cell(L1, C).

% 3 => leftward
next(2, _Lig, _Col, L, C, L, C1) :-
	C > 0,
	C1 is C - 1,
	\+cell(L, C1).

</lang>



Output:


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

  1. 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

Next

Global Dim wallvalue(#numDirs)
For i = 0 To #numDirs: Read.i wallvalue(i): 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 shuffle, randrange

def make_maze(w = 16, h = 8):
	vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)]
	ver = [["|  "] * w + ['|'] for _ in range(h)] + [[]]
	hor = [["+--"] * w + ['+'] for _ in range(h + 1)]

	def walk(x, y):
		vis[y][x] = 1

		d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
		shuffle(d)
		for (xx, yy) in d:
			if vis[yy][xx]: continue
			if xx == x: hor[max(y, yy)][x] = "+  "
			if yy == y: ver[y][max(x, xx)] = "   "
			walk(xx, yy)

	walk(randrange(w), randrange(h))
	for (a, b) in zip(hor, ver):
		print(.join(a + ['\n'] + b))

make_maze()</lang>



Output:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|        |     |     |                    |     |
+  +  +  +  +  +  +  +  +--+--+--+--+--+  +--+  +
|  |  |     |  |  |     |     |        |        |
+--+  +--+--+  +  +--+--+--+  +  +--+  +--+--+  +
|     |     |  |  |  |        |     |  |        |
+  +--+  +--+  +  +  +  +  +  +--+  +  +  +--+--+
|  |           |  |     |  |     |  |     |     |
+  +--+  +--+--+  +  +--+  +--+--+  +--+--+  +  +
|     |  |        |     |           |        |  |
+--+  +  +  +--+--+--+  +--+--+--+--+--+--+--+  +
|     |  |  |        |        |           |     |
+  +--+--+  +--+--+  +--+--+  +--+  +--+  +  +  +
|        |        |        |        |     |  |  |
+  +--+  +--+--+--+  +  +--+--+--+--+  +--+  +  +
|     |              |                       |  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Ruby
<lang ruby>class Maze

 DIRECTIONS = [ [1, 0], [-1, 0], [0, 1], [0, -1] ]

 def initialize(width, height)
   @width = width
   @height = height
   @start_x = rand(width)
   @start_y = 0
   @end_x = rand(width)
   @end_y = height - 1

   # Which walls do exist? Default to "true". Both arrays are
   # one element bigger than they need to be. For example, the
   # @vertical_walls[y][x] is true if there is a wall between
   # (x,y) and (x+1,y). The additional entry makes printing
   # easier.
   @vertical_walls = Array.new(height) { Array.new(width, true) }
   @horizontal_walls = Array.new(height) { Array.new(width, true) }
   # Path for the solved maze.
   @path = Array.new(height) { Array.new(width) }

   # "Hack" to print the exit.
   @horizontal_walls[@end_y][@end_x] = false

   reset_visiting_state

   # Generate the maze.
   generate
 end

 # Print a nice ASCII maze.
 def print
   # Special handling: print the top line.
   line = "+"
   for x in (0...@width)
     line.concat(x == @start_x ? "   +" : "---+")
   end
   puts line

   # For each cell, print the right and bottom wall, if it exists.
   for y in (0...@height)
     line = "|"
     for x in (0...@width)

	line.concat(@path[y][x] ? " o " : "   ")
	line.concat(@vertical_walls[y][x] ? "|" : " ")

     end
     puts line

     line = "+"
     for x in (0...@width)

	line.concat(@horizontal_walls[y][x] ? "---+" : "   +")

     end
     puts line
   end
 end

 private

 # Reset the VISITED state of all cells.
 def reset_visiting_state
   @visited = Array.new(@height) { Array.new(@width) }
 end

 # Check whether the given coordinate is within the valid range.
 def coordinate_valid?(x, y)
   (x >= 0) && (y >= 0) && (x < @width) && (y < @height)
 end

 # Is the given coordinate valid and the cell not yet visited?
 def move_valid?(x, y)
   coordinate_valid?(x, y) && !@visited[y][x]
 end

 # Generate the maze.
 def generate
   generate_visit_cell @start_x, @start_y
   reset_visiting_state
 end

 # Depth-first maze generation.
 def generate_visit_cell(x, y)
   # Mark cell as visited.
   @visited[y][x] = true

   # Randomly get coordinates of surrounding cells (may be outside
   # of the maze range, will be sorted out later).
   coordinates = []
   for dir in DIRECTIONS.shuffle
     coordinates << [ x + dir[0], y + dir[1] ]
   end

   for new_x, new_y in coordinates
     next unless move_valid?(new_x, new_y)

     # Recurse if it was possible to connect the current
     # and the the cell (this recursion is the "depth-first"
     # part).
     connect_cells(x, y, new_x, new_y)
     generate_visit_cell new_x, new_y 
   end
 end

 # Try to connect two cells. Returns whether it was valid to do so.
 def connect_cells(x1, y1, x2, y2)
   if x1 == x2
     # Cells must be above each other, remove a horizontal
     # wall.
     @horizontal_walls[ [y1, y2].min ][x1] = false
   else
     # Cells must be next to each other, remove a vertical
     # wall.
     @vertical_walls[y1][ [x1, x2].min ] = false
   end
 end

end

  1. Demonstration:
maze = Maze.new 20, 10
maze.print</lang>



Output:
+---+---+---+---+---+---+---+---+---+---+---+---+---+   +---+---+---+---+---+---+
|                   |   |                       |   |       |           |       |
+   +---+   +---+   +   +   +---+---+---+   +   +   +---+   +   +---+   +---+   +
|   |   |   |           |   |       |       |   |       |       |   |   |       |
+   +   +   +---+---+   +   +   +---+   +---+   +---+   +---+---+   +   +   +---+
|   |   |           |   |       |       |       |           |   |       |       |
+   +   +---+---+   +---+---+   +   +---+---+   +   +---+   +   +   +---+---+   +
|   |           |           |   |           |       |       |   |               |
+   +---+---+   +---+---+   +   +---+---+   +---+---+   +---+   +---+---+---+   +
|               |       |   |       |   |   |                       |       |   |
+---+---+   +---+   +   +   +---+   +   +   +---+---+---+---+   +---+   +   +   +
|   |       |       |           |       |           |           |       |       |
+   +   +---+   +---+---+---+---+---+   +---+---+   +   +---+---+   +---+---+---+
|   |       |                       |   |       |   |       |   |   |           |
+   +---+   +---+---+---+---+---+   +   +---+   +   +---+   +   +   +---+---+   +
|       |           |   |           |           |       |       |   |           |
+   +   +---+---+   +   +   +---+---+---+---+   +---+   +---+---+   +   +---+---+
|   |       |       |   |       |               |       |           |           |
+   +   +---+   +---+   +---+   +   +---+---+---+   +---+   +---+---+---+---+   +
|   |                       |                   |                               |
+---+---+---+---+---+---+---+---+---+---+   +---+---+---+---+---+---+---+---+---+

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:
+   +---+---+---+---+---+---+---+---+---+---+
|                   |               |       |
+---+---+   +---+---+   +   +---+   +---+   +
|           |           |   |       |       |
+   +   +---+   +---+---+   +---+   +   +   +
|   |   |               |       |   |   |   |
+   +---+   +---+---+---+   +   +   +   +   +
|       |   |           |   |   |       |   |
+   +   +   +   +---+---+   +   +---+---+   +
|   |       |       |       |   |   |       |
+---+---+---+---+   +   +---+   +   +   +---+
|               |   |   |   |   |   |       |
+   +---+---+   +   +   +   +   +   +---+   +
|       |   |       |       |   |       |   |
+---+   +   +---+---+---+---+   +   +---+   +
|                               |            
+---+---+---+---+---+---+---+---+---+---+---+





























































































































Retrieved from "https://rosettacode.org/wiki/Maze_generation?oldid=167471"