commit 64dd54f68c964d3faba1b00c3ca94156033e9107
parent 692ddf141a275255a814638b368e2593044122bf
Author: Petar Yotsev <petar@yotsev.xyz>
Date: Sun, 23 Aug 2020 19:34:16 +0100
Add recursive divider for maze generation
This is the simple version of the recursive divider that divides
rectangles in two with a straight wall with a hole in it. The expanding
set recursive divider that was previously implemented with function
name "RecursiveDivider" has been renamed to "RecursiveDividerSet" and
the "RecursiveDivider" function name has been given to the simpler
implementation (from this commit).
Diffstat:
2 files changed, 106 insertions(+), 108 deletions(-)
diff --git a/maze_gen.cpp b/maze_gen.cpp
@@ -558,6 +558,99 @@ void maze_gen::Wilson(bool* field, const int& width, const int& height)
void maze_gen::RecursiveDivider(bool* field, const int& width, const int& height)
{
+ s.draw.lock();
+ for (int y = 1; y < height - 1; ++y) {
+ for (int x = 1; x < width - 1; ++x) {
+ field[y * width + x] = true;
+ mvprintw(y, x * 2, " ");
+ }
+ }
+ refresh();
+ s.draw.unlock();
+
+ timer cycle;
+
+ std::function<void(vec2<int>&, vec2<int>&)> Divide =
+ [&](vec2<int>& top_left, vec2<int>& bottom_right) {
+ // base case
+ if (top_left.x >= bottom_right.x - 3 || top_left.y >= bottom_right.y - 3)
+ return;
+
+ int dx = bottom_right.x - top_left.x;
+ int dy = bottom_right.y - top_left.y;
+
+ if (std::rand() % dx > std::rand() % dy) {
+ // vertical split
+ dx -= 4;
+ // walls row
+ int wx;
+ if (dx < 2) {
+ wx = (top_left.x + bottom_right.x) / 2;
+ } else {
+ wx = top_left.x + (2 * (std::rand() % (dx / 2))) + 2;
+ }
+ dy -= 2;
+ // hole column
+ int hy = top_left.y + (2 * (std::rand() % (dy / 2))) + 1;
+ s.draw.lock();
+ attron(COLOR_PAIR(white));
+ for (int y = top_left.y + 1; y < bottom_right.y; y++) {
+ field[y * width + wx] = false;
+ mvprintw(y, wx * 2, " ");
+ }
+ attroff(COLOR_PAIR(white));
+ attron(COLOR_PAIR(black));
+ field[hy * width + wx] = true;
+ mvprintw(hy, wx * 2, " ");
+ attron(COLOR_PAIR(black));
+ refresh();
+ s.draw.unlock();
+ cycle.WaitInterval(s.time_hard_maze_gen);
+ vec2<int> new_bottom_right(wx, bottom_right.y);
+ vec2<int> new_top_left(wx, top_left.y);
+ Divide(top_left, new_bottom_right);
+ Divide(new_top_left, bottom_right);
+ } else {
+ // horizontal split
+ dy -= 4;
+ // walls column
+ int wy;
+ if (dy < 2) {
+ wy = (top_left.y + bottom_right.y) / 2;
+ } else {
+ wy = top_left.y + (2 * (std::rand() % (dy / 2))) + 2;
+ }
+ dx -= 2;
+ // hole row
+ int hx = top_left.x + (2 * (std::rand() % (dx / 2))) + 1;
+ s.draw.lock();
+ attron(COLOR_PAIR(white));
+ for (int x = top_left.x + 1; x < bottom_right.x; x++) {
+ field[wy * width + x] = false;
+ mvprintw(wy, x * 2, " ");
+ }
+ attroff(COLOR_PAIR(white));
+ attron(COLOR_PAIR(black));
+ field[wy * width + hx] = true;
+ mvprintw(wy, hx * 2, " ");
+ attron(COLOR_PAIR(black));
+ refresh();
+ s.draw.unlock();
+ cycle.WaitInterval(s.time_hard_maze_gen);
+ vec2<int> new_bottom_right(bottom_right.x, wy);
+ vec2<int> new_top_left(top_left.x, wy);
+ Divide(top_left, new_bottom_right);
+ Divide(new_top_left, bottom_right);
+ }
+ };
+
+ vec2<int> tl(0, 0);
+ vec2<int> br(width, height);
+ Divide(tl, br);
+}
+
+void maze_gen::RecursiveDividerSet(bool* field, const int& width, const int& height)
+{
struct cell {
vec2<int> pos;
bool isVisited = false;
@@ -669,16 +762,17 @@ void maze_gen::RecursiveDivider(bool* field, const int& width, const int& height
o.push_back(seedB);
seedA->isVisited = true;
seedB->isVisited = true;
- s.draw.lock();
- attron(COLOR_PAIR(red));
- mvprintw(seedA->pos.y, seedA->pos.x * 2, " ");
- attroff(COLOR_PAIR(red));
- attron(COLOR_PAIR(blue));
- mvprintw(seedB->pos.y, seedB->pos.x * 2, " ");
- attroff(COLOR_PAIR(blue));
- if (s.render_maze_gen)
+ if (s.render_maze_gen) {
+ s.draw.lock();
+ attron(COLOR_PAIR(red));
+ mvprintw(seedA->pos.y, seedA->pos.x * 2, " ");
+ attroff(COLOR_PAIR(red));
+ attron(COLOR_PAIR(blue));
+ mvprintw(seedB->pos.y, seedB->pos.x * 2, " ");
+ attroff(COLOR_PAIR(blue));
refresh();
- s.draw.unlock();
+ s.draw.unlock();
+ }
// expands a and b until they cover the whole of the local set
int index;
@@ -817,104 +911,6 @@ void maze_gen::RecursiveDivider(bool* field, const int& width, const int& height
}
}
-/* void maze_gen::RecursiveDivider(bool* field, const int& width, const int& height) */
-/* { */
-/* for (int y = 1; y < height - 1; ++y) { */
-/* for (int x = 1; x < width - 1; ++x) { */
-/* field[y * width + x] = true; */
-/* mvprintw(y, x * 2, " "); */
-/* } */
-/* } */
-
-/* auto RandOdd = [&](int a, int b) { */
-/* return (a >= b) ? (std::rand() % ((a - b) / 2)) * 2 + 1 */
-/* : (std::rand() % ((b - a) / 2)) * 2; */
-/* }; */
-
-/* auto RandEven = [&](int a, int b) { */
-/* return (a >= b) ? (std::rand() % ((a - b - 1) / 2)) * 2 + 1 */
-/* : (std::rand() % ((b - a - 1) / 2)) * 2 + 1; */
-/* }; */
-
-/* refresh(); */
-/* timer cycle; */
-
-/* std::function<void(vec2<int>&, vec2<int>&)> Divide = */
-/* [&](vec2<int>& top_left, vec2<int>& bottom_right) { */
-/* if (top_left.x >= bottom_right.x || top_left.y >= bottom_right.y) */
-/* return; */
-
-/* attron(COLOR_PAIR(white)); */
-/* int vwallx = top_left.x + RandOdd(top_left.x, bottom_right.x); */
-/* for (int y = top_left.y; y <= bottom_right.y; ++y) { */
-/* field[y * width + vwallx] = false; */
-/* mvprintw(y, vwallx * 2, " "); */
-/* } */
-/* attroff(COLOR_PAIR(white)); */
-/* getch(); */
-
-/* attron(COLOR_PAIR(black)); */
-/* int vwallholey = top_left.y + RandEven(top_left.y, bottom_right.y); */
-/* field[vwallholey * width + top_left.x + vwallx] = true; */
-/* mvprintw(vwallholey, (top_left.x + vwallx) * 2, " "); */
-/* attroff(COLOR_PAIR(black)); */
-/* getch(); */
-
-/* attron(COLOR_PAIR(white)); */
-/* int hwally = top_left.y + RandOdd(top_left.y, bottom_right.y); */
-/* for (int x = top_left.x; x <= bottom_right.x; ++x) { */
-/* field[hwally * width + x] = false; */
-/* mvprintw(hwally, x * 2, " "); */
-/* } */
-/* attroff(COLOR_PAIR(white)); */
-/* getch(); */
-
-/* attron(COLOR_PAIR(black)); */
-/* int vwallholex1 = top_left.x + RandEven(top_left.x, bottom_right.x); */
-/* int vwallholex2 = top_left.x + RandEven(top_left.x, bottom_right.x); */
-/* field[hwally * width + top_left.x + vwallholex1] = true; */
-/* field[hwally * width + top_left.x + vwallholex2] = true; */
-/* mvprintw(hwally, (top_left.x + vwallholex1) * 2, " "); */
-/* mvprintw(hwally, (top_left.x + vwallholex2) * 2, " "); */
-/* attroff(COLOR_PAIR(black)); */
-/* getch(); */
-
-/* refresh(); */
-
-/* vec2<int> tl(top_left); */
-/* vec2<int> br(top_left.x + vwallx, top_left.y + hwally); */
-/* /1* std::thread worker_tl(Divide, tl, br); *1/ */
-/* cycle.WaitInterval(s.time_hard_maze_gen); */
-/* Divide(tl, br); */
-
-/* tl = vec2<int>(top_left.x + vwallx, top_left.y); */
-/* br = vec2<int>(bottom_right.x, top_left.y + hwally); */
-/* /1* std::thread worker_tr(Divide, tl, br); *1/ */
-/* cycle.WaitInterval(s.time_hard_maze_gen); */
-/* Divide(tl, br); */
-
-/* tl = vec2<int>(top_left.x, top_left.y + hwally); */
-/* br = vec2<int>(top_left.x + vwallx, bottom_right.y); */
-/* /1* std::thread worker_bl(Divide, tl, br); *1/ */
-/* cycle.WaitInterval(s.time_hard_maze_gen); */
-/* Divide(tl, br); */
-
-/* tl = vec2<int>(top_left.x + vwallx, top_left.y + hwally); */
-/* br = vec2<int>(bottom_right); */
-/* /1* std::thread worker_br(Divide, tl, br); *1/ */
-/* cycle.WaitInterval(s.time_hard_maze_gen); */
-/* Divide(tl, br); */
-
-/* /1* worker_tl.join(); *1/ */
-/* /1* worker_tr.join(); *1/ */
-/* /1* worker_bl.join(); *1/ */
-/* /1* worker_br.join(); *1/ */
-/* }; */
-/* vec2<int> tl(1, 1); */
-/* vec2<int> br(width - 1, height - 1); */
-/* Divide(tl, br); */
-/* } */
-
std::map<std::string,
void (*)(
bool* field,
@@ -926,6 +922,7 @@ std::map<std::string,
{ "PrimRandom", maze_gen::PrimRandom },
{ "PrimWeighted", maze_gen::PrimWeighted },
{ "Wilson", maze_gen::Wilson },
- { "RecursiveDivider", maze_gen::RecursiveDivider }
+ { "RecursiveDivider", maze_gen::RecursiveDivider },
+ { "RecursiveDividerSet", maze_gen::RecursiveDividerSet }
};
diff --git a/maze_gen.hpp b/maze_gen.hpp
@@ -24,6 +24,7 @@ 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 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);
}; // namespace maze_gen
