Code:
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <ostream>
#include <stdexcept>
#include <vector>
#define PATH_CELL ' '
#define WALL_CELL 'x'
#define BOUNDARY_CELL '0'
struct Cell
{
// coordinates (row, col) denotes the position at grid[row][col],
// i.e., (0, 0) is the top left cell
size_t row;
size_t col;
Cell(size_t row, size_t col) : row(row), col(col) {}
};
class Maze
{
public:
friend std::ostream& operator<<(std::ostream& out, const Maze& maze);
Maze(size_t num_rows, size_t num_cols) : grid(num_rows, std::vector<char>(num_cols, WALL_CELL))
{
if (num_rows < 1)
{
throw std::domain_error("The maze must have at least one row.");
}
if (num_cols < 1)
{
throw std::domain_error("The maze must have at least one column.");
}
grid[0][0] = PATH_CELL;
}
void generate_path();
void clear_path()
{
using std::vector;
vector<vector<char>>(grid.size(), vector<char>(grid[0].size(), WALL_CELL)).swap(grid);
grid[0][0] = PATH_CELL;
}
private:
std::vector<std::vector<char>> grid;
typedef decltype(grid.size()) size_type;
size_type row_last_index() const
{
return grid.size() - 1;
}
size_type col_last_index() const
{
return grid[0].size() - 1;
}
bool generate_complete_path();
Cell find_dead_end_path_start() const;
void generate_dead_end_path();
std::vector<Cell> generate_candidate_cells(const Cell& current_cell) const;
void filter_candidate_cells(const Cell& current_cell,
std::vector<Cell>& candidate_cells) const;
};
void Maze::generate_path()
{
const size_type max_tries = grid.size() * grid[0].size();
size_type tries = 0;
while (tries <= max_tries && !generate_complete_path())
{
clear_path();
++tries;
}
if (tries > max_tries)
{
throw std::runtime_error("Maximum number of tries to generate path exceeded.");
}
for (size_type i = 0; i < max_tries / 2; ++i)
{
generate_dead_end_path();
}
}
bool Maze::generate_complete_path()
{
auto current_cell = Cell(0, 0);
while (current_cell.row != row_last_index() || current_cell.col != col_last_index())
{
auto candidate_cells = generate_candidate_cells(current_cell);
filter_candidate_cells(current_cell, candidate_cells);
if (candidate_cells.empty())
{
return false;
}
current_cell = candidate_cells[rand() % candidate_cells.size()];
grid[current_cell.row][current_cell.col] = PATH_CELL;
}
return true;
}
Cell Maze::find_dead_end_path_start() const
{
auto open_cells = std::vector<Cell>();
for (size_type i = 0; i < grid.size(); ++i)
{
for (size_type j = 0; j < grid[i].size(); ++j)
{
if (grid[i][j] == PATH_CELL)
{
open_cells.emplace_back(i, j);
}
}
}
if (open_cells.empty())
{
throw std::logic_error("No open cells to start a dead end path.");
}
return open_cells[rand() % open_cells.size()];
}
void Maze::generate_dead_end_path()
{
auto current_cell = find_dead_end_path_start();
for (;;)
{
auto candidate_cells = generate_candidate_cells(current_cell);
filter_candidate_cells(current_cell, candidate_cells);
if (candidate_cells.empty())
{
break;
}
current_cell = candidate_cells[rand() % candidate_cells.size()];
grid[current_cell.row][current_cell.col] = PATH_CELL;
}
}
std::vector<Cell> Maze::generate_candidate_cells(const Cell& current_cell) const
{
auto candidate_cells = std::vector<Cell>();
auto append_if_candidate = [this, &candidate_cells](size_t row, size_t col)
{
if (grid[row][col] == WALL_CELL)
{
candidate_cells.emplace_back(row, col);
}
};
if (current_cell.row == 0)
{
if (current_cell.col == 0)
{
// top left corner:
append_if_candidate(current_cell.row, current_cell.col + 1);
append_if_candidate(current_cell.row + 1, current_cell.col);
}
else if (current_cell.col == col_last_index())
{
// top right corner:
append_if_candidate(current_cell.row, current_cell.col - 1);
append_if_candidate(current_cell.row + 1, current_cell.col);
}
else
{
// remaining top row:
append_if_candidate(current_cell.row, current_cell.col - 1);
append_if_candidate(current_cell.row, current_cell.col + 1);
append_if_candidate(current_cell.row + 1, current_cell.col);
}
}
else if (current_cell.row == row_last_index())
{
if (current_cell.col == 0)
{
// bottom left corner:
append_if_candidate(current_cell.row - 1, current_cell.col);
append_if_candidate(current_cell.row, current_cell.col + 1);
}
else if (current_cell.col == col_last_index())
{
// bottom right corner:
append_if_candidate(current_cell.row - 1, current_cell.col);
append_if_candidate(current_cell.row, current_cell.col - 1);
}
else
{
// remaining bottom row:
append_if_candidate(current_cell.row - 1, current_cell.col);
append_if_candidate(current_cell.row, current_cell.col - 1);
append_if_candidate(current_cell.row, current_cell.col + 1);
}
}
else if (current_cell.col == 0)
{
// remaining left column:
append_if_candidate(current_cell.row - 1, current_cell.col);
append_if_candidate(current_cell.row, current_cell.col + 1);
append_if_candidate(current_cell.row + 1, current_cell.col);
}
else if (current_cell.col == col_last_index())
{
// remaining right column:
append_if_candidate(current_cell.row - 1, current_cell.col);
append_if_candidate(current_cell.row, current_cell.col - 1);
append_if_candidate(current_cell.row + 1, current_cell.col);
}
else
{
// not at an edge:
append_if_candidate(current_cell.row - 1, current_cell.col);
append_if_candidate(current_cell.row, current_cell.col - 1);
append_if_candidate(current_cell.row, current_cell.col + 1);
append_if_candidate(current_cell.row + 1, current_cell.col);
}
return candidate_cells;
}
void Maze::filter_candidate_cells(const Cell& current_cell,
std::vector<Cell>& candidate_cells) const
{
auto is_open = [this, ¤t_cell](size_t row, size_t col)
{
return !(row == current_cell.row && col == current_cell.col)
&& grid[row][col] == PATH_CELL;
};
candidate_cells.erase(
std::remove_if(
candidate_cells.begin(),
candidate_cells.end(),
[this, is_open](const Cell& cell)
{
if (cell.row == 0)
{
if (cell.col == 0)
{
// top left corner:
return is_open(cell.row, cell.col + 1)
|| is_open(cell.row + 1, cell.col);
}
else if (cell.col == col_last_index())
{
// top right corner:
return is_open(cell.row, cell.col - 1)
|| is_open(cell.row + 1, cell.col);
}
else
{
// remaining top row:
return is_open(cell.row, cell.col - 1)
|| is_open(cell.row, cell.col + 1)
|| is_open(cell.row + 1, cell.col);
}
}
else if (cell.row == row_last_index())
{
if (cell.col == 0)
{
// bottom left corner:
return is_open(cell.row - 1, cell.col)
|| is_open(cell.row, cell.col + 1);
}
else if (cell.col == col_last_index())
{
// bottom right corner:
return is_open(cell.row - 1, cell.col)
|| is_open(cell.row, cell.col - 1);
}
else
{
// remaining bottom row:
return is_open(cell.row - 1, cell.col)
|| is_open(cell.row, cell.col - 1)
|| is_open(cell.row, cell.col + 1);
}
}
else if (cell.col == 0)
{
// remaining left column:
return is_open(cell.row - 1, cell.col)
|| is_open(cell.row, cell.col + 1)
|| is_open(cell.row + 1, cell.col);
}
else if (cell.col == col_last_index())
{
// remaining right column:
return is_open(cell.row - 1, cell.col)
|| is_open(cell.row, cell.col - 1)
|| is_open(cell.row + 1, cell.col);
}
else
{
// not at an edge:
return is_open(cell.row - 1, cell.col)
|| is_open(cell.row, cell.col - 1)
|| is_open(cell.row, cell.col + 1)
|| is_open(cell.row + 1, cell.col);
}
}
),
candidate_cells.end()
);
}
namespace
{
void print_maze_header(std::ostream& out, size_t num_cols)
{
for (size_t i = 0; i < num_cols + 2; ++i)
{
out << BOUNDARY_CELL;
}
out << '\n';
}
}
std::ostream& operator<<(std::ostream& out, const Maze& maze)
{
print_maze_header(out, maze.grid[0].size());
for (const auto& row : maze.grid)
{
out << BOUNDARY_CELL;
for (const auto& col : row)
{
out << col;
}
out << BOUNDARY_CELL << '\n';
}
print_maze_header(out, maze.grid[0].size());
return out;
}
int main()
{
using namespace std;
srand((unsigned)time(NULL));
try
{
auto maze = Maze(20, 40);
maze.generate_path();
cout << maze;
}
catch (const exception& e)
{
cerr << "Error: " << e.what() << endl;
}
}
EDIT: