Random Maze Generator

0-example.txt

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| S             |               |   |                       |
+   +---+   +---+---+   +---+---+   +---+   +   +---+   +---+
|       |           |   |   |               |   |       |   |
+   +---+   +   +---+   +   +---+   +---+---+---+---+   +   +
|   |   |   |       |               |   |   |   |   |       |
+   +   +---+   +---+---+---+   +---+   +   +   +   +---+   +
|       |   |           |       |                       |   |
+---+   +   +---+   +---+   +   +---+   +---+   +   +---+   +
|               |       |   |   |       |   |   |       |   |
+---+---+   +---+   +---+---+   +---+   +   +---+   +---+   +
|   |   |       |           |   |               |           |
+   +   +   +---+   +   +---+---+   +---+   +---+   +   +   +
|               |   |           |   |       |   |   |   |   |
+   +---+   +---+---+   +   +---+---+---+   +   +---+---+   +
|       |   |       |   |       |   |   |           |       |
+   +---+---+---+   +---+   +---+   +   +---+   +---+---+   +
|       |                                   |       |       |
+   +---+---+   +   +   +   +   +   +   +---+   +---+   +   +
|       |       |   |   |   |   |   |               |   | D |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

1-example.txt

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| S             |   |   |                   |   |                   |       |
+   +---+   +---+   +   +   +---+   +   +---+   +   +---+   +   +---+---+   +
|   |   |   |               |   |   |                   |   |           |   |
+   +   +---+---+   +---+   +   +---+---+---+---+---+---+---+   +   +---+   +
|       |           |           |   |   |   |   |   |       |   |           |
+---+   +---+   +   +---+---+   +   +   +   +   +   +---+   +---+   +   +---+
|   |   |       |   |   |                           |   |           |       |
+   +   +---+   +---+   +---+   +   +   +   +---+   +   +---+   +---+---+---+
|       |           |   |   |   |   |   |   |               |   |   |   |   |
+   +---+---+   +---+   +   +---+---+---+---+---+---+   +---+---+   +   +   +
|       |           |               |           |       |   |               |
+   +---+---+   +---+   +---+   +---+   +---+---+---+   +   +---+   +---+   +
|   |               |       |           |   |   |   |               |   |   |
+   +---+   +   +---+   +---+   +   +---+   +   +   +---+---+---+---+   +   +
|   |       |   |           |   |   |   |               |   |   |   |       |
+   +---+   +---+   +---+---+   +---+   +   +---+   +---+   +   +   +   +---+
|               |       |       |   |           |                           |
+   +   +   +---+   +---+   +---+   +   +---+---+   +   +   +   +   +   +---+
|   |   |   |   |       |   |               |   |   |   |   |   |   |       |
+   +---+---+   +   +---+   +---+   +---+---+   +---+---+---+---+---+   +---+
|       |   |           |   |           |   |   |           |               |
+   +---+   +---+   +---+   +---+   +---+   +   +   +---+---+---+   +   +---+
|               |       |   |   |       |           |   |           |   |   |
+   +   +   +---+   +---+---+   +   +---+   +---+---+   +---+   +   +---+   +
|   |   |       |       |   |           |       |               |   |   |   |
+---+---+   +---+   +---+   +   +---+---+   +---+---+   +   +   +---+   +   +
|                   |   |           |           |       |   |   |           |
+   +---+---+---+---+   +   +---+---+   +---+---+---+   +---+---+---+---+   +
|   |   |   |   |   |           |       |   |   |                   |   |   |
+---+   +   +   +   +   +---+---+---+   +   +   +---+   +   +   +---+   +   +
|   |                       |                       |   |   |       |       |
+   +   +---+   +   +   +---+---+   +   +   +---+   +---+---+   +---+   +---+
|           |   |   |   |   |       |   |   |           |                   |
+   +---+---+---+---+---+   +---+   +---+---+---+---+   +---+   +   +   +   +
|       |                   |                   |           |   |   |   |   |
+   +---+---+   +   +---+   +---+   +   +   +---+---+   +---+---+---+---+   +
|       |       |   |   |       |   |   |       |   |               |       |
+   +---+   +   +---+   +   +---+---+---+   +---+   +   +---+   +---+---+   +
|       |   |   |               |           |               |       |       |
+   +---+---+   +---+   +---+   +---+   +   +---+   +---+---+   +   +---+   +
|   |   |   |   |       |   |   |       |   |       |   |       |   |       |
+   +   +   +---+---+   +   +---+---+   +---+---+   +   +---+---+   +---+   +
|               |               |           |           |   |   |   |       |
+---+---+   +---+   +---+   +---+---+   +---+---+---+   +   +   +---+---+   +
|   |   |       |   |       |                   |               |           |
+   +   +   +---+   +---+   +---+   +   +   +---+---+   +---+   +---+   +   +
|               |   |               |   |           |   |               | D |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

main.cpp

#include <exception>
#include <iostream>
#include <string>
#include <unistd.h>

#include "maze.h"

using std::cout;
using std::invalid_argument;
using std::stoi;

void
print_usage(const char *program_name) {
  printf("\n");
  printf("usage: %s %s %s\n\n", program_name, "<num_rows>", "<num_cols>");
  printf("Options:\n");
  printf("  -h  show this help message and exit\n\n");
}

int
main(int argc, char **argv) {
  // parsing command line options
  int c_i;
  while ((c_i = getopt(argc, argv, "h")) != -1) {
    switch (c_i) {
      case 'h':
      case '?':
      default:
        print_usage(argv[0]);
        return 0;
    }
  }

  // parse non-option arguments; two expected
  if (optind + 2 != argc) {
    print_usage(argv[0]);
    return -1;
  }

  const int rows = stoi(argv[optind]);
  const int cols = stoi(argv[++optind]);

  if (rows < 1 || cols < 1) {
    printf("Error: the number of rows and columns must be greater than 0.\n");
    return -1;
  }

  try {
    // heavy lifting done by RandomMaze
    RandomMaze maze(rows, cols);

    // output maze to stdout
    cout << maze;

  } catch (const invalid_argument& e) {
    cout << "Error: " << e.what() << "\n";
    return -1;
  }

  return 0;
}

Makefile

TARGET := maze_gen
CXX_FLAGS += -std=c++11 -Wall


.PHONY: all
all: $(TARGET)


.PHONY: clean
clean:
	rm -f $(TARGET)
	rm -f *.o


maze.o: maze.cpp maze.h
	$(CXX) $(CXX_FLAGS) -c $< -o $@


main.o: main.cpp
	$(CXX) $(CXX_FLAGS) -c $< -o $@


$(TARGET): main.o maze.o
	$(CXX) $^ -o $(TARGET)

maze.cpp

#include "maze.h"

#include <algorithm>
#include <array>
#include <exception>
#include <chrono>
#include <iostream>
#include <random>
#include <set>
#include <string>
#include <vector>

using std::array;
using std::chrono::system_clock;
using std::default_random_engine;
using std::invalid_argument;
using std::ostream;
using std::set;
using std::shuffle;
using std::string;
using std::vector;


// -- construction --

RandomMaze::RandomMaze(unsigned int rows, unsigned int cols)
: rows_(rows), cols_(cols) {

  // initialize random number generator
  unsigned seed = system_clock::now().time_since_epoch().count();
  prg_ = default_random_engine(seed);

  // ensure rows and cols are both greater than 0
  if (rows == 0 || cols == 0) {
    string msg = "the number of rows and columns must be greater than zero.";
    throw invalid_argument(msg);
  }

  // allocate a contiguous region of memory to efficiently
  // contain all cells of a two-dimensional array
  cell_t *cells = new cell_t[rows * cols];

  matrix_ = new cell_t*[rows];
  for (int ix = 0; ix < rows; ++ix) {
    matrix_[ix] = &cells[ix * cols];
  }

  for (int ix = 0; ix < rows; ++ix) {
    for (int jx = 0; jx < cols; ++jx) {
      matrix_[ix][jx].row = ix;
      matrix_[ix][jx].col = jx;
    }
  }

  // set start and destination cells
  matrix_[rows_ - 1][0].cell_flags |= START_CELL;
  matrix_[0][cols_ - 1].cell_flags |= DEST_CELL;

  generate_maze();
}


RandomMaze::~RandomMaze() {
  delete[] matrix_[0]; // deallocating single contiguous block of cells
  delete[] matrix_;    // deallocating array of pointers to matrix rows
}


// -- public interface --

ostream&
operator<<(ostream& out, const RandomMaze& maze) {
  for (int row = maze.rows_ - 1; row >= 0; --row) {
    maze.output_row(out, row);
  }

  return out;
}


// -- private interface --

// maze generation

void
RandomMaze::generate_maze() {
  vector<cell_t*> cell_stack;
  cell_stack.push_back(&matrix_[0][0]);

  while (cell_stack.size() > 0) {
    cell_t *curr_cell = cell_stack.back();
    cell_stack.pop_back();

    auto neighbors = cell_neighbors(curr_cell->row, curr_cell->col);
    shuffle(neighbors.begin(), neighbors.end(), prg_);

    for (cell_t *neighbor : neighbors) {
      if (neighbor && cells_seen_.find(neighbor) == cells_seen_.end()) {
        // cell is unseen so far
        disable_wall(curr_cell, neighbor);
        cells_seen_.insert(neighbor);
        cell_stack.push_back(neighbor);
      }
    }
  }
}


