Maze generation: Difference between revisions
m
→{{header|POV-Ray}}: Explanation added about iterative approach
m (→{{header|Uiua}}: slightly nicer algorithm) |
m (→{{header|POV-Ray}}: Explanation added about iterative approach) |
||
| (11 intermediate revisions by 3 users not shown) | |||
Line 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 5,574 ⟶ 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 7,072 ⟶ 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 9,705 ⟶ 10,098:
↯+1H⊂↯W1 0 # hor
⊂⊟
# Stack: ([
Walk [0 0]
| |||