huc::maze::SidewinderGenerator Class Reference

#include <sidewinder_generator.hxx>

Public Types
typedef Grid< CellInfoBase >	Maze
typedef Maze::Cell	Cell

Public Member Functions
std::unique_ptr< Maze >	operator() (const uint32_t width, const uint32_t height, const uint32_t seed=0)

Detailed Description

Sidewinder Generator - Generate a maze using a sidewinder strategy.

Sidewinder Maze Generator is very similar to the Binary Tree algorithm, and only slightly more complicated. Furthermore, the Sidewinder algorithm only needs to consider the current row, and therefore can be used to generate infinitely large mazes (like the Binary Tree).

While binary tree mazes have two of its four sides being one long passage, a Sidewinder mazes have just one long passage.

Parameters

width	desired width for the maze.
height	desired height for the maze.
seed	number used to initiate the random generator.

Returns

Operator() returns Maze Grid pointer to be owned, nullptr if construction failed.

Definition at line 47 of file sidewinder_generator.hxx.

Member Typedef Documentation

typedef Maze::Cell huc::maze::SidewinderGenerator::Cell

Definition at line 51 of file sidewinder_generator.hxx.

typedef Grid<CellInfoBase> huc::maze::SidewinderGenerator::Maze

Definition at line 50 of file sidewinder_generator.hxx.

Member Function Documentation

std::unique_ptr<Maze> huc::maze::SidewinderGenerator::operator() ( const uint32_t  width, const uint32_t  height, const uint32_t  seed = 0  )

inline

Definition at line 53 of file sidewinder_generator.hxx.

      {
        if (width < 1 || height < 1)
          return nullptr;

        auto maze(std::unique_ptr<Maze>(new Maze(width, height)));
        std::mt19937 mt(seed);                   // Random generator based on Mersenne Twister algorithm
        std::set<std::shared_ptr<Cell>> runSet;  // Keep track of possible paths to expand

        // Initialize an empty “run” set to keep track of the current line path.
        // Scan grid line by line starting with the cell[0,0]:
        for (uint32_t y = 0; y < height; ++y)
        {
          for (uint32_t x = 0; x < width; ++x)
          {
            // Add current cell to the path (avoid useless insertion)
            if (y > 0)
              runSet.insert((*maze)[x][y]);

            // Randomly carve to east or north
            // If a passage was carved, continue line scan.
            // First row can only be a single passage, crave it to the east
            if (x + 1 < width && (mt() % 2 == 0 || y == 0))
            {
              maze->Connect((*maze)[x][y], (*maze)[x+1][y]);
            }
            // Otherwise randomly choose a cell in the run set and carve north
            else if (y > 0)
            {
              auto cellIt = runSet.begin();
              std::advance(cellIt, mt() % runSet.size());

              maze->Connect(*cellIt, (*maze)[(*cellIt)->x][(*cellIt)->y - 1]);
              runSet.clear(); // Empty the run set and continue line scan
            }
          }

          runSet.clear();
        }

        return maze;
      }

---

The documentation for this class was generated from the following file:

• sidewinder_generator.hxx