commit b22441d60e45dbf97bc42e6318f9cf3f33f32e54
parent e76c6284c4f17d44cfc4f099bd62dabd31d32acb
Author: Petar Yotsev <petar@yotsev.xyz>
Date: Sat, 22 Aug 2020 16:41:20 +0100
Added Prim's algorithm with random weights
There are two modifications that can be made to Prim's algorithm to make
it generate mazes: Running Prim's algorithm on a graph with random
weights and choosing the next edge to be connected randomly. This commit
adds the former while renaming the latter from simply "Prim" to
"PrimRandom". The new algorithm is named "PrimWeighted".
Diffstat:
2 files changed, 106 insertions(+), 3 deletions(-)
diff --git a/maze_gen.cpp b/maze_gen.cpp
@@ -232,7 +232,7 @@ void maze_gen::Kruskal(bool* field, const int& width, const int& height)
attroff(COLOR_PAIR(black));
}
-void maze_gen::Prim(bool* field, const int& width, const int& height)
+void maze_gen::PrimRandom(bool* field, const int& width, const int& height)
{
struct cell {
vec2<int> pos;
@@ -314,9 +314,110 @@ void maze_gen::Prim(bool* field, const int& width, const int& height)
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 {
+ 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]);
+ }
+ };
+
+ // 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()) {
+ // get edge with smallest weight
+ index = 0;
+ for (int i = 1; i < openSet.size(); ++i) {
+ if (openSet[i]->weight < openSet[index]->weight)
+ index = i;
+ }
+ 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() % range;
+ 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();
+ }
}
}
}
@@ -822,7 +923,8 @@ std::map<std::string,
generators = {
{ "Backtracker", maze_gen::Backtracker },
{ "Kruskal", maze_gen::Kruskal },
- { "Prim", maze_gen::Prim },
+ { "PrimRandom", maze_gen::PrimRandom },
+ { "PrimWeighted", maze_gen::PrimWeighted },
{ "Wilson", maze_gen::Wilson },
{ "RecursiveDivider", maze_gen::RecursiveDivider }
};
diff --git a/maze_gen.hpp b/maze_gen.hpp
@@ -21,7 +21,8 @@
namespace maze_gen {
void Backtracker(bool* field, const int& width, const int& height);
void Kruskal(bool* field, const int& width, const int& height);
-void Prim(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 RecursiveDivider(bool* field, const int& width, const int& height);
}; // namespace maze_gen
