Maze generation: Difference between revisions

Content added Content deleted
Line 295: Line 295:
=={{header|D}}==
=={{header|D}}==
{{works with|D|2}}
{{works with|D|2}}
<lang d>import std.stdio: write, writeln;
<lang d>import std.stdio, std.string, std.random, std.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, r;
int n = i - width;
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;
if (c.r < n.r) {
int w = i - 1;
c.m &= ~SOUTH;
if (w >= 0 && w / width == i / width && !maze[w].length)
n.m &= ~NORTH;
neighbors ~= w;
} else if (c.r > n.r) {
return 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) {
foreach (n; nbrs) {
auto maze = new int[][](totalCells);
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)) {
if (neighbors.length) {
c = stack[$ - 1];
int ne = neighbors[uniform(0, neighbors.length)];
stack.length -= 1;
maze[currentCell] ~= ne;
setNeighbors(c, nbrs);
maze[ne] ~= currentCell;
cellstack ~= currentCell;
currentCell = ne;
visited++;
} else {
} else {
dig(c, stack, nbrs);
currentCell = cellstack[$ - 1];
cellstack.length -= 1;
}
}
}
}
Line 389: Line 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 &= ~EAST;
s1 = "+";
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) ? "| " : " ";
}
}
writeln(hori, "\n", vert);
s1 ~= (indexOf(maze[i], i - width) != -1) ? " +" : "--+";
s2 ~= (indexOf(maze[i], i + 1) != -1) ? " " : " |";
}
}
writeln("+", repeat("--+", width));

foreach (c; 0 .. width)
write("+---");
writeln("+");
}
}



void main() {
void main() {
enum int height = 8, width = 11;
printMaze(buildMaze(11, 8));
showMaze(makeMaze(height, width), height, width);
}</lang>
}</lang>
Output example:
Output example:
<pre>
<pre>+ +---+---+---+---+---+---+---+---+---+---+
| | | |
+ +---+ + +---+ +---+---+---+ + +
| | | | | |
+ + +---+---+---+---+---+ +---+---+ +
| | | | | |
+ +---+---+---+---+---+ + + +---+---+
| | | | |
+---+ + +---+---+ +---+---+---+---+ +
| | | |
+ + +---+---+---+ + +---+---+---+---+
| | | | | | |
+ +---+ +---+ + +---+---+ + + +
| | | | | | | |
+ + +---+ + +---+ + +---+---+ +
| | | |
+---+---+---+---+---+---+---+---+---+---+---+</pre>


+--+--+--+--+--+--+--+--+--+--+--+
| | | |
+ +--+--+ + +--+--+ + + +--+
| | | | | | | |
+ + + +--+ +--+--+ + +--+ +
| | | | | | | |
+ + +--+--+ + + + +--+ + +
| | | | | | | |
+ + + + +--+ +--+--+--+--+ +
| | | | | | | |
+ + + +--+ +--+ + +--+ +--+
| | | | | | |
+ +--+--+ + + +--+--+ +--+ +
| | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+</pre>
===Alternative version ===
===Alternative version ===
See [[Maze_solving#D]]
See [[Maze_solving#D]]
Retrieved from "https://rosettacode.org/wiki/Maze_generation"