commit 7aeb451d3992f0c5c294101298058a9b27b7598b
parent 7f726056c97d57832700bab60ec2fa5e066fb348
Author: Petar Yotsev <petar@yotsev.xyz>
Date: Sat, 14 Nov 2020 10:47:26 +0000
Add sidewinder and Eller's algorithm
Diffstat:
4 files changed, 182 insertions(+), 10 deletions(-)
diff --git a/README.md b/README.md
@@ -18,8 +18,8 @@ the terminal.
* [ ] Growing tree
* [X] Wilson's random walk algorithm
* [X] Binary tree
- * [ ] Eller's algorithm
- * [ ] Sidewinder
+ * [X] Eller's algorithm
+ * [X] Sidewinder
* Pathfinding algorithms
* [X] A*
* [X] Dijkstra's
diff --git a/maze_gen.cpp b/maze_gen.cpp
@@ -398,7 +398,7 @@ void maze_gen::PrimWeighted(bool* field, const int& width, const int& height)
attron(COLOR_PAIR(red));
for (cell* n : current->neighbors) {
n->parent = current;
- n->weight = std::rand() % range;
+ n->weight = std::rand();
openSet.push_back(n);
mvprintw(n->pos.y, n->pos.x * 2, " ");
}
@@ -916,17 +916,20 @@ void maze_gen::BinaryTree(bool* field, const int& width, const int& height)
std::vector<vec2<int>> neighbors;
vec2<int>* selected;
timer cycle;
+ // goes through all positions
for (int y = 1; y < height - 1; y += 2) {
for (int x = 1; x < width - 1; x += 2) {
+ // checks if neighbors are within bounds
if (x < width - 3)
neighbors.push_back(vec2<int>(x + 2, y));
if (y < height - 3)
neighbors.push_back(vec2<int>(x, y + 2));
if (neighbors.empty())
continue;
+ // chooses randomly between bottom and right neighbor and
+ // carves the wall to it
selected = &neighbors[std::rand() % neighbors.size()];
field[(y * width) + x] = true;
- field[(selected->y * width) + selected->x] = true;
field[((selected->y + y) * width / 2) + (selected->x + x) / 2] = true;
s::draw.lock();
mvprintw(y, x * 2, " ");
@@ -940,6 +943,171 @@ void maze_gen::BinaryTree(bool* field, const int& width, const int& height)
}
}
+void maze_gen::Eller(bool* field, const int& width, const int& height)
+{
+ struct cell {
+ vec2<int> pos;
+ int s = 0;
+ };
+
+ cell grid[width][height];
+ for (int y = 0; y < height; ++y) {
+ for (int x = 0; x < width; ++x) {
+ grid[x][y].pos.x = x;
+ grid[x][y].pos.y = y;
+ }
+ }
+
+ std::vector<cell*> local_set;
+ int last_set;
+ int next_set = 1;
+ timer cycle;
+
+ for (int y = 1; y < height - 1; y += 2) {
+ // assigns sets to new cells and caries sets from previous row
+ if (y == 1) {
+ for (int x = 1; x < width - 1; x += 2) {
+ grid[x][y].s = next_set;
+ ++next_set;
+ }
+ } else {
+ for (int x = 1; x < width - 1; x += 2) {
+ if (field[(y - 1) * width + x]) {
+ grid[x][y].s = grid[x][y - 2].s;
+ } else {
+ grid[x][y].s = next_set;
+ ++next_set;
+ }
+ }
+ }
+ // randomly merges sets
+ for (int x = 1; x < width - 1; x += 2) {
+ // sets the field to path where it's guarantied to always be
+ // a path (see documentation)
+ field[(y * width) + x] = true;
+ s::draw.lock();
+ mvprintw(y, x * 2, " ");
+ refresh();
+ s::draw.unlock();
+ // randomly chooses to merge sets
+ if (grid[x + 2][y].s != grid[x][y].s && std::rand() % 2 == 0 && x < width - 3) {
+ grid[x + 2][y].s = grid[x][y].s;
+ field[(y * width) + x + 1] = true;
+ s::draw.lock();
+ mvprintw(y, (x + 1) * 2, " ");
+ mvprintw(y, (x + 2) * 2, " ");
+ refresh();
+ s::draw.unlock();
+ }
+ cycle.WaitInterval(s::time_hard_maze_gen);
+ }
+ // places the down walls
+ local_set.push_back(&grid[1][y]);
+ last_set = grid[1][y].s;
+ if (y < height - 3) {
+ for (int x = 3; x < width - 1; x += 2) {
+ if (grid[x][y].s != last_set || x > width - 2) {
+ // encounters next set, drills one hole & clears set
+ vec2<int>* pos = &local_set[std::rand() % local_set.size()]->pos;
+ field[(pos->y + 1) * width + pos->x] = true;
+ s::draw.lock();
+ mvprintw(pos->y + 1, pos->x * 2, " ");
+ refresh();
+ s::draw.unlock();
+ local_set.clear();
+ local_set.push_back(&grid[x][y]);
+ last_set = grid[x][y].s;
+ cycle.WaitInterval(s::time_hard_maze_gen);
+ } else {
+ // expands local set
+ local_set.push_back(&grid[x][y]);
+ }
+ }
+ vec2<int>* pos = &local_set[std::rand() % local_set.size()]->pos;
+ field[(pos->y + 1) * width + pos->x] = true;
+ s::draw.lock();
+ mvprintw(pos->y + 1, pos->x * 2, " ");
+ refresh();
+ s::draw.unlock();
+ local_set.clear();
+ } else {
+ // preform final merge
+ for (int x = 1; x < width - 1; x += 2) {
+ if (grid[x + 2][y].s != grid[x][y].s && x < width - 3) {
+ field[(y * width) + x + 1] = true;
+ s::draw.lock();
+ mvprintw(y, (x + 1) * 2, " ");
+ mvprintw(y, (x + 2) * 2, " ");
+ refresh();
+ s::draw.unlock();
+ }
+ cycle.WaitInterval(s::time_hard_maze_gen);
+ }
+ }
+ }
+}
+
+void maze_gen::Sidewinder(bool* field, const int& width, const int& height)
+{
+ std::vector<vec2<int>> run_set;
+ vec2<int>* selected;
+ timer cycle;
+ for (int y = 1; y < height - 1; y += 2) {
+ run_set.push_back(vec2<int>(1, y));
+ for (int x = 1; x < width - 1; x += 2) {
+ // sets the field to path where it's guarantied to always be
+ // a path (see documentation)
+ field[(y * width) + x] = true;
+ s::draw.lock();
+ mvprintw(y, x * 2, " ");
+ s::draw.unlock();
+ // randomly chooses to carve up or right
+ // safeguards for the top row \/ \/
+ if ((std::rand() % 2 == 0 || x == width - 2) && (y > 1)) {
+ // carve the up wall from random position in the run set
+ if (run_set.empty())
+ run_set.push_back(vec2<int>(x, y));
+ selected = &run_set[std::rand() % run_set.size()];
+ field[((selected->y - 1) * width) + selected->x] = true;
+ s::draw.lock();
+ mvprintw(selected->y - 1, selected->x * 2, " ");
+ mvprintw(selected->y - 2, selected->x * 2, " ");
+ refresh();
+ s::draw.unlock();
+ // clears the run set
+ run_set.clear();
+ cycle.WaitInterval(s::time_hard_maze_gen);
+ } else if (x < width - 3) {
+ // adds this position if previously carved up
+ if (run_set.empty())
+ run_set.push_back(vec2<int>(x, y));
+ // adds right neighbor to the run set
+ run_set.push_back(vec2<int>(x + 2, y));
+ // carves the right wall
+ field[(y * width) + x + 1] = true;
+ s::draw.lock();
+ mvprintw(y, (x + 1) * 2, " ");
+ mvprintw(y, (x + 2) * 2, " ");
+ refresh();
+ s::draw.unlock();
+ cycle.WaitInterval(s::time_hard_maze_gen);
+ }
+ }
+ if (!run_set.empty() && y > 1) {
+ // carve the up wall from random position in the run set
+ selected = &run_set[std::rand() % run_set.size()];
+ field[((selected->y - 1) * width) + selected->x] = true;
+ s::draw.lock();
+ mvprintw(selected->y - 1, selected->x * 2, " ");
+ mvprintw(selected->y - 2, selected->x * 2, " ");
+ refresh();
+ s::draw.unlock();
+ cycle.WaitInterval(s::time_hard_maze_gen);
+ }
+ run_set.clear();
+ }
+}
+
std::map<std::string,
void (*)(
bool* field,
@@ -948,11 +1116,13 @@ std::map<std::string,
generators = {
{ "Backtracker", maze_gen::Backtracker },
{ "Kruskal", maze_gen::Kruskal },
- { "PrimRandom", maze_gen::PrimRandom },
- { "PrimWeighted", maze_gen::PrimWeighted },
+ { "Prim random edges", maze_gen::PrimRandom },
+ { "Prim random weights", maze_gen::PrimWeighted },
{ "Wilson", maze_gen::Wilson },
- { "RecursiveDivider", maze_gen::RecursiveDivider },
- { "RecursiveDividerSet", maze_gen::RecursiveDividerSet },
- { "BinaryTree", maze_gen::BinaryTree },
+ { "Recursive divider", maze_gen::RecursiveDivider },
+ { "Recursive divider (set based)", maze_gen::RecursiveDividerSet },
+ { "Binary tree", maze_gen::BinaryTree },
+ { "Eller", maze_gen::Eller },
+ { "Sidewinder", maze_gen::Sidewinder },
};
diff --git a/maze_gen.hpp b/maze_gen.hpp
@@ -27,6 +27,8 @@ 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);
void BinaryTree(bool* field, const int& width, const int& height);
+void Eller(bool* field, const int& width, const int& height);
+void Sidewinder(bool* field, const int& width, const int& height);
}; // namespace maze_gen
#endif // MAZE_GEN_HPP
diff --git a/state.cpp b/state.cpp
@@ -16,5 +16,5 @@ bool render_pathfinding = true; // should you render pathfinding proccess?
bool ui_is_open = false; // is ui open or waiting to be rendered?
bool ui_render_is_safe = false; // is it safe to render ui?
std::string pathfinder = "A*";
-std::string generator = "BinaryTree";
+std::string generator = "Prim random weights";
};