int
RandomMaze::disable_wall(cell_t *cell_a, cell_t *cell_b) {
  if (cell_a == cell_b) {
    return -1; // error
  }

  if (cell_a->row == cell_b->row - 1 && cell_a->col == cell_b->col) {
    // cell_b is north of cell_a; disable cell_b's south wall
    cell_b->cell_flags &= ~SOUTH_WALL;

  } else if (cell_a->row == cell_b->row && cell_a->col == cell_b->col - 1) {
    // cell_b is east of cell_a; disable cell_a's east wall
    cell_a->cell_flags &= ~EAST_WALL;

  } else if (cell_a->row == cell_b->row + 1 && cell_a->col == cell_b->col) {
    // cell_b is south of cell_a; disable cell_a's south wall
    cell_a->cell_flags &= ~SOUTH_WALL;

  } else if (cell_a->row == cell_b->row && cell_a->col == cell_b->col + 1) {
    // cell_b is west of cell_a; disable cell_b's east wall
    cell_b->cell_flags &= ~EAST_WALL;

  } else {
    return -1; // error; cells are not neighboring each other
  }

  return 0;
}


array<RandomMaze::cell_t*,4>
RandomMaze::cell_neighbors(int row, int col) const {
  cell_t *N = is_within_bounds(row + 1, col) ? &matrix_[row + 1][col] : NULL;
  cell_t *E = is_within_bounds(row, col + 1) ? &matrix_[row][col + 1] : NULL;
  cell_t *S = is_within_bounds(row - 1, col) ? &matrix_[row - 1][col] : NULL;
  cell_t *W = is_within_bounds(row, col - 1) ? &matrix_[row][col - 1] : NULL;

  return {{ N, E, S, W }};
}


bool
RandomMaze::is_within_bounds(int row, int col) const {
  if (row < 0 || row >= rows_) {
    return false;
  }

  if (col < 0 || col >= cols_) {
    return false;
  }

  return true;
}



// input/output

ostream&
RandomMaze::output_row(ostream& out, int row) const {
  // north wall
  if (row + 1 == rows_) {
    for (int col = 0; col < cols_; ++col) {
      out << "+---";
    }

    out << "+\n";
  }

  // west wall
  out << "|";

  for (int col = 0; col < cols_; ++col) {
    const cell_t *cell = &matrix_[row][col];

    // cell contents
    if (cell->cell_flags & START_CELL) {
      out << " S ";
    } else if (cell->cell_flags & DEST_CELL) {
      out << " D ";
    } else {
      out << "   ";
    }

    // east wall
    string wall = (cell->cell_flags & EAST_WALL) ? "|" : " ";
    out << wall;
  }

  out << "\n";
  out << "+";

  // south wall
  for (int col = 0; col < cols_; ++col) {
    string wall = (matrix_[row][col].cell_flags & SOUTH_WALL) ? "---+" : "   +";
    out << wall;
  }

  out << "\n";

  return out;
}

maze.h

#ifndef __MAZE_H__
#define __MAZE_H__

#include <array>
#include <iostream>
#include <random>
#include <set>

using std::array;
using std::default_random_engine;
using std::ostream;
using std::set;
using std::vector;


class RandomMaze {
public:

  RandomMaze(unsigned int rows, unsigned int cols);

  // stream operator used to output the maze's ASCII representation
  friend ostream& operator<<(ostream &out, const RandomMaze& maze);

  ~RandomMaze();


private:

  // -- matrix cell definition --

  // Bitmasks to control a cell's flags;
  // Walls: only East and South status flags are necessary;
  // The status of a cell's N/W walls is defined by
  // the E/S walls of neighboring cells.
  enum { EAST_WALL = 0x1, SOUTH_WALL = 0x2, START_CELL = 0x4, DEST_CELL = 0x8 };

  struct cell_t {
    cell_t() : cell_flags(EAST_WALL|SOUTH_WALL) {}
    unsigned int row;
    unsigned int col;
    uint8_t cell_flags;
  };


  // -- private member functions --

  // maze generation

  void generate_maze();
  int disable_wall(cell_t *cell_a, cell_t *cell_b);

  array<cell_t*,4> cell_neighbors(int row, int col) const;
  bool is_within_bounds(int row, int col) const;

  // input/output

  ostream& output_row(ostream& out, int row) const;


  // -- data members --

  const unsigned int rows_;
  const unsigned int cols_;

  cell_t **matrix_; // two dimensional array
  set<cell_t*> cells_seen_; // cells visited during depth-first search
  default_random_engine prg_; // pseudo-random number generator


  // -- operations disallowed --
  RandomMaze(const RandomMaze&); // copy constructor
  void operator=(const RandomMaze&); //assignment operator
};

#endif