huc::maze::PrimsGenerator Class Reference

#include <prims_generator.hxx>

Classes
struct	CellInfo

Public Types
typedef Grid< CellInfo >	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 Point &startPoint=Point(0, 0), const uint32_t seed=0)

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

Detailed Description

Prim's Generator - Generate a maze using a Depth First Search (Prims) strategy.

Prim's Maze Generator is a randomized version of Prim's algorithm: a method for producing a minimal spanning tree for a undirected weighted graph.

Prim's algorithm creates a tree by getting the adjacent cells and finding the best one to travel to next. To Generate mazes using Prim's, we will instead take a random cell to travel to the next one.

Although the classical Prim's algorithm keeps a list of edges, here is studied the modified version for our maze generation by maintaining a list of adjacent cells. Running faster, it still requires storage proportional to the size of the Maze.

Parameters

width	desired width for the maze.
height	desired height for the maze.
startPoint	possible point to start the algorithm, {x: 0, y: 0} by default.
seed	number used to initiate the random generator, 0 by default.

Returns

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

Definition at line 52 of file prims_generator.hxx.

Member Typedef Documentation

typedef Maze::Cell huc::maze::PrimsGenerator::Cell

Definition at line 59 of file prims_generator.hxx.

typedef Grid<CellInfo> huc::maze::PrimsGenerator::Maze

Definition at line 58 of file prims_generator.hxx.

typedef Maze::Point huc::maze::PrimsGenerator::Point

Definition at line 60 of file prims_generator.hxx.

Member Function Documentation

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

inlinestatic

GetNeighbours - Retrieve available neighbours

Parameters

maze	Grid within the search occurs
cell	Cell of which neighbours will be found.
visited	select whether or (and only or) not cells that are visited

Returns

vector of neighbours, empty vector if none.

Definition at line 107 of file prims_generator.hxx.

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

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

        // Push left if available
        if (static_cast<int>(x - 1) >= 0 &&
            ((visited) ? maze[x-1][y]->info.isVisited : !maze[x-1][y]->info.isVisited))
          neighbour.push_back(maze[x-1][y]);
        // Push bottom if available
        if (static_cast<int>(y - 1) >= 0 &&
            ((visited) ? maze[x][y-1]->info.isVisited : !maze[x][y-1]->info.isVisited))
          neighbour.push_back(maze[x][y-1]);
        // Push top if available
        if (x + 1 < maze.Width() &&
            ((visited) ? maze[x+1][y]->info.isVisited : !maze[x+1][y]->info.isVisited))
          neighbour.push_back(maze[x+1][y]);
        // Push right if available
        if (y + 1 < maze.Height() &&
            ((visited) ? maze[x][y+1]->info.isVisited : !maze[x][y+1]->info.isVisited))
          neighbour.push_back(maze[x][y+1]);

        return neighbour;
      }

std::unique_ptr<Maze> huc::maze::PrimsGenerator::operator() ( const uint32_t  width, const uint32_t  height, const Point &  startPoint = Point(0,0), const uint32_t  seed = 0  )

inline

Definition at line 62 of file prims_generator.hxx.

      {
        if (width < 1 || height < 1 || startPoint.x >= width || startPoint.y >= height)
          return nullptr;

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

        // While there is cell within the set:
        (*maze)[startPoint.x][startPoint.y]->info.rootDistance = 0;
        pathSet.insert((*maze)[startPoint.x][startPoint.y]);
        while (!pathSet.empty())
        {
          auto cellIt = pathSet.begin();
          std::advance(cellIt, mt() % pathSet.size());
          (*cellIt)->info.isVisited = true;

          // Randomly connect it to a cell that is already part of the mze
          auto neighbours = GetNeighbours(*maze, *(*cellIt).get(), true);
          if (!neighbours.empty())
          {
            auto randIdx = mt() % neighbours.size();
            (*cellIt)->info.rootDistance = neighbours[randIdx]->info.rootDistance + 1;
            maze->Connect(*cellIt, neighbours[randIdx]);
          }

          // Add available neighbours and remove current cell
          neighbours = GetNeighbours(*maze, *(*cellIt).get(), false);
          pathSet.insert(neighbours.begin(), neighbours.end());
          pathSet.erase(cellIt);
        }

        return maze;
      }

---

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

• prims_generator.hxx