huc::maze::RecursiveDivisionGenerator Class Reference

#include <recursive_division_generator.hxx>

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

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 void	Compute (std::mt19937 &mt, Maze &maze, const Point &origin, const uint32_t width, uint32_t height)

Detailed Description

Recursive Division Generator - Generate a maze using a recursive division strategy.

Recursive Division Maze Generator is the fastest algorithm without directional biases. While Recursive division really stands out with respect to parallelism, this algorithm is particularly fascinating because of its fractal nature: you could theoretically continue the process indefinitely at finer and finer levels of detail (smaller and smaller scales).

This algorithm is somewhat similar to recursive backtracking, since they're both stack based, except this focuses on walls instead of passages. As a Wall Builders generator, the process begins with a large empty space (all cells are connected), and adds walls (disconnect cells) until a maze results.

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 50 of file recursive_division_generator.hxx.

Member Typedef Documentation

typedef Maze::Cell huc::maze::RecursiveDivisionGenerator::Cell

Definition at line 54 of file recursive_division_generator.hxx.

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

Definition at line 53 of file recursive_division_generator.hxx.

typedef Maze::Point huc::maze::RecursiveDivisionGenerator::Point

Definition at line 55 of file recursive_division_generator.hxx.

Member Function Documentation

static void huc::maze::RecursiveDivisionGenerator::Compute ( std::mt19937 &  mt, Maze &  maze, const Point &  origin, const uint32_t  width, uint32_t  height  )

inlinestaticprivate

Definition at line 72 of file recursive_division_generator.hxx.

      {
        if (width < 2 || height < 2)
          return;

        // Build a wall within the room, whether vertical or horizontal,
        // Open a gate at a random position
        bool isHorizontalCut = (mt() % 2 == 0) ? true : false; //(width <= height);
        uint32_t wallIdx = (isHorizontalCut) ? mt() % (height - 1) : mt() % (width - 1);
        uint32_t pathIdx = (isHorizontalCut) ? mt() % width : mt() % height;

        // Build wall and Recurse on sub areas (Top and Bottom)
        if (isHorizontalCut)
        {
          maze.DisconnectRow(origin, wallIdx, width, pathIdx);
          Compute(mt, maze, origin, width, wallIdx + 1);
          Compute(mt, maze, Point(origin.x, origin.y + wallIdx + 1),  width, height - wallIdx - 1);
        }
        // Recurse on sub areas (Left and Right)
        else
        {
          maze.DisconnectCol(origin, wallIdx, height, pathIdx);
          Compute(mt, maze, origin, wallIdx + 1, height);
          Compute(mt, maze, Point(origin.x + wallIdx + 1, origin.y),  width - wallIdx - 1, height);
        }
      }

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

inline

Definition at line 57 of file recursive_division_generator.hxx.

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

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

        Compute(mt, *maze, Point(0,0), width, height);

        return maze;
      }

---

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

• recursive_division_generator.hxx