huc::maze::BinaryTreeGenerator Class Reference

#include <binary_tree_generator.hxx>

Public Types

typedef Grid< CellInfoBaseMaze
typedef Maze::Cell Cell

Public Member Functions

std::unique_ptr< Mazeoperator() (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.

widthdesired width for the maze.
heightdesired height for the maze.
seednumber used to initiate the random generator.
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

Member Function Documentation

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

GetNeighbours - Retrieve available neighbours

mazeGrid within the search occurs
cellCell of which neighbours will be found.
vector of the available top and left neighbours, empty vector if none.

Definition at line 89 of file binary_tree_generator.hxx.

90  {
91  std::vector<std::shared_ptr<Cell>> neighbours;
93  const auto x = cell.x;
94  const auto y = cell.y;
96  if (x > 0) neighbours.push_back(maze[x-1][y]); // West Direction - Push left if available
97  if (y > 0) neighbours.push_back(maze[x][y-1]); // North Direction - Push top if available
99  return neighbours;
100  }
std::unique_ptr<Maze> huc::maze::BinaryTreeGenerator::operator() ( const uint32_t  width,
const uint32_t  height,
const uint32_t  seed = 0 

Definition at line 53 of file binary_tree_generator.hxx.

54  {
55  if (width < 1 || height < 1)
56  return nullptr;
58  auto maze(std::unique_ptr<Maze>(new Maze(width, height)));
59  std::mt19937 mt(seed); // Initialize random generator based on Mersenne Twister algorithm
61  // For each existing cell in the grid, randomly carve a passage either east or south
62  for (uint32_t y = 0; y < height; ++y)
63  {
64  for (uint32_t x = 0; x < width; ++x)
65  {
66  // Get available neighbours
67  auto cell = (*maze)[x][y];
68  auto curNeighbours = GetNeighbours(*maze, *cell.get());
70  if (curNeighbours.empty())
71  continue;
73  // Randomly select a node to be processed
74  auto randIdx = mt() % curNeighbours.size();
75  maze->Connect(cell, curNeighbours[randIdx]);
76  }
77  }
79  return maze;
80  }
static std::vector< std::shared_ptr< Cell > > GetNeighbours(const Maze &maze, const Cell &cell)

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