termaze

commit 00325f0cb6cd3f425d41eed3fc446c336784c106
parent 8b1e1b2e345cfa4c11978f5021712f6ec0475d6d
Author: Petar Yotsev <petar@yotsev.xyz>
Date:   Mon, 12 Jul 2021 16:00:02 +0100

Add growing tree algorith for maze generation

Diffstat:
M
README.md
 | 
2
+-
M
maze_gen.cpp
 | 
100
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
maze_gen.hpp
 | 
1
+

3 files changed, 102 insertions(+), 1 deletion(-)
diff --git a/README.md b/README.md
@@ -13,7 +13,7 @@ in mind. It runs in the terminal.
     * [X] Modified Kruskal's algorithm
     * [X] Modified Prim's algorithm - random edges
     * [X] Modified Prim's algorithm - weighted graph
-    * [ ] Growing tree
+    * [X] Growing tree
     * [X] Wilson's random walk algorithm
     * [X] Binary tree
     * [X] Eller's algorithm
diff --git a/maze_gen.cpp b/maze_gen.cpp
@@ -323,6 +323,105 @@ void maze_gen::PrimRandom(bool* field, const int& width, const int& height)
     }
 }
 
+void maze_gen::GrowingTree(bool* field, const int& width, const int& height)
+{
+    struct cell {
+        vec2<int> pos;
+        const cell* parent;
+        int weight;
+        std::vector<cell*> neighbors;
+        // adds valid neighbors
+        void AddNeighbors(const bool* field, cell* grid, const int& width,
+            const int& height)
+        {
+            neighbors.clear();
+            // up
+            if (pos.y > 1 && !field[(pos.y - 2) * width + pos.x])
+                neighbors.emplace_back(&grid[(pos.y - 2) * width + pos.x]);
+            // down
+            if (pos.y < height - 2 && !field[(pos.y + 2) * width + pos.x])
+                neighbors.emplace_back(&grid[(pos.y + 2) * width + pos.x]);
+            // left
+            if (pos.x > 1 && !field[(pos.y * width) + pos.x - 2])
+                neighbors.emplace_back(&grid[(pos.y * width) + pos.x - 2]);
+            // right
+            if (pos.x < width - 2 && !field[(pos.y * width) + pos.x + 2])
+                neighbors.emplace_back(&grid[(pos.y * width) + pos.x + 2]);
+            shuffle(neighbors.begin(), neighbors.end(),
+                std::default_random_engine(std::rand()));
+        }
+    };
+
+    // setting the coordinates of each cell according to their placement in the
+    // array because the contents of the cells will map to their locations in
+    // memory making addressing easier
+    cell grid[width * height];
+    for (int y = 0; y < height; ++y) {
+        for (int x = 0; x < width; ++x) {
+            grid[(y * width) + x].pos.x = x;
+            grid[(y * width) + x].pos.y = y;
+        }
+    }
+
+    // gives the index of a cell in the field
+    auto Index = [&](vec2<int> v) { return v.y * width + v.x; };
+
+    // initializing the open set with a viable random position, aka the root
+    // because the mazes look more interesting when having irregular roots
+    std::vector<cell*> openSet;
+    openSet.push_back(&grid[(((std::rand() % (height / 2)) * 2 + 1) * width)
+        + ((std::rand() % (width / 2)) * 2) + 1]);
+    /* field[(openSet[0]->pos.y * width) + openSet[0]->pos.x] = true; */
+    /* mvprintw(openSet[0]->pos.y, openSet[0]->pos.x * 2, "  "); */
+    openSet[0]->parent = openSet[0];
+
+    const int range = std::sqrt(width * height);
+    int index;
+    cell* current;
+    vec2<int> midpoint;
+    timer cycle;
+
+    // carving a path to a random unexplored cell
+    // until there are no more explorable cells
+    while (!openSet.empty()) {
+        // 50/50 use bottom or top of the stack as the next cell
+        index = 0;
+        if (std::rand() % 100 < 50)
+            index = openSet.size() - 1;
+        current = openSet[index];
+        openSet.erase(openSet.begin() + index);
+
+        // if the current position is not part of the maze, make it one
+        if (!field[Index(current->pos)]) {
+            current->AddNeighbors(field, grid, width, height);
+            s::draw.lock();
+            attron(COLOR_PAIR(red));
+            for (cell* n : current->neighbors) {
+                n->parent = current;
+                n->weight = std::rand();
+                openSet.push_back(n);
+                mvprintw(n->pos.y, n->pos.x * 2, "  ");
+            }
+            attroff(COLOR_PAIR(red));
+            s::draw.unlock();
+
+            midpoint = (current + (current->parent - current) / 2)->pos;
+            field[Index(current->pos)] = true;
+            field[Index(midpoint)] = true;
+            s::draw.lock();
+            mvprintw(current->pos.y, current->pos.x * 2, "  ");
+            mvprintw(midpoint.y, midpoint.x * 2, "  ");
+            if (s::render_maze_gen) {
+                refresh();
+                s::draw.unlock();
+                cycle.WaitInterval(s::time_hard_maze_gen);
+            } else {
+                s::draw.unlock();
+            }
+        }
+    }
+}
+
 void maze_gen::PrimWeighted(bool* field, const int& width, const int& height)
 {
     struct cell {
@@ -1118,6 +1217,7 @@ std::map<std::string,
         { "Kruskal", maze_gen::Kruskal },
         { "Prim random edges", maze_gen::PrimRandom },
         { "Prim random weights", maze_gen::PrimWeighted },
+        { "Growing tree", maze_gen::GrowingTree },
         { "Wilson", maze_gen::Wilson },
         { "Recursive divider", maze_gen::RecursiveDivider },
         { "Recursive divider (set based)", maze_gen::RecursiveDividerSet },
diff --git a/maze_gen.hpp b/maze_gen.hpp
@@ -23,6 +23,7 @@ void Backtracker(bool* field, const int& width, const int& height);
 void Kruskal(bool* field, const int& width, const int& height);
 void PrimRandom(bool* field, const int& width, const int& height);
 void PrimWeighted(bool* field, const int& width, const int& height);
+void GrowingTree(bool* field, const int& width, const int& height);
 void Wilson(bool* field, const int& width, const int& height);
 void RecursiveDividerSet(bool* field, const int& width, const int& height);
 void RecursiveDivider(bool* field, const int& width, const int& height);