Maze generation: Difference between revisions
m
→{{header|POV-Ray}}: Explanation added about iterative approach
m (→{{header|POV-Ray}}: Explanation added about iterative approach) |
|||
| (28 intermediate revisions by 10 users not shown) | |||
Line 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#}}==
Line 1,997 ⟶ 2,150:
//--------------------------------------------------------------------------------------------------
</syntaxhighlight>
=={{header|Chapel}}==
<syntaxhighlight lang="chapel">
use Random;
config const rows: int = 9;
config const cols: int = 16;
if rows < 1 || cols < 1 {
writeln("Maze must be at least 1x1 in size.");
exit(1);
}
enum direction {N = 1, E = 2, S = 3, W = 4};
record Cell {
var spaces: [direction.N .. direction.W] bool;
var visited: bool;
}
const dirs = [
((-1, 0), direction.N, direction.S), // ((rowDir, colDir), myWall, neighbourWall)
((0, 1), direction.E, direction.W),
((1, 0), direction.S, direction.N),
((0, -1), direction.W, direction.E)
];
var maze: [1..rows, 1..cols] Cell;
var startingCell = (choose(maze.dim(0)), choose(maze.dim(1)));
checkCell(maze, startingCell);
displayMaze(maze);
proc checkCell(ref maze, cell) {
maze[cell].visited = true;
for dir in permute(dirs) {
var (offset, thisDir, neighbourDir) = dir;
var neighbour = cell + offset;
if maze.domain.contains(neighbour) && !maze[neighbour].visited {
maze[cell].spaces[thisDir] = true;
maze[neighbour].spaces[neighbourDir] = true;
checkCell(maze, neighbour);
}
}
}
proc displayMaze(maze) {
for row in maze.dim(0) {
for col in maze.dim(1) {
write(if maze[row, col].spaces[direction.N] then "+ " else "+---");
}
writeln("+");
for col in maze.dim(1) {
write(if maze[row, col].spaces[direction.W] then " " else "| ");
}
writeln("|");
}
write("+---" * maze.dim(1).size);
writeln("+");
}
</syntaxhighlight>
{{out}}
<pre>
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | | |
+ + + +---+---+ + +---+ + +---+---+ +---+---+ +
| | | | | | | | | |
+ +---+---+---+ +---+---+ + +---+ +---+ + + +---+
| | | | | | |
+---+---+ + +---+---+---+---+---+---+ + +---+---+---+ +
| | | | | | |
+ + +---+---+---+---+---+ + +---+---+---+---+---+ + +
| | | | | | | |
+ +---+---+---+ + +---+---+ + +---+ +---+ +---+ +
| | | | | | | | | | |
+ +---+ + +---+---+ + +---+---+ + + +---+ + +
| | | | | | | | |
+---+---+---+ + + + +---+---+ + +---+---+ +---+ +
| | | | | | | | | | | |
+ + +---+ + + +---+ + + +---+ + +---+ + +
| | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
</pre>
=={{header|Clojure}}==
Line 2,514 ⟶ 2,751:
=={{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]
<syntaxhighlight
size = 15
n = 2 * size + 1
f = 100 / (n - 0.5)
len m[] n * n
#
background 000
proc show_maze . .
Line 2,537 ⟶ 2,774:
.
offs[] = [ 1 n -1 (-n) ]
#
proc m_maze pos . .
m[pos] = 0
Line 2,543 ⟶ 2,780:
d[] = [ 1 2 3 4 ]
for i = 4 downto 1
d =
dir = offs[d[d]]
d[d] = d[i]
Line 2,563 ⟶ 2,800:
m[n * n - n + i] = 2
.
h = 2 *
m_maze h
m[endpos] = 0
Line 2,571 ⟶ 2,808:
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}}==
Line 4,161 ⟶ 4,733:
[[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}}==
Line 4,984 ⟶ 5,658:
<a id='solve' style='display:none' href='javascript:solve(); void(0)'>Solve</a>
</fieldset></form><table id='maze'/></body></html></syntaxhighlight>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
'''Works with jq, the C implementation of jq'''
'''Works with gojq, the Go implementation of jq'''
Since jq does not have a builtin PRNG,
it is assumed that /dev/urandom is available.
An invocation such as the following may be used:
<pre>
< /dev/urandom tr -cd '0-9' | fold -w 1 | jq -Rcnr -f maze-generation.jq
</pre>
In the following, a maze is represented by a matrix, each of whose elements
is in turn a JSON object representing the bounding box:
$box["N"] is true iff the northern (top) edge is open, and similarly for the
other points of the compass.
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
display.
<syntaxhighlight lang="jq">
# Output: a prn in range(0;$n) where $n is .
def prn:
if . == 1 then 0
else . as $n
| (($n-1)|tostring|length) as $w
| [limit($w; inputs)] | join("") | tonumber
| if . < $n then . else ($n | prn) end
end;
# Input: an array
def knuthShuffle:
length as $n
| if $n <= 1 then .
else {i: $n, a: .}
| 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
# directions in which to move, i.e. to open a gate.
# For example, Compass.n corresponds to a move north (i.e. dx is 0, dy is 1),
# 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.
# .[$i][$j] represents the box in row $i, column $j.
# 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
def generate($cx; $cy):
def interior($a; $upper): $a >= 0 and $a < $upper;
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
def display:
. 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
def amaze($x;$y):
MazeMatrix($x; $y)
| generate(0; 0)
| display;
# Example
amaze(4; 5);
</syntaxhighlight>
{{output}}
Example output:
<pre>
+---+---+---+---+---+
| | |
+---+ + +---+ +
| | | | |
+ + + + + +
| | | | | |
+ + +---+ + +
| | |
+---+---+---+---+---+
</pre>
=={{header|Julia}}==
Line 6,482 ⟶ 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}}==
Line 8,243 ⟶ 9,226:
func walk(x, y) {
cell[y][x] = false
avail-- > 0 || return
var d = [[-1, 0], [0, 1], [1, 0], [0, -1]]
Line 9,078 ⟶ 10,061:
=={{header|
{{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="
import "os" for Process
Line 9,252 ⟶ 10,216:
| | |
+---+---+---+---+---+---+---+---+
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang="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)
def LeftWall, Ceiling, Connected; \attributes of each cell (= 0, 1 and 2)
proc ConnectFrom(X, Y); \Connect cells starting from cell X,Y
int X, Y;
int Dir, Dir0;
[Cell(X, Y, Connected):= true; \mark current cell as connected
Dir:= Ran(4); \randomly choose a direction
Dir0:= Dir; \save this initial direction
repeat case Dir of \try to connect to cell at Dir
0: if X+1<Cols & not Cell(X+1, Y, Connected) then \go right
[Cell(X+1, Y, LeftWall):= false; ConnectFrom(X+1, Y)];
1: if Y+1<Rows & not Cell(X, Y+1, Connected) then \go down
[Cell(X, Y+1, Ceiling):= false; ConnectFrom(X, Y+1)];
2: if X-1>=0 & not Cell(X-1, Y, Connected) then \go left
[Cell(X, Y, LeftWall):= false; ConnectFrom(X-1, Y)];
3: if Y-1>=0 & not Cell(X, Y-1, Connected) then \go up
[Cell(X, Y, Ceiling):= false; ConnectFrom(X, Y-1)]
other []; \(never occurs)
Dir:= Dir+1 & $03; \next direction
until Dir = Dir0;
];
int X, Y;
[for Y:= 0 to Rows do
for X:= 0 to Cols do
[Cell(X, Y, LeftWall):= true; \start with all walls and
Cell(X, Y, Ceiling):= true; \ ceilings in place
Cell(X, Y, Connected):= false; \ and all cells disconnected
];
Cell(0, 0, LeftWall):= false; \make left and right doorways
Cell(Cols, Rows-1, LeftWall):= false;
ConnectFrom(Ran(Cols), Ran(Rows)); \randomly pick a starting cell
for Y:= 0 to Rows do \display the maze
[CrLf(0);
for X:= 0 to Cols do
Text(0, if X#Cols & Cell(X, Y, Ceiling) then "+--" else "+ ");
CrLf(0);
for X:= 0 to Cols do
Text(0, if Y#Rows & Cell(X, Y, LeftWall) then "| " else " ");
];
]</syntaxhighlight>
Output:
<pre>
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | |
+ +--+ +--+ +--+--+--+ + +--+ + +--+--+--+--+--+--+ +
| | | | | | | | | | | |
+ + + + +--+ + +--+--+ + +--+--+ +--+--+ +--+ +--+
| | | | | | | | | | |
+ +--+--+ + +--+ + +--+--+--+--+--+--+ + +--+ +--+ +
| | | | | | | | | |
+--+ + +--+--+ + + + +--+--+ + +--+--+--+--+--+--+ +
| | | | | | | | | | | | |
+ + + + +--+--+ + + + + +--+--+ + + + + +--+--+
| | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
</pre>
| |||