Maze generation: Difference between revisions

← Older edit Newer edit →

Content deleted Content added

Inline

@@ Line 10: / Line 10: @@
 See also [[Maze solving]].
+=={{header|D}}==
+<lang d>import std.stdio, std.random, std.array, std.date;
+enum {visited = 1, north = 2, east = 4, south = 8, west = 16};
+const w = 11, h = 8;
+struct cell { int c, r, m; }
+cell[][] maze;
+void main() {
+    build();
+    print();
+}
+void build() {
+    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;
+            }
+        }
+    }
+    bool deadEnd(cell[] nbrs) {
+        foreach (n; nbrs) {
+            if ((n.m & visited) == 0)
+                return false;
+        }
+        return true;
+    }
+    void setNeighbors(cell c, ref cell[] nbrs) {
+        nbrs.length = 0;
+        if (c.r != 0) {
+            nbrs ~= maze[c.r - 1][c.c]; // n
+        }
+        if (c.c != 0) {
+            nbrs ~= maze[c.r][c.c - 1]; // w
+        }
+        if (c.r != h - 1) {
+            nbrs ~= maze[c.r + 1][c.c]; // s
+        }
+        if (c.c != w - 1) {
+            nbrs ~= maze[c.r][c.c + 1]; // 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.r][c.c] = c;
+        maze[n.r][n.c] = n;
+        stack ~= c;
+        c = n;
+        setNeighbors(c, nbrs);
+    }
+    // setup
+    maze = new cell[][](h, w);
+    for (int r = 0; r < h; r++)
+        for (int c = 0; c < w; c++)
+            maze[r][c] = cell(c, r, north|east|south|west);
+    cell[] nbrs;
+    cell[] stack;
+    cell c = maze[uniform(0, h)][uniform(0, w)];
+    c.m |= visited;
+    setNeighbors(c, nbrs);
+    dig(c, stack, nbrs);
+    // go
+    while (stack.length > 0) {
+        if (deadEnd(nbrs)) {
+            c = stack.back;
+            stack.popBack;
+            setNeighbors(c, nbrs);
+        } else {
+            dig(c, stack, nbrs);
+        }
+    }
+}
+void print() {
+    for (int r = 0; r < h; r++) {
+        auto hori = appender("");
+        auto vert = appender("");
+        for (int c; c < w; c++) {
+            if (maze[r][c].m & north) {
+                if (c == w - 1) hori.put("+---+"); else hori.put("+---");
+            } else {
+                if (c == w - 1) hori.put("+   +"); else hori.put("+   ");
+            }
+            if (maze[r][c].m & west) {
+                if (c == w - 1) vert.put("|   |"); else vert.put("|   ");
+            } else {
+                if (c == w - 1) vert.put("    |"); else vert.put("    ");
+            }
+        }
+        writeln(hori.data, "\n", vert.data);
+    }
+    for (int c; c < w; c++)
+        write("+---");
+    writeln("+");
+}</lang>
+<pre>+---+---+---+---+---+---+---+---+---+---+---+
+|                       |               |   |
++---+---+---+   +---+   +   +---+---+   +   +
+|               |       |           |       |
++   +---+---+---+   +---+---+---+   +---+   +
+|       |                       |   |   |   |
++---+   +---+---+---+---+---+   +   +   +   +
+|       |           |       |   |   |       |
++   +   +   +---+   +---+   +   +   +---+---+
+|   |   |   |   |   |       |   |           |
++   +   +---+   +   +   +   +   +---+---+   +
+|   |   |           |   |   |       |       |
++   +---+   +---+---+   +---+---+   +   +   +
+|       |       |   |           |       |   |
++   +   +---+   +   +   +---+   +---+---+   +
+|   |           |           |               |
++---+---+---+---+---+---+---+---+---+---+---+</pre>
 =={{header|J}}==