Rosetta Code

Maze generation: Difference between revisions

Page Discussion

Maze generation (view source)

Revision as of 10:45, 27 December 2010

126 bytes added ,  13 years ago
→‎First version
(→‎{{header|D}}: one more)
Line 296:
===First version===
{{works with|D|2}}
<lang d>import std.stdio,: std.randomwrite, std.arraywriteln;
import std.random: uniform;
 
enum : uint {visited VISITED = 1, northNORTH = 2, eastEAST = 4, southSOUTH = 8, westWEST = 16 };
const w = 11, h = 8;
 
struct cellCell { int c, r, m; }
int c, }r;▼
cell[][] maze;▼
build()uint m;▼
}▼
 
void main() {▼
▲ build();
print();
▲}
 
Cell[][] buildMaze(int width, int height) {
void build() {
▲cell Cell[][] maze;
 
pure nothrow static void breakWall(ref cellCell c, ref cellCell n) {
if (c.c == n.c) {
if (c.r < n.r) {
c.m &= ~south; n.m &= ~northSOUTH;
if (maze[c][r] n.m &= east) {~NORTH;▼
} else if (c.r > n.r) {
c.m &= ~north; n.m &= ~southNORTH;
n.m &= ~SOUTH;
}
} else if (c.r == n.r) {
if (c.c < n.c) {
c.m &= ~east; n.m &= ~westEAST;
} else { n.m &= ~WEST;▼
} else if (c.c > n.c) {
c.m &= ~west; n.m &= ~eastWEST;
n.m &= ~EAST;
}
}
}
 
pure nothrow static bool deadEnd(cellconst Cell[] nbrs) {
foreach (n; nbrs) {
if ((n.m & visitedVISITED) == 0)
return false;
}
Line 335 ⟶ 338:
}
 
nothrow void setNeighbors(cellconst Cell c, ref cellCell[] nbrs) {
nbrs.length = 0;
if (c.r != 0) {
nbrs ~= maze[c.c][c.r - 1]; // n
}if (c.c != 0)
if ( nbrs ~= maze[c.c !=- 1][c.r]; 0)// {width
if (c.r nbrs ~!= maze[c.cheight - 1][c.r]; // w)
▲ }
if (c.r != h - 1) {▼
nbrs ~= maze[c.c][c.r + 1]; // s
}if (c.c != width - 1)
if (c.c != w - 1) {▼
nbrs ~= maze[c.c + 1][c.r]; // e
}
}
 
void dig(ref cellCell c, ref cellCell[] stack, ref cellCell[] nbrs) {
cellCell n;
do {
n = nbrs[uniform(0, nbrs.length)];
} while ((n.m & visitedVISITED) != 0)
 
n.m |= visitedVISITED;
breakWall(c, n);
maze[c.c][c.r] = c;
Line 367 ⟶ 366:
 
// setup
maze = new cellCell[][](wwidth, hheight);
forforeach (int r =; 0; r.. < h; r++height)
forforeach (int c =; 0; c.. < w; c++width)
maze[c][r] = cellCell(c, r, northNORTH|eastEAST|southSOUTH|westWEST);
cellCell[] nbrs, stack;
 
cell[] stack;
cellCell c = maze[uniform(0, wwidth)][uniform(0, hheight)];▼
c.m |= visitedVISITED;▼
▲ cell c = maze[uniform(0, w)][uniform(0, h)];
▲ c.m |= visited;
setNeighbors(c, nbrs);
dig(c, stack, nbrs);
 
// go
while (stack.length > 0) {
if (deadEnd(nbrs)) {
c = stack.back;[$ - 1];
stack.popBacklength -= 1;
setNeighbors(c, nbrs);
} else {
Line 389 ⟶ 387:
}
}
 
return maze;
}
 
void print() {
maze[0][0].m &= ~north;▼
maze[w-1][h-1].m &= ~east;
 
void printMaze(Cell[][] maze) {
for (int r = 0; r < h; r++) {
immutable int auto horiwidth = appender("")maze.length;
immutable int auto vertheight = appender("")maze[0].length;
 
for (int c; c < w; c++) {
if (maze[c0][r0].m &= north) {~NORTH;
▲ maze[0$-1][0$-1].m &= ~northEAST;
if (c == w - 1) hori.put("+---+"); else hori.put("+---");▼
 
▲ } else {
foreach (r; 0 .. height) {
if (c == w - 1) hori.put("+ +"); else hori.put("+ ");▼
string hori, }vert;
 
▲ if (maze[c][r].m & east) {
ifforeach (c ==; 0) vert.put("|. |"width); else vert.put(" |");{
}if else(maze[c][r].m {& NORTH)
ifhori ~= (c == 0)width vert.put("|- "1); else? vert.put("+---+" : ")+---";
}else
▲ ifhori ~= (c == wwidth - 1) hori.put(? "+--- +"); else: hori.put("+--- ");
 
▲ if (maze[c][r].cm !=& w - 1EAST) {
▲ ifvert ~= (c == w0) -? 1) hori.put("+| +|"); else: hori.put("+ |");
▲ if (c.r != h - 1) {else
vert ~= (c == 0) ? "| " : " ";
}
 
writeln(hori.data, "\n", vert.data);
}
 
for (int c; c < w; c++)
foreach (c; 0 .. width)
write("+---");
writeln("+");
}
}</lang>▼
 
 
▲void main() {
printMaze(buildMaze(11, 8));
▲}</lang>
Output example:
<pre>+ +---+---+---+---+---+---+---+---+---+---+
| | | |
Line 434 ⟶ 444:
| | | |
+---+---+---+---+---+---+---+---+---+---+---+</pre>
 
===Second version===
{{works with|D|2.050}}
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/167380"