huc::maze::BinaryTreeGenerator Class Reference

#include <binary_tree_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)

Static Private Member Functions
static std::vector< std::shared_ptr< Cell > >	GetNeighbours (const Maze &maze, const Cell &cell)

Detailed Description

Binary Tree Generator - Generate a maze using a binary tree strategy.

Binary Tree Maze Generator is one of the very rareful algorithms with the ability to generate a perfect maze without keeping any state at all: it is a true memoryless Maze generation algorithm with no limit to the size of Maze you can create. It can build the entire maze by looking at each cell independantly. This is basically the simplest and fastest algorithm possible.

Mazes generated are real Binary Tree Data Structure, while having a very biased texture.

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 binary_tree_generator.hxx.

Member Typedef Documentation

typedef Maze::Cell huc::maze::BinaryTreeGenerator::Cell

Definition at line 51 of file binary_tree_generator.hxx.

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

Definition at line 50 of file binary_tree_generator.hxx.

Member Function Documentation

static std::vector<std::shared_ptr<Cell> > huc::maze::BinaryTreeGenerator::GetNeighbours ( const Maze &  maze, const Cell &  cell  )

inlinestaticprivate

GetNeighbours - Retrieve available neighbours

Parameters

maze	Grid within the search occurs
cell	Cell of which neighbours will be found.

Returns

vector of the available top and left neighbours, empty vector if none.

Definition at line 89 of file binary_tree_generator.hxx.

      {
        std::vector<std::shared_ptr<Cell>> neighbours;

        const auto x = cell.x;
        const auto y = cell.y;

        if (x > 0) neighbours.push_back(maze[x-1][y]);  // West Direction - Push left if available
        if (y > 0) neighbours.push_back(maze[x][y-1]);  // North Direction - Push top if available

        return neighbours;
       }

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

inline

Definition at line 53 of file binary_tree_generator.hxx.

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

        auto maze(std::unique_ptr<Maze>(new Maze(width, height)));
        std::mt19937 mt(seed); // Initialize random generator based on Mersenne Twister algorithm

        // For each existing cell in the grid, randomly carve a passage either east or south
        for (uint32_t y = 0; y < height; ++y)
        {
          for (uint32_t x = 0; x < width; ++x)
          {
            // Get available neighbours
            auto cell = (*maze)[x][y];
            auto curNeighbours = GetNeighbours(*maze, *cell.get());

            if (curNeighbours.empty())
              continue;

            // Randomly select a node to be processed
            auto randIdx = mt() % curNeighbours.size();
            maze->Connect(cell, curNeighbours[randIdx]);
          }
        }

        return maze;
      }

---

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

• binary_tree_generator.hxx