Maze generation: Difference between revisions
(Undo revision 98188 by 79.27.12.250 (talk)) |
(→{{header|D}}: Not a dept first search) |
||
| Line 295: | Line 295: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{works with|D|2}} |
{{works with|D|2}} |
||
<lang d>import std.stdio, std.random, std.string; |
|||
enum { N = 1, S = 2, E = 4, W = 8 } |
|||
uint[][] maze; |
|||
enum DX = [E: 1, W: -1, N: 0, S: 0]; |
|||
enum DY = [E: 0, W: 0, N: -1, S: 1]; |
|||
enum INVERSE = [E: W, W: E, N: S, S: N]; |
|||
void generateMaze(int cx, int cy) { |
|||
auto directions = [N, S, E, W]; |
|||
randomShuffle(directions); |
|||
foreach (direction; directions) { |
|||
auto nx = cx + DX[direction]; |
|||
auto ny = cy + DY[direction]; |
|||
if (0 <= ny && ny < maze.length && |
|||
0 <= nx && nx < maze[0].length && maze[ny][nx] == 0) { |
|||
maze[cy][cx] |= direction; |
|||
maze[ny][nx] |= INVERSE[direction]; |
|||
generateMaze(nx, ny); |
|||
} |
|||
} |
|||
} |
|||
void printMaze() { |
|||
writeln(" " ~ repeat("_", maze[0].length * 2 - 1)); |
|||
foreach (y; 0 .. maze.length) { |
|||
write('|'); |
|||
foreach (x; 0 .. maze[0].length) { |
|||
write(((maze[y][x] & S) != 0) ? ' ' : '_'); |
|||
if ((maze[y][x] & E) != 0) |
|||
write((((maze[y][x] | maze[y][x+1]) & S) != 0) ? ' ' : '_'); |
|||
else |
|||
write('|'); |
|||
} |
|||
writeln(); |
|||
} |
|||
} |
|||
void main() { |
|||
maze = new uint[][](8, 11); |
|||
generateMaze(0, 0); |
|||
printMaze(); |
|||
}</lang> |
|||
Output: |
|||
<pre> _____________________ |
|||
|___ |_ _______ | | |
|||
| ___| _| ___ |_ | |
|||
|___ | ___| _| | | | |
|||
| _| |_ ___| _| | | |
|||
| | _| _| | |_____| |
|||
| |_ | _| | |_ _ | |
|||
| | _|_| _|_ |_| | |
|||
|_________|_________|_|</pre> |
|||
===Alternative version 1=== |
|||
<lang d>import std.stdio: write, writeln; |
<lang d>import std.stdio: write, writeln; |
||
import std.random: uniform; |
import std.random: uniform; |
||
| Line 358: | Line 304: | ||
uint m; |
uint m; |
||
} |
} |
||
Cell[][] buildMaze(int width, int height) { |
Cell[][] buildMaze(int width, int height) { |
||
| Line 496: | Line 441: | ||
+---+---+---+---+---+---+---+---+---+---+---+</pre> |
+---+---+---+---+---+---+---+---+---+---+---+</pre> |
||
===Alternative version |
===Alternative version === |
||
See [[Maze_solving#D]] |
See [[Maze_solving#D]] |
||
Revision as of 10:16, 30 December 2010
You are encouraged to solve this task according to the task description, using any language you may know.
| This page uses content from Wikipedia. The original article was at Maze generation algorithm. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
Generate and show a maze, using the simple Depth-first search algorithm.
- Start at a random cell.
- Mark the current cell as visited, and get a list of its neighbors. For each neighbor, starting with a randomly selected neighbor:
- If that neighbor hasn't been visited, remove the wall between this cell and that neighbor, and then recurse with that neighbor as the current cell.
See also Maze solving.
Ada
mazes.ads: <lang Ada>generic
Height : Positive; Width : Positive;
package Mazes is
type Maze_Grid is private;
procedure Initialize (Maze : in out Maze_Grid);
procedure Put (Item : Maze_Grid);
private
type Directions is (North, South, West, East);
type Cell_Walls is array (Directions) of Boolean;
type Cells is record
Walls : Cell_Walls := (others => True);
Visited : Boolean := False;
end record;
subtype Height_Type is Positive range 1 .. Height; subtype Width_Type is Positive range 1 .. Width;
type Maze_Grid is array (Height_Type, Width_Type) of Cells;
end Mazes;</lang>
mazes.adb: <lang Ada>with Ada.Numerics.Discrete_Random; with Ada.Text_IO;
package body Mazes is
package RNG is new Ada.Numerics.Discrete_Random (Positive); package Random_Direction is new Ada.Numerics.Discrete_Random (Directions);
Generator : RNG.Generator; Dir_Generator : Random_Direction.Generator;
function "-" (Dir : Directions) return Directions;
procedure Depth_First_Algorithm
(Maze : in out Maze_Grid;
Row : Height_Type;
Column : Width_Type);
function Has_Unvisited_Neighbours
(Maze : Maze_Grid;
Row : Height_Type;
Column : Width_Type)
return Boolean;
procedure Move
(Row : in out Height_Type;
Column : in out Width_Type;
Direction : Directions;
Valid_Move : out Boolean);
function "-" (Dir : Directions) return Directions is
begin
case Dir is
when North =>
return South;
when South =>
return North;
when East =>
return West;
when West =>
return East;
end case;
end "-";
procedure Depth_First_Algorithm
(Maze : in out Maze_Grid;
Row : Height_Type;
Column : Width_Type)
is
Next_Row : Height_Type;
Next_Column : Width_Type;
Next_Direction : Directions;
Valid_Direction : Boolean;
begin
-- mark as visited
Maze (Row, Column).Visited := True;
-- continue as long as there are unvisited neighbours left
while Has_Unvisited_Neighbours (Maze, Row, Column) loop
-- use random direction
Next_Direction := Random_Direction.Random (Dir_Generator);
Next_Row := Row;
Next_Column := Column;
Move (Next_Row, Next_Column, Next_Direction, Valid_Direction);
if Valid_Direction then
-- connect the two cells
if not Maze (Next_Row, Next_Column).Visited then
Maze (Row, Column).Walls (Next_Direction) :=
False;
Maze (Next_Row, Next_Column).Walls (-Next_Direction) :=
False;
Depth_First_Algorithm (Maze, Next_Row, Next_Column);
end if;
end if;
end loop;
end Depth_First_Algorithm;
function Has_Unvisited_Neighbours
(Maze : Maze_Grid;
Row : Height_Type;
Column : Width_Type)
return Boolean
is
Neighbour_Row : Height_Type;
Neighbour_Column : Width_Type;
Is_Valid : Boolean;
begin
for Dir in Directions loop
Neighbour_Row := Row;
Neighbour_Column := Column;
Move
(Row => Neighbour_Row,
Column => Neighbour_Column,
Direction => Dir,
Valid_Move => Is_Valid);
if Is_Valid
and then not Maze (Neighbour_Row, Neighbour_Column).Visited
then
return True;
end if;
end loop;
return False;
end Has_Unvisited_Neighbours;
procedure Initialize (Maze : in out Maze_Grid) is
Row, Column : Positive;
begin
-- initialize random generators
RNG.Reset (Generator);
Random_Direction.Reset (Dir_Generator);
-- choose starting cell
Row := RNG.Random (Generator) mod Height + 1;
Column := RNG.Random (Generator) mod Width + 1;
Ada.Text_IO.Put_Line
("Starting generation at " &
Positive'Image (Row) &
" x" &
Positive'Image (Column));
Depth_First_Algorithm (Maze, Row, Column);
end Initialize;
procedure Move
(Row : in out Height_Type;
Column : in out Width_Type;
Direction : Directions;
Valid_Move : out Boolean)
is
begin
Valid_Move := False;
case Direction is
when North =>
if Row > Height_Type'First then
Valid_Move := True;
Row := Row - 1;
end if;
when East =>
if Column < Width_Type'Last then
Valid_Move := True;
Column := Column + 1;
end if;
when West =>
if Column > Width_Type'First then
Valid_Move := True;
Column := Column - 1;
end if;
when South =>
if Row < Height_Type'Last then
Valid_Move := True;
Row := Row + 1;
end if;
end case;
end Move;
procedure Put (Item : Maze_Grid) is
begin
for Row in Item'Range (1) loop
if Row = Item'First (1) then
for Col in Item'Range (2) loop
if Col = Item'First (2) then
Ada.Text_IO.Put ('+');
end if;
if Item (Row, Col).Walls (North) then
Ada.Text_IO.Put ("---");
else
Ada.Text_IO.Put (" ");
end if;
Ada.Text_IO.Put ('+');
end loop;
Ada.Text_IO.New_Line;
end if;
for Col in Item'Range (2) loop
if Col = Item'First (2) then
if Item (Row, Col).Walls (West) then
Ada.Text_IO.Put ('|');
else
Ada.Text_IO.Put (' ');
end if;
elsif Item (Row, Col).Walls (West)
and then Item (Row, Col - 1).Walls (East)
then
Ada.Text_IO.Put ('|');
elsif Item (Row, Col).Walls (West)
or else Item (Row, Col - 1).Walls (East)
then
Ada.Text_IO.Put ('>');
else
Ada.Text_IO.Put (' ');
end if;
if Item (Row, Col).Visited then
Ada.Text_IO.Put (" ");
else
Ada.Text_IO.Put ("???");
end if;
if Col = Item'Last (2) then
if Item (Row, Col).Walls (East) then
Ada.Text_IO.Put ('|');
else
Ada.Text_IO.Put (' ');
end if;
end if;
end loop;
Ada.Text_IO.New_Line;
for Col in Item'Range (2) loop
--for Col in Item'Range (2) loop
if Col = Item'First (2) then
Ada.Text_IO.Put ('+');
end if;
if Item (Row, Col).Walls (South) then
Ada.Text_IO.Put ("---");
else
Ada.Text_IO.Put (" ");
end if;
Ada.Text_IO.Put ('+');
--end loop;
end loop;
Ada.Text_IO.New_Line;
end loop;
end Put;
end Mazes;</lang>
Example main.adb: <lang Ada>with Mazes; procedure Main is
package Small_Mazes is new Mazes (Height => 8, Width => 11); My_Maze : Small_Mazes.Maze_Grid;
begin
Small_Mazes.Initialize (My_Maze); Small_Mazes.Put (My_Maze);
end Main;</lang>
Output:
Starting generation at 3 x 7 +---+---+---+---+---+---+---+---+---+---+---+ | | | | | + + + +---+ + + +---+---+---+ + | | | | | | | + +---+---+ +---+---+ + + + +---+ | | | | | | | | + +---+---+---+---+ +---+ + + + + | | | | | | | + + +---+ + + + +---+---+---+ + | | | | | | | + + +---+---+---+---+---+ +---+ + + | | | | | | +---+ + +---+---+---+ +---+---+---+ + | | | | | + +---+ +---+---+ +---+---+---+---+---+ | | +---+---+---+---+---+---+---+---+---+---+---+
D
<lang d>import std.stdio: write, writeln; import std.random: uniform;
enum : uint { VISITED = 1, NORTH = 2, EAST = 4, SOUTH = 8, WEST = 16 };
struct Cell {
int c, r; uint m;
}
Cell[][] buildMaze(int width, int height) {
Cell[][] maze;
pure nothrow static void breakWall(ref Cell c, ref Cell n) {
if (c.c == n.c) {
if (c.r < n.r) {
c.m &= ~SOUTH;
n.m &= ~NORTH;
} else if (c.r > n.r) {
c.m &= ~NORTH;
n.m &= ~SOUTH;
}
} else if (c.r == n.r) {
if (c.c < n.c) {
c.m &= ~EAST;
n.m &= ~WEST;
} else if (c.c > n.c) {
c.m &= ~WEST;
n.m &= ~EAST;
}
}
}
pure nothrow static bool deadEnd(const Cell[] nbrs) {
foreach (n; nbrs) {
if ((n.m & VISITED) == 0)
return false;
}
return true;
}
nothrow void setNeighbors(const Cell c, ref Cell[] nbrs) {
nbrs.length = 0;
if (c.r != 0)
nbrs ~= maze[c.c][c.r - 1]; // n
if (c.c != 0)
nbrs ~= maze[c.c - 1][c.r]; // w
if (c.r != height - 1)
nbrs ~= maze[c.c][c.r + 1]; // s
if (c.c != width - 1)
nbrs ~= maze[c.c + 1][c.r]; // e
}
void dig(ref Cell c, ref Cell[] stack, ref Cell[] nbrs) {
Cell n;
do {
n = nbrs[uniform(0, nbrs.length)];
} while ((n.m & VISITED) != 0)
n.m |= VISITED;
breakWall(c, n);
maze[c.c][c.r] = c;
maze[n.c][n.r] = n;
stack ~= c;
c = n;
setNeighbors(c, nbrs);
}
// setup
maze = new Cell[][](width, height);
foreach (r; 0 .. height)
foreach (c; 0 .. width)
maze[c][r] = Cell(c, r, NORTH|EAST|SOUTH|WEST);
Cell[] nbrs, stack;
Cell c = maze[uniform(0, width)][uniform(0, height)]; c.m |= VISITED; setNeighbors(c, nbrs); dig(c, stack, nbrs);
// go
while (stack.length > 0) {
if (deadEnd(nbrs)) {
c = stack[$ - 1];
stack.length -= 1;
setNeighbors(c, nbrs);
} else {
dig(c, stack, nbrs);
}
}
return maze;
}
void printMaze(Cell[][] maze) {
immutable int width = maze.length; immutable int height = maze[0].length;
maze[0][0].m &= ~NORTH; maze[$-1][$-1].m &= ~EAST;
foreach (r; 0 .. height) {
string hori, vert;
foreach (c; 0 .. width) {
if (maze[c][r].m & NORTH)
hori ~= (c == width - 1) ? "+---+" : "+---";
else
hori ~= (c == width - 1) ? "+ +" : "+ ";
if (maze[c][r].m & EAST)
vert ~= (c == 0) ? "| |" : " |";
else
vert ~= (c == 0) ? "| " : " ";
}
writeln(hori, "\n", vert);
}
foreach (c; 0 .. width)
write("+---");
writeln("+");
}
void main() {
printMaze(buildMaze(11, 8));
}</lang> Output example:
+ +---+---+---+---+---+---+---+---+---+---+ | | | | + +---+ + +---+ +---+---+---+ + + | | | | | | + + +---+---+---+---+---+ +---+---+ + | | | | | | + +---+---+---+---+---+ + + +---+---+ | | | | | +---+ + +---+---+ +---+---+---+---+ + | | | | + + +---+---+---+ + +---+---+---+---+ | | | | | | | + +---+ +---+ + +---+---+ + + + | | | | | | | | + + +---+ + +---+ + +---+---+ + | | | | +---+---+---+---+---+---+---+---+---+---+---+
Alternative version
See Maze_solving#D
J
This algorithm allows almost no parallelism. So, while it might be "simple", generating very large mazes this way will not be necessarily efficient to implement on future (highly parallel) systems. That said, perhaps mazes with millions of cells are not very likely to be needed to be generated quickly.
Anyways, based on the picolisp implementation, except without any relevant grid support:
<lang j>maze=:4 :0
assert.0<:n=.<:x*y
horiz=. 0$~x,y-1
verti=. 0$~(x-1),y
path=.,:here=. ?x,y
unvisited=.0 (<here+1)} 0,0,~|:0,0,~1$~y,x
while.n do.
neighbors=. here+"1 (,-)=0 1
neighbors=. neighbors #~ (<"1 neighbors+1) {unvisited
if.#neighbors do.
n=.n-1
next=. ({~ ?@#) neighbors
unvisited=.0 (<next+1)} unvisited
if.{.next=here
do. horiz=.1 (<-:here+next-0 1)} horiz
else. verti=. 1 (<-:here+next-1 0)} verti end.
path=.path,here=.next
else.
here=.{:path
path=.}:path
end.
end.
horiz;verti
)
display=:3 :0
size=. >.&$&>/y
text=. (}:1 3$~2*1+{:size)#"1":size$<' '
'hdoor vdoor'=. 2 4&*&.>&.> (#&,{@;&i./@$)&.> y
' ' (a:-.~0 1;0 2; 0 3;(2 1-~$text);(1 4&+&.> hdoor),,vdoor+&.>"0/2 1;2 2;2 3)} text
)</lang>
The result of maze is a pair of arrays: one for open "doors" in the horizontal direction and the other for open "doors" in the vertical direction. The entry and exit doors are not represented by maze -- they are implicitly defined and are implemented in display.
Example use (with ascii box drawing enabled):
<lang j> display 8 maze 11 + +---+---+---+---+---+---+---+---+---+---+ | | | | | + + + + +---+ + +---+---+ + + | | | | | | | | + +---+---+ + +---+---+---+ + + + | | | | | | | +---+ +---+ + + +---+ + +---+---+ | | | | | | | + + +---+---+ +---+ + +---+---+ + | | | | | | | | | + +---+ + + + + +---+---+ + + | | | | | + +---+---+---+---+---+---+---+ +---+ + | | | | | | | | | + + + + + + + + +---+ + + | | | | | +---+---+---+---+---+---+---+---+---+---+---+</lang>
JavaScript
<lang javascript>function maze(x,y) { var n=x*y-1; if (n<0) {alert("illegal maze dimensions");return;} var horiz=[]; for (var j= 0; j<x+1; j++) horiz[j]= []; var verti=[]; for (var j= 0; j<x+1; j++) verti[j]= []; var here= [Math.floor(Math.random()*x), Math.floor(Math.random()*y)]; var path= [here]; var unvisited= []; for (var j= 0; j<x+2; j++) { unvisited[j]= []; for (var k= 0; k<y+1; k++) unvisited[j].push(j>0 && j<x+1 && k>0 && (j != here[0]+1 || k != here[1]+1)); } while (0<n) { var potential= [[here[0]+1, here[1]], [here[0],here[1]+1], [here[0]-1, here[1]], [here[0],here[1]-1]]; var neighbors= []; for (var j= 0; j < 4; j++) if (unvisited[potential[j][0]+1][potential[j][1]+1]) neighbors.push(potential[j]); if (neighbors.length) { n= n-1; next= neighbors[Math.floor(Math.random()*neighbors.length)]; unvisited[next[0]+1][next[1]+1]= false; if (next[0] == here[0]) horiz[next[0]][(next[1]+here[1]-1)/2]= true; else verti[(next[0]+here[0]-1)/2][next[1]]= true; path.push(here= next); } else here= path.pop(); } return ({x: x, y: y, horiz: horiz, verti: verti}); }
function display(m) {
var text= [];
for (var j= 0; j<m.x*2+1; j++) {
var line= [];
if (0 == j%2)
for (var k=0; k<m.y*4+1; k++)
if (0 == k%4)
line[k]= '+';
else
if (j>0 && m.verti[j/2-1][Math.floor(k/4)])
line[k]= ' ';
else
line[k]= '-';
else
for (var k=0; k<m.y*4+1; k++)
if (0 == k%4)
if (k>0 && m.horiz[(j-1)/2][k/4-1])
line[k]= ' ';
else
line[k]= '|';
else
line[k]= ' ';
if (0 == j) line[1]= line[2]= line[3]= ' ';
if (m.x*2-1 == j) line[4*m.y]= ' ';
text.push(line.join()+'\r\n');
}
return text.join();
}</lang>
Variable meanings in function maze:
x,y-- dimensions of mazen-- number of openings to be generatedhoriz-- two dimensional array of locations of horizontal openings (true means wall is open)verti-- two dimensional array of locations of vertical openings (true means wall is open)here-- current location under considerationpath-- history (stack) of locations that might need to be revisitedunvisited-- two dimensional array of locations that have not been visited, padded to avoid need for boundary tests (true means location needs to be visited)potential-- locations adjacent tohereneighbors-- unvisited locations adjacent tohere
Variable meanings in function display:
m-- maze to be drawntext-- lines of text representing mazeline-- characters of current line
Note that this implementation relies on javascript arrays being treatable as infinite in size with false (null) values springing into existence as needed, to support referenced array locations. (This significantly reduces the bulk of the necessary initialization code.)
Example use:
<lang html><html><head><title></title></head><body>
</body></html>
<script type="text/javascript"> /* ABOVE CODE GOES HERE */ document.getElementById('out').innerHTML= display(maze(8,11)); </script></lang>
produced:
<lang>+ +---+---+---+---+---+---+---+---+---+---+ | | | | +---+---+ + +---+ + +---+---+ + + | | | | | | | | + + + +---+ +---+ +---+---+ + + | | | | | | | + +---+ +---+---+---+---+---+ + + + | | | | | | +---+ +---+ +---+---+ + +---+---+ + | | | | | | | + + + +---+---+---+---+---+ + + + | | | | | | + +---+---+ +---+---+ + +---+---+ + | | | | | | | + + + +---+ +---+---+ + + +---+ | | | | +---+---+---+---+---+---+---+---+---+---+---+</lang>
For an animated presentation of the progress of this maze creation process, you can use display in each iteration of the main loop. You would also need to take steps to make sure you could see each intermediate result.
For example, change replace the line while (0<n) { with:
<lang javascript> function step() { if (0<n) {</lang>
And replace the closing brace for this while loop with:
<lang javascript> document.getElementById('out').innerHTML= display({x: x, y: y, horiz: horiz, verti: verti, here: here}); setTimeout(step, 100); } } step();</lang>
To better see the progress, you might want a marker in place, showing the position being considered. To do that, replace the line which reads if (0 == k%4) { with
<lang javascript> if (m.here && m.here[0]*2+1 == j && m.here[1]*4+2 == k) line[k]= '#' else if (0 == k%4) {</lang>
Note however that this leaves the final '#' in place on maze completion, and that the function maze no longer returns a result which represents a generated maze.
Note also that this display suggests an optimization. You can replace the line reading path.push(here= next); with:
<lang javascript> here= next; if (1 < neighbors.length) path.push(here);</lang>
And this does indeed save a negligible bit of processing, but the maze algorithm will still be forced to backtrack through a number of locations which have no unvisited neighbors.
PicoLisp
This solution uses 'grid' from "lib/simul.l" to generate the two-dimensional structure. <lang PicoLisp>(load "@lib/simul.l")
(de maze (DX DY)
(let Maze (grid DX DY)
(let Fld (get Maze (rand 1 DX) (rand 1 DY))
(recur (Fld)
(for Dir (shuffle '((west . east) (east . west) (south . north) (north . south)))
(with ((car Dir) Fld)
(unless (or (: west) (: east) (: south) (: north))
(put Fld (car Dir) This)
(put This (cdr Dir) Fld)
(recurse This) ) ) ) ) )
(for (X . Col) Maze
(for (Y . This) Col
(set This
(cons
(cons
(: west)
(or
(: east)
(and (= Y 1) (= X DX)) ) )
(cons
(: south)
(or
(: north)
(and (= X 1) (= Y DY)) ) ) ) ) ) )
Maze ) )
(de display (Maze)
(disp Maze 0 '((This) " ")) )</lang>
Output:
: (display (maze 11 8))
+ +---+---+---+---+---+---+---+---+---+---+
8 | | | |
+ + + + + + +---+ +---+---+ +
7 | | | | | | | | |
+---+ +---+---+ + + +---+ + + +
6 | | | | | | | |
+ +---+ +---+ +---+---+---+ + +---+
5 | | | | | |
+---+ +---+ +---+---+---+ +---+---+ +
4 | | | | | | |
+ +---+ +---+ +---+ + + +---+ +
3 | | | | | | | |
+ +---+---+ + + + + +---+ + +
2 | | | | | | | | |
+ + + +---+ + +---+ + +---+ +
1 | | | |
+---+---+---+---+---+---+---+---+---+---+---+
a b c d e f g h i j k
PureBasic
<lang PureBasic>Enumeration
;types of offsets #visited #maze #wall ;direction indexes #dir_N = 0 #dir_E #dir_S #dir_W #dir_ID ;identity value, produces no changes #dirMax
EndEnumeration
DataSection
;maze(x,y) offsets for visited, maze, & walls for each direction Data.i 1, 0, 0, -1, 0, 0 ;N Data.i 2, 1, 1, 0, 1, 0 ;E Data.i 1, 2, 0, 1, 0, 1 ;S Data.i 0, 1, -1, 0, 0, 0 ;W Data.i 1, 1, 0, 0, 0, 0 ;ID Data.i %01, %10, %01, %10, %00 ;wall values for N, E, S, W, ID
EndDataSection
- setup reference values indexed by direction from current map cell
Global Dim offset.POINT(2, #dirMax) Define i, j For i = #dir_N To #dir_ID
For j = 0 To 2 Read.i offset(j, i)\x: Read.i offset(j, i)\y Next
Next
Global Dim wallvalue(#dirMax) For i = #dir_N To #dir_ID: Read.i wallvalue(i): Next
Procedure displayMaze(Array maze(2))
Protected x, y, vWall.s, hWall.s Protected mazeWidth = ArraySize(maze(), 1), mazeHeight = ArraySize(maze(), 2)
For y = 0 To mazeHeight
vWall = "": hWall = ""
For x = 0 To mazeWidth
If maze(x, y) & wallvalue(#dir_N): vWall + "+ ": Else: vWall + "+---": EndIf
If maze(x, y) & wallvalue(#dir_W): hWall + " ": Else: hWall + "| ": EndIf
Next
PrintN(Left(vWall, Len(vWall) - 3))
If y <> mazeHeight: PrintN(hWall): EndIf
Next
EndProcedure
Procedure generateMaze(Array maze(2), mazeWidth, mazeHeight)
Dim maze(mazeWidth, mazeHeight) ;includes an extra row and column for the SE corner Dim visited(mazeWidth + 1, mazeHeight + 1) ;includes padding for easy border detection Protected i ;mark outside border as already visited (off limits) For i = 1 To mazeWidth visited(i, 0) = #True: visited(i, mazeHeight + 1) = #True Next For i = 1 To mazeHeight visited(0, i) = #True: visited(mazeWidth + 1, i) = #True Next
;generate maze
Protected x = Random(mazeWidth - 1), y = Random (mazeHeight - 1), cellCount, nextCell
visited(x + offset(#visited, #dir_ID)\x, y + offset(#visited, #dir_ID)\y) = #True
PrintN("Started generation at " + Str(x) + " x " + Str(y))
NewList stack.POINT()
Dim unvisited(#dirMax - 1)
Repeat
cellCount = 0
For i = #dir_N To #dir_W
If Not visited(x + offset(#visited, i)\x, y + offset(#visited, i)\y)
unvisited(cellCount) = i: cellCount + 1
EndIf
Next
If cellCount
nextCell = unvisited(Random(cellCount - 1))
visited(x + offset(#visited, nextCell)\x, y + offset(#visited, nextCell)\y) = #True
maze(x + offset(#wall, nextCell)\x, y + offset(#wall, nextCell)\y) | wallvalue(nextCell)
If cellCount > 1
AddElement(stack())
stack()\x = x: stack()\y = y
EndIf
x + offset(#maze, nextCell)\x: y + offset(#maze, nextCell)\y
ElseIf ListSize(stack()) > 0
x = stack()\x: y = stack()\y
DeleteElement(stack())
Else
Break ;end maze generation
EndIf
ForEver
ProcedureReturn
EndProcedure
Dim maze(0, 0)
If OpenConsole()
generateMaze(maze(), 11, 8) displayMaze(maze())
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input() CloseConsole()
EndIf </lang> Sample output:
Started generation at 9 x 3 +---+---+---+---+---+---+---+---+---+---+---+ | | | | | + + +---+ + +---+ + +---+ + + | | | | | | | | + +---+ +---+---+ +---+ + +---+---+ | | | | | | + + +---+---+ +---+---+---+---+---+ + | | | | | | + +---+ +---+ + +---+ + +---+---+ | | | | | | +---+---+---+ + + +---+---+ +---+ + | | | | | | + +---+---+ +---+ +---+---+ + +---+ | | | | | | | + + + +---+---+---+ + +---+---+ + | | | | +---+---+---+---+---+---+---+---+---+---+---+
Python
<lang Python>from random import randrange, choice
def make_maze(height, width):
def get_candidate_neighbors(cells, i):
neighbors = []
n = i - width
s = i + width
e = i + 1
w = i - 1
if n >= 0 and not cells[n]:
neighbors.append(n)
if (s < height * width) and (not cells[s]):
neighbors.append(s)
if (e // width == i // width) and (not cells[e]):
neighbors.append(e)
if (w // width == i // width) and (not cells[w]):
neighbors.append(w)
return neighbors
# cells data structure is simply a list of lists. Each cell # has a list of the neighbors where there is a connection # so an empty list means that a cell has all walls remaining. total_cells = height * width cells = [[] for i in xrange(total_cells)] cur_cell = randrange(total_cells) visited = 1 cellstack = []
while visited < total_cells:
neighbors = get_candidate_neighbors(cells, cur_cell)
if len(neighbors):
new = choice(neighbors)
# breakdown the wall
cells[cur_cell].append(new)
cells[new].append(cur_cell)
cellstack.append(cur_cell)
cur_cell = new
visited += 1
else:
cur_cell = cellstack.pop()
return cells
def show_maze(cells, height, width):
s1, s2 = "", ""
for i in xrange(height * width):
if i % width == 0:
print s1
print s2
s1 = "+"
s2 = "|"
s1 += " +" if (i - width) in cells[i] else "--+"
s2 += " " if (i + 1) in cells[i] else " |"
s1 = "+"
for i in xrange(width):
s1 += "--+"
print s1
def main():
height, width = 8, 11 show_maze(make_maze(height, width), height, width)
if __name__=="__main__":
main()</lang>
Sample Output:
+--+--+--+--+--+--+--+--+--+--+--+ | | | | + +--+--+ +--+ + +--+ + + + | | | | | | | | +--+--+ + + +--+ + +--+--+ + | | | | | | + + +--+ +--+--+--+ +--+--+--+ | | | | | | + + + +--+ + +--+--+--+--+ + | | | | | | + +--+--+--+--+--+--+ + + +--+ | | | | | +--+--+ +--+ + +--+--+--+--+ + | | | | | | | +--+--+--+--+--+--+--+--+--+--+--+
Tcl
<lang tcl>package require TclOO; # Or Tcl 8.6
- Helper to pick a random number
proc rand n {expr {int(rand() * $n)}}
- Helper to pick a random element of a list
proc pick list {lindex $list [rand [llength $list]]}
- Helper _function_ to index into a list of lists
proc tcl::mathfunc::idx {v x y} {lindex $v $x $y}
oo::class create maze {
variable x y horiz verti content
constructor {width height} {
set y $width set x $height
set n [expr {$x * $y - 1}] if {$n < 0} {error "illegal maze dimensions"} set horiz [set verti [lrepeat $x [lrepeat $y 0]]] # This matrix holds the output for the Maze Solving task; not used for generation set content [lrepeat $x [lrepeat $y " "]] set unvisited [lrepeat [expr {$x+2}] [lrepeat [expr {$y+2}] 0]] # Helper to write into a list of lists (with offsets) proc unvisited= {x y value} { upvar 1 unvisited u lset u [expr {$x+1}] [expr {$y+1}] $value }
lappend stack [set here [list [rand $x] [rand $y]]] for {set j 0} {$j < $x} {incr j} { for {set k 0} {$k < $y} {incr k} { unvisited= $j $k [expr {$here ne [list $j $k]}] } }
while {0 < $n} { lassign $here hx hy set neighbours {} foreach {dx dy} {1 0 0 1 -1 0 0 -1} { if {idx($unvisited, $hx+$dx+1, $hy+$dy+1)} { lappend neighbours [list [expr {$hx+$dx}] [expr {$hy+$dy}]] } } if {[llength $neighbours]} { lassign [set here [pick $neighbours]] nx ny unvisited= $nx $ny 0 if {$nx == $hx} { lset horiz $nx [expr {min($ny, $hy)}] 1 } else { lset verti [expr {min($nx, $hx)}] $ny 1 } lappend stack $here incr n -1 } else { set here [lindex $stack end] set stack [lrange $stack 0 end-1] } }
rename unvisited= {}
}
# Maze displayer; takes a maze dictionary, returns a string
method view {} {
set text {} for {set j 0} {$j < $x*2+1} {incr j} { set line {} for {set k 0} {$k < $y*4+1} {incr k} { if {$j%2 && $k%4==2} { # At the centre of the cell, put the "content" of the cell append line [expr {idx($content, $j/2, $k/4)}] } elseif {$j%2 && ($k%4 || $k && idx($horiz, $j/2, $k/4-1))} { append line " " } elseif {$j%2} { append line "|" } elseif {0 == $k%4} { append line "+" } elseif {$j && idx($verti, $j/2-1, $k/4)} { append line " " } else { append line "-" } } if {!$j} { lappend text [string replace $line 1 3 " "] } elseif {$x*2-1 == $j} { lappend text [string replace $line end end " "] } else { lappend text $line } } return [join $text \n]
}
}
- Demonstration
maze create m 11 8 puts [m view]</lang> Output:
+ +---+---+---+---+---+---+---+---+---+---+ | | | | +---+---+ +---+---+ + +---+ +---+ + | | | | | | + + +---+ +---+---+ +---+ + + + | | | | | | | | + +---+ +---+---+---+ + + + + + | | | | | | | | + + + + +---+---+ + +---+---+ + | | | | | | | | +---+---+---+---+ + +---+ + + +---+ | | | | | | | | + +---+---+ + + + + + +---+ + | | | | | | | | +---+ + +---+---+---+---+ + +---+ + | | +---+---+---+---+---+---+---+---+---+---+---+