maze_gen.cpp (45128B)
1 #include <cstdlib> 2 #include <exception> 3 #include <ncurses.h> 4 5 #include <algorithm> 6 #include <functional> 7 #include <map> 8 #include <random> 9 #include <set> 10 #include <stack> 11 #include <thread> 12 #include <vector> 13 14 #include "colors.hpp" 15 #include "maze_gen.hpp" 16 #include "state.hpp" 17 #include "timer.hpp" 18 #include "vec2.hpp" 19 20 void maze_gen::Backtracker(bool* field, const int& width, const int& height) 21 { 22 enum dir { 23 up, 24 down, 25 left, 26 right 27 }; 28 29 // setting the coordinates of each cell according to their placement in the 30 // array because the contents of the cells will map to their locations in 31 // memory making addressing easier 32 vec2<int> grid[width * height]; 33 for (int y = 0; y < height; ++y) { 34 for (int x = 0; x < width; ++x) { 35 grid[(y * width) + x].y = y; 36 grid[(y * width) + x].x = x; 37 } 38 } 39 std::stack<vec2<int>*> cells; 40 std::vector<dir> dirs; 41 timer cycle; 42 43 auto offset = [&](int x, int y) { 44 return ((cells.top()->y + y) * width) + cells.top()->x + x; 45 }; 46 auto drawoffset = [&](int x, int y) { 47 s::draw.lock(); 48 mvprintw(cells.top()->y + y, (cells.top()->x + x) * 2, " "); 49 s::draw.unlock(); 50 }; 51 52 // setting a random root position 53 // because the mazes look more interesting when having irregular roots 54 cells.push(&grid[(((std::rand() % (height / 2)) * 2 + 1) * width) 55 + ((std::rand() % (width / 2)) * 2) + 1]); 56 field[offset(0, 0)] = true; 57 drawoffset(0, 0); 58 59 while (!cells.empty()) { 60 // checking for viable directions 61 dirs.clear(); 62 if (cells.top()->y > 1 && !field[offset(0, -2)]) 63 dirs.emplace_back(up); 64 if (cells.top()->y < height - 2 && !field[offset(0, 2)]) 65 dirs.emplace_back(down); 66 if (cells.top()->x > 1 && !field[offset(-2, 0)]) 67 dirs.emplace_back(left); 68 if (cells.top()->x < width - 2 && !field[offset(2, 0)]) 69 dirs.emplace_back(right); 70 71 // picks a random viable direction and carves a path two cells in that 72 // direction 73 if (!dirs.empty()) { 74 shuffle(dirs.begin(), dirs.end(), 75 std::default_random_engine(std::rand())); 76 switch (dirs[std::rand() % dirs.size()]) { 77 case up: 78 field[offset(0, -1)] = true; 79 field[offset(0, -2)] = true; 80 drawoffset(0, -1); 81 drawoffset(0, -2); 82 cells.push(&grid[offset(0, -2)]); 83 break; 84 case down: 85 field[offset(0, 1)] = true; 86 field[offset(0, 2)] = true; 87 drawoffset(0, 1); 88 drawoffset(0, 2); 89 cells.push(&grid[offset(0, 2)]); 90 break; 91 case left: 92 field[offset(-1, 0)] = true; 93 field[offset(-2, 0)] = true; 94 drawoffset(-1, 0); 95 drawoffset(-2, 0); 96 cells.push(&grid[offset(-2, 0)]); 97 break; 98 case right: 99 field[offset(1, 0)] = true; 100 field[offset(2, 0)] = true; 101 drawoffset(1, 0); 102 drawoffset(2, 0); 103 cells.push(&grid[offset(2, 0)]); 104 break; 105 } 106 } else { 107 // if there are no viable directions it backtracks 108 cells.pop(); 109 } 110 if (s::render_maze_gen) { 111 s::draw.lock(); 112 refresh(); 113 s::draw.unlock(); 114 cycle.WaitInterval(s::time_hard_maze_gen); 115 } 116 } 117 } 118 119 void maze_gen::Kruskal(bool* field, const int& width, const int& height) 120 { 121 struct cell { 122 vec2<int> pos; 123 cell* parent = nullptr; 124 }; 125 struct edge { 126 cell* primary = nullptr; 127 cell* secondary = nullptr; 128 } current; 129 130 // setting the coordinates of each cell according to their placement in the 131 // array because the contents of the cells will map to their locations in 132 // memory making addressing easier 133 cell grid[width * height]; 134 for (int y = 0; y < height; ++y) { 135 for (int x = 0; x < width; ++x) { 136 grid[(y * width) + x].pos.x = x; 137 grid[(y * width) + x].pos.y = y; 138 } 139 } 140 141 // initializing the list of edges 142 std::vector<edge> edges; 143 for (int y = 1; y < height - 1; y += 2) { 144 for (int x = 1; x < width - 1; x += 2) { 145 // initializing horizontal edges 146 if (x < width - 3) { 147 current.primary = &grid[(y * width) + x]; 148 current.secondary = &grid[(y * width) + x + 2]; 149 edges.push_back(current); 150 } 151 // initializing vertical edges 152 if (y < height - 3) { 153 current.primary = &grid[(y * width) + x]; 154 current.secondary = &grid[((y + 2) * width) + x]; 155 edges.push_back(current); 156 } 157 // setting the squares where it's guarantied to always be a path 158 // here instead of later when the path is being carved to prevent 159 // multiple unnecessary changes to the path when edges of the same 160 // cell are being evaluated 161 field[(y * width) + x] = true; 162 } 163 } 164 165 shuffle(edges.begin(), edges.end(), 166 std::default_random_engine(std::rand())); 167 168 // initializing the roots for set identification of cells 169 cell* pRoot; // primary cell root 170 cell* sRoot; // secondary cell root 171 cell* prev; 172 vec2<int> edgePos; 173 timer cycle; 174 175 attron(COLOR_PAIR(black)); 176 for (edge e : edges) { 177 // finds the root of the primary cell 178 prev = e.primary; 179 while (prev->parent != nullptr) { 180 prev = prev->parent; 181 } 182 // if the cell has no root it sets the root to itself 183 if (prev == nullptr) { 184 pRoot = e.primary; 185 } else { 186 pRoot = prev; 187 } 188 189 // finds the root of the secondary cell 190 prev = e.secondary; 191 while (prev->parent != nullptr) { 192 prev = prev->parent; 193 } 194 // if the cell has no root it sets the root to itself 195 if (prev == nullptr) { 196 sRoot = e.secondary; 197 } else { 198 sRoot = prev; 199 } 200 201 // checks if the primary cell and the secondary cell are part of the 202 // same tree if not it joins the two trees until there is only one tree 203 // left (the maze) 204 if (pRoot != sRoot) { 205 edgePos = (e.primary + (e.secondary - e.primary) / 2)->pos; 206 field[(edgePos.y * width) + edgePos.x] = true; 207 208 s::draw.lock(); 209 mvprintw(e.primary->pos.y, e.primary->pos.x * 2, " "); 210 mvprintw(e.secondary->pos.y, e.secondary->pos.x * 2, " "); 211 mvprintw(edgePos.y, edgePos.x * 2, " "); 212 213 // need to add meta data option to state class 214 mvprintw(sRoot->pos.y, sRoot->pos.x * 2, " "); 215 sRoot->parent = pRoot; 216 attron(COLOR_PAIR(red)); 217 mvprintw(pRoot->pos.y, pRoot->pos.x * 2, " "); 218 attroff(COLOR_PAIR(red)); 219 s::draw.unlock(); 220 221 if (s::render_maze_gen) { 222 s::draw.lock(); 223 refresh(); 224 s::draw.unlock(); 225 cycle.WaitInterval(s::time_hard_maze_gen); 226 } 227 } 228 } 229 s::draw.lock(); 230 mvprintw(sRoot->pos.y, sRoot->pos.x * 2, " "); 231 s::draw.unlock(); 232 attroff(COLOR_PAIR(black)); 233 } 234 235 void maze_gen::PrimRandom(bool* field, const int& width, const int& height) 236 { 237 struct cell { 238 vec2<int> pos; 239 const cell* parent; 240 std::vector<cell*> neighbors; 241 // adds valid neighbors 242 void AddNeighbors(const bool* field, cell* grid, const int& width, 243 const int& height) 244 { 245 neighbors.clear(); 246 // up 247 if (pos.y > 1 && !field[(pos.y - 2) * width + pos.x]) 248 neighbors.emplace_back(&grid[(pos.y - 2) * width + pos.x]); 249 // down 250 if (pos.y < height - 2 && !field[(pos.y + 2) * width + pos.x]) 251 neighbors.emplace_back(&grid[(pos.y + 2) * width + pos.x]); 252 // left 253 if (pos.x > 1 && !field[(pos.y * width) + pos.x - 2]) 254 neighbors.emplace_back(&grid[(pos.y * width) + pos.x - 2]); 255 // right 256 if (pos.x < width - 2 && !field[(pos.y * width) + pos.x + 2]) 257 neighbors.emplace_back(&grid[(pos.y * width) + pos.x + 2]); 258 } 259 }; 260 261 // setting the coordinates of each cell according to their placement in the 262 // array because the contents of the cells will map to their locations in 263 // memory making addressing easier 264 cell grid[width * height]; 265 for (int y = 0; y < height; ++y) { 266 for (int x = 0; x < width; ++x) { 267 grid[(y * width) + x].pos.x = x; 268 grid[(y * width) + x].pos.y = y; 269 } 270 } 271 272 // gives the index of a cell in the field 273 auto Index = [&](vec2<int> v) { return v.y * width + v.x; }; 274 275 // initializing the open set with a viable random position, aka the root 276 // because the mazes look more interesting when having irregular roots 277 std::vector<cell*> openSet; 278 openSet.push_back(&grid[(((std::rand() % (height / 2)) * 2 + 1) * width) 279 + ((std::rand() % (width / 2)) * 2) + 1]); 280 /* field[(openSet[0]->pos.y * width) + openSet[0]->pos.x] = true; */ 281 /* mvprintw(openSet[0]->pos.y, openSet[0]->pos.x * 2, " "); */ 282 openSet[0]->parent = openSet[0]; 283 284 int index; 285 cell* current; 286 vec2<int> midpoint; 287 timer cycle; 288 289 // carving a path to a random unexplored cell 290 // until there are no more explorable cells 291 while (!openSet.empty()) { 292 index = std::rand() % openSet.size(); 293 current = openSet[index]; 294 openSet.erase(openSet.begin() + index); 295 296 // if the current position is not part of the maze, make it one 297 if (!field[Index(current->pos)]) { 298 current->AddNeighbors(field, grid, width, height); 299 s::draw.lock(); 300 attron(COLOR_PAIR(red)); 301 for (cell* n : current->neighbors) { 302 n->parent = current; 303 openSet.push_back(n); 304 mvprintw(n->pos.y, n->pos.x * 2, " "); 305 } 306 attroff(COLOR_PAIR(red)); 307 s::draw.unlock(); 308 309 midpoint = (current + (current->parent - current) / 2)->pos; 310 field[Index(current->pos)] = true; 311 field[Index(midpoint)] = true; 312 s::draw.lock(); 313 mvprintw(current->pos.y, current->pos.x * 2, " "); 314 mvprintw(midpoint.y, midpoint.x * 2, " "); 315 if (s::render_maze_gen) { 316 refresh(); 317 s::draw.unlock(); 318 cycle.WaitInterval(s::time_hard_maze_gen); 319 } else { 320 s::draw.unlock(); 321 } 322 } 323 } 324 } 325 326 void maze_gen::GrowingTree(bool* field, const int& width, const int& height) 327 { 328 struct cell { 329 vec2<int> pos; 330 const cell* parent; 331 int weight; 332 std::vector<cell*> neighbors; 333 // adds valid neighbors 334 void AddNeighbors(const bool* field, cell* grid, const int& width, 335 const int& height) 336 { 337 neighbors.clear(); 338 // up 339 if (pos.y > 1 && !field[(pos.y - 2) * width + pos.x]) 340 neighbors.emplace_back(&grid[(pos.y - 2) * width + pos.x]); 341 // down 342 if (pos.y < height - 2 && !field[(pos.y + 2) * width + pos.x]) 343 neighbors.emplace_back(&grid[(pos.y + 2) * width + pos.x]); 344 // left 345 if (pos.x > 1 && !field[(pos.y * width) + pos.x - 2]) 346 neighbors.emplace_back(&grid[(pos.y * width) + pos.x - 2]); 347 // right 348 if (pos.x < width - 2 && !field[(pos.y * width) + pos.x + 2]) 349 neighbors.emplace_back(&grid[(pos.y * width) + pos.x + 2]); 350 shuffle(neighbors.begin(), neighbors.end(), 351 std::default_random_engine(std::rand())); 352 } 353 }; 354 355 // setting the coordinates of each cell according to their placement in the 356 // array because the contents of the cells will map to their locations in 357 // memory making addressing easier 358 cell grid[width * height]; 359 for (int y = 0; y < height; ++y) { 360 for (int x = 0; x < width; ++x) { 361 grid[(y * width) + x].pos.x = x; 362 grid[(y * width) + x].pos.y = y; 363 } 364 } 365 366 // gives the index of a cell in the field 367 auto Index = [&](vec2<int> v) { return v.y * width + v.x; }; 368 369 // initializing the open set with a viable random position, aka the root 370 // because the mazes look more interesting when having irregular roots 371 std::vector<cell*> openSet; 372 openSet.push_back(&grid[(((std::rand() % (height / 2)) * 2 + 1) * width) 373 + ((std::rand() % (width / 2)) * 2) + 1]); 374 /* field[(openSet[0]->pos.y * width) + openSet[0]->pos.x] = true; */ 375 /* mvprintw(openSet[0]->pos.y, openSet[0]->pos.x * 2, " "); */ 376 openSet[0]->parent = openSet[0]; 377 378 const int range = std::sqrt(width * height); 379 int index; 380 cell* current; 381 vec2<int> midpoint; 382 timer cycle; 383 384 // carving a path to a random unexplored cell 385 // until there are no more explorable cells 386 while (!openSet.empty()) { 387 // 50/50 use bottom or top of the stack as the next cell 388 index = 0; 389 if (std::rand() % 100 < 50) 390 index = openSet.size() - 1; 391 current = openSet[index]; 392 openSet.erase(openSet.begin() + index); 393 394 // if the current position is not part of the maze, make it one 395 if (!field[Index(current->pos)]) { 396 current->AddNeighbors(field, grid, width, height); 397 s::draw.lock(); 398 attron(COLOR_PAIR(red)); 399 for (cell* n : current->neighbors) { 400 n->parent = current; 401 n->weight = std::rand(); 402 openSet.push_back(n); 403 mvprintw(n->pos.y, n->pos.x * 2, " "); 404 } 405 attroff(COLOR_PAIR(red)); 406 s::draw.unlock(); 407 408 midpoint = (current + (current->parent - current) / 2)->pos; 409 field[Index(current->pos)] = true; 410 field[Index(midpoint)] = true; 411 s::draw.lock(); 412 mvprintw(current->pos.y, current->pos.x * 2, " "); 413 mvprintw(midpoint.y, midpoint.x * 2, " "); 414 if (s::render_maze_gen) { 415 refresh(); 416 s::draw.unlock(); 417 cycle.WaitInterval(s::time_hard_maze_gen); 418 } else { 419 s::draw.unlock(); 420 } 421 } 422 } 423 } 424 425 void maze_gen::PrimWeighted(bool* field, const int& width, const int& height) 426 { 427 struct cell { 428 vec2<int> pos; 429 const cell* parent; 430 int weight; 431 std::vector<cell*> neighbors; 432 // adds valid neighbors 433 void AddNeighbors(const bool* field, cell* grid, const int& width, 434 const int& height) 435 { 436 neighbors.clear(); 437 // up 438 if (pos.y > 1 && !field[(pos.y - 2) * width + pos.x]) 439 neighbors.emplace_back(&grid[(pos.y - 2) * width + pos.x]); 440 // down 441 if (pos.y < height - 2 && !field[(pos.y + 2) * width + pos.x]) 442 neighbors.emplace_back(&grid[(pos.y + 2) * width + pos.x]); 443 // left 444 if (pos.x > 1 && !field[(pos.y * width) + pos.x - 2]) 445 neighbors.emplace_back(&grid[(pos.y * width) + pos.x - 2]); 446 // right 447 if (pos.x < width - 2 && !field[(pos.y * width) + pos.x + 2]) 448 neighbors.emplace_back(&grid[(pos.y * width) + pos.x + 2]); 449 } 450 }; 451 452 // setting the coordinates of each cell according to their placement in the 453 // array because the contents of the cells will map to their locations in 454 // memory making addressing easier 455 cell grid[width * height]; 456 for (int y = 0; y < height; ++y) { 457 for (int x = 0; x < width; ++x) { 458 grid[(y * width) + x].pos.x = x; 459 grid[(y * width) + x].pos.y = y; 460 } 461 } 462 463 // gives the index of a cell in the field 464 auto Index = [&](vec2<int> v) { return v.y * width + v.x; }; 465 466 // initializing the open set with a viable random position, aka the root 467 // because the mazes look more interesting when having irregular roots 468 std::vector<cell*> openSet; 469 openSet.push_back(&grid[(((std::rand() % (height / 2)) * 2 + 1) * width) 470 + ((std::rand() % (width / 2)) * 2) + 1]); 471 /* field[(openSet[0]->pos.y * width) + openSet[0]->pos.x] = true; */ 472 /* mvprintw(openSet[0]->pos.y, openSet[0]->pos.x * 2, " "); */ 473 openSet[0]->parent = openSet[0]; 474 475 const int range = std::sqrt(width * height); 476 int index; 477 cell* current; 478 vec2<int> midpoint; 479 timer cycle; 480 481 // carving a path to a random unexplored cell 482 // until there are no more explorable cells 483 while (!openSet.empty()) { 484 // get edge with smallest weight 485 index = 0; 486 for (int i = 1; i < openSet.size(); ++i) { 487 if (openSet[i]->weight < openSet[index]->weight) 488 index = i; 489 } 490 current = openSet[index]; 491 openSet.erase(openSet.begin() + index); 492 493 // if the current position is not part of the maze, make it one 494 if (!field[Index(current->pos)]) { 495 current->AddNeighbors(field, grid, width, height); 496 s::draw.lock(); 497 attron(COLOR_PAIR(red)); 498 for (cell* n : current->neighbors) { 499 n->parent = current; 500 n->weight = std::rand(); 501 openSet.push_back(n); 502 mvprintw(n->pos.y, n->pos.x * 2, " "); 503 } 504 attroff(COLOR_PAIR(red)); 505 s::draw.unlock(); 506 507 midpoint = (current + (current->parent - current) / 2)->pos; 508 field[Index(current->pos)] = true; 509 field[Index(midpoint)] = true; 510 s::draw.lock(); 511 mvprintw(current->pos.y, current->pos.x * 2, " "); 512 mvprintw(midpoint.y, midpoint.x * 2, " "); 513 if (s::render_maze_gen) { 514 refresh(); 515 s::draw.unlock(); 516 cycle.WaitInterval(s::time_hard_maze_gen); 517 } else { 518 s::draw.unlock(); 519 } 520 } 521 } 522 } 523 524 void maze_gen::Wilson(bool* field, const int& width, const int& height) 525 { 526 enum direction { up, 527 down, 528 left, 529 right }; 530 531 // setting the coordinates of each cell according to their placement in the 532 // array because the contents of the cells will map to their locations in 533 // memory making addressing easier 534 vec2<int> grid[width * height]; 535 for (int y = 0; y < height; ++y) { 536 for (int x = 0; x < width; ++x) { 537 grid[(y * width) + x].y = y; 538 grid[(y * width) + x].x = x; 539 } 540 } 541 std::vector<vec2<int>*> cells; 542 std::vector<direction> dirs; 543 vec2<int>* nextCell; 544 vec2<int>* prevCell; 545 vec2<int>* wall; 546 timer cycle; 547 548 // gives the index of a cell in the grid 549 auto Index = [&](vec2<int>* v) { return v->y * width + v->x; }; 550 // gives the index of a cell with a coordinate offset in the grid 551 auto IndexOffset = [&](int x, int y) { 552 return ((cells.back()->y + y) * width) + cells.back()->x + x; 553 }; 554 // draws a cell in the grid 555 auto Draw = [&](vec2<int>* v) { 556 s::draw.lock(); 557 mvprintw(v->y, v->x * 2, " "); 558 s::draw.unlock(); 559 }; 560 // draws a cell with a coordinate offset 561 auto DrawOffset = [&](int x, int y) { 562 s::draw.lock(); 563 mvprintw(cells.back()->y + y, (cells.back()->x + x) * 2, " "); 564 s::draw.unlock(); 565 }; 566 567 // looping through all path cells in the grid that are not part of the maze 568 field[width + 1] = true; 569 s::draw.lock(); 570 mvprintw(1, 2, " "); 571 s::draw.unlock(); 572 for (int y = 1; y < height; y += 2) { 573 for (int x = 1; x < width; x += 2) { 574 if (!field[y * width + x]) { 575 cells.clear(); 576 cells.emplace_back(&grid[y * width + x]); 577 Draw(cells.back()); 578 579 // going on a loop erased random walk until the maze is reached 580 while (!field[IndexOffset(0, 0)]) { 581 dirs.clear(); 582 if (cells.back()->y > 1) 583 dirs.emplace_back(up); 584 if (cells.back()->y < height - 2) 585 dirs.emplace_back(down); 586 if (cells.back()->x > 1) 587 dirs.emplace_back(left); 588 if (cells.back()->x < width - 2) 589 dirs.emplace_back(right); 590 switch (dirs[std::rand() % dirs.size()]) { 591 case up: 592 nextCell = &grid[IndexOffset(0, -2)]; 593 break; 594 case down: 595 nextCell = &grid[IndexOffset(0, 2)]; 596 break; 597 case left: 598 nextCell = &grid[IndexOffset(-2, 0)]; 599 break; 600 case right: 601 nextCell = &grid[IndexOffset(2, 0)]; 602 break; 603 } 604 605 // looping through the cells in the random walk 606 // to test if a loop has been created and erase it 607 attron(COLOR_PAIR(white)); 608 for (int i = cells.size() - 1; i >= 0; i--) { 609 if (cells[i] == nextCell) { 610 while (cells.back() != nextCell) { 611 Draw(cells.back()); 612 prevCell = cells.back(); 613 cells.pop_back(); 614 wall = cells.back() + (prevCell - cells.back()) / 2; 615 Draw(wall); 616 } 617 goto self_collision; 618 } 619 } 620 attroff(COLOR_PAIR(white)); 621 622 // if no loop was detected committing the new cell to the 623 // walk 624 wall = cells.back() + (nextCell - cells.back()) / 2; 625 Draw(nextCell); 626 Draw(wall); 627 cells.emplace_back(nextCell); 628 self_collision: 629 if (s::render_maze_gen) { 630 s::draw.lock(); 631 refresh(); 632 s::draw.unlock(); 633 cycle.WaitInterval(s::time_soft_maze_gen); 634 } 635 } 636 637 // committing the random walk to the maze 638 prevCell = cells[0]; 639 field[Index(prevCell)] = true; 640 for (int i = 1; i < cells.size(); ++i) { 641 wall = prevCell + (cells[i] - prevCell) / 2; 642 field[Index(wall)] = true; 643 field[Index(cells[i])] = true; 644 prevCell = cells[i]; 645 } 646 647 if (s::render_maze_gen) { 648 s::draw.lock(); 649 refresh(); 650 s::draw.unlock(); 651 cycle.WaitInterval(s::time_hard_maze_gen); 652 } 653 } 654 } 655 } 656 } 657 658 void maze_gen::RecursiveDivider(bool* field, const int& width, const int& height) 659 { 660 s::draw.lock(); 661 for (int y = 1; y < height - 1; ++y) { 662 for (int x = 1; x < width - 1; ++x) { 663 field[y * width + x] = true; 664 mvprintw(y, x * 2, " "); 665 } 666 } 667 refresh(); 668 s::draw.unlock(); 669 670 timer cycle; 671 672 std::function<void(vec2<int>&, vec2<int>&)> Divide = 673 [&](vec2<int>& top_left, vec2<int>& bottom_right) { 674 // base case 675 if (top_left.x >= bottom_right.x - 3 || top_left.y >= bottom_right.y - 3) 676 return; 677 678 int dx = bottom_right.x - top_left.x; 679 int dy = bottom_right.y - top_left.y; 680 681 if (std::rand() % dx > std::rand() % dy) { 682 // vertical split 683 dx -= 4; 684 // walls row 685 int wx; 686 if (dx < 2) { 687 wx = (top_left.x + bottom_right.x) / 2; 688 } else { 689 wx = top_left.x + (2 * (std::rand() % (dx / 2))) + 2; 690 } 691 dy -= 2; 692 // hole column 693 int hy = top_left.y + (2 * (std::rand() % (dy / 2))) + 1; 694 s::draw.lock(); 695 attron(COLOR_PAIR(white)); 696 for (int y = top_left.y + 1; y < bottom_right.y; y++) { 697 field[y * width + wx] = false; 698 mvprintw(y, wx * 2, " "); 699 } 700 attroff(COLOR_PAIR(white)); 701 attron(COLOR_PAIR(black)); 702 field[hy * width + wx] = true; 703 mvprintw(hy, wx * 2, " "); 704 attron(COLOR_PAIR(black)); 705 refresh(); 706 s::draw.unlock(); 707 cycle.WaitInterval(s::time_hard_maze_gen); 708 vec2<int> new_bottom_right(wx, bottom_right.y); 709 vec2<int> new_top_left(wx, top_left.y); 710 Divide(top_left, new_bottom_right); 711 Divide(new_top_left, bottom_right); 712 } else { 713 // horizontal split 714 dy -= 4; 715 // walls column 716 int wy; 717 if (dy < 2) { 718 wy = (top_left.y + bottom_right.y) / 2; 719 } else { 720 wy = top_left.y + (2 * (std::rand() % (dy / 2))) + 2; 721 } 722 dx -= 2; 723 // hole row 724 int hx = top_left.x + (2 * (std::rand() % (dx / 2))) + 1; 725 s::draw.lock(); 726 attron(COLOR_PAIR(white)); 727 for (int x = top_left.x + 1; x < bottom_right.x; x++) { 728 field[wy * width + x] = false; 729 mvprintw(wy, x * 2, " "); 730 } 731 attroff(COLOR_PAIR(white)); 732 attron(COLOR_PAIR(black)); 733 field[wy * width + hx] = true; 734 mvprintw(wy, hx * 2, " "); 735 attron(COLOR_PAIR(black)); 736 refresh(); 737 s::draw.unlock(); 738 cycle.WaitInterval(s::time_hard_maze_gen); 739 vec2<int> new_bottom_right(bottom_right.x, wy); 740 vec2<int> new_top_left(top_left.x, wy); 741 Divide(top_left, new_bottom_right); 742 Divide(new_top_left, bottom_right); 743 } 744 }; 745 746 vec2<int> tl(0, 0); 747 vec2<int> br(width, height); 748 Divide(tl, br); 749 } 750 751 void maze_gen::RecursiveDividerSet(bool* field, const int& width, const int& height) 752 { 753 struct cell { 754 vec2<int> pos; 755 bool isVisited = false; 756 char setName; 757 std::vector<cell*> neighbors; 758 // adds valid neighbors 759 void AddNeighbors( 760 cell* grid, 761 const int& width, 762 const int& height) 763 { 764 neighbors.clear(); 765 // up 766 if (pos.y > 2 && !grid[(pos.y - 2) * width + pos.x].isVisited) 767 neighbors.push_back(&grid[(pos.y - 2) * width + pos.x]); 768 // down 769 if (pos.y < height - 2 && !grid[(pos.y + 2) * width + pos.x].isVisited) 770 neighbors.push_back(&grid[(pos.y + 2) * width + pos.x]); 771 // left 772 if (pos.x > 2 && !grid[(pos.y * width) + pos.x - 2].isVisited) 773 neighbors.push_back(&grid[(pos.y * width) + pos.x - 2]); 774 // right 775 if (pos.x < width - 2 && !grid[(pos.y * width) + pos.x + 2].isVisited) 776 neighbors.push_back(&grid[(pos.y * width) + pos.x + 2]); 777 } 778 std::vector<cell*> GetNeighbors( 779 cell* grid, 780 const int& width, 781 const int& height) 782 { 783 std::vector<cell*> ns; 784 if (pos.x > 2) 785 ns.push_back(&grid[(pos.y * width) + pos.x - 2]); 786 if (pos.x < width - 2) 787 ns.push_back(&grid[(pos.y * width) + pos.x + 2]); 788 if (pos.y > 2) 789 ns.push_back(&grid[(pos.y - 2) * width + pos.x]); 790 if (pos.y < height - 2) 791 ns.push_back(&grid[(pos.y + 2) * width + pos.x]); 792 return ns; 793 } 794 }; 795 796 // gets rid of the walls inside the maze 797 s::draw.lock(); 798 attron(COLOR_PAIR(black)); 799 for (int y = 1; y < height - 1; ++y) { 800 for (int x = 1; x < width - 1; ++x) { 801 field[y * width + x] = true; 802 mvprintw(y, x * 2, " "); 803 } 804 } 805 // sets the corner squares to walls for consistent representation of maze 806 for (int y = 2; y < height - 2; y += 2) { 807 for (int x = 2; x < width - 2; x += 2) { 808 field[y * width + x] = false; 809 } 810 } 811 if (s::render_maze_gen) 812 refresh(); 813 attroff(COLOR_PAIR(black)); 814 s::draw.unlock(); 815 // initializes the grid 816 cell grid[width * height]; 817 for (int y = 0; y < height; ++y) { 818 for (int x = 0; x < width; ++x) { 819 grid[(y * width) + x].pos.x = x; 820 grid[(y * width) + x].pos.y = y; 821 } 822 } 823 // populates the globals set 824 std::vector<cell*> l; // l for local set 825 for (int y = 1; y < height; y += 2) { 826 for (int x = 1; x < width; x += 2) { 827 l.push_back(&grid[y * width + x]); 828 } 829 } 830 831 timer cycle; 832 833 std::function<void(std::vector<cell*>&)> 834 Divide = [&](std::vector<cell*>& l) { 835 // base case 836 if (l.size() < 4) 837 return; 838 839 // cleans the set from previous data 840 s::draw.lock(); 841 attron(COLOR_PAIR(purple)); 842 for (cell* c : l) { 843 c->setName = 'l'; 844 c->neighbors.clear(); 845 c->isVisited = false; 846 mvprintw(c->pos.y, c->pos.x * 2, " "); 847 } 848 attroff(COLOR_PAIR(purple)); 849 s::draw.unlock(); 850 851 // gets two random seeds for set a and b respectively 852 cell* seedA = l[std::rand() % l.size()]; 853 seedA->setName = 'a'; 854 cell* seedB; 855 do { 856 seedB = l[std::rand() % l.size()]; 857 } while (seedB == seedA); 858 seedB->setName = 'b'; 859 std::vector<cell*> o; // o stands for the open set 860 o.push_back(seedA); 861 o.push_back(seedB); 862 seedA->isVisited = true; 863 seedB->isVisited = true; 864 if (s::render_maze_gen) { 865 s::draw.lock(); 866 attron(COLOR_PAIR(red)); 867 mvprintw(seedA->pos.y, seedA->pos.x * 2, " "); 868 attroff(COLOR_PAIR(red)); 869 attron(COLOR_PAIR(blue)); 870 mvprintw(seedB->pos.y, seedB->pos.x * 2, " "); 871 attroff(COLOR_PAIR(blue)); 872 refresh(); 873 s::draw.unlock(); 874 } 875 876 // expands a and b until they cover the whole of the local set 877 int index; 878 cell* current; 879 while (!o.empty()) { 880 index = std::rand() % o.size(); 881 current = o[index]; 882 o.erase(o.begin() + index); 883 current->AddNeighbors(grid, width, height); 884 if (s::render_maze_gen) { 885 s::draw.lock(); 886 attron(COLOR_PAIR(red)); 887 if (current->setName == 'b') 888 attron(COLOR_PAIR(blue)); 889 mvprintw(current->pos.y, current->pos.x * 2, " "); 890 attroff(COLOR_PAIR(blue)); 891 attroff(COLOR_PAIR(red)); 892 refresh(); 893 s::draw.unlock(); 894 } 895 for (cell* c : current->neighbors) { 896 c->setName = current->setName; 897 o.push_back(c); 898 } 899 if (!current->isVisited && s::render_maze_gen) { 900 cycle.WaitInterval(s::time_soft_maze_gen); 901 } 902 current->isVisited = true; 903 } 904 905 // separates set a and b from the local set for further division 906 // and gets the boundary between set a and b 907 std::vector<cell*> a; 908 std::vector<cell*> b; 909 vec2<int>* midpoint; 910 std::vector<vec2<int>*> w; // wall 911 for (cell* c : l) { 912 if (c->setName == 'a') { 913 a.push_back(c); 914 } else { 915 b.push_back(c); 916 } 917 for (cell* n : c->GetNeighbors(grid, width, height)) { 918 // TODO see if you can avoid executing this twice 919 // i.e. c -> n wall and n -> c wall when n becomes c 920 if (c->setName != n->setName && c->setName != 's' && n->setName != 's') { 921 midpoint = &(c + (n - c) / 2)->pos; 922 w.push_back(midpoint); 923 // build a wall on the boundary 924 field[midpoint->y * width + midpoint->x] = false; 925 } 926 } 927 } 928 // draws the corners of the wall 929 s::draw.lock(); 930 attron(COLOR_PAIR(white)); 931 for (vec2<int>* mid : w) { 932 std::vector<cell*> wallCorners; 933 if (mid->y % 2 == 0) { // vertical wall | positions start from 0 934 if (mid->x > 1) 935 wallCorners.push_back(&grid[(mid->y * width) + mid->x - 1]); 936 if (mid->x < width - 1) 937 wallCorners.push_back(&grid[(mid->y * width) + mid->x + 1]); 938 } else { // horizontal wall 939 if (mid->y > 1) 940 wallCorners.push_back(&grid[(mid->y - 1) * width + mid->x]); 941 if (mid->y < height - 1) 942 wallCorners.push_back(&grid[(mid->y + 1) * width + mid->x]); 943 } 944 for (cell* c : wallCorners) { 945 int nNeighborWalls = 0; 946 if (!field[(c->pos.y - 1) * width + c->pos.x]) 947 ++nNeighborWalls; 948 if (!field[(c->pos.y + 1) * width + c->pos.x]) 949 ++nNeighborWalls; 950 if (!field[(c->pos.y * width) + c->pos.x - 1]) 951 ++nNeighborWalls; 952 if (!field[(c->pos.y * width) + c->pos.x + 1]) 953 ++nNeighborWalls; 954 if (nNeighborWalls > 1) { 955 mvprintw(c->pos.y, c->pos.x * 2, " "); 956 } 957 } 958 } 959 // draws the middle of the wall 960 for (vec2<int>* mid : w) { 961 mvprintw(mid->y, mid->x * 2, " "); 962 } 963 attroff(COLOR_PAIR(white)); 964 if (s::render_maze_gen) 965 refresh(); 966 s::draw.unlock(); 967 if (s::render_maze_gen) 968 cycle.WaitInterval(s::time_soft_maze_gen); 969 // punches a hole in the wall 970 midpoint = w[std::rand() % w.size()]; 971 field[midpoint->y * width + midpoint->x] = true; 972 973 s::draw.lock(); 974 attron(COLOR_PAIR(black)); 975 mvprintw(midpoint->y, midpoint->x * 2, " "); 976 attroff(COLOR_PAIR(black)); 977 if (s::render_maze_gen) 978 refresh(); 979 s::draw.unlock(); 980 if (s::render_maze_gen) 981 cycle.WaitInterval(s::time_hard_maze_gen); 982 983 // cleans up after a division is made 984 if (s::render_maze_gen) { 985 s::draw.lock(); 986 attron(COLOR_PAIR(black)); 987 for (cell* c : l) { 988 c->setName = 's'; 989 mvprintw(c->pos.y, c->pos.x * 2, " "); 990 } 991 attroff(COLOR_PAIR(black)); 992 refresh(); 993 s::draw.unlock(); 994 } else { 995 for (cell* c : l) { 996 c->setName = 's'; 997 } 998 } 999 1000 Divide(a); 1001 Divide(b); 1002 }; 1003 1004 Divide(l); 1005 1006 if (!s::render_maze_gen) { 1007 s::draw.lock(); 1008 refresh(); 1009 s::draw.unlock(); 1010 } 1011 } 1012 1013 void maze_gen::BinaryTree(bool* field, const int& width, const int& height) 1014 { 1015 std::vector<vec2<int>> neighbors; 1016 vec2<int>* selected; 1017 timer cycle; 1018 // goes through all positions 1019 for (int y = 1; y < height - 1; y += 2) { 1020 for (int x = 1; x < width - 1; x += 2) { 1021 // checks if neighbors are within bounds 1022 if (x < width - 3) 1023 neighbors.push_back(vec2<int>(x + 2, y)); 1024 if (y < height - 3) 1025 neighbors.push_back(vec2<int>(x, y + 2)); 1026 if (neighbors.empty()) 1027 continue; 1028 // chooses randomly between bottom and right neighbor and 1029 // carves the wall to it 1030 selected = &neighbors[std::rand() % neighbors.size()]; 1031 field[(y * width) + x] = true; 1032 field[((selected->y + y) * width / 2) + (selected->x + x) / 2] = true; 1033 s::draw.lock(); 1034 mvprintw(y, x * 2, " "); 1035 mvprintw(selected->y, selected->x * 2, " "); 1036 mvprintw((selected->y + y) / 2, (selected->x + x), " "); 1037 refresh(); 1038 s::draw.unlock(); 1039 cycle.WaitInterval(s::time_hard_maze_gen); 1040 neighbors.clear(); 1041 } 1042 } 1043 } 1044 1045 void maze_gen::Eller(bool* field, const int& width, const int& height) 1046 { 1047 struct cell { 1048 vec2<int> pos; 1049 int s = 0; 1050 }; 1051 1052 cell grid[width][height]; 1053 for (int y = 0; y < height; ++y) { 1054 for (int x = 0; x < width; ++x) { 1055 grid[x][y].pos.x = x; 1056 grid[x][y].pos.y = y; 1057 } 1058 } 1059 1060 std::vector<cell*> local_set; 1061 int last_set; 1062 int next_set = 1; 1063 timer cycle; 1064 1065 for (int y = 1; y < height - 1; y += 2) { 1066 // assigns sets to new cells and caries sets from previous row 1067 if (y == 1) { 1068 for (int x = 1; x < width - 1; x += 2) { 1069 grid[x][y].s = next_set; 1070 ++next_set; 1071 } 1072 } else { 1073 for (int x = 1; x < width - 1; x += 2) { 1074 if (field[(y - 1) * width + x]) { 1075 grid[x][y].s = grid[x][y - 2].s; 1076 } else { 1077 grid[x][y].s = next_set; 1078 ++next_set; 1079 } 1080 } 1081 } 1082 // randomly merges sets 1083 for (int x = 1; x < width - 1; x += 2) { 1084 // sets the field to path where it's guarantied to always be 1085 // a path (see documentation) 1086 field[(y * width) + x] = true; 1087 s::draw.lock(); 1088 mvprintw(y, x * 2, " "); 1089 refresh(); 1090 s::draw.unlock(); 1091 // randomly chooses to merge sets 1092 if (grid[x + 2][y].s != grid[x][y].s && std::rand() % 2 == 0 && x < width - 3) { 1093 grid[x + 2][y].s = grid[x][y].s; 1094 field[(y * width) + x + 1] = true; 1095 s::draw.lock(); 1096 mvprintw(y, (x + 1) * 2, " "); 1097 mvprintw(y, (x + 2) * 2, " "); 1098 refresh(); 1099 s::draw.unlock(); 1100 } 1101 cycle.WaitInterval(s::time_hard_maze_gen); 1102 } 1103 // places the down walls 1104 local_set.push_back(&grid[1][y]); 1105 last_set = grid[1][y].s; 1106 if (y < height - 3) { 1107 for (int x = 3; x < width - 1; x += 2) { 1108 if (grid[x][y].s != last_set || x > width - 2) { 1109 // encounters next set, drills one hole & clears set 1110 vec2<int>* pos = &local_set[std::rand() % local_set.size()]->pos; 1111 field[(pos->y + 1) * width + pos->x] = true; 1112 s::draw.lock(); 1113 mvprintw(pos->y + 1, pos->x * 2, " "); 1114 refresh(); 1115 s::draw.unlock(); 1116 local_set.clear(); 1117 local_set.push_back(&grid[x][y]); 1118 last_set = grid[x][y].s; 1119 cycle.WaitInterval(s::time_hard_maze_gen); 1120 } else { 1121 // expands local set 1122 local_set.push_back(&grid[x][y]); 1123 } 1124 } 1125 vec2<int>* pos = &local_set[std::rand() % local_set.size()]->pos; 1126 field[(pos->y + 1) * width + pos->x] = true; 1127 s::draw.lock(); 1128 mvprintw(pos->y + 1, pos->x * 2, " "); 1129 refresh(); 1130 s::draw.unlock(); 1131 local_set.clear(); 1132 } else { 1133 // preform final merge 1134 for (int x = 1; x < width - 1; x += 2) { 1135 if (grid[x + 2][y].s != grid[x][y].s && x < width - 3) { 1136 field[(y * width) + x + 1] = true; 1137 s::draw.lock(); 1138 mvprintw(y, (x + 1) * 2, " "); 1139 mvprintw(y, (x + 2) * 2, " "); 1140 refresh(); 1141 s::draw.unlock(); 1142 } 1143 cycle.WaitInterval(s::time_hard_maze_gen); 1144 } 1145 } 1146 } 1147 } 1148 1149 void maze_gen::Sidewinder(bool* field, const int& width, const int& height) 1150 { 1151 std::vector<vec2<int>> run_set; 1152 vec2<int>* selected; 1153 timer cycle; 1154 for (int y = 1; y < height - 1; y += 2) { 1155 run_set.push_back(vec2<int>(1, y)); 1156 for (int x = 1; x < width - 1; x += 2) { 1157 // sets the field to path where it's guarantied to always be 1158 // a path (see documentation) 1159 field[(y * width) + x] = true; 1160 s::draw.lock(); 1161 mvprintw(y, x * 2, " "); 1162 s::draw.unlock(); 1163 // randomly chooses to carve up or right 1164 // safeguards for the top row \/ \/ 1165 if ((std::rand() % 2 == 0 || x == width - 2) && (y > 1)) { 1166 // carve the up wall from random position in the run set 1167 if (run_set.empty()) 1168 run_set.push_back(vec2<int>(x, y)); 1169 selected = &run_set[std::rand() % run_set.size()]; 1170 field[((selected->y - 1) * width) + selected->x] = true; 1171 s::draw.lock(); 1172 mvprintw(selected->y - 1, selected->x * 2, " "); 1173 mvprintw(selected->y - 2, selected->x * 2, " "); 1174 refresh(); 1175 s::draw.unlock(); 1176 // clears the run set 1177 run_set.clear(); 1178 cycle.WaitInterval(s::time_hard_maze_gen); 1179 } else if (x < width - 3) { 1180 // adds this position if previously carved up 1181 if (run_set.empty()) 1182 run_set.push_back(vec2<int>(x, y)); 1183 // adds right neighbor to the run set 1184 run_set.push_back(vec2<int>(x + 2, y)); 1185 // carves the right wall 1186 field[(y * width) + x + 1] = true; 1187 s::draw.lock(); 1188 mvprintw(y, (x + 1) * 2, " "); 1189 mvprintw(y, (x + 2) * 2, " "); 1190 refresh(); 1191 s::draw.unlock(); 1192 cycle.WaitInterval(s::time_hard_maze_gen); 1193 } 1194 } 1195 if (!run_set.empty() && y > 1) { 1196 // carve the up wall from random position in the run set 1197 selected = &run_set[std::rand() % run_set.size()]; 1198 field[((selected->y - 1) * width) + selected->x] = true; 1199 s::draw.lock(); 1200 mvprintw(selected->y - 1, selected->x * 2, " "); 1201 mvprintw(selected->y - 2, selected->x * 2, " "); 1202 refresh(); 1203 s::draw.unlock(); 1204 cycle.WaitInterval(s::time_hard_maze_gen); 1205 } 1206 run_set.clear(); 1207 } 1208 } 1209 1210 std::map<std::string, 1211 void (*)( 1212 bool* field, 1213 const int& width, 1214 const int& height)> 1215 generators = { 1216 { "Backtracker", maze_gen::Backtracker }, 1217 { "Kruskal", maze_gen::Kruskal }, 1218 { "Prim random edges", maze_gen::PrimRandom }, 1219 { "Prim random weights", maze_gen::PrimWeighted }, 1220 { "Growing tree", maze_gen::GrowingTree }, 1221 { "Wilson", maze_gen::Wilson }, 1222 { "Recursive divider", maze_gen::RecursiveDivider }, 1223 { "Recursive divider (set based)", maze_gen::RecursiveDividerSet }, 1224 { "Binary tree", maze_gen::BinaryTree }, 1225 { "Eller", maze_gen::Eller }, 1226 { "Sidewinder", maze_gen::Sidewinder }, 1227 }; 1228