Maze generation: Difference between revisions

111,316 bytes added ,  1 month ago
m
(→‎{{header|PHP}}: Fixed typos)
 
(101 intermediate revisions by 36 users not shown)
Line 1:
{{task|Games}}{{wikipedia|Maze generation algorithm}}
[[File:a maze.png|300px350px||right|a maze]]
 
<br>
Line 16:
* [[Maze solving]].
<br><br>
 
=={{header|11l}}==
{{trans|Python}}
 
<syntaxhighlight lang="11l">F make_maze(w = 16, h = 8)
V vis = [[0] * w [+] [1]] * h [+] [[1] * (w + 1)]
V ver = [[‘| ’] * w [+] [String(‘|’)]] * h [+] [[String]()]
V hor = [[‘+--’] * w [+] [String(‘+’)]] * (h + 1)
 
F walk(Int x, Int y) -> Void
@vis[y][x] = 1
V d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
random:shuffle(&d)
L(=xx, =yy) d
I yy == -1
yy = @vis.len - 1
I xx == -1
xx = @vis[0].len - 1
I @vis[yy][xx]
L.continue
I xx == x
@hor[max(y, yy)][x] = ‘+ ’
I yy == y
@ver[y][max(x, xx)] = ‘ ’
@walk(xx, yy)
 
walk(random:(w), random:(h))
 
V s = ‘’
L(a, b) zip(hor, ver)
s ‘’= (a [+] [String("\n")] + b [+] [String("\n")]).join(‘’)
R s
 
print(make_maze())</syntaxhighlight>
 
{{out}}
<pre>
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | |
+ +--+--+--+--+--+--+--+--+--+ + +--+ + +--+
| | | | | | |
+--+--+--+--+--+--+ + +--+ +--+ + + + + +
| | | | | | | | | |
+ + +--+--+ + +--+ + +--+ +--+ + +--+ +
| | | | | | | | |
+ +--+--+--+--+--+ + + + +--+ + +--+--+--+
| | | | | | | | | | |
+ +--+--+ + + + +--+ + + +--+--+ +--+ +
| | | | | | | | | |
+--+ + +--+ +--+ + +--+ + + +--+--+ + +
| | | | | | | | | | |
+ + +--+ +--+ +--+--+ +--+--+--+--+--+ + +
| | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
</pre>
 
=={{header|Action!}}==
Action! language does not support recursion. Therefore an iterative approach with a stack has been proposed.
<syntaxhighlight lang="action!">DEFINE TOP="0"
DEFINE RIGHT="1"
DEFINE BOTTOM="2"
DEFINE LEFT="3"
DEFINE WIDTH="160"
DEFINE HEIGHT="96"
 
DEFINE STACK_SIZE="5000"
BYTE ARRAY stack(STACK_SIZE)
INT stackSize
 
PROC InitStack()
stackSize=0
RETURN
 
BYTE FUNC IsEmpty()
IF stackSize=0 THEN
RETURN (1)
FI
RETURN (0)
 
BYTE FUNC IsFull()
IF stackSize>=STACK_SIZE THEN
RETURN (1)
FI
RETURN (0)
 
PROC Push(BYTE x,y)
IF IsFull() THEN Break() RETURN FI
stack(stackSize)=x stackSize==+1
stack(stackSize)=y stackSize==+1
RETURN
 
PROC Pop(BYTE POINTER x,y)
IF IsEmpty() THEN Break() RETURN FI
stackSize==-1 y^=stack(stackSize)
stackSize==-1 x^=stack(stackSize)
RETURN
 
PROC FillScreen()
BYTE POINTER ptr ;pointer to the screen memory
INT screenSize=[3840]
 
ptr=PeekC(88)
SetBlock(ptr,screenSize,$55)
 
Color=0
Plot(0,HEIGHT-1) DrawTo(WIDTH-1,HEIGHT-1) DrawTo(WIDTH-1,0)
RETURN
 
PROC GetNeighbors(BYTE x,y BYTE ARRAY n BYTE POINTER count)
DEFINE WALL="1"
 
count^=0
IF y>2 AND Locate(x,y-2)=WALL THEN
n(count^)=TOP count^==+1
FI
IF x<WIDTH-3 AND Locate(x+2,y)=WALL THEN
n(count^)=RIGHT count^==+1
FI
IF y<HEIGHT-3 AND Locate(x,y+2)=WALL THEN
n(count^)=BOTTOM count^==+1
FI
IF x>2 AND Locate(x-2,y)=WALL THEN
n(count^)=LEFT count^==+1
FI
RETURN
 
PROC Maze(BYTE x,y)
BYTE ARRAY stack,neighbors
BYTE dir,nCount
 
FillScreen()
 
Color=2
InitStack()
Push(x,y)
WHILE IsEmpty()=0
DO
Pop(@x,@y)
GetNeighbors(x,y,neighbors,@nCount)
IF nCount>0 THEN
Push(x,y)
Plot(x,y)
dir=neighbors(Rand(nCount))
IF dir=TOP THEN
y==-2
ELSEIF dir=RIGHT THEN
x==+2
ELSEIF dir=BOTTOM THEN
y==+2
ELSE
x==-2
FI
DrawTo(x,y)
Push(x,y)
FI
OD
RETURN
 
PROC Main()
BYTE CH=$02FC,COLOR0=$02C4,COLOR1=$02C5
BYTE x,y
 
Graphics(7+16)
COLOR0=$0A
COLOR1=$04
 
x=Rand((WIDTH RSH 1)-1) LSH 1+1
y=Rand((HEIGHT RSH 1)-1) LSH 1+1
Maze(x,y)
 
DO UNTIL CH#$FF OD
CH=$FF
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Maze_generation.png Screenshot from Atari 8-bit computer]
 
=={{header|Ada}}==
Line 21 ⟶ 196:
{{works with|GNAT}}
mazes.ads:
<langsyntaxhighlight Adalang="ada">generic
Height : Positive;
Width : Positive;
Line 47 ⟶ 222:
type Maze_Grid is array (Height_Type, Width_Type) of Cells;
 
