1. rcrnstn/cxx-maze
  2. maze.cpp
Browse code

Use an actually uniform distribution

Robert Cranston authored on 21/05/2025 21:58:13
Showing 1 changed files
maze.cpp
History View file @ 6a747c1
... ... 
@@ -79,7 +79,7 @@ Maze hunt_and_kill(int w, int h, unsigned seed, C callback = [](Maze &){})
79 79 
         // If we have neighbors, carve path to random one.
80 80 
         if (n != 0)
81 81 
         {
82 
-            n = (int)rand() % n;
82 
+            n = std::uniform_int_distribution<>(0, n-1)(rand);
83 83 
             FOR_NEIGHBOR(
84 84 
                 if (maze(cx+nx, cy+ny) == Maze::WALL && n-- == 0)
85 85 
                 {
Browse code

Switch from C to C++ stdlib for randomness

Robert Cranston authored on 21/05/2025 21:54:38
Showing 1 changed files
maze.cpp
History View file @ 70cd6f7
... ... 
@@ -1,6 +1,6 @@
1 1 
 #include <chrono>
2 
-#include <cstdlib>
3 2 
 #include <iostream>
3 
+#include <random>
4 4 
 #include <sstream>
5 5 
 #include <thread>
6 6 
 #include <vector>
... ... 
@@ -51,7 +51,7 @@ template<typename C = void(*)(Maze &)>
51 51 
 Maze hunt_and_kill(int w, int h, unsigned seed, C callback = [](Maze &){})
52 52 
 {
53 53 
     auto maze = Maze(w, h, Maze::WALL);
54 
-    std::srand(seed);
54 
+    auto rand = std::default_random_engine(seed);
55 55 
     // Entrance.
56 56 
     maze(1, 0) = maze(1, 1) = Maze::PATH;
57 57 
     // Interior.
... ... 
@@ -79,7 +79,7 @@ Maze hunt_and_kill(int w, int h, unsigned seed, C callback = [](Maze &){})
79 79 
         // If we have neighbors, carve path to random one.
80 80 
         if (n != 0)
81 81 
         {
82 
-            n = std::rand() % n;
82 
+            n = (int)rand() % n;
83 83 
             FOR_NEIGHBOR(
84 84 
                 if (maze(cx+nx, cy+ny) == Maze::WALL && n-- == 0)
85 85 
                 {
Browse code

Switch from C to C++ stdlib for time

Robert Cranston authored on 21/05/2025 21:57:36
Showing 1 changed files
maze.cpp
History View file @ ff3fc90
... ... 
@@ -1,6 +1,5 @@
1 1 
 #include <chrono>
2 2 
 #include <cstdlib>
3 
-#include <ctime>
4 3 
 #include <iostream>
5 4 
 #include <sstream>
6 5 
 #include <thread>
... ... 
@@ -119,7 +118,8 @@ int main(int argc, char const * [])
119 118 
     using namespace std::chrono;
120 119 
     if (argc == 1)
121 120 
     {
122 
-        auto seed = (unsigned)std::time(nullptr);
121 
+        auto time = system_clock::now().time_since_epoch();
122 
+        auto seed = (unsigned)duration_cast<seconds>(time).count();
123 123 
         auto maze = hunt_and_kill(80/2, 24-1, seed, [](Maze & maze) {
124 124 
             maze.print();
125 125 
             std::this_thread::sleep_for(milliseconds(20));
Browse code

Use a smaller representation for maze cells

Robert Cranston authored on 21/05/2025 20:25:47
Showing 1 changed files
maze.cpp
History View file @ 1177462
... ... 
@@ -8,7 +8,7 @@
8 8
9 9 
 struct Maze
10 10 
 {
11 
-    enum Cell
11 
+    enum Cell : char
12 12 
     {
13 13 
         INVALID,
14 14 
         EDGE,
Browse code

Use less redundant and branchy neighbor iteration

Robert Cranston authored on 21/05/2025 20:13:27
Showing 1 changed files
maze.cpp
History View file @ e735756
... ... 
@@ -61,28 +61,34 @@ Maze hunt_and_kill(int w, int h, unsigned seed, C callback = [](Maze &){})
61 61 
     auto done = false;
62 62 
     while (!done)
63 63 
     {
64 
+        #define FOR_NEIGHBOR(...) \
65 
+            for (auto i = 0; i < 4; ++i) \
66 
+            { \
67 
+                auto ni = i%2*4-2;   /* -2, +2, -2, +2 */ \
68 
+                auto nx = ni* (i/2); /*  0,  0, -2, +2 */ \
69 
+                auto ny = ni*!(i/2); /* -2, +2,  0,  0 */ \
70 
+                __VA_ARGS__ \
71 
+            }
64 72 
         // Call callback.
65 73 
         callback(maze);
66 74 
         // Find number of neighbors.
67 75 
         auto n = 0;
68 
-        for (auto ny = -2; ny <= 2; ny += 2)
69 
-        for (auto nx = -2; nx <= 2; nx += 2)
70 
-            if (!nx != !ny)
76 
+        FOR_NEIGHBOR(
71 77 
             if (maze(cx+nx, cy+ny) == Maze::WALL)
72 78 
                 ++n;
79 
+        )
73 80 
         // If we have neighbors, carve path to random one.
74 81 
         if (n != 0)
75 82 
         {
76 83 
             n = std::rand() % n;
77 
-            for (auto ny = -2; ny <= 2; ny += 2)
78 
-            for (auto nx = -2; nx <= 2; nx += 2)
79 
-                if (!nx != !ny)
84 
+            FOR_NEIGHBOR(
80 85 
                 if (maze(cx+nx, cy+ny) == Maze::WALL && n-- == 0)
81 86 
                 {
82 87 
                     maze(cx+nx/2, cy+ny/2) = maze(cx+nx, cy+ny) = Maze::PATH;
83 88 
                     cx = cx+nx;
84 89 
                     cy = cy+ny;
85 90 
                 }
91 
+            )
86 92 
             continue;
87 93 
         }
88 94 
         // No neighbors, done unless there's an uncarved cell to restart at.
... ... 
@@ -90,17 +96,17 @@ Maze hunt_and_kill(int w, int h, unsigned seed, C callback = [](Maze &){})
90 96 
             for (; ry < h; ry += 2, rx = 1)
91 97 
             for (; rx < w; rx += 2)
92 98 
                 if (maze(rx, ry) == Maze::WALL)
93 
-                    for (auto ny = -2; ny <= 2; ny += 2)
94 
-                    for (auto nx = -2; nx <= 2; nx += 2)
95 
-                        if (!nx != !ny)
99 
+                    FOR_NEIGHBOR(
96 100 
                         if (maze(rx+nx, ry+ny) == Maze::PATH)
97 101 
                         {
98 102 
                             cx = rx+nx;
99 103 
                             cy = ry+ny;
100 104 
                             return false;
101 105 
                         }
106 
+                    )
102 107 
             return true;
103 108 
         }();
109 
+        #undef FOR_NEIGHBOR
104 110 
     }
105 111 
     // Exit.
106 112 
     w -= (w + 1) % 2;
Browse code

Remember last restart position

Robert Cranston authored on 21/05/2025 15:15:40
Showing 1 changed files
maze.cpp
History View file @ 1bb5e84
... ... 
@@ -56,8 +56,8 @@ Maze hunt_and_kill(int w, int h, unsigned seed, C callback = [](Maze &){})
56 56 
     // Entrance.
57 57 
     maze(1, 0) = maze(1, 1) = Maze::PATH;
58 58 
     // Interior.
59 
-    auto cx = 1;
60 
-    auto cy = 1;
59 
+    auto cx = 1; auto rx = 1;
60 
+    auto cy = 1; auto ry = 1;
61 61 
     auto done = false;
62 62 
     while (!done)
63 63 
     {
... ... 
@@ -86,19 +86,21 @@ Maze hunt_and_kill(int w, int h, unsigned seed, C callback = [](Maze &){})
86 86 
             continue;
87 87 
         }
88 88 
         // No neighbors, done unless there's an uncarved cell to restart at.
89 
-        done = true;
90 
-        for (auto ry = 1; ry < h && done; ry += 2)
91 
-        for (auto rx = 1; rx < w && done; rx += 2)
92 
-            if (maze(rx, ry) == Maze::WALL)
93 
-                for (auto ny = -2; ny <= 2 && done; ny += 2)
94 
-                for (auto nx = -2; nx <= 2 && done; nx += 2)
95 
-                    if (!nx != !ny)
96 
-                    if (maze(rx+nx, ry+ny) == Maze::PATH)
97 
-                    {
98 
-                        cx = rx+nx;
99 
-                        cy = ry+ny;
100 
-                        done = false;
101 
-                    }
89 
+        done = [&]() {
90 
+            for (; ry < h; ry += 2, rx = 1)
91 
+            for (; rx < w; rx += 2)
92 
+                if (maze(rx, ry) == Maze::WALL)
93 
+                    for (auto ny = -2; ny <= 2; ny += 2)
94 
+                    for (auto nx = -2; nx <= 2; nx += 2)
95 
+                        if (!nx != !ny)
96 
+                        if (maze(rx+nx, ry+ny) == Maze::PATH)
97 
+                        {
98 
+                            cx = rx+nx;
99 
+                            cy = ry+ny;
100 
+                            return false;
101 
+                        }
102 
+            return true;
103 
+        }();
102 104 
     }
103 105 
     // Exit.
104 106 
     w -= (w + 1) % 2;
... ... 
@@ -121,7 +123,7 @@ int main(int argc, char const * [])
121 123 
     else
122 124 
     {
123 125 
         auto const t1 = steady_clock::now();
124 
-        hunt_and_kill(1000, 1000, 0);
126 
+        hunt_and_kill(10000, 10000, 0);
125 127 
         auto const t2 = steady_clock::now();
126 128 
         std::cout << duration_cast<milliseconds>(t2 - t1).count() << "ms\n";
127 129 
     }
Browse code

Add benchmarking

Robert Cranston authored on 21/05/2025 15:09:29
Showing 1 changed files
maze.cpp
History View file @ 2ef8d83
... ... 
@@ -106,13 +106,23 @@ Maze hunt_and_kill(int w, int h, unsigned seed, C callback = [](Maze &){})
106 106 
     return maze;
107 107 
 }
108 108
109 
-int main()
109 
+int main(int argc, char const * [])
110 110 
 {
111 111 
     using namespace std::chrono;
112 
-    auto seed = (unsigned)std::time(nullptr);
113 
-    auto maze = hunt_and_kill(80/2, 24-1, seed, [](Maze & maze) {
112 
+    if (argc == 1)
113 
+    {
114 
+        auto seed = (unsigned)std::time(nullptr);
115 
+        auto maze = hunt_and_kill(80/2, 24-1, seed, [](Maze & maze) {
116 
+            maze.print();
117 
+            std::this_thread::sleep_for(milliseconds(20));
118 
+        });
114 119 
         maze.print();
115 
-        std::this_thread::sleep_for(milliseconds(20));
116 
-    });
117 
-    maze.print();
120 
+    }
121 
+    else
122 
+    {
123 
+        auto const t1 = steady_clock::now();
124 
+        hunt_and_kill(1000, 1000, 0);
125 
+        auto const t2 = steady_clock::now();
126 
+        std::cout << duration_cast<milliseconds>(t2 - t1).count() << "ms\n";
127 
+    }
118 128 
 }
Browse code

Buffer printing

Robert Cranston authored on 21/05/2025 01:54:54
Showing 1 changed files
maze.cpp
History View file @ bbe7918
... ... 
@@ -2,6 +2,7 @@
2 2 
 #include <cstdlib>
3 3 
 #include <ctime>
4 4 
 #include <iostream>
5 
+#include <sstream>
5 6 
 #include <thread>
6 7 
 #include <vector>
7 8
... ... 
@@ -36,9 +37,11 @@ struct Maze
36 37 
     }
37 38 
     void print() const
38 39 
     {
39 
-        for (auto y = 0; y < h; ++y, std::cout << '\n')
40 
+        std::ostringstream oss;
41 
+        for (auto y = 0; y < h; ++y, oss << '\n')
40 42 
         for (auto x = 0; x < w; ++x)
41 
-            std::cout << (cells[w * y + x] == PATH ? "  " : "██");
43 
+            oss << (cells[w * y + x] == PATH ? "  " : "██");
44 
+        std::cout << oss.str();
42 45 
     }
43 46 
     int w;
44 47 
     int h;
Browse code

Add callback during generation

Robert Cranston authored on 21/05/2025 01:50:09
Showing 1 changed files
maze.cpp
History View file @ 2de3a8b
... ... 
@@ -1,6 +1,8 @@
1 
+#include <chrono>
1 2 
 #include <cstdlib>
2 3 
 #include <ctime>
3 4 
 #include <iostream>
5 
+#include <thread>
4 6 
 #include <vector>
5 7
6 8 
 struct Maze
... ... 
@@ -43,7 +45,8 @@ struct Maze
43 45 
     std::vector<Cell> cells;
44 46 
 };
45 47
46 
-Maze hunt_and_kill(int w, int h, unsigned seed)
48 
+template<typename C = void(*)(Maze &)>
49 
+Maze hunt_and_kill(int w, int h, unsigned seed, C callback = [](Maze &){})
47 50 
 {
48 51 
     auto maze = Maze(w, h, Maze::WALL);
49 52 
     std::srand(seed);
... ... 
@@ -55,6 +58,8 @@ Maze hunt_and_kill(int w, int h, unsigned seed)
55 58 
     auto done = false;
56 59 
     while (!done)
57 60 
     {
61 
+        // Call callback.
62 
+        callback(maze);
58 63 
         // Find number of neighbors.
59 64 
         auto n = 0;
60 65 
         for (auto ny = -2; ny <= 2; ny += 2)
... ... 
@@ -100,7 +105,11 @@ Maze hunt_and_kill(int w, int h, unsigned seed)
100 105
101 106 
 int main()
102 107 
 {
108 
+    using namespace std::chrono;
103 109 
     auto seed = (unsigned)std::time(nullptr);
104 
-    auto maze = hunt_and_kill(80/2, 24-1, seed);
110 
+    auto maze = hunt_and_kill(80/2, 24-1, seed, [](Maze & maze) {
111 
+        maze.print();
112 
+        std::this_thread::sleep_for(milliseconds(20));
113 
+    });
105 114 
     maze.print();
106 115 
 }
Browse code

Seed with time in seconds since the epoch

Robert Cranston authored on 21/05/2025 01:04:11
Showing 1 changed files
maze.cpp
History View file @ f92a0e8
... ... 
@@ -1,4 +1,5 @@
1 1 
 #include <cstdlib>
2 
+#include <ctime>
2 3 
 #include <iostream>
3 4 
 #include <vector>
4 5
... ... 
@@ -99,7 +100,7 @@ Maze hunt_and_kill(int w, int h, unsigned seed)
99 100
100 101 
 int main()
101 102 
 {
102 
-    auto seed = 0;
103 
+    auto seed = (unsigned)std::time(nullptr);
103 104 
     auto maze = hunt_and_kill(80/2, 24-1, seed);
104 105 
     maze.print();
105 106 
 }
Browse code

Handle mazes of any size

Robert Cranston authored on 21/05/2025 01:01:36
Showing 1 changed files
maze.cpp
History View file @ fc6c194
... ... 
@@ -7,6 +7,7 @@ struct Maze
7 7 
     enum Cell
8 8 
     {
9 9 
         INVALID,
10 
+        EDGE,
10 11 
         WALL,
11 12 
         PATH,
12 13 
     };
... ... 
@@ -15,7 +16,14 @@ struct Maze
15 16 
         w{w},
16 17 
         h{h},
17 18 
         cells(w * h, initial)
18 
-    {}
19 
+    {
20 
+        for (auto y = 0; y < h; y += h-1)
21 
+        for (auto x = 0; x < w; x += 1)
22 
+            cells[w * y + x] = EDGE;
23 
+        for (auto y = 0; y < h; y += 1)
24 
+        for (auto x = 0; x < w; x += w-1)
25 
+            cells[w * y + x] = EDGE;
26 
+    }
19 27 
     Cell & operator ()(int x, int y)
20 28 
     {
21 29 
         static auto invalid = INVALID; // Yes, naughty.
... ... 
@@ -84,13 +92,14 @@ Maze hunt_and_kill(int w, int h, unsigned seed)
84 92 
                     }
85 93 
     }
86 94 
     // Exit.
87 
-    maze(w-2, h-1) = Maze::PATH;
95 
+    w -= (w + 1) % 2;
96 
+    maze(w-2, h-2) = maze(w-2, h-1) = Maze::PATH;
88 97 
     return maze;
89 98 
 }
90 99
91 100 
 int main()
92 101 
 {
93 102 
     auto seed = 0;
94 
-    auto maze = hunt_and_kill(80/2-1, 24-1, seed);
103 
+    auto maze = hunt_and_kill(80/2, 24-1, seed);
95 104 
     maze.print();
96 105 
 }
Browse code

Add implementation

Robert Cranston authored on 20/05/2025 23:55:27
Showing 1 changed files
maze.cpp
History View file @ 861359a
1 1 
new file mode 100644
... ... 
@@ -0,0 +1,96 @@
1 
+#include <cstdlib>
2 
+#include <iostream>
3 
+#include <vector>
4 
+
5 
+struct Maze
6 
+{
7 
+    enum Cell
8 
+    {
9 
+        INVALID,
10 
+        WALL,
11 
+        PATH,
12 
+    };
13 
+    Maze(int w, int h, Cell initial)
14 
+    :
15 
+        w{w},
16 
+        h{h},
17 
+        cells(w * h, initial)
18 
+    {}
19 
+    Cell & operator ()(int x, int y)
20 
+    {
21 
+        static auto invalid = INVALID; // Yes, naughty.
22 
+        if (0 <= x && x < w && 0 <= y && y < h)
23 
+            return cells[w * y + x];
24 
+        return invalid;
25 
+    }
26 
+    void print() const
27 
+    {
28 
+        for (auto y = 0; y < h; ++y, std::cout << '\n')
29 
+        for (auto x = 0; x < w; ++x)
30 
+            std::cout << (cells[w * y + x] == PATH ? "  " : "██");
31 
+    }
32 
+    int w;
33 
+    int h;
34 
+    std::vector<Cell> cells;
35 
+};
36 
+
37 
+Maze hunt_and_kill(int w, int h, unsigned seed)
38 
+{
39 
+    auto maze = Maze(w, h, Maze::WALL);
40 
+    std::srand(seed);
41 
+    // Entrance.
42 
+    maze(1, 0) = maze(1, 1) = Maze::PATH;
43 
+    // Interior.
44 
+    auto cx = 1;
45 
+    auto cy = 1;
46 
+    auto done = false;
47 
+    while (!done)
48 
+    {
49 
+        // Find number of neighbors.
50 
+        auto n = 0;
51 
+        for (auto ny = -2; ny <= 2; ny += 2)
52 
+        for (auto nx = -2; nx <= 2; nx += 2)
53 
+            if (!nx != !ny)
54 
+            if (maze(cx+nx, cy+ny) == Maze::WALL)
55 
+                ++n;
56 
+        // If we have neighbors, carve path to random one.
57 
+        if (n != 0)
58 
+        {
59 
+            n = std::rand() % n;
60 
+            for (auto ny = -2; ny <= 2; ny += 2)
61 
+            for (auto nx = -2; nx <= 2; nx += 2)
62 
+                if (!nx != !ny)
63 
+                if (maze(cx+nx, cy+ny) == Maze::WALL && n-- == 0)
64 
+                {
65 
+                    maze(cx+nx/2, cy+ny/2) = maze(cx+nx, cy+ny) = Maze::PATH;
66 
+                    cx = cx+nx;
67 
+                    cy = cy+ny;
68 
+                }
69 
+            continue;
70 
+        }
71 
+        // No neighbors, done unless there's an uncarved cell to restart at.
72 
+        done = true;
73 
+        for (auto ry = 1; ry < h && done; ry += 2)
74 
+        for (auto rx = 1; rx < w && done; rx += 2)
75 
+            if (maze(rx, ry) == Maze::WALL)
76 
+                for (auto ny = -2; ny <= 2 && done; ny += 2)
77 
+                for (auto nx = -2; nx <= 2 && done; nx += 2)
78 
+                    if (!nx != !ny)
79 
+                    if (maze(rx+nx, ry+ny) == Maze::PATH)
80 
+                    {
81 
+                        cx = rx+nx;
82 
+                        cy = ry+ny;
83 
+                        done = false;
84 
+                    }
85 
+    }
86 
+    // Exit.
87 
+    maze(w-2, h-1) = Maze::PATH;
88 
+    return maze;
89 
+}
90 
+
91 
+int main()
92 
+{
93 
+    auto seed = 0;
94 
+    auto maze = hunt_and_kill(80/2-1, 24-1, seed);
95 
+    maze.print();
96 
+}