Rosetta Code

Maze generation: Difference between revisions

Page Discussion

Maze generation (view source)

Revision as of 15:06, 1 January 2011

1,441 bytes removed ,  13 years ago
→‎{{header|D}}
Line 295:
=={{header|D}}==
{{works with|D|2}}
<lang d>import std.stdio:, std.string, writestd.random, writelnstd.algorithm;
import std.random: uniform;
 
int[][] makeMaze(const int height, const int width) {
enum : uint { VISITED = 1, NORTH = 2, EAST = 4, SOUTH = 8, WEST = 16 };
int[] getCandidateNeighbors(const int[][] maze, const int i) {
 
int[] neighbors;
struct Cell {
int c,n = i - rwidth;
if (n >= 0 && !maze[n].length)
uint m;
neighbors ~= n;
}
int s = i + width;
 
if (s < (height * width) && !maze[s].length)
Cell[][] buildMaze(int width, int height) {
neighbors ~= s;
Cell[][] maze;
int e = i + 1;
 
if (e >= 0 && e / width == i / width && !maze[e].length)
pure nothrow static void breakWall(ref Cell c, ref Cell n) {
if (c.c == n.c) {neighbors ~= e;
int w = i if- (c.r < n.r) {1;
if (w >= 0 && w / width c.m== i / width &=& ~SOUTH;!maze[w].length)
neighbors n.m &~= ~NORTHw;
return } else if (c.r > n.r) {neighbors;
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;
}
}
}
 
int totalCells = height * width;
pure nothrow static bool deadEnd(const Cell[] nbrs) {
auto maze = new foreach int[][](ntotalCells); nbrs) {
int currentCell = uniform(0, totalCells);
if ((n.m & VISITED) == 0)
int visited = 1;
return false;
int[] }cellstack;
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);
 
while (visited < totalCells) {
// go
int[] neighbors = getCandidateNeighbors(maze, currentCell);
while (stack.length > 0) {
if (deadEnd(nbrs)neighbors.length) {
cint ne = stackneighbors[$ -uniform(0, 1neighbors.length)];
stack.lengthmaze[currentCell] -~= 1ne;
setNeighbors(c,maze[ne] nbrs)~= currentCell;
cellstack ~= currentCell;
currentCell = ne;
visited++;
} else {
dig(c,currentCell stack,= nbrs)cellstack[$ - 1];
cellstack.length -= 1;
}
}
Line 389 ⟶ 339:
}
 
void showMaze(int[][] maze, const int height, const int width) {
 
string s1, s2;
void printMaze(Cell[][] maze) {
foreach (i; 0 .. height * width) {
immutable int width = maze.length;
if (i % width == 0) {
immutable int height = maze[0].length;
writeln(s1);
 
writeln(s2);
maze[0][0].m &= ~NORTH;
maze[$-1][$-1].m & s1 = ~EAST"+";
s2 = "|";
 
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) ? "| " : " ";
}
writelns1 ~= (horiindexOf(maze[i], i - width) != -1) ? "\n +", vert): "--+";
s2 ~= (indexOf(maze[i], i + 1) != -1) ? " " : " |";
}
writeln("+", repeat("--+", width));
 
foreach (c; 0 .. width)
write("+---");
writeln("+");
}
 
 
void main() {
enum int height = 8, width = 11;
printMaze(buildMaze(11, 8));
showMaze(makeMaze(height, width), height, width);
}</lang>
Output example:
<pre>
<pre>+ +---+---+---+---+---+---+---+---+---+---+
| | | |
+ +---+ + +---+ +---+---+---+ + +
| | | | | |
+ + +---+---+---+---+---+ +---+---+ +
| | | | | |
+ +---+---+---+---+---+ + + +---+---+
| | | | |
+---+ + +---+---+ +---+---+---+---+ +
| | | |
+ + +---+---+---+ + +---+---+---+---+
| | | | | | |
+ +---+ +---+ + +---+---+ + + +
| | | | | | | |
+ + +---+ + +---+ + +---+---+ +
| | | |
+---+---+---+---+---+---+---+---+---+---+---+</pre>
 
+--+--+--+--+--+--+--+--+--+--+--+
| | | |
+ +--+--+ + +--+--+ + + +--+
| | | | | | | |
+ + + +--+ +--+--+ + +--+ +
| | | | | | | |
+ + +--+--+ + + + +--+ + +
| | | | | | | |
+ + + + +--+ +--+--+--+--+ +
| | | | | | | |
+ + + +--+ +--+ + +--+ +--+
| | | | | | |
+ +--+--+ + + +--+--+ +--+ +
| | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+</pre>
===Alternative version ===
See [[Maze_solving#D]]
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/167393"