end Mazes;</langsyntaxhighlight>
mazes.adb:
<langsyntaxhighlight Adalang="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
Line 91 ⟶ 247:
end case;
end "-";
 
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 Depth_First_Algorithm
(Maze : in out Maze_Grid;
Line 101 ⟶ 289:
Next_Direction : Directions;
Valid_Direction : Boolean;
Tested_Wall : array (Directions) of Boolean := (others => False);
All_Tested : Boolean;
begin
-- mark as visited
Maze (Row, Column).Visited := True;
loop
-- continue as long as there are unvisited neighbours left
while Has_Unvisited_Neighbours (Maze, Row, Column) loop
-- use random direction
loop
Next_Direction := Random_Direction.Random (Dir_Generator);
Next_Direction := Random_Direction.Random (Dir_Generator);
exit when not Tested_Wall (Next_Direction);
end loop;
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
-- connect the two cells
Maze (Row, Column).Walls (Next_Direction) :=
False;
Line 121 ⟶ 313:
end if;
end if;
Tested_Wall (Next_Direction) := True;
-- continue as long as there are unvisited neighbours left
All_Tested := True;
for D in Directions loop
All_Tested := All_Tested and Tested_Wall (D);
end loop;
-- all directions are either visited (from here,
-- or previously visited), or invalid.
exit when All_Tested;
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;
Line 167 ⟶ 341:
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
Ada.Text_IO.Put ('+');
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;
Line 239 ⟶ 378:
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;
if Item (Row, Item'Last (2)).Walls (East) then
Ada.Text_IO.New_Line;
Ada.Text_IO.Put_Line ("|");
else
Ada.Text_IO.Put_Line (" ");
end if;
Ada.Text_IO.Put ('+');
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>
</syntaxhighlight>
Example main.adb:
<langsyntaxhighlight Adalang="ada">with Mazes;
procedure Main is
package Small_Mazes is new Mazes (Height => 8, Width => 11);
Line 274 ⟶ 406:
Small_Mazes.Initialize (My_Maze);
Small_Mazes.Put (My_Maze);
end Main;</langsyntaxhighlight>
{{out}}
<pre>Starting generation at 3 x 7
Line 296 ⟶ 428:
 
=={{header|Aime}}==
<langsyntaxhighlight lang="aime">grid_maze(data b, integer N)
{
data d;
Line 369 ⟶ 501:
 
0;
}</langsyntaxhighlight>
{{out}}
<pre>+---+---+---+---+---+---+---+---+---+---+
Line 392 ⟶ 524:
| | | |
+---+---+---+---+---+---+---+---+---+---+
</pre>
 
=={{header|APL}}==
<syntaxhighlight lang="apl">
This example shows how to use GNU APL scripting.
 
#!/usr/local/bin/apl --script --
⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝
⍝ ⍝
⍝ mazeGen.apl 2022-01-07 19:47:35 (GMT-8) ⍝
⍝ ⍝
⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝
 
∇initPRNG
⍝⍝ Seed the internal PRNG used by APL ? operator
⎕RL ← +/ ⎕TS ⍝⍝ Not great... but good enough
 
∇offs ← cellTo dir
⍝⍝ Return the offset (row col) to cell which lies in compass (dir)
offs ← ∊((¯1 0)(0 1)(1 0)(0 ¯1))[('nesw'⍳dir)]
 
∇doMaze rc
⍝⍝ Main function
0 0 mazeGen rc ⍝⍝ Do the maze gen
m ⍝⍝ output result
 
∇b ← m isVisited coord;mr;mc
→( ∨/ (coord[1] < 1) (coord[2] < 1) )/yes
→( ∨/ (coord > ⌊(⍴m)÷2) )/yes
b ← ' ' ∊ m[2×coord[1];2×coord[2]]
→0
yes:
b←1
 
∇c mazeGen sz ;dirs;c;dir;cell;next
→(c≠(0 0))/gen
init:
c ← ?sz[1],?sz[2]
m ← mazeInit sz
gen:
cell ← c
dirs ← 'nesw'[4?4]
m[2×c[1];2×c[2]] ← ' ' ⍝ mark cell as visited
dir1:
dir ← dirs[1]
next ← cell + cellTo dir
→(m isVisited next)/dir2
m ← m openWall cell dir
next mazeGen sz
dir2:
dir ← dirs[2]
next ← cell + cellTo dir
→(m isVisited next)/dir3
m ← m openWall cell dir
next mazeGen sz
dir3:
dir ← dirs[3]
next ← cell + cellTo dir
→(m isVisited next)/dir4
m ← m openWall cell dir
next mazeGen sz
dir4:
dir ← dirs[4]
next ← cell + cellTo dir
→(m isVisited next)/done
m ← m openWall cell dir
next mazeGen sz
done:
 
∇m ← mazeInit sz;rows;cols;r
⍝⍝ Init an ASCII grid which
⍝⍝ has all closed and unvisited cells:
⍝⍝
⍝⍝ +-+
⍝⍝ |.|
⍝⍝ +-+
⍝⍝
⍝⍝ @param sz - tuple (rows cols)
⍝⍝ @return m - ASCII representation of (rows × cols) closed maze cells
⍝⍝⍝⍝
 
initPRNG
(rows cols) ← sz
r ← ∊ (cols ⍴ ⊂"+-" ),"+"
r ← r,∊ (cols ⍴ ⊂"|." ),"|"
r ← (rows,(⍴r))⍴r
r ← ((2×rows),(1+2×cols))⍴r
r ← r⍪ (∊ (cols ⍴ ⊂"+-" ),"+")
m ← r
 
∇r ← m openWall cellAndDir ;ri;ci;rw;cw;row;col;dir
(row col dir) ← ∊cellAndDir
ri ← 2×row
ci ← 2×col
(rw cw) ← (ri ci) + cellTo dir
m[rw;cw] ← ' ' ⍝ open wall in (dir)
r ← m
 
⎕IO←1
 
doMaze 9 9
)OFF
</syntaxhighlight>
{{out}}
<pre>
~/GNUAPL$ workspaces/mazeGen.apl
+-+-+-+-+-+-+-+-+-+
| | |
+ + + +-+ +-+-+-+ +
| | | | | |
+ +-+ +-+-+ + +-+-+
| | | | |
+ + + + +-+-+-+-+ +
| | | | | |
+ + + +-+ +-+-+-+-+
| | | | | | |
+ + +-+ + + + + + +
| | | | | | | |
+ +-+ + + +-+-+ + +
| | | | | | |
+ + + +-+-+-+-+-+ +
| | | |
+-+ +-+ +-+ +-+-+-+
| | |
+-+-+-+-+-+-+-+-+-+
</pre>
 
=={{header|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.
<langsyntaxhighlight AHKlang="ahk">; Initially build the board
Width := 11
Height := 8
Line 460 ⟶ 724:
If (A_Index = Y)
return SubStr(A_LoopField, x, 1)
}</langsyntaxhighlight>
{{out|Sample output}}
<pre>+-+-+-+-+-+-+-+-+-+-+-+
Line 486 ⟶ 750:
=={{header|AWK}}==
 
<langsyntaxhighlight lang="awk">#!/usr/bin/awk -f
 
# Remember: AWK is 1-based, for better or worse.
Line 673 ⟶ 937:
srand(t);
}
</syntaxhighlight>
</lang>
 
Example output:
Line 719 ⟶ 983:
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
</pre>
 
=={{header|BASIC}}==
==={{header|QB64}}===
This implementation was written using QB64. It should also be compatible with Qbasic, as it uses no QB64-exclusive features.
<syntaxhighlight lang="qb64">OPTION BASE 0
RANDOMIZE TIMER
 
REM must be even
width% = 40
height% = 20
 
REM make array and fill
DIM maze$(width%, height%)
FOR x% = 0 TO width%
FOR y% = 0 TO height%
maze$(x%, y%) = "#"
NEXT y%
NEXT x%
 
REM initial start location
currentx% = INT(RND * (width% - 1))
currenty% = INT(RND * (height% - 1))
REM value must be odd
IF currentx% MOD 2 = 0 THEN currentx% = currentx% + 1
IF currenty% MOD 2 = 0 THEN currenty% = currenty% + 1
maze$(currentx%, currenty%) = " "
 
REM generate maze
done% = 0
DO WHILE done% = 0
FOR i% = 0 TO 99
oldx% = currentx%
oldy% = currenty%
 
REM move in random direction
SELECT CASE INT(RND * 4)
CASE 0
IF currentx% + 2 < width% THEN currentx% = currentx% + 2
CASE 1
IF currenty% + 2 < height% THEN currenty% = currenty% + 2
CASE 2
IF currentx% - 2 > 0 THEN currentx% = currentx% - 2
CASE 3
IF currenty% - 2 > 0 THEN currenty% = currenty% - 2
END SELECT
 
REM if cell is unvisited then connect it
IF maze$(currentx%, currenty%) = "#" THEN
maze$(currentx%, currenty%) = " "
maze$(INT((currentx% + oldx%) / 2), ((currenty% + oldy%) / 2)) = " "
END IF
NEXT i%
 
REM check if all cells are visited
done% = 1
FOR x% = 1 TO width% - 1 STEP 2
FOR y% = 1 TO height% - 1 STEP 2
IF maze$(x%, y%) = "#" THEN done% = 0
NEXT y%
NEXT x%
LOOP
 
REM draw maze
FOR y% = 0 TO height%
FOR x% = 0 TO width%
PRINT maze$(x%, y%);
NEXT x%
PRINT
NEXT y%
 
REM wait
DO: LOOP WHILE INKEY$ = ""</syntaxhighlight>
 
{{out}}
This used a slightly modified version that outputs to a text file. (You can't copy from a QB64 window.)
<pre>#########################################
# # # # # # # # # #
# ### # # # # ##### # # ### # # # # # ###
# # # # # # # # # # # # # #
# # # ####### # ####### ####### ##### # #
# # # # # # # #
# ##### ### ### # # ### # # ##### ### ###
# # # # # # # # # # # # #
### ##### # ##### ### ### # ### # # #####
# # # # # # # # # # #
# # # ### # # ##### ### # # # # ##### ###
# # # # # # # # # # #
# ### # # ######### ### ####### # ##### #
# # # # # # # # # # # # # # #
# ### ####### # ### # ##### # # ### # # #
# # # # # # # # # #
##### # ### ### ### ### # # # # # # # # #
# # # # # # # # # # # #
# # # # ### # ### ### ### # ### ### ### #
# # # # # # # # # # # # #
#########################################</pre>
 
==={{header|BASIC256}}===
<syntaxhighlight lang="basic256">global size_x, size_y
size_x = 25
size_y = 15
 
global char_wall, char_room
char_wall = "#"
char_room = " "
 
global directions_permutations
directions_permutations = {{0, 1, 2, 3}, {0, 1, 3, 2}, {0, 2, 1, 3}, {0, 2, 3, 1}, {0, 3, 1, 2}, {0, 3, 2, 1}, {1, 0, 2, 3}, {1, 0, 3, 2}, {1, 2, 0, 3}, {1, 2, 3, 0}, {1, 3, 0, 2}, {1, 3, 2, 0}, {2, 0, 1, 3}, {2, 0, 3, 1}, {2, 1, 0, 3}, {2, 1, 3, 0}, {2, 3, 0, 1}, {2, 3, 1, 0}, {3, 0, 1, 2}, {3, 0, 2, 1}, {3, 1, 0, 2}, {3, 1, 2, 0}, {3, 2, 0, 1}, {3, 2, 1, 0}}
 
global maze
dim maze[size_x * 2 + 1][size_y * 2 + 1]
for i = 0 to size_x * 2
for j = 0 to size_y * 2
maze[i][j] = char_wall
next j
next i
 
call make_room(int(rand * size_x), int(rand * size_y))
 
call draw_maze()
 
end
 
subroutine make_room(room_x, room_y)
maze[1 + room_x * 2][1 + room_y * 2] = char_room
random_directions_index = rand * 24
for i = 0 to 3
random_direction = directions_permutations[random_directions_index][i]
if ((random_direction / 2) mod 2) < 1 then
dx = (random_direction mod 2) * 2 - 1
dy = 0
else
dx = 0
dy = (random_direction mod 2) * 2 - 1
end if
if can_dig(room_x + dx, room_y + dy) then
call make_door(room_x, room_y, dx, dy)
call make_room(room_x + dx, room_y + dy)
end if
next i
end subroutine
 
function can_dig(room_x, room_y)
if (room_x < 0) or (room_x >= size_x) or (room_y < 0) or (room_y >= size_y) then
can_dig = false
else
can_dig = (maze[1 + room_x * 2][1 + room_y * 2] = char_wall)
end if
end function
 
subroutine make_door(room_x, room_y, dx, dy)
maze[1 + room_x * 2 + dx][1 + room_y * 2 + dy] = char_room
end subroutine
 
subroutine draw_maze()
for i = 0 to size_y * 2
for j = 0 to size_x * 2
print maze[j][i];
next j
print
next i
end subroutine</syntaxhighlight>
 
{{out}}
<pre>###################################################
# # # # # # #
# ####### ####### # ##### # ### ##### ##### # # ###
# # # # # # # # # # # # #
# ### # ####### ### # ####### # # # # # ##### ### #
# # # # # # # # # # # # #
# # ##### # ##### ############### # # ### ##### # #
# # # # # # # # # # # #
# ##### ####### ### # # # ##### # ##### ### #######
# # # # # # # # # # # # # # # #
### # ### # ##### ### # # ### # ### # ### # # ### #
# # # # # # # # # # # # #
# ######### ######### ##### ########### # ### # # #
# # # # # # # # # # # #
# # # # # ############# ### # # ### ####### # # ###
# # # # # # # # # # # # # # # #
# # # ####### ### # # # # ### ### ##### # # # ### #
# # # # # # # # # # # # # # #
####### # # ######### ####### # ### # # # ####### #
# # # # # # # # # # # #
# ### # ##### ######### ### ##### # ########### # #
# # # # # # # # # # # #
# ####### ##### ##### # # ######### # ### ### # # #
# # # # # # # # # # # # # # #
### # # # # ##### # ##### ##### # ### # # # ### # #
# # # # # # # # # # # # # # # #
# ### # ##### # ##### ##### ### ### # ##### # ### #
# # # # # # # # # # # # #
# # ####### # ####### # # ####### ### ### ####### #
# # # # #
###################################################</pre>
 
=={{header|Batch File}}==
{{works with|Windows NT}}
 
<langsyntaxhighlight lang="dos">:amaze Rows Cols [wall char]
:: A stack-less, iterative, depth-first maze generator in native WinNT batch.
:: Rows and Cols must each be >1 and Rows*Cols cannot exceed 2096.
Line 817 ⟶ 1,276:
ENDLOCAL
EXIT /B 0
</syntaxhighlight>
</lang>
 
Example output:
Line 845 ⟶ 1,304:
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
</pre>
 
=={{header|BASIC}}==
This implementation was written using QB64. It should also be compatible with Qbasic, as it uses no QB64-exclusive features.
<lang BASIC>OPTION BASE 0
RANDOMIZE TIMER
 
REM must be even
width% = 40
height% = 20
 
REM make array and fill
DIM maze$(width%, height%)
FOR x% = 0 TO width%
FOR y% = 0 TO height%
maze$(x%, y%) = "#"
NEXT y%
NEXT x%
 
REM initial start location
currentx% = INT(RND * (width% - 1))
currenty% = INT(RND * (height% - 1))
REM value must be odd
IF currentx% MOD 2 = 0 THEN currentx% = currentx% + 1
IF currenty% MOD 2 = 0 THEN currenty% = currenty% + 1
maze$(currentx%, currenty%) = " "
 
REM generate maze
done% = 0
DO WHILE done% = 0
FOR i% = 0 TO 99
oldx% = currentx%
oldy% = currenty%
 
REM move in random direction
SELECT CASE INT(RND * 4)
CASE 0
IF currentx% + 2 < width% THEN currentx% = currentx% + 2
CASE 1
IF currenty% + 2 < height% THEN currenty% = currenty% + 2
CASE 2
IF currentx% - 2 > 0 THEN currentx% = currentx% - 2
CASE 3
IF currenty% - 2 > 0 THEN currenty% = currenty% - 2
END SELECT
 
REM if cell is unvisited then connect it
IF maze$(currentx%, currenty%) = "#" THEN
maze$(currentx%, currenty%) = " "
maze$(INT((currentx% + oldx%) / 2), ((currenty% + oldy%) / 2)) = " "
END IF
NEXT i%
 
REM check if all cells are visited
done% = 1
FOR x% = 1 TO width% - 1 STEP 2
FOR y% = 1 TO height% - 1 STEP 2
IF maze$(x%, y%) = "#" THEN done% = 0
NEXT y%
NEXT x%
LOOP
 
REM draw maze
FOR y% = 0 TO height%
FOR x% = 0 TO width%
PRINT maze$(x%, y%);
NEXT x%
PRINT
NEXT y%
 
REM wait
DO: LOOP WHILE INKEY$ = ""</lang>
 
{{out}}
This used a slightly modified version that outputs to a text file. (You can't copy from a QB64 window.)
<pre>#########################################
# # # # # # # # # #
# ### # # # # ##### # # ### # # # # # ###
# # # # # # # # # # # # # #
# # # ####### # ####### ####### ##### # #
# # # # # # # #
# ##### ### ### # # ### # # ##### ### ###
# # # # # # # # # # # # #
### ##### # ##### ### ### # ### # # #####
# # # # # # # # # # #
# # # ### # # ##### ### # # # # ##### ###
# # # # # # # # # # #
# ### # # ######### ### ####### # ##### #
# # # # # # # # # # # # # # #
# ### ####### # ### # ##### # # ### # # #
# # # # # # # # # #
##### # ### ### ### ### # # # # # # # # #
# # # # # # # # # # # #
# # # # ### # ### ### ### # ### ### ### #
# # # # # # # # # # # # #
#########################################</pre>
 
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<langsyntaxhighlight lang="bbcbasic"> MazeWidth% = 11
MazeHeight% = 9
MazeCell% = 50
Line 984 ⟶ 1,348:
ENDIF
NEXT
ENDPROC</langsyntaxhighlight>
'''Sample output:'''
<br>
Line 994 ⟶ 1,358:
Also note that this requires an interpreter with working read-write memory support, which is suprisingly rare in online implementations. Padding the code page with extra blank lines or spaces can sometimes help. Using smaller dimensions might also be preferable, especially on slower implementations.
<langsyntaxhighlight lang="befunge">45*28*10p00p020p030p006p0>20g30g00g*+::"P"%\"P"/6+gv>$\1v@v1::\+g02+*g00+g03-\<
0_ 1!%4+1\-\0!::\-\2%2:p<pv0<< v0p+6/"P"\%"P":\+4%4<^<v-<$>+2%\1-*20g+\1+4%::v^
#| +2%\1-*30g+\1\40g1-:v0+v2?1#<v>+:00g%!55+*>:#0>#,_^>:!|>\#%"P"v#:*+*g00g0<>1
Line 1,000 ⟶ 1,364:
0#$g#<1#<-#<`#<\#<0#<^#_^/>#1+#4<>"P"%\"P"/6+g:2%^!>,1-:#v_$55+^|$$ "JH" $$>#<0
::"P"%\"P"/6+g40p\40g+\:#^"P"%#\<^ ::$_,#!0#:<*"|"<^," _"<:g000 <> /6+g4/2%+#^_
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,023 ⟶ 1,387:
=={{header|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.
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Line 1,168 ⟶ 1,532:
 
return 0;
}</langsyntaxhighlight>
{{out|Sample output}}
<pre>┌───┬─────┬─────────┬───────┬───┐
Line 1,187 ⟶ 1,551:
│     │  ╰┄┄┄╯│  ╰┄┄┄┄┄┄┄╯│  ╰┄┄│
└─────┴───────┴───────────┴─────┘</pre>
 
Alternative approach
<pre>
 
/* --------------------------------------------------- */
/* I include this alternative method for consideration */
/* --------------------------------------------------- */
/* in file define’s.h */
/* I came to ansi-C after Algol-60 etc and these five pretend to be language tokens */
/* I do like ansi-C but the syntax is rather 'scruffy' */
 
#define then
#define endif
#define endwhile
#define endfor
#define endswitch
#ifndef BOOL
#define BOOL int
#define TRUE 1
#define FALSE 0
#endif
#define MAZE_SIZE_X 16
#define MAZE_SIZE_Y 16
/* in file GlobalDefs.h */
unsigned char box[MAZE_SIZE_X+1][MAZE_SIZE_Y+1];
int allowed[4];
int x_[4] = { 0, 1, 0, -1 };
int y_[4] = { 1, 0, -1, 0 };
/* in file DesignMaze.c */
 
/* This produces an enclosed rectangular maze. There will only be one path
between any (x1,y1) and (x2,y2). The code to add doors is not included here */
/* When I write code for me I put an explanation before a function to remind me
what I was thinking at the time – I have retained those explanations to self here */
/* Also note at the end of the path_check() function the return relies on the
weak type checking of ansi-C and (int)TRUE == 1 */
/* By making the recursive functions static, this is a hint to the compiler to
simplify the stack code instructions as the compiler knows everything that it needs
from the current source file and does not need to involve the linker.
Implementation specific #pragma could also be used */
 
/**************************************************************************/
/* */
/* The maze is made up of a set of boxes (it is a rectangular maze). */
/* Each box has a description of the four sides, each side can be :- */
/* (a) a solid wall */
/* (b) a gap */
/* (c) a door */
/* */
/* A side has an opening bit set for gaps and doors, this makes the */
/* movement checking easier. */
/* */
/* For any opening there are four bits corresponding to the four sides:- */
/* Bit 0 is set if Northwards movement is allowed */
/* Bit 1 is set if Eastwards movement is allowed */
/* Bit 2 is set if Southwards movement is allowed */
/* Bit 3 is set if Westwards movement is allowed */
/* */
/* For a door there are four bits corresponding to the four sides:- */
/* Bit 4 is set if North has a door, unset if North has a gap */
/* Bit 5 is set if East has a door, unset if East has a gap */
/* Bit 6 is set if South has a door, unset if South has a gap */
/* Bit 7 is set if West has a door, unset if West has a gap */
/* */
/**************************************************************************/
/**************************************************************************/
/********************************** path_check ****************************/
/**************************************************************************/
/* */
/* This sets: */
/* allowed[0] to TRUE if a path could be extended to the 'North' */
/* allowed[1] to TRUE if a path could be extended to the 'East' */
/* allowed[2] to TRUE if a path could be extended to the 'South' */
/* allowed[3] to TRUE if a path could be extended to the 'West' */
/* */
/* A path could be extended in a given direction if it does not go */
/* beyond the edge of the maze (there are no gaps in the surrounding */
/* walls), or the adjacent box has not already been visited */
/* (i.e. it contains 0). */
/* */
/* It also returns non-zero if there is at least one potential path */
/* which can be extended. */
/* */
/**************************************************************************/
static int path_check(int x, int y)
{
if ( y > (MAZE_SIZE_Y-1) )
then { allowed[0] = FALSE; }
else { allowed[0] = (box[x ][y+1] == 0) ? TRUE : FALSE; }
endif
if ( x > (MAZE_SIZE_X-1) )
then { allowed[1] = FALSE; }
else { allowed[1] = (box[x+1][y ] == 0) ? TRUE : FALSE; }
endif
if ( y < 2 )
then { allowed[2] = FALSE; }
else { allowed[2] = (box[x ][y-1] == 0) ? TRUE : FALSE; }
endif
if ( x < 2 )
then { allowed[3] = FALSE; }
else { allowed[3] = (box[x-1][y ] == 0) ? TRUE : FALSE; }
endif
return (allowed[0]+allowed[1]+allowed[2]+allowed[3]);
} /* end of 'path_check' */
/**************************************************************************/
/********************************** design_maze ***************************/
/**************************************************************************/
/* */
/* This is a recursive routine to produce a random rectangular maze */
/* with only one route between any two points. */
/* For each box reached, a 'wall' is knocked through to an adjacent */
/* box if that box has not previously been reached (i.e. no walls */
/* knocked out). */
/* For the adjacent box the adjacent wall is also knocked out. */
/* Then the routine is called again from the adjacent box. */
/* If there are no adjacent boxes which have not already been reached */
/* then the routine returns to the previous call. */
/* */
/**************************************************************************/
static void design_maze(int x, int y)
{
int direction;
while ( path_check(x,y) > 0)
{
do { direction = rand()%4; } while ( allowed[direction]==FALSE );
box[x ][y ] |= (1 << direction );
box[x+x_[direction]][y+y_[direction]] |= (1 << ((direction+2) % 4) );
design_maze( x+x_[direction] , y+y_[direction] );
} endwhile
} /* end of 'design_maze()' */
</pre>
 
=={{header|C sharp|C#}}==
 
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Drawing;
 
namespace MazeGeneration
{
public static class Extensions
{
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
var e = source.ToArray();
for (var i = e.Length - 1; i >= 0; i--)
{
var swapIndex = rng.Next(i + 1);
yield return e[swapIndex];
e[swapIndex] = e[i];
}
}
 
public static CellState OppositeWall(this CellState orig)
{
return (CellState)(((int) orig >> 2) | ((int) orig << 2)) & CellState.Initial;
}
 
public static bool HasFlag(this CellState cs,CellState flag)
{
return ((int)cs & (int)flag) != 0;
}
}
 
[Flags]
public enum CellState
{
Top = 1,
Right = 2,
Bottom = 4,
Left = 8,
Visited = 128,
Initial = Top | Right | Bottom | Left,
}
 
public struct RemoveWallAction
{
public Point Neighbour;
public CellState Wall;
}
 
public class Maze
{
private readonly CellState[,] _cells;
private readonly int _width;
private readonly int _height;
private readonly Random _rng;
 
public Maze(int width, int height)
{
_width = width;
_height = height;
_cells = new CellState[width, height];
for(var x=0; x<width; x++)
for(var y=0; y<height; y++)
_cells[x, y] = CellState.Initial;
_rng = new Random();
VisitCell(_rng.Next(width), _rng.Next(height));
}
 
public CellState this[int x, int y]
{
get { return _cells[x,y]; }
set { _cells[x,y] = value; }
}
 
public IEnumerable<RemoveWallAction> GetNeighbours(Point p)
{
if (p.X > 0) yield return new RemoveWallAction {Neighbour = new Point(p.X - 1, p.Y), Wall = CellState.Left};
if (p.Y > 0) yield return new RemoveWallAction {Neighbour = new Point(p.X, p.Y - 1), Wall = CellState.Top};
if (p.X < _width-1) yield return new RemoveWallAction {Neighbour = new Point(p.X + 1, p.Y), Wall = CellState.Right};
if (p.Y < _height-1) yield return new RemoveWallAction {Neighbour = new Point(p.X, p.Y + 1), Wall = CellState.Bottom};
}
 
public void VisitCell(int x, int y)
{
this[x,y] |= CellState.Visited;
foreach (var p in GetNeighbours(new Point(x, y)).Shuffle(_rng).Where(z => !(this[z.Neighbour.X, z.Neighbour.Y].HasFlag(CellState.Visited))))
{
this[x, y] -= p.Wall;
this[p.Neighbour.X, p.Neighbour.Y] -= p.Wall.OppositeWall();
VisitCell(p.Neighbour.X, p.Neighbour.Y);
}
}
 
public void Display()
{
var firstLine = string.Empty;
for (var y = 0; y < _height; y++)
{
var sbTop = new StringBuilder();
var sbMid = new StringBuilder();
for (var x = 0; x < _width; x++)
{
sbTop.Append(this[x, y].HasFlag(CellState.Top) ? "+---" : "+ ");
sbMid.Append(this[x, y].HasFlag(CellState.Left) ? "| " : " ");
}
if (firstLine == string.Empty)
firstLine = " " + sbTop.ToString();
Debug.WriteLine(" " + sbTop + "+");
Debug.WriteLine(" " + sbMid + "|");
}
Debug.WriteLine(firstLine);
}
}
 
class Program
{
static void Main(string[] args)
{
var maze = new Maze(20, 20);
maze.Display();
}
}
}
</syntaxhighlight>
Sample output:
<pre>
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | | |
+ +---+ +---+---+ +---+ + +---+---+ +---+ +---+---+ +---+---+ +
| | | | | | | | | | | |
+ + +---+ +---+---+ + +---+---+ +---+---+ + +---+---+ + + +
| | | | | | | | | | | |
+ + +---+---+ + + + + +---+---+ + +---+---+ +---+---+ + +
| | | | | | | | | | | |
+ +---+ + + + +---+---+ +---+---+---+---+---+ + + +---+---+ +
| | | | | | | | | | |
+---+---+---+ + +---+---+ +---+---+---+---+ + +---+---+ + + +---+
| | | | | | | | |
+ +---+---+---+ + +---+---+---+---+ + +---+---+ +---+---+ +---+ +
| | | | | | | | | | |
+ + + +---+---+---+---+ + + + + + +---+---+ + + +---+ +
| | | | | | | | | |
+ +---+---+ +---+ +---+---+ +---+---+ +---+ +---+---+ +---+---+---+
| | | | | | | | | | | | |
+---+---+ +---+ + + +---+---+ +---+ + + + + +---+---+ + +
| | | | | | | | | |
+ +---+---+ +---+---+---+ + + +---+---+ +---+---+---+---+---+---+ +
| | | | | | | | |
+ + + +---+ +---+ + + +---+ +---+---+ +---+---+---+---+---+ +
| | | | | | | | | | |
+ + +---+ +---+ +---+---+ + + + +---+---+ +---+---+---+---+ +
| | | | | | | | | |
+ +---+---+---+---+---+ +---+---+ + +---+ + + + + +---+---+ +
| | | | | | | | | | | | | |
+ + + +---+ + + + +---+ + + +---+---+---+ +---+ + + +
| | | | | | | | | | | |
+---+---+---+ + +---+---+ + +---+ +---+---+ + + +---+---+---+---+
| | | | | | | | | | |
+ +---+ + + + + +---+---+ +---+ + +---+ +---+ +---+ + +
| | | | | | | | | | | | | | |
+ + +---+---+---+ +---+---+---+ + +---+ + + + + + +---+ +
| | | | | | | | | | |
+---+ +---+ + +---+---+---+ +---+ + +---+ + +---+---+---+---+ +
| | | | | | | | | |
+ +---+---+---+ + +---+ +---+---+---+ + + +---+ +---+---+---+ +
| | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---
</pre>
 
=={{header|C++}}==
[[File:maze_cpp.png|300px]]
<langsyntaxhighlight lang="cpp">
#include <windows.h>
#include <iostream>
Line 1,459 ⟶ 2,149:
}
//--------------------------------------------------------------------------------------------------
</syntaxhighlight>
</lang>
 
=={{header|C sharp|C#Chapel}}==
<syntaxhighlight lang="chapel">
use Random;
 
config const rows: int = 9;
<lang csharp>using System;
config const cols: int = 16;
using System.Collections.Generic;
if rows < 1 || cols < 1 {
using System.Diagnostics;
writeln("Maze must be at least 1x1 in size.");
using System.Linq;
exit(1);
using System.Text;
}
using System.Drawing;
 
enum direction {N = 1, E = 2, S = 3, W = 4};
namespace MazeGeneration
{
public static class Extensions
{
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
var e = source.ToArray();
for (var i = e.Length - 1; i >= 0; i--)
{
var swapIndex = rng.Next(i + 1);
yield return e[swapIndex];
e[swapIndex] = e[i];
}
}
 
record Cell {
public static CellState OppositeWall(this CellState orig)
var spaces: [direction.N .. direction.W] bool;
{
var visited: bool;
return (CellState)(((int) orig >> 2) | ((int) orig << 2)) & CellState.Initial;
}
}
 
const dirs = [
public static bool HasFlag(this CellState cs,CellState flag)
((-1, 0), direction.N, direction.S), // ((rowDir, colDir), myWall, neighbourWall)
{
((0, 1), direction.E, direction.W),
return ((int)cs & (int)flag) != 0;
((1, 0), direction.S, direction.N),
}
((0, -1), direction.W, direction.E)
}
];
 
var maze: [1..rows, 1..cols] Cell;
[Flags]
var startingCell = (choose(maze.dim(0)), choose(maze.dim(1)));
public enum CellState
{
Top = 1,
Right = 2,
Bottom = 4,
Left = 8,
Visited = 128,
Initial = Top | Right | Bottom | Left,
}
 
checkCell(maze, startingCell);
public struct RemoveWallAction
displayMaze(maze);
{
public Point Neighbour;
public CellState Wall;
}
 
proc checkCell(ref maze, cell) {
public class Maze
maze[cell].visited = true;
{
for dir in permute(dirs) {
private readonly CellState[,] _cells;
var (offset, thisDir, neighbourDir) = dir;
private readonly int _width;
var neighbour = cell + offset;
private readonly int _height;
if maze.domain.contains(neighbour) && !maze[neighbour].visited {
private readonly Random _rng;
maze[cell].spaces[thisDir] = true;
maze[neighbour].spaces[neighbourDir] = true;
checkCell(maze, neighbour);
}
}
}
 
proc displayMaze(maze) {
public Maze(int width, int height)
for row in maze.dim(0) {
{
for col in maze.dim(1) {
_width = width;
write(if maze[row, col].spaces[direction.N] then "+ " else "+---");
_height = height;
}
_cells = new CellState[width, height];
writeln("+");
for(var x=0; x<width; x++)
for col in maze.dim(1) {
for(var y=0; y<height; y++)
write(if maze[row, col].spaces[direction.W] then " " else "| ");
_cells[x, y] = CellState.Initial;
}
_rng = new Random();
writeln("|");
VisitCell(_rng.Next(width), _rng.Next(height));
}
}
write("+---" * maze.dim(1).size);
writeln("+");
}
</syntaxhighlight>
 
{{out}}
public CellState this[int x, int y]
{
get { return _cells[x,y]; }
set { _cells[x,y] = value; }
}
 
public IEnumerable<RemoveWallAction> GetNeighbours(Point p)
{
if (p.X > 0) yield return new RemoveWallAction {Neighbour = new Point(p.X - 1, p.Y), Wall = CellState.Left};
if (p.Y > 0) yield return new RemoveWallAction {Neighbour = new Point(p.X, p.Y - 1), Wall = CellState.Top};
if (p.X < _width-1) yield return new RemoveWallAction {Neighbour = new Point(p.X + 1, p.Y), Wall = CellState.Right};
if (p.Y < _height-1) yield return new RemoveWallAction {Neighbour = new Point(p.X, p.Y + 1), Wall = CellState.Bottom};
}
 
public void VisitCell(int x, int y)
{
this[x,y] |= CellState.Visited;
foreach (var p in GetNeighbours(new Point(x, y)).Shuffle(_rng).Where(z => !(this[z.Neighbour.X, z.Neighbour.Y].HasFlag(CellState.Visited))))
{
this[x, y] -= p.Wall;
this[p.Neighbour.X, p.Neighbour.Y] -= p.Wall.OppositeWall();
VisitCell(p.Neighbour.X, p.Neighbour.Y);
}
}
 
public void Display()
{
var firstLine = string.Empty;
for (var y = 0; y < _height; y++)
{
var sbTop = new StringBuilder();
var sbMid = new StringBuilder();
for (var x = 0; x < _width; x++)
{
sbTop.Append(this[x, y].HasFlag(CellState.Top) ? "+--" : "+ ");
sbMid.Append(this[x, y].HasFlag(CellState.Left) ? "| " : " ");
}
if (firstLine == string.Empty)
firstLine = sbTop.ToString();
Debug.WriteLine(sbTop + "+");
Debug.WriteLine(sbMid + "|");
Debug.WriteLine(sbMid + "|");
}
Debug.WriteLine(firstLine);
}
}
 
class Program
{
static void Main(string[] args)
{
var maze = new Maze(20, 20);
maze.Display();
}
}
}
</lang>
Sample output:
<pre>
+--+--+--+--+--+--+--+--+---+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
|+ + + | +---+---+ + | +---+ |+ +---+---+ +---+---+ | | | | |+
+| +--+ + + | + + +--+ + +--+ +| + + + | +--+ +| +--+ | | | | |
|+ | +---+---+---+ +---+---+ | |+ +---+ | +---+ + + | | | | | | | |+---+
| | | | | | | | | | | | | |
+ ---+---+ + +---+---+---+---+---+---+ + +--+--+ + + +---+---+ +
| | | | | | | | | | |
+ + +---+---+---+---+---+ + +---+---+---+---+---+ + +
| | | | | | | | | |
| | | | | | | |
+ + +--+--+ + +--+--+ +--+--+--+ + +--+ +--+--+ + +
|+ | +---+---+---+ | + +---+---+ |+ +---+ | +---+ +---+ | | | | | |+
| | | | | | | | | | | | | | | |
+ + +---+ + +---+---+ + + +--+ -+---+ + +--+ +---+ + +--+-- +
| | | | | | | | | | | | | | |
|+---+---+---+ | + | + + |+---+---+ | + +---+---+ | +---+ | | | | | | |+
+| + + +--+ +--+--+ + | + +| + | +--+ +| + +--+--+--+ + | | | | | | |
|+ | + | |+---+ | + + +---+ | |+ | + | +---+ + +---+ |+ | | | |+
| | | | | | | | | | | | | | |
+ ---+ ---+ ---+ ---+---+---+ ---+ ---+---+ ---+---+---+---+---+ ---+ + + + + ---+
| | | | | | | | | | | | |
| | | | | | | | | | | | |
+ +--+--+ + +--+--+--+ +--+--+ + +--+--+ +--+ + +--+
| | | | | | | | |
| | | | | | | | |
+--+--+--+ +--+ + +--+--+ + +--+ + +--+--+--+--+--+ +
| | | | | | | | |
| | | | | | | | |
+ +--+--+--+--+ +--+--+ +--+ +--+--+ + +--+ +--+--+--+
| | | | | | | | | | | |
| | | | | | | | | | | |
+ +--+ + + +--+--+ +--+ +--+--+ + +--+ +--+ + + +
| | | | | | | | | | | |
| | | | | | | | | | | |
+--+ + + +--+--+ +--+ +--+--+ + +--+ +--+ + +--+ +
| | | | | | | | | | |
| | | | | | | | | | |
+ +--+ +--+--+ +--+ +--+ +--+ +--+ +--+ + +--+--+ +
| | | | | | | | | | |
| | | | | | | | | | |
+--+ + +--+ + +--+--+ +--+ +--+--+ + + +--+ +--+--+
| | | | | | | | | | | |
| | | | | | | | | | | |
+ + + + + +--+ +--+ + +--+ + +--+--+--+ +--+--+ +
| | | | | | | | | | | | | |
| | | | | | | | | | | | | |
+ +--+--+ + + +--+ +--+--+--+ + + + + +--+--+ + +
| | | | | | | | | | |
| | | | | | | | | | |
+--+--+--+--+--+ + +--+--+ +--+--+ + + +--+--+ + + +
| | | | | | | | | |
| | | | | | | | | |
+ + + + + + +--+ + +--+ +--+--+--+--+--+ +--+--+ +
| | | | | | | | | | | | |
| | | | | | | | | | | | |
+ +--+--+ +--+ + +--+--+--+ + + + + + +--+--+ + +
| | | | | | | | | | | |
| | | | | | | | | | | |
+--+ + +--+ + +--+--+--+ +--+--+ + + + +--+--+--+ +
| | | | | |
| | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
</pre>
 
 
=={{header|Clojure}}==
<langsyntaxhighlight lang="clojure">(ns maze.core
(:require [clojure.set :refer [intersection
select]]
Line 1,749 ⟶ 2,329:
 
;;Task
(println (maze->str (create-random-maze 10 10)))</langsyntaxhighlight>
 
{{out}}
Line 1,777 ⟶ 2,357:
Written in Commodore BASIC V2 and tested on Commodore 64 and Commodore 128 hardware. (It will also run on the unexpanded Commodore VIC-20 if you reduce the maze size to 8x8.) Due to stack size limitations in the operating systems, this solution eschews recursive subroutine calls. Recursion is accomplished by conditional branching within the maze build routine and the use of an array-based stack for data elements.
 
<langsyntaxhighlight BASIClang="basic">100 MS=10:REM MAZE SIZE
110 DIM S(MS+1,MS+1):REM SOUTH WALLS
120 DIM W(MS+1,MS+1):REM WEST WALLS
Line 1,835 ⟶ 2,415:
670 NEXT R
680 REM PRINT#4:CLOSE 4:REM CLOSE PRINTER DEVICE
690 RETURN</langsyntaxhighlight>
{{out|Output example (for 10x10 maze)}}
<pre>+--+--+--+--+--+--+--+--+--+--+
Line 1,862 ⟶ 2,442:
 
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.
<langsyntaxhighlight lang="lisp">(defun shuffle (list) ;; Z not uniform
(sort list '> :key (lambda(x) (random 1.0))))
 
Line 1,891 ⟶ 2,471:
do (princ (aref maze i j))))))
 
(draw-maze 20 6)</langsyntaxhighlight>
{{out}}
<pre>
Line 1,909 ⟶ 2,489:
 
Another solution using unicode line drawing chars. Assumes they are single width on console. Code pretty horribly unreadable.
<langsyntaxhighlight lang="lisp">(setf *random-state* (make-random-state t))
 
(defun 2d-array (w h)
Line 1,965 ⟶ 2,545:
(show))))
 
(make-maze 20 20)</langsyntaxhighlight>
{{out}}
<pre>┼───┴───┼───┴───┴───┼───┴───┴───┼
Line 1,986 ⟶ 2,566:
 
=={{header|D}}==
<langsyntaxhighlight lang="d">void main() @safe {
import std.stdio, std.algorithm, std.range, std.random;
 
Line 2,007 ⟶ 2,587:
foreach (const a, const b; hor.zip(ver ~ []))
join(a ~ "+\n" ~ b).writeln;
}</langsyntaxhighlight>
{{out}}
<pre>+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Line 2,030 ⟶ 2,610:
| | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</pre>
=={{header|Delphi}}==
<syntaxhighlight lang="pascal">program MazeGen_Rosetta;
 
{$APPTYPE CONSOLE}
 
uses System.SysUtils, System.Types, System.Generics.Collections, System.IOUtils;
 
type
TMCell = record
Visited : Boolean;
PassTop : Boolean;
PassLeft : Boolean;
end;
TMaze = array of array of TMCell;
TRoute = TStack<TPoint>;
 
const
mwidth = 24;
mheight = 14;
 
procedure ClearVisited(var AMaze: TMaze);
var
x, y: Integer;
begin
for y := 0 to mheight - 1 do
for x := 0 to mwidth - 1 do
AMaze[x, y].Visited := False;
end;
 
procedure PrepareMaze(var AMaze: TMaze);
var
Route : TRoute;
Position : TPoint;
d : Integer;
Pool : array of TPoint; // Pool of directions to pick randomly from
begin
SetLength(AMaze, mwidth, mheight);
ClearVisited(AMaze);
Position := Point(Random(mwidth), Random(mheight));
Route := TStack<TPoint>.Create;
try
with Position do
while True do
begin
repeat
SetLength(Pool, 0);
if (y > 0) and not AMaze[x, y-1].Visited then Pool := Pool + [Point(0, -1)];
if (x < mwidth-1) and not AMaze[x+1, y].Visited then Pool := Pool + [Point(1, 0)];
if (y < mheight-1) and not AMaze[x, y+1].Visited then Pool := Pool + [Point(0, 1)];
if (x > 0) and not AMaze[x-1, y].Visited then Pool := Pool + [Point(-1, 0)];
 
if Length(Pool) = 0 then // no direction to draw from
begin
if Route.Count = 0 then Exit; // and we are back at start so this is the end
Position := Route.Pop;
end;
until Length(Pool) > 0;
 
d := Random(Length(Pool));
Offset(Pool[d]);
 
AMaze[x, y].Visited := True;
if Pool[d].y = -1 then AMaze[x, y+1].PassTop := True; // comes from down to up ( ^ )
if Pool[d].x = 1 then AMaze[x, y].PassLeft := True; // comes from left to right ( --> )
if Pool[d].y = 1 then AMaze[x, y].PassTop := True; // comes from left to right ( v )
if Pool[d].x = -1 then AMaze[x+1, y].PassLeft := True; // comes from right to left ( <-- )
Route.Push(Position);
end;
finally
Route.Free;
end;
end;
 
function MazeToString(const AMaze: TMaze; const S, E: TPoint): String; overload;
var
x, y: Integer;
v : Char;
begin
Result := '';
for y := 0 to mheight - 1 do
begin
for x := 0 to mwidth - 1 do
if AMaze[x, y].PassTop then Result := Result + '+'#32#32#32 else Result := Result + '+---';
Result := Result + '+' + sLineBreak;
for x := 0 to mwidth - 1 do
begin
if S = Point(x, y) then v := 'S' else
if E = Point(x, y) then v := 'E' else
v := #32'*'[Ord(AMaze[x, y].Visited) + 1];
 
Result := Result + '|'#32[Ord(AMaze[x, y].PassLeft) + 1] + #32 + v + #32;
end;
Result := Result + '|' + sLineBreak;
end;
for x := 0 to mwidth - 1 do Result := Result + '+---';
Result := Result + '+' + sLineBreak;
end;
 
procedure Main;
var
Maze: TMaze;
begin
Randomize;
PrepareMaze(Maze);
ClearVisited(Maze); // show no route
Write(MazeToString(Maze, Point(-1, -1), Point(-1, -1)));
ReadLn;
end;
 
begin
Main;
 
end.</syntaxhighlight>
{{out}}
<pre>+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | |
+ + +---+---+ + + +---+---+---+---+---+ + + +---+---+---+ +---+ + +---+---+ + + +---+ +---+---+ +
| | | | | | | | | | | | | |
+ +---+ +---+---+---+---+---+---+---+---+---+---+---+ + +---+---+---+ +---+---+ +---+---+ + +---+---+ +---+---+
| | | | | | | | | | | | | |
+ +---+---+ + + + +---+ +---+ + + + +---+---+ +---+---+ + + + +---+---+---+ +---+ + + + +
| | | | | | | | | | | | | | | | | | | |
+---+ +---+ + +---+ +---+---+---+---+---+ +---+---+ +---+---+ +---+---+ +---+ +---+ +---+---+ + + + +
| | | | | | | | | | | | | | | | | |
+ +---+ +---+---+ +---+---+ + +---+ + + + +---+ +---+---+ + + + +---+ +---+ + + +---+---+ +
| | | | | | | | | | | | | | | | | |
+---+---+---+ + +---+---+---+---+---+ +---+---+ +---+ + +---+ +---+ +---+---+ +---+---+---+ + + + + +
| | | | | | | | | | | | | |
+ +---+ +---+---+ + +---+---+ + + + +---+ +---+ + +---+ +---+ +---+---+ + +---+---+---+ +---+---+
| | | | | | | | | | | | | | | |
+ + +---+---+ + + + +---+---+---+ +---+---+---+ +---+---+ + +---+---+---+ +---+---+ +---+---+---+ +---+
| | | | | | | | | | | | | | | |
+---+ + + +---+ + +---+ +---+ +---+---+ +---+---+ + + +---+---+---+---+---+ + +---+---+ + +---+ +
| | | | | | | | | | | | | | |
+ +---+ + + +---+---+ + + +---+ +---+---+---+---+---+---+---+ +---+---+---+ +---+---+---+---+---+---+---+ +
| | | | | | | | | | | | | | | |
+ + + + + + + + + +---+ +---+---+ + +---+ + + + +---+ + +---+---+---+ +---+---+ +---+---+
| | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</pre>
=={{header|EasyLang}}==
 
[https://easylang.dev/show/#cod=fZPLbqswEIb3fopP6iYXQe20WWTBkyB0RLE5sRrsCHJ6e/rKxBhQq7MB/P8z9vibYbBfhgJ1FI6CAzuGoOxRog26lDyycWTI/LgVF+PoygrHDiceEC918/q39/+cRkoprr1vGM7+/U9XfxlycgE0F1P34aP1PTZsy80T9wo6YFu60lYUyKgAHxRsLBlqS+c1brY+F5a2b0ur8RffczqdZqnzb4YPdrRktDxy4HO5miN709xo2aHy4/SO7niX8TFcjLkic6lELnzbDmUovEThyBSbzG2pAp6RR3eHcfXDBKQrr35Id028wkKnrQ488Uy15PaM9u/u5lGxJE1BXztt3Q07abanYKxKl7qaAIdvCnRpV8hDVfuQU419qZ1OYpiGyVigXKcsurW4Z0peo8uFcTr4xX2CQvsio/rVrGbmP6MS50Sldqxi3TrqkJbhxN8kMlwY+J+Wi9acNR53jn/KBF4dY1zIWRtixnK+N/4OIJGLPPYFTuQiURDzTHwD Run it]
[https://easylang.online/apps/run.html?code=size%20%3D%2020%0A%23%20%0Asz%20%3D%202%20%2A%20size%20%2B%201%0Alen%20f%5B%5D%20sz%20%2A%20sz%0A%23%20%0Afunc%20make_maze%20.%20.%0Afor%20i%20range%20len%20f%5B%5D%0Af%5Bi%5D%20%3D%201%0A.%0Af%5B%28sz%20-%201%29%20%2A%20sz%20%2B%20sz%20-%202%5D%20%3D%200%0Ax%20%3D%201%20%2B%202%20%2A%20random%20size%0Ay%20%3D%201%20%2B%202%20%2A%20random%20size%0Af%5Bx%20%2B%20y%20%2A%20sz%5D%20%3D%200%0Avisited%20%3D%201%0Awhile%20visited%20%3C%20size%20%2A%20size%0Aoldx%20%3D%20x%0Aoldy%20%3D%20y%0Adir%20%3D%20random%204%0Aif%20dir%20%3D%200%20and%20x%20%2B%202%20%3C%20sz%0Ax%20%2B%3D%202%0Aelif%20dir%20%3D%201%20and%20y%20%2B%202%20%3C%20sz%0Ay%20%2B%3D%202%0Aelif%20dir%20%3D%202%20and%20x%20%3E%202%0Ax%20-%3D%202%0Aelif%20dir%20%3D%203%20and%20y%20%3E%202%0Ay%20-%3D%202%0A.%0Aif%20f%5By%20%2A%20sz%20%2B%20x%5D%20%3D%201%0Af%5By%20%2A%20sz%20%2B%20x%5D%20%3D%200%0Af%5B%28y%20%2B%20oldy%29%20/%202%20%2A%20sz%20%2B%20%28x%20%2B%20oldx%29%20/%202%5D%20%3D%200%0Avisited%20%2B%3D%201%0A.%0A.%0A.%0Afunc%20show_maze%20.%20.%0Ac2%23%20%3D%20%28100%20-%2024%20/%20size%29%20/%20size%20/%202%0Ac10%23%20%3D%20c2%23%20/%205%0Alinewidth%202%20%2A%20c10%23%0Acolor%20997%0Amove%200%200%0Arect%20100%20100%0Acolor%20543%0Afor%20r%20range%20sz%0Afor%20c%20range%20sz%0Aif%20f%5Br%20%2A%20sz%20%2B%20c%5D%20%3D%201%0Aif%20r%20mod%202%20%3D%200%0Aif%20c%20mod%202%20%3D%201%0Amove%20c10%23%20%2B%20%28c%20-%201%29%20%2A%20c2%23%20c10%23%20%2B%20r%20%2A%20c2%23%0Aline%20c10%23%20%2B%20%28c%20%2B%201%29%20%2A%20c2%23%20c10%23%20%2B%20r%20%2A%20c2%23%0A.%0Aelse%0Amove%20c10%23%20%2B%20c%20%2A%20c2%23%20c10%23%20%2B%20%28r%20-%201%29%20%2A%20c2%23%0Aline%20c10%23%20%2B%20c%20%2A%20c2%23%20c10%23%20%2B%20%28r%20%2B%201%29%20%2A%20c2%23%0A.%0A.%0A.%0A.%0A.%0Acall%20make_maze%0Acall%20show_maze Run it]
 
<syntaxhighlight>
<lang easyprog.online>size = 20
size = 15
#
szn = 2 * size + 1
f = 100 / (n - 0.5)
# we only have one-dimensional arrays
len fm[] szn * szn
#
background 000
func make_maze . .
proc show_maze . .
# the maze is created by random walking around
clear
for i range len f[]
for f[i] = 1 to len m[]
if m[i] = 0
.
x = 1(i +- 2 *1) randommod sizen
y = 1(i +- 2 *1) randomdiv sizen
f[x + y * sz] = 0 color 999
move x * f - f / 2 y * f - f / 2
visited = 1
rect f * 1.5 f * 1.5
while visited < size * size
oldx = x.
oldy = y.
sleep 0.01
dir = random 4
if dir = 0 and x + 2 < sz
x += 2
elif dir = 1 and y + 2 < sz
y += 2
elif dir = 2 and x > 2
x -= 2
elif dir = 3 and y > 2
y -= 2
.
if f[y * sz + x] = 1
f[y * sz + x] = 0
f[(y + oldy) / 2 * sz + (x + oldx) / 2] = 0
visited += 1
.
.
f[(sz - 1) * sz + sz - 2] = 0
.
offs[] = [ 1 n -1 (-n) ]
func show_maze . .
#
c2# = (100 - 24 / size) / size / 2
proc m_maze pos . .
c10# = c2# / 5
m[pos] = 0
linewidth 2 * c10#
show_maze
color 997
d[] = [ 1 2 3 4 ]
move 0 0
for i = 4 downto 1
rect 100 100
d = randint i
color 543
dir = offs[d[d]]
for r range sz
for c ranged[d] sz= d[i]
if fm[rpos *+ szdir] = 1 and m[pos + c2 * dir] = 1
if rm[pos mod+ 2dir] = 0
m_maze ifpos c mod+ 2 =* 1dir
move c10# + (c - 1) * c2# c10# + r * c2#
line c10# + (c + 1) * c2# c10# + r * c2#
.
else
move c10# + c * c2# c10# + (r - 1) * c2#
line c10# + c * c2# c10# + (r + 1) * c2#
.
.
.
.
.
endpos = n * n - 1
call make_maze
proc make_maze . .
call show_maze</lang>
for i = 1 to len m[]
m[i] = 1
.
for i = 1 to n
m[i] = 2
m[n * i] = 2
m[n * i - n + 1] = 2
m[n * n - n + i] = 2
.
h = 2 * randint 15 - n + n * 2 * randint 15
m_maze h
m[endpos] = 0
endpos += n
.
make_maze
show_maze
</syntaxhighlight>
 
=={{header|EDSAC order code}}==
In this EDSAC solution there is no recursion or stack. As suggested in the Wikipedia article "Maze generation algorithm", backtracking information is stored in the maze itself. The code below leaves enough storage for a 24x24 maze, but the demo maze is cut down to 12x8 to save space.
<syntaxhighlight lang="edsac">
[Maze generation for Rosetta Code.
EDSAC program, Initial Orders 2.
 
Cells, horizontal walls, and vertical walls are numbered
as shown in this example:
+---1---+---2---+---3---+
| | | |
1 1 2 2 3 3 4 N
| | | | |
+---5---+---6---+---7---+ W---+---E
| | | | |
5 5 6 6 7 7 8 S
| | | |
+---9---+--10---+--11---+
 
Maze data are held in a single 1-based array of 17-bit values
(equivalent to an array of records in a high-level language).
In each entry, fields for cells and walls are as shown in "Flags" below.]
 
[Arrange the storage]
T51K P56F [G parameter: generator for pseudo-random numbers]
T47K P100F [M parameter: main routine + dependent subroutines]
T45K P398F [H parameter: storage for maze]
[The following once-only code can be overwritten by the maze data.]
T46K P398F [N parameter: library subroutine R4 to read data]
T50K P420F [X parameter: code executed at start-up only]
 
[=========== Executed at start-up, then overwritten ================]
E25K TX GK
[Enter with acc = 0]
[0] A@ GN [read 35-bit maze width into 0D]
AF TM [load and store width, assuming high word = 0]
[4] A4@ GN AF T1M [same for height]
[Initialize linear congruential generator for pseudo-random numbers]
[8] A8@ GN [read seed for LCG into 0D]
AD T4D [pass seed to LCG in 4D]
[12] A12@ GG [initialize LCG]
[Choose a random cell in the maze, for use later.]
[Also update storage of width and height.]
T4D [clear the whole of 4D, including sandwich bit]
AM U4F [load 17-bit width, pass to LCG as 35-bit value]
LD A2F TM [width to address field, add 1, store]
[20] A20@ G1G [call LCG, 0D := random in 0..(width - 1)]
AF T3M [save random to temporary store]
T4D A1M U4F [pass height of maze to LCG]
LD A2F T1M [height to address field, add 1, store]
[30] A30@ G1G [call LCG, 0D := random in 0..(height - 1)]
HF VM L64F L32F [acc := random*(width + 1)]
A3M LD A2F [add first random, shift to address, add 1]
T3M [save random index for use below]
HM V1M L64F L32F T2M [store (width+1)*(height+1)]
E65M [jump to main routine with acc = 0]
 
[================ Main routine ====================]
E25K TM GK
[Variables]
[0] PF [initially maze width; then (width + 1) in address field]
[1] PF [initially maze height; then (height + 1) in address field]
[List of up to four E orders to move N, S, W, E.]
[The first two are also used as temporary store at program start]
[2] PF
[3] PF PF PF
[6] TF [T order to store E order in list]
[Constants]
[7] T2@ [initial value of T order]
[8] TH [order to store into array{0}]
[9] AH [order to load from array{0}]
[10] C1H [order to collate with array{1};]
[also teleprinter colon in figures mode]
[11] MF [add to T order to make A order with same address]
[12] LF [add to T order to make C order with same address]
[Flags]
[13] K4096F [horizontal wall deleted, 10000 hex]
[14] IF [vertical wall deleted, 8000 hex]
[15] RF [no north neighbour, 4000 hex]
[16] WF [no south neighbour, 2000 hex]
[17] QF [no west neighbour, 1000 hex]
[18] P1024F [no east neighbour, 0800 hex]
[19] PD [cell visited, 0001 hex]
[20] V2047F [mask to clear visited bit]
[21] P1023F [mask to select EDSAC address field, which contains
index of previous cell for backtracking (0 if none).
[Teleprinter]
[22] #F [set figures mode]
[23] !F [space]
[24] @F [carriage return]
[25] &F [line feed]
 
[Subroutine called to set flag "no north neighbour" in cells along north edge,
similarly for east, south and west edges (order must be N, E, S, W).
Input: 4F = negative count of cells
5F = step in array index
6F = flag to be set]
[26] A3F T42@ [plant return link as usual]
A36@
G34@ [jump into middle of loop (since A < 0)]
[30] T4F [loop: update megative count]
A36@ A5F U36@
[34] S11@ T38@
[The following order initially refers to the NW corner cell.
First call leaves it referring to NE corner; second call to SE corner, etc.
Hence the need for calls to be in the order N, E, S, W.]
[36] A1H [planted; loaded as A1H]
A6F
[38] TF
A4F A2F [add 1 to negative count]
G30@ [if not yet 0, loop back]
[42] ZF
 
[Subroutine to test for unvisited neighbour of current cell in a given direction.
Input: 4F = E order to be added to list if unvisited neighbour is found
5F = step in array index to reach neighbour
6F = flag to test for no neighbour in this direction]
[43] A3F T64@ [plant return link as usual]
S6F H6F CH [if no neighbour then acc = 0, else acc < 0]
E64@ [exit if no neighbour]
TF A118@
A5F T55@
S19@ H19@
[55] CF E64@
TF A6@ U63@
A2F T6@
A4F [load jump to execute move]
[63] TF [store in list of moves]
[64] ZF [(planted) jump back to caller]
 
[Jump to here from once-only code, with acc = 0]
[Clear maze array]
[65] S2@
[66] TF [use 0F as loop counter]
[67] TH [planted, loaded as TH]
A67@ A2F T67@
AF A2F G66@
 
[Set flag "no north neighbour" in cells along northern edge]
S@ A2F T4F [count = width, pass in 4F]
A2F T5F [step in array index = 1, pass in 5F]
A15@ T6F [pass flag in 6F]
[81] A81@ G26@ [call subroutine to set flag]
 
[Repeat for east, south, west edges (must be in that order)]
S1@ A2F T4F A@ T5F A18@ T6F
[90] A90@ G26@
S@ A2F T4F S2F T5F A16@ T6F
[99] A99@ G26@
S1@ A2F T4F S@ T5F A17@ T6F
[108] A108@ G26@
 
[Start with the random cell chosen at program start (X parameter)]
A3@ A8@
[Loop: here acc = T order for current cell]
[112] U121@ [plant T order]
A12@ T118@ [make and plant C order, same address]
[Initialize storing in list of moves]
A7@ T6@
H20@
[118] CF A19@ [mark cell as visited]
UH [store flags of current cell in array{0} for easy access]
[121] TF [and also in the body of the array]
 
[If cell has unvisited North neighbour, add North to list of possible moves]
A177@ T4F
S@ T5F
A15@ T6F
[128] A128@ G43@
[Repeat for South, West, East neighbours]
A178@ T4F
A@ T5F
A16@ T6F
[136] A136@ G43@
A179@ T4F
S2F T5F
A17@ T6F
[144] A144@ G43@
A180@ T4F
A2F T5F
A18@ T6F
[152] A152@ G43@
 
[List now has 0..4 possible moves. If more than one, choose randomly.]
T4D [clear whole of 4D, including sandwich bit, for randomizer]
A6@ S7@ [address field := count of moves]
S2F G225@ [jump if none]
S2F G169@ [jump if one only]
RD A2F T4F [pass count, right-justified, to randomizer]
[164] A164@ G1G [0F := random value 0..(count - 1)]
AF LD E170@
[169] TF [only one move, must be at list{0}]
[170] A7@ A11@ T173@
[173] AF T176@
A121@ [common to all moves]
[176] EF [jump to move N,S,E, or W with acc = 0]
[177] E181@
[178] E190@
[179] E199@
[180] E208@
 
[Move North and delete horizontal wall]
[181] U186@ A11@ T184@
[184] AF A13@
[186] TF A121@ S@ E216@
 
[Move South and delete horizontal wall]
[190] A@ U196@ A11@ T194@
[194] AF A13@
[196] TF A196@ E216@
 
[Move West and delete vertical wall]
[199] U204@ A11@ T202@
[202] AF A14@
[204] TF A121@ S2F E216@
 
[Move East and delete vertical wall]
[208] A2F U214@ A11@ T212@
[212] AF A14@
[214] TF A214@
[fall through]
 
[Set index of current cell as previous to the new cell.
Here with T order for new cell in acc.]
[216] U222@ A11@ T221@
A121@ S8@
[221] AF
[222] TF
A222@ E112@
 
[No unvisited neighbour, backtrack if possible]
[225] TF [clear acc, needed]
H21@ CH [get index of previous cell (in address field)]
S2F [is it 0?]
G233@ [if so, maze is complete, jump to print]
A2F [restore]
A8@ [make T order]
E112@
 
[Print the maze created above]
[233] O22@ [set teleprinter to figures mode]
TF [clear acc]
S1@ T5F
[Outer 'loop and a half' with 5F as negative counter.
h + 1 rows for horizontal walls plus h rows for vertical walls]
[237]
[Print row for horizontal walls]
O296@ [print leading + sign]
S@ A2F [set inner loop counter in 4F]
H13@
[241] T4F [4F := negative count of horizontal walls per row]
S13@ [has current horizontal wall been deleted?]
[243] C1H [planted; loaded as C1H]
G247@ [jump if not]
A23@ G249@
[247] T1F [clear acc]
[248] A248@ [load hyphen (since A = minus in figures mode)]
[249] TF OF OF OF [print 3 spaces or 3 minus]
O296@ [print plus sign]
A243@ A2F T243@ [inc address in C order]
A4F A2F G241@
[Here with acc = 0 after printing one row]
A243@ A2F T243@ [skip next element in array]
O24@ O25@ [print CR, LF]
A5F A2F E295@
T5F
[Print row for vertical walls]
S@
T4F
H14@
[272] S14@
[273] C1H [planted; loaded as C1H]
G277@
A23@ G279@
[277] T1F [clear acc]
A10@ [colon in figures mode]
[279] TF OF [print colon or space]
A273@ A2F T273@ [update C order]
A4F A2F [inc negative counter for inner loop]
E292@ [jump out of loop if counter = 0]
T4F [update counter]
O23@ O23@ O23@ [print 3 spaces]
E272@
[Exit from inner loop for vertical walls]
[292] O24@ O25@ [print CR, LF]
E237@
[Exit]
[295] O22@ [dummy character to flush print buffer]
[296] ZF [(1) halt program (2) plus sign in figures mode]
 
[==================== Generator for pseudo-random numbers ===========]
[Linear congruential generator, same algorithm as Delphi 7 LCG
38 locations]
E25K TG
GKG10@G15@T2#ZPFT2ZI514DP257FT4#ZPFT4ZPDPFT6#ZPFT6ZPFRFA6#@S4#@
T6#@E25FE8ZPFT8ZPFPFA3FT14@A4DT8#@ZFA3FT37@H2#@V8#@L512FL512F
L1024FA4#@T8#@H6#@C8#@T8#@S4DG32@TDA8#@E35@H4DTDV8#@L1FTDZF
 
[==================== LIBRARY SUBROUTINE ============================]
E25K TN
[R4 Input of one signed integer.
22 storage locations; working positions 4, 5, and 6.]
GKA3FT21@T4DH6@E11@P5DJFT6FVDL4FA4DTDI4FA4FS5@G7@S5@G20@SDTDT6FEF
 
[===================================================================]
[The following, without the comments and white space, might have
been input from a separate tape.]
E25K TX GK
EZ [define entry point]
PF [acc = 0 on entry]
[Integers supplied by user: maze width, maze height, seed for LCG.
To be read by library subroutine R4; sign comes after value.]
12+8+987654321+
</syntaxhighlight>
{{out}}
<pre>
+---+---+---+---+---+---+---+---+---+---+---+---+
: : : : :
+ +---+ +---+---+ +---+---+ + +---+ +
: : : : : :
+ + +---+ +---+---+ +---+---+---+---+ +
: : : : : : :
+ + +---+---+ + +---+ +---+ + +---+
: : : : : : : :
+---+---+ + +---+---+ +---+ + +---+ +
: : : : : :
+ +---+---+---+ + +---+---+---+---+ + +
: : : : : : :
+ + +---+ +---+---+---+---+ + +---+ +
: : : : : :
+ +---+ +---+---+---+---+ +---+---+---+ +
: : :
+---+---+---+---+---+---+---+---+---+---+---+---+
</pre>
 
=={{header|EGL}}==
<langsyntaxhighlight EGLlang="egl">program MazeGen
 
// First and last columns/rows are "dead" cells. Makes generating
Line 2,247 ⟶ 3,294:
end
 
end</langsyntaxhighlight>
{{out|Output example (for 10x10 maze)}}
<pre>
Line 2,275 ⟶ 3,322:
=={{header|Elixir}}==
{{trans|D}}
<langsyntaxhighlight lang="elixir">defmodule Maze do
def generate(w, h) do
maze = (for i <- 1..w, j <- 1..h, into: Map.new, do: {{:vis, i, j}, true})
Line 2,305 ⟶ 3,352:
end
 
Maze.generate(20, 10)</langsyntaxhighlight>
 
{{out}}
Line 2,333 ⟶ 3,380:
 
=={{header|Elm}}==
<langsyntaxhighlight lang="elm">import Maybe as M
import Result as R
import Matrix
Line 2,581 ⟶ 3,628:
, update = update
, subscriptions = subscriptions
}</langsyntaxhighlight>
 
Link to live demo: http://dc25.github.io/mazeGenerationElm/
 
=={{header|Emacs Lisp}}==
{{libheader|cl-lib}}
 
<syntaxhighlight lang="lisp">(require 'cl-lib)
 
(cl-defstruct maze rows cols data)
 
(defmacro maze-pt (w r c)
`(+ (* (mod ,r (maze-rows ,w)) (maze-cols ,w))
(mod ,c (maze-cols ,w))))
 
(defmacro maze-ref (w r c)
`(aref (maze-data ,w) (maze-pt ,w ,r ,c)))
 
(defun new-maze (rows cols)
(setq rows (1+ rows)
cols (1+ cols))
(let ((m (make-maze :rows rows :cols cols :data (make-vector (* rows cols) nil))))
 
(dotimes (r rows)
(dotimes (c cols)
(setf (maze-ref m r c) (copy-sequence '(wall ceiling)))))
 
(dotimes (r rows)
(maze-set m r (1- cols) 'visited))
 
(dotimes (c cols)
(maze-set m (1- rows) c 'visited))
 
(maze-unset m 0 0 'ceiling) ;; Maze Entrance
(maze-unset m (1- rows) (- cols 2) 'ceiling) ;; Maze Exit
 
m))
 
(defun maze-is-set (maze r c v)
(member v (maze-ref maze r c)))
 
(defun maze-set (maze r c v)
(let ((cell (maze-ref maze r c)))
(when (not (member v cell))
(setf (maze-ref maze r c) (cons v cell)))))
 
(defun maze-unset (maze r c v)
(setf (maze-ref maze r c) (delete v (maze-ref maze r c))))
 
(defun print-maze (maze &optional marks)
(dotimes (r (1- (maze-rows maze)))
 
(dotimes (c (1- (maze-cols maze)))
(princ (if (maze-is-set maze r c 'ceiling) "+---" "+ ")))
(princ "+")
(terpri)
 
(dotimes (c (1- (maze-cols maze)))
(princ (if (maze-is-set maze r c 'wall) "|" " "))
(princ (if (member (cons r c) marks) " * " " ")))
(princ "|")
(terpri))
 
(dotimes (c (1- (maze-cols maze)))
(princ (if (maze-is-set maze (1- (maze-rows maze)) c 'ceiling) "+---" "+ ")))
(princ "+")
(terpri))
 
(defun shuffle (lst)
(sort lst (lambda (a b) (= 1 (random 2)))))
 
(defun to-visit (maze row col)
(let (unvisited)
(dolist (p '((0 . +1) (0 . -1) (+1 . 0) (-1 . 0)))
(let ((r (+ row (car p)))
(c (+ col (cdr p))))
(unless (maze-is-set maze r c 'visited)
(push (cons r c) unvisited))))
unvisited))
 
(defun make-passage (maze r1 c1 r2 c2)
(if (= r1 r2)
(if (< c1 c2)
(maze-unset maze r2 c2 'wall) ; right
(maze-unset maze r1 c1 'wall)) ; left
(if (< r1 r2)
(maze-unset maze r2 c2 'ceiling) ; up
(maze-unset maze r1 c1 'ceiling)))) ; down
 
(defun dig-maze (maze row col)
(let (backup
(run 0))
(maze-set maze row col 'visited)
(push (cons row col) backup)
(while backup
(setq run (1+ run))
(when (> run (/ (+ row col) 3))
(setq run 0)
(setq backup (shuffle backup)))
(setq row (caar backup)
col (cdar backup))
(let ((p (shuffle (to-visit maze row col))))
(if p
(let ((r (caar p))
(c (cdar p)))
(make-passage maze row col r c)
(maze-set maze r c 'visited)
(push (cons r c) backup))
(pop backup)
(setq backup (shuffle backup))
(setq run 0))))))
 
(defun generate (rows cols)
(let* ((m (new-maze rows cols)))
(dig-maze m (random rows) (random cols))
(print-maze m)))
 
(defun parse-ceilings (line)
(let (rtn
(i 1))
(while (< i (length line))
(push (eq ?- (elt line i)) rtn)
(setq i (+ i 4)))
(nreverse rtn)))
 
(defun parse-walls (line)
(let (rtn
(i 0))
(while (< i (length line))
(push (eq ?| (elt line i)) rtn)
(setq i (+ i 4)))
(nreverse rtn)))
 
(defun parse-maze (file-name)
(let ((rtn)
(lines (with-temp-buffer
(insert-file-contents-literally file-name)
(split-string (buffer-string) "\n" t))))
(while lines
(push (parse-ceilings (pop lines)) rtn)
(push (parse-walls (pop lines)) rtn))
(nreverse rtn)))
 
(defun read-maze (file-name)
(let* ((raw (parse-maze file-name))
(rows (1- (/ (length raw) 2)))
(cols (length (car raw)))
(maze (new-maze rows cols)))
(dotimes (r rows)
(let ((ceilings (pop raw)))
(dotimes (c cols)
(unless (pop ceilings)
(maze-unset maze r c 'ceiling))))
(let ((walls (pop raw)))
(dotimes (c cols)
(unless (pop walls)
(maze-unset maze r c 'wall)))))
maze))
 
(defun find-exits (maze row col)
(let (exits)
(dolist (p '((0 . +1) (0 . -1) (-1 . 0) (+1 . 0)))
(let ((r (+ row (car p)))
(c (+ col (cdr p))))
(unless
(cond
((equal p '(0 . +1)) (maze-is-set maze r c 'wall))
((equal p '(0 . -1)) (maze-is-set maze row col 'wall))
((equal p '(+1 . 0)) (maze-is-set maze r c 'ceiling))
((equal p '(-1 . 0)) (maze-is-set maze row col 'ceiling)))
(push (cons r c) exits))))
exits))
 
(defun drop-visited (maze points)
(let (not-visited)
(while points
(unless (maze-is-set maze (caar points) (cdar points) 'visited)
(push (car points) not-visited))
(pop points))
not-visited))
 
(defun solve-maze (maze)
(let (solution
(exit (cons (- (maze-rows maze) 2) (- (maze-cols maze) 2)))
(pt (cons 0 0)))
(while (not (equal pt exit))
(maze-set maze (car pt) (cdr pt) 'visited)
(let ((exits (drop-visited maze (find-exits maze (car pt) (cdr pt)))))
(if (null exits)
(setq pt (pop solution))
(push pt solution)
(setq pt (pop exits)))))
(push pt solution)))
 
(defun solve (file-name)
(let* ((maze (read-maze file-name))
(solution (solve-maze maze)))
(print-maze maze solution)))
 
(generate 20 20)</syntaxhighlight>
 
{{out}}
<pre style="height:35ex;overflow:scroll;">
+ +---+---+---+---+---+---+---+---+---+
| | | | |
+---+---+ + +---+---+ +---+---+ +
| | | | | | | |
+ + + + +---+ + + +---+ +
| | | | |
+---+---+---+---+---+ +---+---+ + +
| | | | | | | | |
+ +---+ + + +---+ + + + +
| | | | | | |
+ + + + +---+ + + +---+ +
| | | | | | |
+ + + +---+---+---+ +---+---+ +
| | | | | | |
+ + +---+---+ + + + + + +
| | | | | | |
+ + + +---+---+---+---+---+ + +
| | | | | |
+ +---+---+ + + +---+---+---+ +
| | | |
+---+---+---+---+---+---+---+---+---+ +
</pre>
 
=={{header|Erlang}}==
Line 2,589 ⟶ 3,858:
 
===Using multiple processes===
<syntaxhighlight lang="erlang">
<lang Erlang>
-module( maze ).
 
Line 2,733 ⟶ 4,002:
[Pid ! {Key, My_pid} || {_Position, Pid} <- Position_pids],
[{Position, read_receive(Pid, Key)} || {Position, Pid} <- Position_pids].
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,769 ⟶ 4,038:
 
Usage: start with generate_default/0. Use generate_MxN() to test other maze sizes.
<syntaxhighlight lang="erlang">
<lang Erlang>
-module(maze).
-record(maze, {g, m, n}).
Line 2,884 ⟶ 4,153:
generate_default() ->
generate_MxN(9, 9).
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,912 ⟶ 4,181:
=={{header|F_Sharp|F#}}==
Using mutable state in the form of 2D arrays:
<langsyntaxhighlight lang="fsharp">let rnd : int -> int =
let gen = new System.Random()
fun max -> gen.Next(max)
Line 2,968 ⟶ 4,237:
 
let m = new Maze(10,10)
m.Print()</langsyntaxhighlight>
{{out|Output example}}
<pre>+-+-+-+-+-+-+-+-+-+-+
Line 2,991 ⟶ 4,260:
| | |
+-+-+-+-+-+-+-+-+-+-+</pre>
 
=={{header|Forth}}==
{{works with|gforth|0.7.3}}
<br>
The solution uses the following library <tt>bits.fs</tt>, which implements bit-arrays:
<br>
<syntaxhighlight lang="forth">\ Bit Arrays
 
: to-bits ( c -- f f f f f f f f )
8 0 ?do
2 /mod
swap negate swap
loop
drop ;
 
: from-bits ( f f f f f f f f -- )
8 0 ?do
if [char] 1 emit else [char] 0 emit then
loop ;
 
: byte-bin. ( c -- )
to-bits from-bits space ;
 
: byte. ( c -- )
dup byte-bin.
dup 2 ['] u.r 16 base-execute space
3 u.r space ;
 
: bytes-for-bits ( u1 -- u2 )
8 /mod swap
0> if 1+ then ;
 
: bits ( u -- bits )
dup bytes-for-bits cell + \ u-bits u-bytes
dup allocate throw \ u-bits u-bytes addr
2dup swap erase nip \ u-bits addr
swap over ! ; \ addr
 
: free-bits ( bits -- )
free throw ;
 
: bits. ( bits -- )
dup @ bytes-for-bits \ addr bytes
swap cell+ swap \ addr+cell bytes
bounds ?do
i cr 20 ['] u.r 16 base-execute space
i c@ byte.
loop
cr ;
 
: bit-position ( u -- u-bit u-byte )
8 /mod ;
 
: assert-bit ( bits u -- bits u )
assert( 2dup swap @ < ) ;
 
: find-bit ( bits u1 -- addr u2 )
assert-bit
bit-position \ addr bit byte
rot \ bit byte addr
cell+ + swap ; \ addr' bit
: set-true ( addr u -- )
1 swap lshift over \ addr mask addr
c@ or swap c! ;
: set-false ( addr u -- )
1 swap lshift invert over \ addr mask addr
c@ and swap c! ;
 
: set ( addr u f -- )
if set-true else set-false then ;
: set-bit ( bits u f -- )
{ f }
find-bit f set ;
 
: set-bits-at-addr ( addr u-start u-stop f -- )
{ f }
1+ swap u+do
dup i f set
loop
drop ;
 
: byte-from-flag ( f -- c )
if 255 else 0 then ;
 
: set-bits { bits u-start u-stop f -- }
 
u-start u-stop > if exit then
 
bits u-start find-bit { addr-start bit-start }
bits u-stop find-bit { addr-stop bit-stop }
 
addr-start addr-stop = if
addr-start bit-start bit-stop f set-bits-at-addr
else
addr-start bit-start 7 f set-bits-at-addr
addr-start 1+ addr-stop addr-start - 1- f byte-from-flag fill
addr-stop 0 bit-stop f set-bits-at-addr
then ;
 
: check-bit ( addr u -- f )
find-bit \ addr bit
1 swap lshift swap \ mask addr
c@ and 0> ;
 
: resize-bits ( bits u -- bits )
over @ { old-size }
tuck bytes-for-bits cell + resize throw \ u-bits bits
2dup ! swap \ bits u-bits
dup old-size > if
over swap \ bits bits u-bits
1- old-size swap false set-bits
else
drop
then ;</syntaxhighlight>
<br>
The solution uses three bit-arrays: one to track whether a cell has been visited, one for "East"-walls (walls to the right of a cell) and one for "South"-walls (walls to the bottom of a cell).
<br>
<syntaxhighlight lang="forth">#! /usr/bin/gforth
\ Maze Generation
 
warnings off
 
require random.fs
require bits.fs
 
\ command line
 
: parse-number s>number? invert throw drop ;
: parse-width ." width : " next-arg parse-number dup . cr ;
: parse-height ." height: " next-arg parse-number dup . cr ;
: parse-args cr parse-width parse-height ;
 
parse-args constant HEIGHT constant WIDTH
 
2 CONSTANT AISLE-WIDTH
1 CONSTANT AISLE-HEIGHT
 
WIDTH HEIGHT * bits CONSTANT VISITED
WIDTH 1- HEIGHT * bits CONSTANT EAST-WALLS
HEIGHT 1- WIDTH * bits CONSTANT SOUTH-WALLS
 
0 CONSTANT NORTH
1 CONSTANT EAST
2 CONSTANT SOUTH
3 CONSTANT WEST
 
: visited-ix ( x y -- u ) WIDTH * + ;
: east-wall-ix ( x y -- u ) [ WIDTH 1- ] literal * + ;
: south-wall-ix ( x y -- u ) WIDTH * + ;
: visited! ( x y -- ) visited-ix VISITED swap TRUE set-bit ;
: visited? ( x y -- f ) visited-ix VISITED swap check-bit ;
: east-wall? ( x y -- f ) east-wall-ix EAST-WALLS swap check-bit ;
: south-wall? ( x y -- f ) south-wall-ix SOUTH-WALLS swap check-bit ;
: remove-east-wall ( x y -- ) east-wall-ix EAST-WALLS swap FALSE set-bit ;
: remove-south-wall ( x y -- ) south-wall-ix SOUTH-WALLS swap FALSE set-bit ;
 
: clear-visited ( -- ) VISITED 0 WIDTH 1- HEIGHT 1- visited-ix FALSE set-bits ;
: set-east-walls ( -- ) EAST-WALLS 0 WIDTH 2 - HEIGHT 1- east-wall-ix TRUE set-bits ;
: set-south-walls ( -- ) SOUTH-WALLS 0 WIDTH 1- HEIGHT 2 - south-wall-ix TRUE set-bits ;
: initial-pos ( -- x y ) WIDTH random HEIGHT random ;
: init-state ( -- -1 x y 0 ) clear-visited set-east-walls set-south-walls -1 initial-pos 2dup visited! 0 ;
 
: north-valid? ( x y -- f ) nip 0> ;
: east-valid? ( x y -- f ) drop [ WIDTH 1- ] literal < ;
: south-valid? ( x y -- f ) nip [ HEIGHT 1- ] literal < ;
: west-valid? ( x y -- f ) drop 0> ;
: dir-valid? ( x y d -- f ) case
NORTH of north-valid? endof
EAST of east-valid? endof
SOUTH of south-valid? endof
WEST of west-valid? endof
endcase ;
: move-north ( x y -- x' y' ) 1- ;
: move-east ( x y -- x' y' ) swap 1+ swap ;
: move-south ( x y -- x' y' ) 1+ ;
: move-west ( x y -- x' y' ) swap 1- swap ;
: move ( x y d -- x' y' ) case
NORTH of move-north endof
EAST of move-east endof
SOUTH of move-south endof
WEST of move-west endof
endcase ;
 
: remove-north-wall ( x y -- ) 1- remove-south-wall ;
: remove-west-wall ( x y -- ) swap 1- swap remove-east-wall ;
: remove-wall ( x y d -- ) case
NORTH of remove-north-wall endof
EAST of remove-east-wall endof
SOUTH of remove-south-wall endof
WEST of remove-west-wall endof
endcase ;
 
: dir? ( m d -- f ) 1 swap lshift and 0= ;
: dir! ( m d -- m' ) 1 swap lshift or ;
: pick-dir ( m -- m' d ) assert( dup $f <> ) begin 4 random 2dup dir? if tuck dir! swap exit then drop again ;
 
: update-state ( x y m d -- x' y' m' ) { x y m d }
x y d dir-valid? if
x y m
x y d move
2dup visited? if
2drop
else
2dup visited!
x y d remove-wall
0
then
else
x y m
then ;
 
: step ( x y m -- x' y' m' ) dup $f = if
drop 2drop \ backtracking!
else
pick-dir update-state
then ;
 
: build-maze ( -- ) init-state
begin
dup -1 <> while
step
repeat drop ;
 
: corner ( -- ) [char] + emit ;
: h-wall ( -- ) [char] - emit ;
: v-wall ( -- ) [char] | emit ;
: top-bottom. ( -- ) cr corner WIDTH 0 ?do AISLE-WIDTH 0 ?do h-wall loop corner loop ;
: empty ( -- ) AISLE-WIDTH 0 ?do space loop ;
: interior-cell ( x y -- ) empty east-wall? if v-wall else space then ;
: last-cell ( -- ) empty v-wall ;
: row ( y -- ) cr v-wall [ WIDTH 1- ] literal 0 ?do i over interior-cell loop drop last-cell ;
: last-row ( y -- ) cr WIDTH 0 ?do corner i over south-wall? if AISLE-WIDTH 0 ?do h-wall loop else empty then loop drop corner ;
: aisle ( y -- ) AISLE-HEIGHT 0 ?do dup row loop dup [ HEIGHT 1- ] literal < if last-row else drop then ;
: maze. ( -- ) top-bottom.
HEIGHT 0 ?do i aisle loop
top-bottom. ;
: maze ( width height -- ) build-maze maze. ;
 
maze cr bye</syntaxhighlight>
 
{{out}}<pre>
./maze-generation.fs 20 10
 
width : 20
height: 10
 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | |
+ +--+ + +--+ +--+--+ + +--+ +--+--+ + +--+--+ + +
| | | | | | | | | | |
+--+--+--+--+ +--+ +--+--+--+ + + +--+--+--+ + +--+ +
| | | | | | | | |
+ +--+--+--+--+--+--+--+ + + + +--+--+--+ +--+--+ +--+
| | | | | | |
+ +--+--+--+--+--+ + +--+--+--+--+ + + +--+--+ + + +
| | | | | | | | | | | | | |
+ + + + +--+ + + + +--+ +--+ + +--+ + + +--+ +
| | | | | | | | | | | |
+--+--+--+--+ + + + +--+ +--+--+--+--+--+--+ +--+--+ +
| | | | | | | | |
+ +--+ + +--+--+ +--+--+ + +--+ +--+ +--+--+--+ +--+
| | | | | | | | | | | | | |
+--+ + + + + + + +--+--+ + + + + + + + +--+ +
| | | | | | | | | | | | | | | |
+ +--+--+--+--+ + + + + + + + + +--+ +--+--+ + +
| | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
 
./maze-generation.fs 40 20
 
width : 40
height: 20
 
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | |
+ +--+ + +--+ +--+--+ + +--+ +--+--+ + + + +--+--+--+ + +--+ +--+ +--+ + + + +--+ + + + + +--+ +
| | | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+ +--+ +--+--+--+ + + +--+--+--+ + +--+ +--+--+--+ +--+--+--+--+--+ + +--+ + +--+ + +--+--+ +
| | | | | | | | | | | | | | | | | | |
+ + + + +--+--+--+ +--+ + + +--+--+--+ +--+--+ +--+ + + +--+--+--+--+--+ +--+--+ +--+--+ +--+ + +--+ +
| | | | | | | | | | | | | | | | | | |
+ +--+ +--+--+--+--+--+ + +--+--+ +--+ +--+--+ + + +--+ +--+ + +--+ + +--+--+ +--+--+--+--+ + +--+--+--+
| | | | | | | | | | | | | | | | | |
+ +--+--+ +--+--+--+--+--+ + + +--+ +--+--+ + +--+ + +--+--+--+ + +--+--+ + +--+--+ + + +--+--+--+--+ +
| | | | | | | | | | | | | | | | | | | | |
+ +--+ +--+ +--+--+ + +--+--+--+ + + + + +--+--+--+ +--+ +--+--+--+ + + +--+ + +--+--+--+--+--+--+ + +
| | | | | | | | | | | | | | | | |
+ + +--+--+--+--+--+ +--+ + + +--+--+--+ +--+ + + +--+ +--+--+ +--+--+ +--+--+--+ + + +--+--+--+ +--+ +
| | | | | | | | | | | | | | | | | | | | | |
+--+ + +--+--+--+ +--+--+--+--+--+ +--+ +--+ +--+ +--+--+ + + +--+--+ + +--+--+ + + + + +--+--+ + + +
| | | | | | | | | | | | | | | | | | | | | | |
+ +--+ + + + +--+ +--+ + +--+--+ +--+ + + + + +--+--+--+--+ + + +--+--+ + + +--+ +--+--+ +--+--+ +
| | | | | | | | | | | | | | | | | | | | | | |
+ +--+--+ + +--+ +--+ + + + + + +--+--+ + +--+ + +--+ + +--+ + + +--+--+ +--+--+--+--+ + + +--+--+
| | | | | | | | | | | | | | | | | | | | | | | | | |
+ + +--+ + + +--+ +--+ + + + + + +--+--+ + +--+ + +--+--+ + + +--+ + + + + +--+ +--+ +--+ + +
| | | | | | | | | | | | | | | | | | | | | | | | | | |
+ +--+ +--+--+--+ + + +--+--+ + +--+ +--+ + + + +--+ + + +--+ +--+--+--+--+--+--+ + +--+ +--+ + + +
| | | | | | | | | | | | | | | | | | | | |
+--+ + +--+ + + + +--+--+--+--+--+--+--+--+--+ + + +--+ + +--+--+--+ + + +--+ + +--+ + + +--+ +--+ +
| | | | | | | | | | | | | | | | | | | | | | | |
+ + +--+ +--+--+ + + +--+--+ + +--+--+--+ + + +--+ +--+ + +--+ + + +--+--+--+--+ +--+ +--+ +--+ + +
| | | | | | | | | | | | | | | | | | | | | | | |
+ +--+ + +--+ + + +--+--+ + + + +--+ + +--+ + +--+ + + +--+--+ +--+ +--+--+ +--+ +--+ + +--+--+ +
| | | | | | | | | | | | | | | | | | | | | |
+ +--+ +--+--+ + + + + + +--+--+--+ +--+--+--+--+ + + +--+--+--+--+--+--+--+ +--+--+ +--+ +--+--+ +--+--+
| | | | | | | | | | | | | | | | | | |
+ + +--+ +--+--+ +--+--+--+--+ + + +--+ +--+--+ +--+ +--+--+ + +--+ + +--+--+ +--+--+ +--+ + +--+--+ +
| | | | | | | | | | | | | | | | | | |
+ +--+--+--+ +--+--+ +--+ +--+--+--+ + + + +--+--+ +--+--+ + + + +--+ +--+ + +--+ + + +--+--+--+--+ +
| | | | | | | | | | | | | | | | | | | | | |
+ +--+--+ +--+--+--+--+ + + +--+ +--+--+--+--+ + + + + +--+--+--+ +--+ + +--+--+ + + +--+ +--+ + + +
| | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
 
</pre>
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">' version 04-12-2016
' compile with: fbc -s console
' when generating a big maze it's possible to run out of stack space
Line 3,121 ⟶ 4,710:
Loop
 
End</langsyntaxhighlight>
 
=={{header|Fōrmulæ}}==
 
{{FormulaeEntry|page=https://formulae.org/?script=examples/Maze_generation}}
 
'''Solution'''
 
[[File:Fōrmulæ - Maze generation 01.png]]
 
'''Test cases'''
 
[[File:Fōrmulæ - Maze generation 02.png]]
 
[[File:Fōrmulæ - Maze generation 03.png]]
 
[[File:Fōrmulæ - Maze generation 04.png]]
 
[[File:Fōrmulæ - Maze generation 05.png]]
 
[[File:Fōrmulæ - Maze generation 06.png]]
 
[[File:Fōrmulæ - Maze generation 07.png]]
 
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
_rows = 9
_cols = 11
_size = 32
_mgn = 32
 
_t = ( 1 << 0 )
_l = ( 1 << 1 )
_b = ( 1 << 2 )
_r = ( 1 << 3 )
_a = _t + _l + _b + _r
 
_window = 1
 
void local fn BuildWindow
window _window, @"FutureBasic - Maze generation", (0,0,_cols*_size+_mgn*2,_rows*_size+_mgn*2), NSWindowStyleMaskTitled
end fn
 
 
local fn CellAvailable( r as long, c as long ) as BOOL
if ( r < 0 || c < 0 || r >= _rows || c >= _cols ) then exit fn
if ( mda_integer(r,c) == _a ) then exit fn = YES
end fn = NO
 
 
void local fn ProcessCell( r as long, c as long )
long r1 = r, c1 = c, d(3), count, dir, opp
while ( 1 )
BlockZero( @d(0), sizeof(long) * 4 )
count = 0
if ( fn CellAvailable( r - 1, c ) ) then d(count) = _t : count++
if ( fn CellAvailable( r, c - 1 ) ) then d(count) = _l : count++
if ( fn CellAvailable( r + 1, c ) ) then d(count) = _b : count++
if ( fn CellAvailable( r, c + 1 ) ) then d(count) = _r : count++
if ( count == 0 ) then break
dir = d(rnd(count)-1)
mda(r,c) = @(mda_integer(r,c) - dir)
select ( dir )
case _t
r1 = r-1 : opp = _b
case _l
c1 = c-1 : opp = _r
case _b
r1 = r+1 : opp = _t
case _r
c1 = c+1 : opp = _l
end select
mda(r1,c1) = @(mda_integer(r1,c1) - opp)
fn ProcessCell( r1, c1 )
wend
end fn
 
 
void local fn DrawMaze
long r, c, x = _mgn, y = _mgn, value
pen 2,, NSLineCapStyleRound
for r = 0 to _rows - 1
for c = 0 to _cols - 1
value = mda(r,c)
if ( value & _t ) then line x, y to x + _size, y
if ( value & _l ) then line x, y to x, y + _size
if ( value & _b ) then line x, y + _size to x + _size, y + _size
if ( value & _r ) then line x + _size, y to x + _size, y + _size
x += _size
next
x = _mgn
y += _size
next
end fn
 
 
void local fn BuildMaze
long r, c
for r = 0 to _rows - 1
for c = 0 to _cols - 1
mda(r,c) = _a
next
next
random
r = rnd(_rows) - 1
c = rnd(_cols) - 1
fn ProcessCell( r, c )
fn DrawMaze
end fn
 
fn BuildWindow
fn BuildMaze
 
HandleEvents
</syntaxhighlight>
[[file:FutureBasic - Maze generation1.png]]
[[file:FutureBasic - Maze generation2.png]]
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import (
Line 3,242 ⟶ 4,955:
m.gen()
fmt.Print(m)
}</langsyntaxhighlight>
{{out}}
<pre>
Line 3,257 ⟶ 4,970:
 
=={{header|Haskell}}==
<langsyntaxhighlight lang="haskell">{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeFamilies #-}
 
import Control.Monad
import Control.Monad.ST
import Data.Array
import Data.Array.ST
(STArray, freeze, newArray, readArray, writeArray)
import Data.STRef
import Data.STRef (STRef, newSTRef, readSTRef, writeSTRef)
import System.Random
import System.Random (Random(..), getStdGen, StdGen)
import Control.Monad (forM_, unless)
import Control.Monad.ST (ST, stToIO)
import Data.Array (Array, (!), bounds)
import Data.Bool (bool)
 
rand
rand :: Random a => (a, a) -> STRef s StdGen -> ST s a
:: 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}
{ 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
Maze <$> liftM2 Maze (freeze rWalls) (<*> freeze bWalls)
where
where visit gen visited rWalls bWalls here = do
visit gen visited rWalls bWalls here = do
writeArray visited here True
writeArray visited here True
let ns = neighbors here
i <- rand (0, lengthlet ns -= 1)neighbors genhere
i <- forM_rand (ns0, !! i : take ilength ns ++ drop (i +- 1) ns) $ \there -> dogen
forM_ (ns !! i : take i ns ++ drop seen(i <-+ readArray1) visitedns) there$
\there unless seen $-> do
seen <- readArray removeWall herevisited there
unless seen $
visit gen visited rWalls bWalls there
where removeWall (x1,do y1) (x2, y2) =removeWall writeArrayhere there
visit gen visited (if x1 == x2 thenrWalls bWalls else rWalls)there
where
(min x1 x2, min y1 y2)
removeWall (x1, y1) (x2, y2) False=
writeArray (bool rWalls bWalls (x1 == x2)) (min x1 x2, min y1 y2) False
 
neighbors (x, y) =
(if x == 0 then [] elsebool [(x - 1, y)] [] (0 == )]x) ++
(if x == maxX then [] elsebool [(x + 1, y)] [] (maxX == )]x) ++
bool [(x, y - 1)] [] (if y0 == 0y) ++ then [] elsebool [(x, y -+ 1)]) ++[] (maxY == y)
maxX = width - 1
(if y == maxY then [] else [(x, y + 1)])
maxY = height - 1
 
maxXmazeArray = width - 1
newArray ((0, 0), (maxX, maxY)) =:: heightBool -> ST s (STArray s (Int, Int) 1Bool)
 
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
\y -> putStr "|"do
putStr "|"
forM_ [0 .. maxX] $ \x -> do
forM_ [0 .. maxX] putStr " "$
\x -> do
putStr $ if rWalls ! (x, y) then "|" else " "
putStrLn putStr " "
forM_ [0 .. maxX]putStr $ \xbool ->" " "|" (rWalls ! (x, doy))
putStrputStrLn "+"
forM_ [0 .. maxX] $
putStr $ if bWalls ! (x, y) then "---" else " "
putStrLn\x "+"-> do
where maxX = fst (snd $ bounds rWalls) putStr "+"
maxY = sndputStr $ bool " " "---" (sndbWalls $! bounds(x, rWallsy))
putStrLn "+"
where
maxX = fst (snd $ bounds rWalls)
maxY = snd (snd $ bounds rWalls)
 
main :: IO ()
main = getStdGen >>= stToIO . maze 11 8 >>= printMaze</lang>
main = getStdGen >>= stToIO . maze 11 8 >>= printMaze</syntaxhighlight>
{{out|Sample output}}
+---+---+---+---+---+---+---+---+---+---+---+
Line 3,347 ⟶ 5,068:
 
=={{header|Huginn}}==
<langsyntaxhighlight lang="huginn">import Algorithms as algo;
import Mathematics as math;
import Terminal as term;
Line 3,417 ⟶ 5,138:
maze = Maze( rows, cols );
print( "{}".format( maze ) );
}</langsyntaxhighlight>
 
=={{header|Icon}} and {{header|Unicon}}==
[[File:Mazegen-unicon-20x30-1321112170.gif|thumb|right|20x30 with two random openings]]
[[File:Mazegen-unicon-20x30-1321060467.gif|thumb|right|20x30 with opposite openings]]
<langsyntaxhighlight Iconlang="icon">link printf
 
procedure main(A) # generate rows x col maze
Line 3,514 ⟶ 5,235:
 
return mazeinfo(&window,maze,sprintf("maze-%dx%d-%d.gif",r,c,&now))
end</langsyntaxhighlight>
Note: The underlying maze structure (matrix) is uni-directional from the start
{{libheader|Icon Programming Library}}
Line 3,524 ⟶ 5,245:
{{trans|PicoLisp}}
But without any relevant grid library:
<langsyntaxhighlight lang="j">maze=:4 :0
assert.0<:n=.<:x*y
horiz=. 0$~x,y-1
Line 3,554 ⟶ 5,275:
'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
)</langsyntaxhighlight>
The result of <code>maze</code> 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 <code>maze</code> -- they are implicitly defined and are implemented in <code>display</code>. (The sequences of coordinates in <code>display</code> are the relative coordinates for the doors. For example, <code>2 1;2 2;2 3</code> are where we put spaces for each vertical door. The variable <code>text</code> is an ascii representation of the maze grid before the doors are placed.)
 
{{out|Example use (with ascii box drawing enabled)}}
<langsyntaxhighlight lang="j"> display 8 maze 11
+ +---+---+---+---+---+---+---+---+---+---+
| | | | |
Line 3,575 ⟶ 5,296:
+ + + + + + + + +---+ + +
| | | | |
+---+---+---+---+---+---+---+---+---+---+---+</langsyntaxhighlight>
 
=={{header|Java}}==
{{works with|Java|1.5+}}
<langsyntaxhighlight lang="java5">package org.rosettacode;
 
import java.util.Collections;
Line 3,669 ⟶ 5,390:
}
 
}</langsyntaxhighlight>
{{out}}
<pre>+---+---+---+---+---+---+---+---+---+---+
Line 3,695 ⟶ 5,416:
=={{header|JavaScript}}==
{{trans|J}}
<langsyntaxhighlight lang="javascript">function maze(x,y) {
var n=x*y-1;
if (n<0) {alert("illegal maze dimensions");return;}
Line 3,757 ⟶ 5,478:
}
return text.join('');
}</langsyntaxhighlight>
Variable meanings in function <code>maze</code>:
# <code>x</code>,<code>y</code> — dimensions of maze
Line 3,775 ⟶ 5,496:
 
{{out|Example use}}
<langsyntaxhighlight lang="html"><html><head><title></title></head><body><pre id="out"></pre></body></html>
<script type="text/javascript">
/* ABOVE CODE GOES HERE */
document.getElementById('out').innerHTML= display(maze(8,11));
</script></langsyntaxhighlight>
produced output:
<pre>+ +---+---+---+---+---+---+---+---+---+---+
Line 3,801 ⟶ 5,522:
 
For example, change replace the line <code>while (0<n) {</code> with:
<langsyntaxhighlight lang="javascript"> function step() {
if (0<n) {</langsyntaxhighlight>
And replace the closing brace for this while loop with:
<langsyntaxhighlight lang="javascript"> document.getElementById('out').innerHTML= display({x: x, y: y, horiz: horiz, verti: verti, here: here});
setTimeout(step, 100);
}
}
step();</langsyntaxhighlight>
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 <code>if (0 == k%4) {</code> with
<langsyntaxhighlight lang="javascript"> if (m.here && m.here[0]*2+1 == j && m.here[1]*4+2 == k)
line[k]= '#'
else if (0 == k%4) {</langsyntaxhighlight>
Note however that this leaves the final '#' in place on maze completion, and that the function <code>maze</code> no longer returns a result which represents a generated maze.
 
Note also that this display suggests an optimization. You can replace the line reading <code>path.push(here= next);</code> with:
<langsyntaxhighlight lang="javascript"> here= next;
if (1 < neighbors.length)
path.push(here);</langsyntaxhighlight>
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.
<langsyntaxhighlight lang="html"><html><head><title>Maze maker</title>
<style type="text/css">
table { border-collapse: collapse }
Line 3,936 ⟶ 5,657:
<a href="javascript:make_maze()">Generate</a>
<a id='solve' style='display:none' href='javascript:solve(); void(0)'>Solve</a>
</fieldset></form><table id='maze'/></body></html></langsyntaxhighlight>
 
=={{header|Node.jsjq}}==
'''Adapted from [[#Wren|Wren]]'''
{{trans|Javascript}}
 
'''Works with jq, the C implementation of jq'''
This difers of the basic Javascript in that in NodeJS we take advantage of the asynchronous behaviour. This code was modified from the plain Javascript section to make it '''Asynchronous''' and able to run under ''strict mode''.
 
'''Works with gojq, the Go implementation of jq'''
<lang javascript>
'use strict';
/*
* Imported from http://rosettacode.org/wiki/Maze_generation#JavaScript
* Added asynchronous behaviour to the maze generation.
*
* Port by sigmasoldier
*/
 
Since jq does not have a builtin PRNG,
/**
it is assumed that /dev/urandom is available.
* Generates the maze asynchronously.
An invocation such as the following may be used:
* @param {Number} x Width of the maze.
<pre>
* @param {Number} y Height of the maze.
< /dev/urandom tr -cd '0-9' | fold -w 1 | jq -Rcnr -f maze-generation.jq
* @returns {Promise} finished when resolved.
</pre>
*/
In the following, a maze is represented by a matrix, each of whose elements
function maze(x,y) {
is in turn a JSON object representing the bounding box:
return new Promise((resolve, reject) => {
$box["N"] is true iff the northern (top) edge is open, and similarly for the
let n=x*y-1;
other points of the compass.
if (n<0) {
reject(new Error(`illegal maze dimensions (${x} x ${y} < 1)`));
} else {
let horiz =[]; for (let j= 0; j<x+1; j++) horiz[j]= [];
let verti =[]; for (let j= 0; j<x+1; j++) verti[j]= [];
let here = [Math.floor(Math.random()*x), Math.floor(Math.random()*y)];
let path = [here];
let unvisited = [];
for (let j = 0; j<x+2; j++) {
unvisited[j] = [];
for (let 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) {
let potential = [[here[0]+1, here[1]], [here[0],here[1]+1],
[here[0]-1, here[1]], [here[0],here[1]-1]];
let neighbors = [];
for (let 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;
let 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();
}
resolve({x: x, y: y, horiz: horiz, verti: verti});
}
});
}
 
Note that in the following, the "walk" always starts at the (0,0)
/**
cell; this is just to make it clear that walk starts at the top left of the
* A mere way of generating text.
display.
* The text (Since it can be large) is generated in a non-blocking way.
<syntaxhighlight lang="jq">
* @param {Object} m Maze object.
# Output: a prn in range(0;$n) where $n is .
* @param {Stream} writeTo Optinally, include here a function to write to.
def prn:
* @returns {Promise} finished when the text is generated.
if . == 1 then 0
*/
else . as $n
function display(m, writeTo) {
| (($n-1)|tostring|length) as $w
return new Promise((resolve, reject) => {
| [limit($w; inputs)] | join("") | tonumber
let text = [];
| if . < $n then . else ($n | prn) end
for (let j= 0; j<m.x*2+1; j++) {
end;
let line = [];
if (0 == j%2)
for (let 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 (let 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');
}
const OUTPUT = text.join('');
if (typeof writeTo === 'function')
writeTo(OUTPUT);
resolve(OUTPUT);
});
}
 
# Input: an array
module.exports = {
def knuthShuffle:
maze: maze,
length as $n
display: display
| if $n <= 1 then .
}
else {i: $n, a: .}
</lang>
| until(.i == 0;
.i += -1
| (.i + 1 | prn) as $j
| .a[.i] as $t
| .a[.i] = .a[$j]
| .a[$j] = $t)
| .a
end;
 
# Compass is a JSON object {n,s,e,w} representing the four possible
{{out|Example use}}
# directions in which to move, i.e. to open a gate.
Image that you have a <code>main.js</code> file, to run then invoke in your shell <code>node main.js</code>
# For example, Compass.n corresponds to a move north (i.e. dx is 0, dy is 1),
Here is a basic example of what your main file should contain:
# and Compass.n.gates["N"] is true indicating that the "northern" gate should be opened.
def Compass:
{n: { gates: {"N": true}, dx: 0, dy: -1},
s: { gates: {"S": true}, dx: 0, dy: 1},
e: { gates: {"E": true}, dx: 1, dy: 0},
w: { gates: {"W": true}, dx:-1, dy: 0} }
| .n.opposite = .s
| .s.opposite = .n
| .e.opposite = .w
| .w.opposite = .e
;
 
# Produce a matrix representing an $x x $y maze.
<lang javascript>
# .[$i][$j] represents the box in row $i, column $j.
'use strict';
# Initially, all the gates of all the boxes are closed.
def MazeMatrix($x; $y):
[range(0;$x) | {} ] as $v | [range(0;$y) | $v];
 
# Input: a MazeMatrix
const maze = require('./maze.js');
def generate($cx; $cy):
const X = 20,
def interior($a; $upper): $a >= 0 and $a < $upper;
Y = 20;
length as $x
| (.[0]|length) as $y
| Compass as $Compass
| ([$Compass.n, $Compass.s, $Compass.e, $Compass.w] | knuthShuffle) as $directions
| reduce $directions[] as $v (.;
($cx + $v.dx) as $nx
| ($cy + $v.dy) as $ny
| if interior($nx; $x) and interior($ny; $y) and .[$nx][$ny] == {}
then .[$cx][$cy] += $v.gates
| .[$nx][$ny] += $v.opposite.gates
| generate($nx; $ny)
end );
 
# Input: a MazeMatrix
console.log(`Generating a maze of ${X} x ${Y}...`);
def display:
const origin = new Date().getTime();
. as $maze
| ($maze|length) as $x
| ($maze[0]|length) as $y
| ( range(0;$y) as $i
# draw the north edge
| ([range(0;$x) as $j
| if $maze[$j][$i]["N"] then "+ " else "+---" end] | join("")) + "+",
# draw the west edge
([range(0;$x) as $j
| if $maze[$j][$i]["W"] then " " else "| " end] | join("")) + "|" ),
# draw the bottom line
($x * "+---") + "+"
;
 
# Start the walk at the top left
maze.maze(X, Y).then((m) => {
def amaze($x;$y):
const time = new Date().getTime() - origin;
MazeMatrix($x; $y)
console.log(`Done in ${time <= 1000 ? time+'ms' : Math.round(time/1000)+'s'}!`);
| generate(0; 0)
maze.display(m, console.log); //Here you can pass a given stream (ie: stream) and it's write function;
| display;
//An example could be: maze.display(m, stream.write);
}, (err) => console.error(err));
 
# Example
</lang>
amaze(4; 5);
 
</syntaxhighlight>
Sample Output:
{{output}}
Example output:
<pre>
+---+---+---+---+---+
$ node main.js
| | |
Generating a maze of 10 x 10...
+---+ + +---+ +
Done in 3ms!
| | | | |
+ +---+---+---+---+---+---+---+---+---+
|+ + + + + | |+
+| +---+---+| +---+| +| +---+| + +|
|+ |+ |+---+ + | | | | |+
+| + + +---+ +---+---+ +| + +|
+---+---+---+---+---+
| | | | | | | | |
+ + + + +---+---+ + + +---+
| | | | | | |
+---+ + + +---+---+ +---+---+ +
| | | | | | |
+---+---+ +---+ + +---+ + + +
| | | | | | | |
+ +---+---+ + + + +---+ + +
| | | | |
+---+---+---+---+ +---+ +---+---+ +
| | | | |
+ +---+ + +---+---+---+---+ + +
| | | | | |
+---+ + + +---+ +---+---+---+ +
| | |
+---+---+---+---+---+---+---+---+---+---+
</pre>
 
Line 4,100 ⟶ 5,784:
 
'''Generating functions'''
<syntaxhighlight lang="julia">using Random
<lang julia>check(bound::Vector) = cell -> all([1, 1] .≤ cell .≤ bound)
check(bound::Vector) = cell -> all([1, 1] .≤ cell .≤ bound)
neighbors(cell::Vector, bound::Vector, step::Int=2) =
filter(check(bound), map(dir -> cell + step * dir, [[0, 1], [-1, 0], [0, -1], [1, 0]]))
Line 4,106 ⟶ 5,791:
function walk(maze::Matrix, nxtcell::Vector, visited::Vector=[])
push!(visited, nxtcell)
for neigh in shuffle(neighbors(nxtcell, collect(size(maze))))
if neigh ∉ visited
maze[round.(Int, (nxtcell + neigh) / 2)...] = 0
Line 4,118 ⟶ 5,803:
firstcell = 2 * [rand(1:w), rand(1:h)]
return walk(maze, firstcell)
end</langsyntaxhighlight>
 
'''Printing functions'''
<langsyntaxhighlight lang="julia">pprint(matrix) = for i = 1:size(matrix, 1) println(join(matrix[i, :])) end
function printmaze(maze)
walls = split("╹ ╸ ┛ ╺ ┗ ━ ┻ ╻ ┃ ┓ ┫ ┏ ┣ ┳ ╋")
Line 4,134 ⟶ 5,819:
 
printmaze(maze(10, 10))
</syntaxhighlight>
</lang>
 
{{out}}
Line 4,151 ⟶ 5,836:
=={{header|Kotlin}}==
{{trans|Java}}
<langsyntaxhighlight lang="scala">import java.util.*
 
class MazeGenerator(val x: Int, val y: Int) {
Line 4,217 ⟶ 5,902:
display()
}
}</langsyntaxhighlight>
 
=={{header|Lua}}==
{{Works with|Lua|5.1}}
<syntaxhighlight lang="lua">
<lang Lua>
math.randomseed( os.time() )
 
Line 4,295 ⟶ 5,980:
 
print(make_maze())
</syntaxhighlight>
</lang>
{{Out}}
<pre>#################################
Line 4,314 ⟶ 5,999:
# # # # # #
#################################</pre>
 
 
=={{header|M2000 Interpreter}}==
Line 4,331 ⟶ 6,015:
INT((currentx% + oldx%) / 2) return a double, because has 2 as double so we get (integer+integer)/double or integer/double or double. Int(0.5) return.
 
<syntaxhighlight lang="m2000 interpreter">
<lang M2000 Interpreter>
Module Maze {
width% = 40
Line 4,388 ⟶ 6,072:
}
Maze
</syntaxhighlight>
</lang>
 
===Depth-first search===
Line 4,398 ⟶ 6,082:
 
 
<syntaxhighlight lang="m2000 interpreter">
<lang M2000 Interpreter>
Module Maze2 {
\\ depth-first search
Line 4,428 ⟶ 6,112:
status--
forchoose=forchoose#val(random(0,status))
if status>0 then Push forchoose
OpenDoor(!Entry, !forchoose)
Rem : ShowMaze()
Line 4,469 ⟶ 6,153:
}
Maze2
</syntaxhighlight>
</lang>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight lang="mathematica">MazeGraphics[m_, n_] :=
Block[{$RecursionLimit = Infinity,
unvisited = Tuples[Range /@ {m, n}], maze},
Line 4,486 ⟶ 6,170:
RandomSample@{# + {0, 1}, # - {0, 1}, # + {1, 0}, # - {1,
0}}}]} &@RandomChoice@unvisited; maze];
maze = MazeGraphics[21, 13]</langsyntaxhighlight>
{{Out}}
[[File:MathematicaMazeGraphics.png]]
Line 4,492 ⟶ 6,176:
{{Works with|Mathematica|9.0}}
Here I generate a maze as a graph. Vertices of the graph are cells and edges of the graph are removed walls. This version is mush faster and is convenient to solve.
<langsyntaxhighlight lang="mathematica">MazeGraph[m_, n_] :=
Block[{$RecursionLimit = Infinity, grid = GridGraph[{m, n}],
unvisitedQ}, unvisitedQ[_] := True;
Line 4,502 ⟶ 6,186:
RandomChoice@VertexList@grid][[2, 1]],
GraphLayout -> {"GridEmbedding", "Dimension" -> {m, n}}]];
maze = MazeGraph[13, 21]</langsyntaxhighlight>
{{Out}}
[[File:MathematicaMazeGraph.png]]
 
=={{header|MATLAB}} / {{header|Octave}}==
<langsyntaxhighlight Matlablang="matlab">function M = makeMaze(n)
showProgress = false;
 
Line 4,559 ⟶ 6,243:
 
image(M-VISITED);
axis equal off;</langsyntaxhighlight>
 
=={{header|Nim}}==
{{trans|D}}
<langsyntaxhighlight lang="nim">import mathrandom, sequtils, strutils
randomize()
 
template newSeqWith(len: int, init: expr): expr =
var result {.gensym.} = newSeq[type(init)](len)
for i in 0 .. <len:
result[i] = init
result
 
iterator randomCover[T](xs: openarray[T]): T =
var js = toSeq 0..xs.high
for i in countdown(js.high, 0):
let j = random(i + 1)
swap(js[i], js[j])
for j in js:
Line 4,589 ⟶ 6,267:
ver = newSeqWith(h, newSeqWith(w, "| ") & "|")
 
proc walk(x, y: int) =
vis[y][x] = true
for p in [[x-1,y], [x,y+1], [x+1,y], [x,y-1]].randomCover:
if p[0] notin 0 .. < w or p[1] notin 0 .. < h or vis[p[1]][p[0]]: continue
if p[0] == x: hor[max(y, p[1])][x] = "+ "
if p[1] == y: ver[y][max(x, p[0])] = " "
walk p[0], p[1]
 
walk randomrand(0..<w), randomrand(0..<h)
for a,b in zip(hor, ver & @[""]).items:
echo join(a & "+\n" & b)</langsyntaxhighlight>
 
{{out}}
Example output:
<pre>+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Line 4,622 ⟶ 6,302:
| | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</pre>
 
=={{header|Node.js}}==
{{trans|Javascript}}
 
This difers of the basic Javascript in that in NodeJS we take advantage of the asynchronous behaviour. This code was modified from the plain Javascript section to make it '''Asynchronous''' and able to run under ''strict mode''.
 
<syntaxhighlight lang="javascript">
'use strict';
/*
* Imported from http://rosettacode.org/wiki/Maze_generation#JavaScript
* Added asynchronous behaviour to the maze generation.
*
* Port by sigmasoldier
*/
 
/**
* Generates the maze asynchronously.
* @param {Number} x Width of the maze.
* @param {Number} y Height of the maze.
* @returns {Promise} finished when resolved.
*/
function maze(x,y) {
return new Promise((resolve, reject) => {
let n=x*y-1;
if (n<0) {
reject(new Error(`illegal maze dimensions (${x} x ${y} < 1)`));
} else {
let horiz =[]; for (let j= 0; j<x+1; j++) horiz[j]= [];
let verti =[]; for (let j= 0; j<x+1; j++) verti[j]= [];
let here = [Math.floor(Math.random()*x), Math.floor(Math.random()*y)];
let path = [here];
let unvisited = [];
for (let j = 0; j<x+2; j++) {
unvisited[j] = [];
for (let 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) {
let potential = [[here[0]+1, here[1]], [here[0],here[1]+1],
[here[0]-1, here[1]], [here[0],here[1]-1]];
let neighbors = [];
for (let 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;
let 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();
}
resolve({x: x, y: y, horiz: horiz, verti: verti});
}
});
}
 
/**
* A mere way of generating text.
* The text (Since it can be large) is generated in a non-blocking way.
* @param {Object} m Maze object.
* @param {Stream} writeTo Optinally, include here a function to write to.
* @returns {Promise} finished when the text is generated.
*/
function display(m, writeTo) {
return new Promise((resolve, reject) => {
let text = [];
for (let j= 0; j<m.x*2+1; j++) {
let line = [];
if (0 == j%2)
for (let 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 (let 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');
}
const OUTPUT = text.join('');
if (typeof writeTo === 'function')
writeTo(OUTPUT);
resolve(OUTPUT);
});
}
 
module.exports = {
maze: maze,
display: display
}
</syntaxhighlight>
 
{{out|Example use}}
Image that you have a <code>main.js</code> file, to run then invoke in your shell <code>node main.js</code>
Here is a basic example of what your main file should contain:
 
<syntaxhighlight lang="javascript">
'use strict';
 
const maze = require('./maze.js');
const X = 20,
Y = 20;
 
console.log(`Generating a maze of ${X} x ${Y}...`);
const origin = new Date().getTime();
 
maze.maze(X, Y).then((m) => {
const time = new Date().getTime() - origin;
console.log(`Done in ${time <= 1000 ? time+'ms' : Math.round(time/1000)+'s'}!`);
maze.display(m, console.log); //Here you can pass a given stream (ie: stream) and it's write function;
//An example could be: maze.display(m, stream.write);
}, (err) => console.error(err));
 
</syntaxhighlight>
 
Sample Output:
<pre>
$ node main.js
Generating a maze of 10 x 10...
Done in 3ms!
+ +---+---+---+---+---+---+---+---+---+
| | |
+ +---+---+ +---+ + +---+ + +
| | | | | | | |
+ + + +---+ +---+---+ + + +
| | | | | | | | |
+ + + + +---+---+ + + +---+
| | | | | | |
+---+ + + +---+---+ +---+---+ +
| | | | | | |
+---+---+ +---+ + +---+ + + +
| | | | | | | |
+ +---+---+ + + + +---+ + +
| | | | |
+---+---+---+---+ +---+ +---+---+ +
| | | | |
+ +---+ + +---+---+---+---+ + +
| | | | | |
+---+ + + +---+ +---+---+---+ +
| | |
+---+---+---+---+---+---+---+---+---+---+
</pre>
 
=={{header|OCaml}}==
<langsyntaxhighlight lang="ocaml">let seen = Hashtbl.create 7
let mark t = Hashtbl.add seen t true
let marked t = Hashtbl.mem seen t
Line 4,670 ⟶ 6,508:
Random.self_init();
visit (Random.int nx, Random.int ny);
print_maze ();</langsyntaxhighlight>
Output from 'ocaml gen_maze.ml 10 10':<pre>+---+---+---+---+---+---+---+---+---+---+
| | | |
Line 4,695 ⟶ 6,533:
 
=={{header|Ol}}==
<langsyntaxhighlight lang="scheme">
; maze generation
(import (otus random!))
Line 4,733 ⟶ 6,571:
(loop nx ny)))
(try))))))
</syntaxhighlight>
</lang>
<langsyntaxhighlight lang="scheme">
; maze printing:
(display "+")
Line 4,757 ⟶ 6,595:
maze)
(print)
</syntaxhighlight>
</lang>
{{out|Sample 30 x 8 output}}
<pre>+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Line 4,778 ⟶ 6,616:
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">use List::Util 'max';
 
my ($w, $h) = @ARGV;
Line 4,813 ⟶ 6,651:
print @{$hor[$_]}, "+\n";
print @{$ver[$_]}, "|\n" if $_ < $h;
}</langsyntaxhighlight>
Run as <code>maze.pl [width] [height]</code> or use default dimensions.
{{out|Sample 4 x 1 output}}
Line 4,819 ⟶ 6,657:
| |
+--+--+--+--+</pre>
 
=={{header|Perl 6}}==
{{works with|rakudo|2015-09-22}}
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>constant mapping = :OPEN(' '),
:N< ╵ >,
:E< ╶ >,
:NE< └ >,
:S< ╷ >,
:NS< │ >,
:ES< ┌ >,
:NES< ├ >,
:W< ╴ >,
:NW< ┘ >,
:EW< ─ >,
:NEW< ┴ >,
:SW< ┐ >,
:NSW< ┤ >,
:ESW< ┬ >,
:NESW< ┼ >,
:TODO< x >,
:TRIED< · >;
enum Sym (mapping.map: *.key);
my @ch = mapping.map: *.value;
enum Direction <DeadEnd Up Right Down Left>;
sub gen_maze ( $X,
$Y,
$start_x = (^$X).pick * 2 + 1,
$start_y = (^$Y).pick * 2 + 1 )
{
my @maze;
push @maze, $[ flat ES, -N, (ESW, EW) xx $X - 1, SW ];
push @maze, $[ flat (NS, TODO) xx $X, NS ];
for 1 ..^ $Y {
push @maze, $[ flat NES, EW, (NESW, EW) xx $X - 1, NSW ];
push @maze, $[ flat (NS, TODO) xx $X, NS ];
}
push @maze, $[ flat NE, (EW, NEW) xx $X - 1, -NS, NW ];
@maze[$start_y][$start_x] = OPEN;
my @stack;
my $current = [$start_x, $start_y];
loop {
if my $dir = pick_direction( $current ) {
@stack.push: $current;
$current = move( $dir, $current );
}
else {
last unless @stack;
$current = @stack.pop;
}
}
return @maze;
sub pick_direction([$x,$y]) {
my @neighbors =
(Up if @maze[$y - 2][$x]),
(Down if @maze[$y + 2][$x]),
(Left if @maze[$y][$x - 2]),
(Right if @maze[$y][$x + 2]);
@neighbors.pick or DeadEnd;
}
sub move ($dir, @cur) {
my ($x,$y) = @cur;
given $dir {
when Up { @maze[--$y][$x] = OPEN; @maze[$y][$x-1] -= E; @maze[$y--][$x+1] -= W; }
when Down { @maze[++$y][$x] = OPEN; @maze[$y][$x-1] -= E; @maze[$y++][$x+1] -= W; }
when Left { @maze[$y][--$x] = OPEN; @maze[$y-1][$x] -= S; @maze[$y+1][$x--] -= N; }
when Right { @maze[$y][++$x] = OPEN; @maze[$y-1][$x] -= S; @maze[$y+1][$x++] -= N; }
}
@maze[$y][$x] = 0;
[$x,$y];
}
}
sub display (@maze) {
for @maze -> @y {
for @y.rotor(2) -> ($w, $c) {
print @ch[abs $w];
if $c >= 0 { print @ch[$c] x 3 }
else { print ' ', @ch[abs $c], ' ' }
}
say @ch[@y[*-1]];
}
}
display gen_maze( 29, 19 );</lang>
{{out}}
<small><pre>┌ ╵ ────────────────────────────┬───────────────────────────────────────────┬───────────┬───────────────────────────┐
│ │ │ │ │
│ ╶───────────┬───────────┐ │ ┌───────────────────────╴ ┌───────┐ ├───╴ ╷ │ ┌───────────┬───┬───╴ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │
│ ┌───────┐ ╵ ┌───┐ ├───┘ │ ┌───────────┬───────────┤ ╶───┤ │ ╶───┴───┤ │ ┌───┐ │ │ ╶───┤
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ └───╴ └───────┤ │ ╵ ┌───┘ │ ╷ ╶───┤ ┌───┐ │ ╷ │ ├───────╴ │ ╵ │ │ │ └───┐ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├───────┬───────┐ │ ├───────┤ ╶───┤ └───┐ ╵ │ │ ╵ │ ╵ │ ┌───┐ └───┬───┘ │ │ ╷ │ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ ╶───┤ ╷ ╵ │ ╵ ╷ └───┐ ├───┐ ├───────┤ └───────┴───────┘ │ └───┐ └───╴ │ ╵ ├───┘ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├───╴ │ ├───────┴───┐ ├───╴ │ │ │ ╵ ╷ └───┐ ╶───┬───────┬───┘ ┌───┴───────╴ │ ┌───┘ ╷ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ ╷ │ │ ╶───┐ └───┤ ╷ │ │ └───────┴───┐ └───╴ │ ╷ ╵ ╷ ╵ ╶───────┬───┤ │ ┌───┴───┤
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ │ │ │ ╷ ├───╴ ╵ │ │ │ ┌───────┐ └───────────┤ └───┬───┴───────────┐ ╵ │ │ ╵ ╷ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ │ │ ├───┘ │ ┌───────┴───┘ │ ╵ ┌───┴───────╴ ╷ ├───┐ │ ╶───────┐ └───┐ │ └───┬───┘ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ └───┘ │ ┌───┘ │ ┌───┬───────┼───╴ │ ╶───┬───────┤ ╵ │ └───┬───╴ ├───┐ │ └───┐ │ ╷ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ ┌───────┘ ├───────┤ │ ╵ ╷ │ ┌───┴───┐ │ ╶───┘ ┌───┴───╴ │ ┌───┘ │ │ ┌───┘ │ │ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ └───╴ ╷ │ ╷ │ └───┐ │ ╵ │ ╷ ╵ ├───────┐ │ ╶───────┤ └───┐ │ └───┤ ┌───┘ │ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├───────────┤ │ │ └───╴ │ └───────┤ └───────┘ ╷ └───┴───┬───╴ ├───╴ │ └───┐ │ │ ╶───┴───┤
│ │ │ │ │ │ │ │ │ │ │ │ │ │
│ ┌───╴ │ │ ├───╴ ┌───┴───────┬───┴───┐ ┌───────┴───────┐ ╵ ┌───┤ ╶───┤ ╷ │ ╵ └───┬───╴ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ │ ╶───┘ │ │ ╶───┤ ╶───┐ ╵ ╷ │ └───╴ ┌───╴ └───────┘ ├───╴ │ ├───┴───────┬───┘ ╷ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ ├───────┬───┘ ├───────┴───┐ ├───────┤ └───────────┤ ┌───────────┐ │ ┌───┘ │ ╶───┐ ╵ ┌───┘ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ └───╴ │ ╷ │ ╶───┐ ╵ │ ╷ └───────────┐ │ │ ┌───┐ └───┘ │ ╶───┴───┐ └───────┴───────┤
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├───────╴ │ └───┴───╴ └───────┴───┴───────────╴ │ └───┘ ╵ └───────────┴───╴ ╷ └───────────────┐ │
│ │ │ │ │ │
└───────────┴───────────────────────────────────────────┴───────────────────────────────────┴───────────────────┴ │ ┘</pre></small>
 
=={{header|Phix}}==
Adapted a couple of techniques from the excellent D submission<br>
(however this holds the grid as an array of complete lines)
<!--<syntaxhighlight lang="phix">(phixonline)-->
<lang Phix>--
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
-- grid is eg for w=3,h=2: {"+---+---+---+", -- ("wall")
<span style="color: #000080;font-style:italic;">--
-- "| ? | ? | ? |", -- ("cell")
-- grid is eg for w=3,h=2: {"+---+---+---+", -- ("wall")
-- "| ? | ? | ? |", -- ("cell")
-- "+---+---+---+", -- ("wall")
-- "| ? | ? | ? |"}, -- (for a trailing-- \n("cell")
-- "+---+---+---+", -- ("wall")
--
-- ""} -- (for a trailing \n)
-- note those ?(x,y) are at [y*2][x*4-1], and we navigate
--
-- using y=2..2*h (+/-2), x=3..w*4-1 (+/-4) directly.
-- note those ?(x,y) are at [y*2][x*4-1], and we navigate
--
-- using y=2..2*h (+/-2), x=3..w*4-1 (+/-4) directly.
constant w = 11, h = 8
--</span>
 
<span style="color: #008080;">constant</span> <span style="color: #000000;">w</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">8</span>
sequence wall = join(repeat("+",w+1),"---")&"\n",
cell = join(repeat("|",w+1)," ? ")&"\n",
<span style="color: #004080;">sequence</span> <span style="color: #000000;">wall</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">w</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"---"</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">,</span>
grid = split(join(repeat(wall,h+1),cell),'\n')
<span style="color: #000000;">cell</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"|"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">w</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #008000;">" ? "</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">,</span>
 
<span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wall</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">cell</span><span style="color: #0000FF;">),</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span>
procedure amaze(integer x, integer y)
grid[y][x] = ' ' -- mark cell visited
<span style="color: #008080;">procedure</span> <span style="color: #000000;">amaze</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">)</span>
sequence p = shuffle({{x-4,y},{x,y+2},{x+4,y},{x,y-2}})
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">][</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span> <span style="color: #000080;font-style:italic;">-- mark cell visited</span>
for i=1 to length(p) do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}})</span>
integer {nx,ny} = p[i]
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
if nx>1 and nx<w*4 and ny>1 and ny<=2*h and grid[ny][nx]='?' then
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
integer mx = (x+nx)/2
<span style="color: #008080;">if</span> <span style="color: #000000;">nx</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">nx</span><span style="color: #0000FF;"><</span><span style="color: #000000;">w</span><span style="color: #0000FF;">*</span><span style="color: #000000;">4</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ny</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ny</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">h</span> <span style="color: #008080;">and</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">][</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'?'</span> <span style="color: #008080;">then</span>
grid[(y+ny)/2][mx-1..mx+1] = ' ' -- knock down wall
<span style="color: #004080;">integer</span> <span style="color: #000000;">mx</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span>
amaze(nx,ny)
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">][</span><span style="color: #000000;">mx</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">mx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span> <span style="color: #000080;font-style:italic;">-- knock down wall</span>
end if
<span style="color: #000000;">amaze</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
function heads()
return rand(2)=1 -- 50:50 true(1)/false(0)
<span style="color: #008080;">function</span> <span style="color: #000000;">heads</span><span style="color: #0000FF;">()</span>
end function
<span style="color: #008080;">return</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">-- 50:50 true(1)/false(0)</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
integer {x,y} = {(rand(w)*4)-1,rand(h)*2}
amaze(x,y)
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{(</span><span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">4</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}</span>
-- mark start pos
<span style="color: #000000;">amaze</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">)</span>
grid[y][x] = '*'
<span style="color: #000080;font-style:italic;">-- mark start pos</span>
-- add a random door (heads=rhs/lhs, tails=top/btm)
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">][</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'*'</span>
if heads() then
<span style="color: #000080;font-style:italic;">-- add a random door (heads=rhs/lhs, tails=top/btm)</span>
grid[rand(h)*2][heads()*w*4-1] = ' '
<span style="color: #008080;">if</span> <span style="color: #000000;">heads</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">then</span>
else
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">][</span><span style="color: #000000;">heads</span><span style="color: #0000FF;">()*</span><span style="color: #000000;">w</span><span style="color: #0000FF;">*</span><span style="color: #000000;">4</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span>
x = rand(w)*4-1
<span style="color: #008080;">else</span>
grid[heads()*h*2+1][x-1..x+1] = ' '
<span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">4</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
end if
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">heads</span><span style="color: #0000FF;">()*</span><span style="color: #000000;">h</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">x</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span>
puts(1,join(grid,'\n'))</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">))</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 5,020 ⟶ 6,730:
+---+---+---+---+---+---+---+---+---+---+---+
</pre>
 
 
=={{header|PHP}}==
Code inspired by the D and Python solutions (with the implementation of backtracking, or sometimes it wouldn't work). Could have been done procedurally or fully OO (with cells as class too). A debug flag has been provided to allow following the inner workings. Works on PHP > 5.6.
<langsyntaxhighlight lang="php"><?php
class Maze
{
Line 5,171 ⟶ 6,880:
 
$maze = new Maze(10,10);
$maze->printOut();</langsyntaxhighlight>
{{out}}
<pre>
Line 5,195 ⟶ 6,904:
| | | |
+---+---+---+---+---+---+---+---+---+---+
</pre>
 
=={{header|Picat}}==
<syntaxhighlight lang="picat">main =>
gen_maze(8,8).
 
main([RStr,CStr]) =>
MaxR = to_int(RStr),
MaxC = to_int(CStr),
gen_maze(MaxR,MaxC).
 
gen_maze(MaxR,MaxC) =>
Maze = new_array(MaxR,MaxC),
foreach (R in 1..MaxR, C in 1..MaxC)
Maze[R,C] = 0
end,
gen_maze(Maze,MaxR,MaxC,1,1),
display_maze(Maze,MaxR,MaxC).
 
gen_maze(Maze,MaxR,MaxC,R,C) =>
Dirs = shuffle([left, right, up, down]),
foreach (Dir in Dirs)
dir(Dir,Dr,Dc,B,OB),
R1 := R+Dr,
C1 := C+Dc,
if (R1 >= 1 && R1 =< MaxR && C1 >= 1 && C1 =< MaxC && Maze[R1,C1] == 0) then
Maze[R,C] := Maze[R,C] \/ B,
Maze[R1,C1] := Maze[R1,C1] \/ OB,
gen_maze(Maze,MaxR,MaxC,R1,C1)
end
end.
 
% dir(direction, Dr, Dc, Bit, OppBit)
dir(left, 0, -1, 1, 2).
dir(right, 0, 1, 2, 1).
dir(up, -1, 0, 4, 8).
dir(down, 1, 0, 8, 4).
 
shuffle(Arr) = Res =>
foreach (_ in 1..10)
I1 = random() mod 4 + 1,
I2 = random() mod 4 + 1,
T := Arr[I1],
Arr[I1] := Arr[I2],
Arr[I2] := T
end,
Res = Arr.
 
display_maze(Maze,MaxR,MaxC) =>
foreach (R in 1..MaxR)
foreach (C in 1..MaxC)
printf("%s", cond(Maze[R,C] /\ 4 == 0, "+---", "+ "))
end,
println("+"),
foreach (C in 1..MaxC)
printf("%s", cond(Maze[R,C] /\ 1 == 0, "| ", " ")),
end,
println("|")
end,
foreach (C in 1..MaxC)
print("+---")
end,
println("+").
</syntaxhighlight>
{{out}}
<pre>
+---+---+---+---+---+---+---+---+
| | | |
+---+ + +---+---+ + + +
| | | | | | |
+ +---+ + + +---+ + +
| | | | | |
+---+ + +---+ + + + +
| | | | | | | |
+ + +---+ + +---+ + +
| | | | | |
+ + + +---+---+---+---+ +
| | | | | |
+ +---+---+ + + + +---+
| | | | |
+ + +---+ +---+---+---+ +
| | |
+---+---+---+---+---+---+---+---+
</pre>
 
=={{header|PicoLisp}}==
This solution uses 'grid' from "lib/simul.l" to generate the two-dimensional structure.
<langsyntaxhighlight PicoLisplang="picolisp">(load "@lib/simul.l")
 
(de maze (DX DY)
Line 5,228 ⟶ 7,020:
 
(de display (Maze)
(disp Maze 0 '((This) " ")) )</langsyntaxhighlight>
{{out}}
<pre>: (display (maze 11 8))
Line 5,252 ⟶ 7,044:
=={{header|PL/I}}==
{{trans|REXX}}
<langsyntaxhighlight lang="pli">*process source attributes xref or(!);
mgg: Proc Options(main);
/* REXX ***************************************************************
Line 5,468 ⟶ 7,260:
 
End;
End;</langsyntaxhighlight>
Output:
<pre>
Line 5,485 ⟶ 7,277:
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 11
</pre>
 
=={{header|POV-Ray}}==
This POV-Ray solution uses an iterative rather than recursive approach because POV-Ray has a small stack for recursion (about 100 levels) and so the program would crash on even quite small mazes. With the iterative approach it works on very large mazes.
<syntaxhighlight lang="pov">
#version 3.7;
 
global_settings {
assumed_gamma 1
}
 
#declare Rows = 15;
#declare Cols = 17;
 
#declare Seed = seed(2); // A seed produces a fixed sequence of pseudorandom numbers
 
#declare Wall = prism {
0, 0.8, 7,
<0, -0.5>, <0.05, -0.45>, <0.05, 0.45>, <0, 0.5>,
<-0.05, 0.45>, <-0.05, -0.45>, <0, -0.5>
texture {
pigment {
brick colour rgb 1, colour rgb <0.8, 0.25, 0.1> // Colour mortar, colour brick
brick_size 3*<0.25, 0.0525, 0.125>
mortar 3*0.01 // Size of the mortar
}
normal { wrinkles 0.75 scale 0.01 }
finish { diffuse 0.9 phong 0.2 }
}
}
 
#macro Fisher_Yates_Shuffle(Stack, Start, Top)
#for (I, Top, Start+1, -1)
#local J = floor(rand(Seed)*I + 0.5);
#if (J != I) // Waste of time swapping an element with itself
#local Src_Row = Stack[I][0];
#local Src_Col = Stack[I][1];
#local Dst_Row = Stack[I][2];
#local Dst_Col = Stack[I][3];
#declare Stack[I][0] = Stack[J][0];
#declare Stack[I][1] = Stack[J][1];
#declare Stack[I][2] = Stack[J][2];
#declare Stack[I][3] = Stack[J][3];
#declare Stack[J][0] = Src_Row;
#declare Stack[J][1] = Src_Col;
#declare Stack[J][2] = Dst_Row;
#declare Stack[J][3] = Dst_Col;
#end
#end
#end
 
#macro Initialise(Visited, North_Walls, East_Walls)
#for (R, 0, Rows-1)
#for (C, 0, Cols-1)
#declare Visited[R][C] = false;
#declare North_Walls[R][C] = true;
#declare East_Walls[R][C] = true;
#end
#end
#end
 
#macro Push(Stack, Top, Src_Row, Src_Col, Dst_Row, Dst_Col)
#declare Top = Top + 1;
#declare Stack[Top][0] = Src_Row;
#declare Stack[Top][1] = Src_Col;
#declare Stack[Top][2] = Dst_Row;
#declare Stack[Top][3] = Dst_Col;
#end
 
#macro Generate_Maze(Visited, North_Walls, East_Walls)
#local Stack = array[Rows*Cols][4]; // 0: from row, 1: from col, 2: to row, 3: to col
#local Row = floor(rand(Seed)*(Rows-1) + 0.5); // Random start row
#local Col = floor(rand(Seed)*(Cols-1) + 0.5); // Random start column
#local Top = -1;
Push(Stack, Top, Row, Col, Row, Col)
 
#while (Top >= 0)
#declare Visited[Row][Col] = true;
#local Start = Top + 1;
 
#if (Row < Rows-1) // Add north neighbour
#if (Visited[Row+1][Col] = false)
Push(Stack, Top, Row, Col, Row+1, Col)
#end
#end
 
#if (Col < Cols-1) // Add east neighbour
#if (Visited[Row][Col+1] = false)
Push(Stack, Top, Row, Col, Row, Col+1)
#end
#end
 
#if (Row > 0) // Add south neighbour
#if (Visited[Row-1][Col] = false)
Push(Stack, Top, Row, Col, Row-1, Col)
#end
#end
 
#if (Col > 0) // Add west neighbour
#if (Visited[Row][Col-1] = false)
Push(Stack, Top, Row, Col, Row, Col-1)
#end
#end
 
Fisher_Yates_Shuffle(Stack, Start, Top)
 
#local Removed_Wall = false;
#while (Top >= 0 & Removed_Wall = false)
#local Src_Row = Stack[Top][0];
#local Src_Col = Stack[Top][1];
#local Dst_Row = Stack[Top][2];
#local Dst_Col = Stack[Top][3];
#declare Top = Top - 1;
 
#if (Visited[Dst_Row][Dst_Col] = false)
#if (Dst_Row = Src_Row+1 & Dst_Col = Src_Col) // North wall
#declare North_Walls[Src_Row][Src_Col] = false;
#elseif (Dst_Row = Src_Row & Dst_Col = Src_Col+1) // East wall
#declare East_Walls[Src_Row][Src_Col] = false;
#elseif (Dst_Row = Src_Row-1 & Dst_Col = Src_Col) // South wall
#declare North_Walls[Dst_Row][Src_Col] = false;
#elseif (Dst_Row = Src_Row & Dst_Col = Src_Col-1) // West wall
#declare East_Walls[Src_Row][Dst_Col] = false;
#else
#error "Unknown wall!\n"
#end
 
#declare Row = Dst_Row;
#declare Col = Dst_Col;
#declare Removed_Wall = true;
#end
#end
#end
#end
 
#macro Draw_Maze(North_Walls, East_Walls)
merge {
#for (R, 0, Rows-1)
object { Wall translate <1, 0, 0.5> translate <-1, 0, R> } // West edge
#for (C, 0, Cols-1)
#if (R = 0) // South edge
object { Wall rotate y*90 translate <0.5, 0, 1> translate <C, 0, -1> }
#end
#if (North_Walls[R][C])
object { Wall rotate y*90 translate <0.5, 0, 1> translate <C, 0, R> }
#end
#if (East_Walls[R][C])
object { Wall translate <1, 0, 0.5> translate <C, 0, R> }
#end
#end
#end
translate <-0.5*Cols, 0, 0> // Centre maze on x=0
}
#end
 
camera {
location <0, 13, -2>
right x*image_width/image_height
look_at <0, 2, 5>
}
 
light_source {
<-0.1*Cols, Rows, 0.5*Rows>, colour rgb <1, 1, 1>
area_light
x, y, 3, 3
circular orient
}
 
box {
<-0.5*Cols, -0.1, 0>, <0.5*Cols, 0, Rows>
texture {
pigment {
checker colour rgb <0, 0.3, 0> colour rgb <0, 0.4, 0>
scale 0.5
}
finish { specular 0.5 reflection { 0.1 } }
}
}
 
#declare Visited = array[Rows][Cols];
#declare North_Walls = array[Rows][Cols];
#declare East_Walls = array[Rows][Cols];
 
Initialise(Visited, North_Walls, East_Walls)
Generate_Maze(Visited, North_Walls, East_Walls)
Draw_Maze(North_Walls, East_Walls)
</syntaxhighlight>
{{out}}
[[File:Povray maze solution 640px.png|640px|frame|none|alt=POV-Ray maze with red brick walls|POV-Ray solution with 15 rows and 17 columns]]
 
=={{header|Processing}}==
<syntaxhighlight lang="java">int g_size = 10;
color background_color = color (80, 80, 220);
color runner = color (255, 50, 50);
color visited_color = color(220, 240, 240);
color done_color = color (100, 160, 250);
int c_size;
 
Cell[][] cell;
ArrayList<Cell> done = new ArrayList<Cell>();
ArrayList<Cell> visit = new ArrayList<Cell>();
Cell run_cell;
 
void setup() {
size(600, 600);
frameRate(20);
smooth(4);
strokeCap(ROUND);
c_size = max(width/g_size, height/g_size);
cell = new Cell[g_size][g_size];
for (int i = 0; i < g_size; i++) {
for (int j = 0; j < g_size; j++) {
cell[i][j] = new Cell(i, j);
}
}
for (int i = 0; i < g_size; i++) {
for (int j = 0; j < g_size; j++) {
cell[i][j].add_neighbor();
}
}
run_cell = cell[0][0];
visit.add(run_cell);
}
 
void draw() {
background(background_color);
for (int i = 0; i < g_size; i++) {
for (int j = 0; j < g_size; j++) {
cell[i][j].draw_cell();
cell[i][j].draw_wall();
}
}
if (visit.size() < g_size*g_size) {
if (run_cell.check_sides()) {
Cell chosen = run_cell.pick_neighbor();
done.add(run_cell);
run_cell.stacked = true;
if (chosen.i - run_cell.i == 1) {
run_cell.wall[1] = false;
chosen.wall[3] = false;
} else if (chosen.i - run_cell.i == -1) {
run_cell.wall[3] = false;
chosen.wall[1] = false;
} else if (chosen.j - run_cell.j == 1) {
run_cell.wall[2] = false;
chosen.wall[0] = false;
} else {
run_cell.wall[0] = false;
chosen.wall[2] = false;
}
run_cell.current = false;
run_cell = chosen;
run_cell.current = true;
run_cell.visited = true;
} else if (done.size()>0) {
run_cell.current = false;
run_cell = done.remove(done.size()-1);
run_cell.stacked = false;
run_cell.current = true;
}
}
}
 
class Cell {
ArrayList<Cell> neighbor;
boolean visited, stacked, current;
boolean[] wall;
int i, j;
Cell(int _i, int _j) {
i = _i;
j = _j;
wall = new boolean[]{true,true,true,true};
}
Cell pick_neighbor() {
ArrayList<Cell> unvisited = new ArrayList<Cell>();
for(int i = 0; i < neighbor.size(); i++){
Cell nb = neighbor.get(i);
if(nb.visited == false) unvisited.add(nb);
}
return unvisited.get(floor(random(unvisited.size())));
}
void add_neighbor() {
neighbor = new ArrayList<Cell>();
if(i>0){neighbor.add(cell[i-1][j]);}
if(i<g_size-1){neighbor.add(cell[i+1][j]);}
if(j>0){neighbor.add(cell[i][j-1]);}
if(j<g_size-1){neighbor.add(cell[i][j+1]);}
}
boolean check_sides() {
for(int i = 0; i < neighbor.size(); i++){
Cell nb = neighbor.get(i);
if(!nb.visited) return true;
}
return false;
}
void draw_cell() {
noStroke();
noFill();
if(current) fill(runner);
else if(stacked) fill(done_color);
else if(visited) fill(visited_color);
rect(j*c_size,i*c_size,c_size,c_size);
}
void draw_wall() {
stroke(0);
strokeWeight(5);
if(wall[0]) line(j*c_size, i*c_size, j*c_size, (i+1)* c_size);
if(wall[1]) line(j*c_size, (i+1)*c_size, (j+1)*c_size, (i+1)*c_size);
if(wall[2]) line((j+1)*c_size, (i+1)*c_size, (j+1)*c_size, i*c_size);
if(wall[3]) line((j+1)*c_size, i*c_size, j*c_size, i*c_size);
}
}</syntaxhighlight>
'''It can be played on line''' :<BR> [https://www.openprocessing.org/sketch/880778/ here.]
 
==={{header|Processing Python mode}}===
 
<syntaxhighlight lang="python">
g_size = 10
background_color = color(80, 80, 220)
runner = color(255, 50, 50)
visited_color = color(220, 240, 240)
done_color = color(100, 160, 250)
 
def setup():
global cell, done, visit, run_cell, c_size
size(600, 600)
frameRate(20)
smooth(4)
strokeCap(ROUND)
c_size = max(width / g_size, height / g_size)
cell = [[None] * g_size for _ in range(g_size)]
for i in range(g_size):
for j in range(g_size):
cell[i][j] = Cell(i, j)
 
for i in range(g_size):
for j in range(g_size):
cell[i][j].add_neighbor()
 
run_cell = cell[0][0]
visit, done = [], []
visit.append(run_cell)
 
 
def draw():
global run_cell
background(background_color)
for i in range(g_size):
for j in range(g_size):
cell[i][j].draw_cell()
cell[i][j].draw_wall()
 
if len(visit) < g_size * g_size:
if run_cell.check_sides():
chosen = run_cell.pick_neighbor()
done.append(run_cell)
run_cell.stacked = True
if chosen.i - run_cell.i == 1:
run_cell.wall[1] = False
chosen.wall[3] = False
elif chosen.i - run_cell.i == -1:
run_cell.wall[3] = False
chosen.wall[1] = False
elif chosen.j - run_cell.j == 1:
run_cell.wall[2] = False
chosen.wall[0] = False
else:
run_cell.wall[0] = False
chosen.wall[2] = False
run_cell.current = False
run_cell = chosen
run_cell.current = True
run_cell.visited = True
elif done:
run_cell.current = False
run_cell = done.pop()
run_cell.stacked = False
run_cell.current = True
 
 
class Cell:
 
def __init__(self, i, j):
self.i = i
self.j = j
self.wall = [True, True, True, True]
self.visited = False
self.stacked = False
self.current = False
 
def pick_neighbor(self):
from random import choice
unvisited = [nb for nb in self.neighbor
if nb.visited == False]
return choice(unvisited)
 
def add_neighbor(self):
i, j = self.i, self.j
neighbor = []
if i > 0:
neighbor.append(cell[i - 1][j])
if i < g_size - 1:
neighbor.append(cell[i + 1][j])
if j > 0:
neighbor.append(cell[i][j - 1])
if j < g_size - 1:
neighbor.append(cell[i][j + 1])
self.neighbor = neighbor
 
def check_sides(self):
for nb in self.neighbor:
if not nb.visited:
return True
return False
 
def draw_cell(self):
s = c_size
noStroke()
noFill()
if self.current:
fill(runner)
elif self.stacked:
fill(done_color)
elif self.visited:
fill(visited_color)
rect(self.j * s, self.i * s, s, s)
 
def draw_wall(self):
i, j = self.i, self.j
wall = self.wall
stroke(0)
strokeWeight(5)
if wall[0]: line(j * c_size, i * c_size, j * c_size, (i + 1) * c_size)
if wall[1]: line(j * c_size, (i + 1) * c_size, (j + 1) * c_size, (i + 1) * c_size)
if wall[2]: line((j + 1) * c_size, (i + 1) * c_size, (j + 1) * c_size, i * c_size)
if wall[3]: line((j + 1) * c_size, i * c_size, j * c_size, i * c_size)
</syntaxhighlight>
 
=={{header|Prolog}}==
Works with SWI-Prolog and XPCE.
<langsyntaxhighlight Prologlang="prolog">:- dynamic cell/2.
 
maze(Lig,Col) :-
Line 5,578 ⟶ 7,815:
\+cell(L, C1).
 
</syntaxhighlight>
</lang>
{{out}}
[[File:Prolog-Maze.jpg]]
 
=={{header|PureBasic}}==
<langsyntaxhighlight PureBasiclang="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
Line 5,718 ⟶ 7,955:
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf</langsyntaxhighlight>
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.
 
Line 5,742 ⟶ 7,979:
 
=={{header|Python}}==
<langsyntaxhighlight lang="python">from random import shuffle, randrange
 
def make_maze(w = 16, h = 8):
Line 5,768 ⟶ 8,005:
 
if __name__ == '__main__':
print(make_maze())</langsyntaxhighlight>
{{out}}
<pre>+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Line 5,791 ⟶ 8,028:
 
Maze generator
<langsyntaxhighlight lang="racket">
#lang racket
 
Line 5,822 ⟶ 8,059:
; return the result
(maze N M tbl))
</syntaxhighlight>
</lang>
 
Printing out the maze
 
<langsyntaxhighlight lang="racket">
;; Shows a maze
(define (show-maze m)
Line 5,846 ⟶ 8,083:
(displayln "+"))
(newline))
</syntaxhighlight>
</lang>
 
Example:
Line 5,868 ⟶ 8,105:
+---+---+---+---+---+---+---+---+---+---+
</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
{{works with|rakudo|2015-09-22}}
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.
<syntaxhighlight lang="raku" line>constant mapping = :OPEN(' '),
:N< ╵ >,
:E< ╶ >,
:NE< └ >,
:S< ╷ >,
:NS< │ >,
:ES< ┌ >,
:NES< ├ >,
:W< ╴ >,
:NW< ┘ >,
:EW< ─ >,
:NEW< ┴ >,
:SW< ┐ >,
:NSW< ┤ >,
:ESW< ┬ >,
:NESW< ┼ >,
:TODO< x >,
:TRIED< · >;
enum Sym (mapping.map: *.key);
my @ch = mapping.map: *.value;
enum Direction <DeadEnd Up Right Down Left>;
sub gen_maze ( $X,
$Y,
$start_x = (^$X).pick * 2 + 1,
$start_y = (^$Y).pick * 2 + 1 )
{
my @maze;
push @maze, $[ flat ES, -N, (ESW, EW) xx $X - 1, SW ];
push @maze, $[ flat (NS, TODO) xx $X, NS ];
for 1 ..^ $Y {
push @maze, $[ flat NES, EW, (NESW, EW) xx $X - 1, NSW ];
push @maze, $[ flat (NS, TODO) xx $X, NS ];
}
push @maze, $[ flat NE, (EW, NEW) xx $X - 1, -NS, NW ];
@maze[$start_y][$start_x] = OPEN;
my @stack;
my $current = [$start_x, $start_y];
loop {
if my $dir = pick_direction( $current ) {
@stack.push: $current;
$current = move( $dir, $current );
}
else {
last unless @stack;
$current = @stack.pop;
}
}
return @maze;
sub pick_direction([$x,$y]) {
my @neighbors =
(Up if @maze[$y - 2][$x]),
(Down if @maze[$y + 2][$x]),
(Left if @maze[$y][$x - 2]),
(Right if @maze[$y][$x + 2]);
@neighbors.pick or DeadEnd;
}
sub move ($dir, @cur) {
my ($x,$y) = @cur;
given $dir {
when Up { @maze[--$y][$x] = OPEN; @maze[$y][$x-1] -= E; @maze[$y--][$x+1] -= W; }
when Down { @maze[++$y][$x] = OPEN; @maze[$y][$x-1] -= E; @maze[$y++][$x+1] -= W; }
when Left { @maze[$y][--$x] = OPEN; @maze[$y-1][$x] -= S; @maze[$y+1][$x--] -= N; }
when Right { @maze[$y][++$x] = OPEN; @maze[$y-1][$x] -= S; @maze[$y+1][$x++] -= N; }
}
@maze[$y][$x] = 0;
[$x,$y];
}
}
sub display (@maze) {
for @maze -> @y {
for @y.rotor(2) -> ($w, $c) {
print @ch[abs $w];
if $c >= 0 { print @ch[$c] x 3 }
else { print ' ', @ch[abs $c], ' ' }
}
say @ch[@y[*-1]];
}
}
display gen_maze( 29, 19 );</syntaxhighlight>
{{out}}
<small><pre style="font-family: consolas, inconsolata, monospace; line-height: normal;">┌ ╵ ────────────────────────────┬───────────────────────────────────────────┬───────────┬───────────────────────────┐
│ │ │ │ │
│ ╶───────────┬───────────┐ │ ┌───────────────────────╴ ┌───────┐ ├───╴ ╷ │ ┌───────────┬───┬───╴ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │
│ ┌───────┐ ╵ ┌───┐ ├───┘ │ ┌───────────┬───────────┤ ╶───┤ │ ╶───┴───┤ │ ┌───┐ │ │ ╶───┤
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ └───╴ └───────┤ │ ╵ ┌───┘ │ ╷ ╶───┤ ┌───┐ │ ╷ │ ├───────╴ │ ╵ │ │ │ └───┐ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├───────┬───────┐ │ ├───────┤ ╶───┤ └───┐ ╵ │ │ ╵ │ ╵ │ ┌───┐ └───┬───┘ │ │ ╷ │ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ ╶───┤ ╷ ╵ │ ╵ ╷ └───┐ ├───┐ ├───────┤ └───────┴───────┘ │ └───┐ └───╴ │ ╵ ├───┘ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├───╴ │ ├───────┴───┐ ├───╴ │ │ │ ╵ ╷ └───┐ ╶───┬───────┬───┘ ┌───┴───────╴ │ ┌───┘ ╷ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ ╷ │ │ ╶───┐ └───┤ ╷ │ │ └───────┴───┐ └───╴ │ ╷ ╵ ╷ ╵ ╶───────┬───┤ │ ┌───┴───┤
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ │ │ │ ╷ ├───╴ ╵ │ │ │ ┌───────┐ └───────────┤ └───┬───┴───────────┐ ╵ │ │ ╵ ╷ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ │ │ ├───┘ │ ┌───────┴───┘ │ ╵ ┌───┴───────╴ ╷ ├───┐ │ ╶───────┐ └───┐ │ └───┬───┘ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ └───┘ │ ┌───┘ │ ┌───┬───────┼───╴ │ ╶───┬───────┤ ╵ │ └───┬───╴ ├───┐ │ └───┐ │ ╷ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ ┌───────┘ ├───────┤ │ ╵ ╷ │ ┌───┴───┐ │ ╶───┘ ┌───┴───╴ │ ┌───┘ │ │ ┌───┘ │ │ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ └───╴ ╷ │ ╷ │ └───┐ │ ╵ │ ╷ ╵ ├───────┐ │ ╶───────┤ └───┐ │ └───┤ ┌───┘ │ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├───────────┤ │ │ └───╴ │ └───────┤ └───────┘ ╷ └───┴───┬───╴ ├───╴ │ └───┐ │ │ ╶───┴───┤
│ │ │ │ │ │ │ │ │ │ │ │ │ │
│ ┌───╴ │ │ ├───╴ ┌───┴───────┬───┴───┐ ┌───────┴───────┐ ╵ ┌───┤ ╶───┤ ╷ │ ╵ └───┬───╴ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ │ ╶───┘ │ │ ╶───┤ ╶───┐ ╵ ╷ │ └───╴ ┌───╴ └───────┘ ├───╴ │ ├───┴───────┬───┘ ╷ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ ├───────┬───┘ ├───────┴───┐ ├───────┤ └───────────┤ ┌───────────┐ │ ┌───┘ │ ╶───┐ ╵ ┌───┘ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
│ └───╴ │ ╷ │ ╶───┐ ╵ │ ╷ └───────────┐ │ │ ┌───┐ └───┘ │ ╶───┴───┐ └───────┴───────┤
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├───────╴ │ └───┴───╴ └───────┴───┴───────────╴ │ └───┘ ╵ └───────────┴───╴ ╷ └───────────────┐ │
│ │ │ │ │ │
└───────────┴───────────────────────────────────────────┴───────────────────────────────────┴───────────────────┴ │ ┘</pre></small>
 
=={{header|Rascal}}==
{{trans|Python}}
<langsyntaxhighlight lang="rascal">import IO;
import util::Math;
import List;
Line 5,899 ⟶ 8,268:
println(("" | it + "<z>" | z <- b));
}
}</langsyntaxhighlight>
 
<pre>rascal>make_maze(10,10)
Line 5,925 ⟶ 8,294:
 
ok
</pre>
 
=={{header|Red}}==
<syntaxhighlight lang="red">Red ["Maze generation"]
 
size: as-pair to-integer ask "Maze width: " to-integer ask "Maze height: "
random/seed now/time
offsetof: function [pos] [pos/y * size/x + pos/x + 1]
visited?: function [pos] [find visited pos]
 
newneighbour: function [pos][
nnbs: collect [
if all [pos/x > 0 not visited? p: pos - 1x0] [keep p]
if all [pos/x < (size/x - 1) not visited? p: pos + 1x0] [keep p]
if all [pos/y > 0 not visited? p: pos - 0x1] [keep p]
if all [pos/y < (size/y - 1) not visited? p: pos + 0x1] [keep p]
]
pick nnbs random length? nnbs
]
expand: function [pos][
insert visited pos
either npos: newneighbour pos [
insert exploring npos
do select [
0x-1 [o: offsetof npos walls/:o/y: 0]
1x0 [o: offsetof pos walls/:o/x: 0]
0x1 [o: offsetof pos walls/:o/y: 0]
-1x0 [o: offsetof npos walls/:o/x: 0]
] npos - pos
][
remove exploring
]
]
visited: []
walls: append/dup [] 1x1 size/x * size/y
exploring: reduce [random size - 1x1]
 
until [
expand exploring/1
empty? exploring
]
 
print append/dup "" " _" size/x
repeat j size/y [
prin "|"
repeat i size/x [
p: pick walls (j - 1 * size/x + i)
prin rejoin [pick " _" 1 + p/y pick " |" 1 + p/x]
]
print ""
]</syntaxhighlight>
{{out}}
<pre>Maze width: 15
Maze height: 15
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ | _ _ _ _| _ _ |
|_ _ |_ _| | _ _ |_ | |_ _|
| | |_ |_ _ _ _| | _|_ _ |
| |_|_ _ |_ | | | _ _| _|
| _ _|_ _| |_ _| | _ _| |
| | |_ _ _ _| | _ _| | _ _|
|_ _ _ | | |_| | | _|_ _ |
|_ _ | | | |_ _ _| | | _ | |
| _ _| | |_ _ _ |_ _| | | |
| _ | |_ | |_ |_ _ _| | |
| | |_ _|_ _ _ |_ |_ _| _| |
| | _ |_ _| | |_ | |
| |_|_ |_ |_| _|_|_|_ _ _| |
|_ _ | | |_ |_ _ _ _ _ | |
|_ _ _ _|_ _ _ _ _ _ _ _|_ _ _|
</pre>
 
Line 5,931 ⟶ 8,370:
In order to preserve the aspect ratio (for most display terminals), several &nbsp; '''changestr''' &nbsp; invocations and
<br>some other instructions were added to increase the horizontal dimension (cell size).
<langsyntaxhighlight lang="rexx">/*REXX program generates and displays a rectangular solvable maze (of any size). */
parse arg rows cols seed . /*allow user to specify the maze size. */
if rows='' | rows==',' then rows= 19 /*No rows given? Then use the default.*/
Line 5,937 ⟶ 8,376:
if datatype(seed, 'W') then call random ,,seed /*use a random seed for repeatability.*/
ht=0; @.=0 /*HT= # rows in grid; @.: default cell*/
call makeRow '┌'copies('"~┬'", cols - 1)'~┐' /*construct the top edge of the maze. */
/* [↓] construct the maze's grid. */
do r=1 for rows; _=; __=; hp= "|"; hj= '├'
Line 5,971 ⟶ 8,410:
say translate( _ , '─│' , "═|\10" ) /*make it presentable for the screen. */
end /*#*/
exit /*stick a fork in it, we're all done. */
end /*#*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
@: parse arg _r,_c; return @._r._c /*a fast way to reference a maze cell. */
Line 6,028 ⟶ 8,466:
otherwise nop
end /*select*/
end /*k*/; return</langsyntaxhighlight>
Some older REXXes don't have a &nbsp; '''changestr''' &nbsp; BIF, so one is included here &nbsp; ──► &nbsp; [[CHANGESTR.REX]].
 
{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 23 &nbsp; 19 &nbsp; 6 </tt>}}
 
<pre>
(Shown at one-half size.)
 
<pre style="font-size:50%">
┌───────────┬───────────────┬───────────────────────┬───────────────────┬───┐
│ │ │ │ │ │
Line 6,085 ⟶ 8,526:
The above REXX version had a quite of bit of code to "dress up" the maze presentation, &nbsp; so a slimmed-down version
<br>was included here for easier reading and understanding of the program's logic.
<langsyntaxhighlight lang="rexx">/*REXX program generates and displays a rectangular solvable maze (of any size). */
parse arg rows cols seed . /*allow user to specify the maze size. */
if rows='' | rows=="," then rows= 19 /*No rows given? Then use the default.*/
Line 6,138 ⟶ 8,579:
if hood(rr,cc)==1 then do; r!= rr; c!= cc; @.r!.c!= 0; return 1; end
end /*c*/ /* [↑] r! and c! are used by invoker.*/
end /*r*/; return 0</langsyntaxhighlight>
{{out|output|text=&nbsp; when using input: &nbsp; &nbsp; <tt> 10 &nbsp;10 </tt>}}
 
<pre>
Shown at one-half size.)
 
<pre style="font-size:50%">
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ │ │
Line 6,165 ⟶ 8,609:
 
===version 3===
<langsyntaxhighlight lang="rexx">/* REXX ***************************************************************
* 04.09.2013 Walter Pachl
**********************************************************************/
Line 6,332 ⟶ 8,776:
End
End
Return is js /* return the new start point*/</langsyntaxhighlight>
Output:
<pre>
Line 6,353 ⟶ 8,797:
 
=={{header|Ruby}}==
<langsyntaxhighlight lang="ruby">class Maze
DIRECTIONS = [ [1, 0], [-1, 0], [0, 1], [0, -1] ]
Line 6,447 ⟶ 8,891:
# Demonstration:
maze = Maze.new 20, 10
maze.print</langsyntaxhighlight>
 
{{out}}
Line 6,473 ⟶ 8,917:
+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+
</pre>
 
=={{header|Rust}}==
Uses the [https://crates.io/crates/rand rand] library
<syntaxhighlight lang="rust">use rand::{thread_rng, Rng, rngs::ThreadRng};
 
const WIDTH: usize = 16;
const HEIGHT: usize = 16;
 
#[derive(Clone, Copy)]
struct Cell {
col: usize,
row: usize,
}
 
impl Cell {
fn from(col: usize, row: usize) -> Cell {
Cell {col, row}
}
}
 
struct Maze {
cells: [[bool; HEIGHT]; WIDTH], //cell visited/non visited
walls_h: [[bool; WIDTH]; HEIGHT + 1], //horizontal walls existing/removed
walls_v: [[bool; WIDTH + 1]; HEIGHT], //vertical walls existing/removed
thread_rng: ThreadRng, //Random numbers generator
}
 
impl Maze {
 
///Inits the maze, with all the cells unvisited and all the walls active
fn new() -> Maze {
Maze {
cells: [[true; HEIGHT]; WIDTH],
walls_h: [[true; WIDTH]; HEIGHT + 1],
walls_v: [[true; WIDTH + 1]; HEIGHT],
thread_rng: thread_rng(),
}
}
 
///Randomly chooses the starting cell
fn first(&mut self) -> Cell {
Cell::from(self.thread_rng.gen_range(0, WIDTH), self.thread_rng.gen_range(0, HEIGHT))
}
 
///Opens the enter and exit doors
fn open_doors(&mut self) {
let from_top: bool = self.thread_rng.gen();
let limit = if from_top { WIDTH } else { HEIGHT };
let door = self.thread_rng.gen_range(0, limit);
let exit = self.thread_rng.gen_range(0, limit);
if from_top {
self.walls_h[0][door] = false;
self.walls_h[HEIGHT][exit] = false;
} else {
self.walls_v[door][0] = false;
self.walls_v[exit][WIDTH] = false;
}
}
 
///Removes a wall between the two Cell arguments
fn remove_wall(&mut self, cell1: &Cell, cell2: &Cell) {
if cell1.row == cell2.row {
self.walls_v[cell1.row][if cell1.col > cell2.col { cell1.col } else { cell2.col }] = false;
} else {
self.walls_h[if cell1.row > cell2.row { cell1.row } else { cell2.row }][cell1.col] = false;
};
}
 
///Returns a random non-visited neighbor of the Cell passed as argument
fn neighbor(&mut self, cell: &Cell) -> Option<Cell> {
self.cells[cell.col][cell.row] = false;
let mut neighbors = Vec::new();
if cell.col > 0 && self.cells[cell.col - 1][cell.row] { neighbors.push(Cell::from(cell.col - 1, cell.row)); }
if cell.row > 0 && self.cells[cell.col][cell.row - 1] { neighbors.push(Cell::from(cell.col, cell.row - 1)); }
if cell.col < WIDTH - 1 && self.cells[cell.col + 1][cell.row] { neighbors.push(Cell::from(cell.col + 1, cell.row)); }
if cell.row < HEIGHT - 1 && self.cells[cell.col][cell.row + 1] { neighbors.push(Cell::from(cell.col, cell.row + 1)); }
if neighbors.is_empty() {
None
} else {
let next = neighbors.get(self.thread_rng.gen_range(0, neighbors.len())).unwrap();
self.remove_wall(cell, next);
Some(*next)
}
}
 
///Builds the maze (runs the Depth-first search algorithm)
fn build(&mut self) {
let mut cell_stack: Vec<Cell> = Vec::new();
let mut next = self.first();
loop {
while let Some(cell) = self.neighbor(&next) {
cell_stack.push(cell);
next = cell;
}
match cell_stack.pop() {
Some(cell) => next = cell,
None => break,
}
}
}
 
///Displays a wall
fn paint_wall(h_wall: bool, active: bool) {
if h_wall {
print!("{}", if active { "+---" } else { "+ " });
} else {
print!("{}", if active { "| " } else { " " });
}
}
 
///Displays a final wall for a row
fn paint_close_wall(h_wall: bool) {
if h_wall { println!("+") } else { println!() }
}
 
///Displays a whole row of walls
fn paint_row(&self, h_walls: bool, index: usize) {
let iter = if h_walls { self.walls_h[index].iter() } else { self.walls_v[index].iter() };
for &wall in iter {
Maze::paint_wall(h_walls, wall);
}
Maze::paint_close_wall(h_walls);
}
 
///Paints the maze
fn paint(&self) {
for i in 0 .. HEIGHT {
self.paint_row(true, i);
self.paint_row(false, i);
}
self.paint_row(true, HEIGHT);
}
}
 
fn main() {
let mut maze = Maze::new();
maze.build();
maze.open_doors();
maze.paint();
}</syntaxhighlight>
 
{{out}}
<pre>+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | |
+ +---+---+ + + +---+ +---+---+---+ +---+---+---+ +
| | | | | | | | | |
+ +---+ + + + + +---+ + + +---+---+ + + +
| | | | | | | | | |
+---+ + + + +---+---+ + +---+---+ +---+---+---+ +
| | | | | | | | | |
+ +---+---+---+ + + +---+ + + +---+ +---+---+---+
| | | | | | | | |
+---+---+ +---+ + +---+ + +---+---+ + + + + +
| | | | | | | | | | |
+ +---+---+ +---+ + +---+---+---+ +---+ + + +---+
| | | | | | | | | |
+ + + + + +---+ +---+ + +---+ + +---+---+ +
| | | | | | | | | | | | |
+ + +---+ +---+ +---+---+ +---+ + + + + + +
| | | | | | | | | | | | |
+ + + +---+ + + + +---+---+---+ + + + + +
| | | | | | | | | | | |
+ + + + + + + +---+ +---+ + +---+---+---+ +
| | | | | | | | | |
+---+ + + +---+---+ + +---+---+---+ + + +---+---+
| | | | | | | | | |
+ +---+ +---+---+ + +---+---+---+ + + + + + +
| | | | | | | | | | | |
+---+---+ + + +---+---+ + + +---+ + + +---+ +
| | | | | | | | | | |
+---+ +---+ +---+ + + + + +---+---+---+---+ + +
| | | | | | | | |
+ +---+ +---+ + +---+---+ +---+---+---+---+ +---+ +
| | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ +</pre>
 
=={{header|Scala}}==
<langsyntaxhighlight lang="scala">import scala.util.Random
 
object MazeTypes {
Line 6,560 ⟶ 9,179:
private def openInDirection(loc: Loc, dir: Direction): Boolean =
doors.contains(Door(loc, loc + dir)) || doors.contains(Door(loc + dir, loc))
}</langsyntaxhighlight>
{{out}}
<pre>
Line 6,595 ⟶ 9,214:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
</pre>
 
=={{header|Sidef}}==
{{trans|Perl}}
<langsyntaxhighlight lang="ruby">var(w:5, h:5) = ARGV.map{.to_i}...
var avail = (w * h)
 
Line 6,606 ⟶ 9,226:
 
func walk(x, y) {
cell[y][x] = false;
avail-- > 0 || return; nil # no more bottles, er, cells
 
var d = [[-1, 0], [0, 1], [1, 0], [0, -1]]
Line 6,629 ⟶ 9,249:
say (ver[i].join('') + '|')
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 6,646 ⟶ 9,266:
 
=={{header|SuperCollider}}==
<syntaxhighlight lang="supercollider">
<lang SuperCollider>
// some useful functions
(
Line 6,703 ⟶ 9,323:
w.front.refresh;
)
</syntaxhighlight>
</lang>
 
=={{header|Swift}}==
{{works with|Swift|3}}
<langsyntaxhighlight Swiftlang="swift">import Foundation
 
extension Array {
Line 6,875 ⟶ 9,495:
let y = 10
let maze = MazeGenerator(x, y)
maze.display()</langsyntaxhighlight>
{{out}}
<pre>
Line 6,902 ⟶ 9,522:
=={{header|Tcl}}==
{{trans|Javascript}}
<langsyntaxhighlight lang="tcl">package require TclOO; # Or Tcl 8.6
 
# Helper to pick a random number
Line 6,998 ⟶ 9,618:
# Demonstration
maze create m 11 8
puts [m view]</langsyntaxhighlight>
{{out}}
<pre>
Line 7,026 ⟶ 9,646:
Legend: cu = current location; vi = boolean hash of visited locations; pa = hash giving a list neighboring cells to which there is a path from a given cell.
 
<langsyntaxhighlight lang="txr">@(bind (width height) (15 15))
@(do
(defvar *r* (make-random-state nil))
Line 7,080 ⟶ 9,700:
@;;
@(bind m @(make-maze width height))
@(do (print-maze m width height))</langsyntaxhighlight>
 
{{out}}
Line 7,145 ⟶ 9,765:
At the user interface level, the straightness parameter is represented as a percentage. This percentage is converted to a number of cells based on the width and height of the maze. For instance if the straightness parameter is 15, and the maze size is 20x20, it means that 15% out of 400 cells, or 60 cells will be traversed before the queue is scrambled. Then another 60 will be traversed and the queue will be scrambled, and so forth.
 
<langsyntaxhighlight lang="txrlisp">(defvar vi) ;; visited hash
(defvar pa) ;; path connectivity hash
(defvar sc) ;; count, derived from straightness fator
Line 7,224 ⟶ 9,844:
(set h (max 1 h))
(print-maze (make-maze w h s) w h))
(else (usage))))</langsyntaxhighlight>
 
{{out}}
Line 7,337 ⟶ 9,957:
| | |
+----+----+----+----+----+----+----+----+----+----+</pre>
 
=={{header|TypeScript}}==
 
===randomized depth first search function to create maze===
 
 
<syntaxhighlight lang="typescript">
 
interface mazeData{
nodes:Node[]
x:number
y:number
blockSize:number
}
 
class Node{
x:number
y:number
wallsTo:Node[]
visited = false
constructor(x:number,y:number){
this.x = x
this.y = y
}
getTouchingNodes(nodes:Node[],blockSize:number){
return nodes.filter(n=>
(this != n) &&
(Math.hypot(this.x-n.x,this.y-n.y) == blockSize )
)
}
draw(ctx:CanvasRenderingContext2D,blockSize:number){
ctx.fillStyle ='black'
this.wallsTo.forEach(el=>{
ctx.save()
ctx.translate(this.x,this.y)
ctx.rotate(Math.atan2(this.y-el.y,this.x-el.x)+ Math.PI)
ctx.beginPath()
ctx.moveTo(blockSize/2,blockSize/2)
ctx.lineTo(blockSize/2,-blockSize/2)
ctx.stroke()
ctx.restore()
})
}
}
 
export function maze(x:number,y:number):mazeData {
let blockSize = 20
x *= blockSize
y *= blockSize
let nodes = Array((x/blockSize)*(y/blockSize)).fill(0).map((_el,i)=>
new Node(
(i%(x/blockSize)*(blockSize))+(blockSize/2),
(Math.floor(i/(x/blockSize))*(blockSize))+(blockSize/2)
)
)
nodes.forEach(n=>n.wallsTo = n.getTouchingNodes(nodes,blockSize))
let que = [nodes[0]]
while(que.length > 0){
let current = que.shift()
let unvisited = current
.getTouchingNodes(nodes,blockSize)
.filter(el=>!el.visited)
if(unvisited.length >0){
que.push(current)
let chosen = unvisited[Math.floor(Math.random()*unvisited.length)];
current.wallsTo = current.wallsTo.filter((el)=>el != chosen)
chosen.wallsTo = chosen.wallsTo.filter((el)=>el != current)
chosen.visited = true
que.unshift(chosen)
}
}
return {x:x,y:y,nodes:nodes,blockSize:blockSize}
}
 
export function display(c:HTMLCanvasElement,mazeData:mazeData){
let ctx = c.getContext('2d')
c.width = mazeData.x
c.height = mazeData.y
ctx.fillStyle = 'white'
ctx.strokeStyle = 'black'
ctx.fillRect(0,0,mazeData.x,mazeData.y)
ctx.strokeRect(0,0,mazeData.x,mazeData.y)
mazeData.nodes.forEach(el=>el.draw(ctx,mazeData.blockSize))
}
</syntaxhighlight>
 
=== maze creation using html canvas===
 
<syntaxhighlight lang="typescript">
import { maze,display } from "./maze"
const X = 10
const Y = 10
 
let canvas = document.createElement('canvas')
document.body.appendChild(canvas)
let m = maze(X,Y)
display(canvas,m)
</syntaxHighlight>
 
{{out}}
=== rendered 10x20 maze ===
[[File:TSMaze.png]]
 
 
=={{header|Uiua}}==
{{works with|Uiua|0.10.3}}
{{trans|Python}}
Inspired by the Python algorithm, so will produce identical output.
<syntaxhighlight lang="Uiua">
H ← 8
W ← 18
Ver ← 0
Hor ← 1
Vis ← 2
 
BreakNS ← ⊂Ver⊂⊃(/↥≡⊡0|⊡0_1)
BreakEW ← ⊂Hor⊂⊃(⊡0_0|/↥≡⊡1)
# ([here, next], maze) -> (maze')
BreakWall ← ⍜⊡(0◌)⟨BreakNS|BreakEW⟩=°⊟≡⊢.
 
Neighbours ← +⊙¤[[¯1 0] [1 0] [0 1] [0 ¯1]] # Gives N4
Shuffle ← ⊏⍏[⍥⚂]⧻.
IsVisited ← ¬⊡⊂Vis
MarkAsVisited ← ⟜(⍜(⊡|1◌)⊂Vis)
OnlyInBounds ← ▽≡IsVisited ⊙¤,, # (finds the boundary 1's)
 
# (here, maze) -> (maze')
Walk ← |2 (
MarkAsVisited
# (here, maze) -> ([[here, next] x(up to)4], maze)
≡⊟¤⟜(Shuffle OnlyInBounds Neighbours)
 
# Update maze for each in turn. For each, if it
# still isn't visited, break the wall, recurse into it.
∧(⟨◌|Walk ⊡1 ⟜BreakWall⟩IsVisited◌°⊟,,)
)
 
⊂↯H⊂↯W0 1↯+1W1 # vis (added 1's help bounds checks)
⊂↯H⊂↯W1 1↯+1W 0 # ver
↯+1H⊂↯W1 0 # hor
⊂⊟
# Stack: ([hor, ver, vis])
Walk [0 0]
 
PP! ← ≡/⊂∵^! # Pretty print using switch.
≡(&p$"_\n_")⊃(PP!⟨"+ "|"+--"⟩⊡Ver|PP!⟨" "|"| "⟩⊡Hor)
 
</syntaxhighlight>
 
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="wren">import "random" for Random
import "os" for Process
 
var Rand = Random.new()
 
class Direction {
static n { __n }
static s { __s }
static e { __e }
static w { __w }
 
static init() {
__n = new_(1, 0, -1)
__s = new_(2, 0, 1)
__e = new_(4, 1, 0)
__w = new_(8, -1, 0)
 
__n.opposite = __s
__s.opposite = __n
__e.opposite = __w
__w.opposite = __e
}
 
construct new_(bit, dx, dy) {
_bit = bit
_dx = dx
_dy = dy
_opposite = null
}
 
bit { _bit }
dx { _dx }
dy { _dy }
 
opposite { _opposite }
opposite=(d) { _opposite = d }
}
 
Direction.init()
 
class MazeGenerator {
construct new(x, y) {
_x = x
_y = y
_maze = List.filled(x, null)
for (i in 0...x) _maze[i] = List.filled(y, 0)
}
 
between_(v, upper) { v >= 0 && v < upper }
 
generate(cx, cy) {
var values = [Direction.n, Direction.s, Direction.e, Direction.w]
Rand.shuffle(values)
values.each { |v|
var nx = cx + v.dx
var ny = cy + v.dy
if (between_(nx, _x) && between_(ny, _y) && _maze[nx][ny] == 0) {
_maze[cx][cy] = _maze[cx][cy] | v.bit
_maze[nx][ny] = _maze[nx][ny] | v.opposite.bit
generate(nx, ny)
}
}
}
 
display() {
for (i in 0..._y) {
// draw the north edge
for (j in 0..._x) System.write((_maze[j][i] & 1) == 0 ? "+---" : "+ ")
System.print("+")
 
// draw the west edge
for (j in 0..._x) System.write((_maze[j][i] & 8) == 0 ? "| " : " ")
System.print("|")
}
// draw the bottom line
for (j in 0..._x) System.write("+---")
System.print("+")
}
}
 
var args = Process.arguments
var x = (args.count >= 1) ? Num.fromString(args[0]) : 8
var y = (args.count == 2) ? Num.fromString(args[1]) : 8
var mg = MazeGenerator.new(x, y)
mg.generate(0, 0)
mg.display()</syntaxhighlight>
 
{{out}}
Sample 8 x 8 maze:
<pre>
+---+---+---+---+---+---+---+---+
| | | | |
+ + + + + + +---+ +
| | | | | |
+ + + +---+---+---+---+ +
| | | | | | |
+ +---+ +---+ + + + +
| | | | |
+---+---+---+ +---+ +---+---+
| | | |
+ + + +---+---+---+---+ +
| | | | | |
+ + + + +---+---+ + +
| | | | | | |
+ + +---+---+ +---+ + +
| | |
+---+---+---+---+---+---+---+---+
</pre>
 
=={{header|XPL0}}==
<langsyntaxhighlight XPL0lang="xpl0">code Ran=1, CrLf=9, Text=12; \intrinsic routines
def Cols=20, Rows=6; \dimensions of maze (cells)
int Cell(Cols+1, Rows+1, 3); \cells (plus right and bottom borders)
Line 7,382 ⟶ 10,262:
Text(0, if Y#Rows & Cell(X, Y, LeftWall) then "| " else " ");
];
]</langsyntaxhighlight>
 
Output:
Line 7,405 ⟶ 10,285:
Generate a maze without marked entry or exit points.
{{trans|Python}}
<langsyntaxhighlight lang="zkl">
fcn make_maze(w = 16, h = 8){
// make arrays with lists of lists (all mutable)
Line 7,426 ⟶ 10,306:
return(ver,hor);
}
make_maze();</langsyntaxhighlight>
{{out}}
<pre>
1,481

edits