// maze.cpp
//
// This program creates a random maze, and then "floods" it with water. The
// spreading of the water is simulated in two different ways: one way using a
// loop, and one way using recursion. The code for the recursive solution is
// shorter and simpler than the one using a loop.
//
#include <iostream>
#include "cmpt_error.h"
#include <vector>
#include <cassert>
#include <cstdlib>
#include <ctime>
using namespace std;
// An enum class creates a new data type with a finite set of values. The ":
// char" means that wall, dirt, and water are implemented as characters, which
// is convenient here since we are displaying the maze in plain text.
enum class Tile : char {
wall='m', dirt=' ', water='.'
};
// Returns a random number r where 0.0 <= r < 1.0. Note that the srand
// function, which is called below at the start of main(), is used to
// initialize rand().
double rand01() {
return rand() / (RAND_MAX + 1.0);
}
class Maze {
// a maze is a 2-dimensional vector of Tiles
vector<vector<Tile>> maze;
// this struct is needed by the iterative flood method below
struct Location {
int row;
int col;
};
public:
Maze(int w, int h) // constructor
: maze(h)
{
assert(w > 1 && h > 1);
// initialize all tiles to dirt
for(int i = 0; i < maze.size(); ++i) {
maze[i] = vector<Tile>(w, Tile::dirt);
}
// add a ring of walls around the entire maze
for(int i = 0; i < w; ++i) maze[0][i] = Tile::wall; // top row
for(int i = 0; i < w; ++i) maze[h-1][i] = Tile::wall; // bottom row
for(int i = 0; i < h; ++i) maze[i][0] = Tile::wall; // left column
for(int i = 0; i < h; ++i) maze[i][w-1] = Tile::wall; // right column
// randomly set some more wall locations
const double prob_of_wall = 0.33;
for(int i = 1; i < h - 1; ++i) {
for(int j = 1; j < w - 1; ++j) {
if (rand01() < prob_of_wall) {
maze[i][j] = Tile::wall;
}
}
}
}
// get the width and height of the maze
int width() const { return maze[0].size(); }
int height() const { return maze.size(); }
// tests if maze[row][col] is a valid location
bool in_maze(int row, int col) const {
return (0 <= row && row < height())
&& (0 <= col && col < width());
}
// set the location at row r, column c to be tile t
void set(int r, int c, const Tile& t) {
assert(in_maze(r, c));
maze[r][c] = t;
}
// return the value at row r, column c
Tile get(int r, int c) const {
assert(in_maze(r, c));
return maze[r][c];
}
// print the maze to the screen
void print() const {
for(int i = 0; i < height(); ++i) {
for(int j = 0; j < width(); ++j) {
cout << char(maze[i][j]) << " "; // char(maze[i][j]) converts
} // maze[i][j] (which is of type Tile)
cout << "\n"; // to its underlying char
}
}
void println() const {
print();
cout << "\n";
}
// Sets all locations reachable from maze[start_row][start_col] to water.
// A location is reachable if you can get to it without hitting a wall,
// and going one step at a time in either the north, south, east, or west
// direction (diagonal steps are not allowed).
//
// Uses a vector of Locations to remember which locations to visit next.
// This is a purely iterative function, i.e. it only uses loops. It does
// not recursion anywhere.
void flood(int start_row, int start_col) {
vector<Location> choices = { Location{start_row, start_col} };
while (!choices.empty()) {
// remove a Location from choices
Location loc = choices.back();
choices.pop_back(); // removes last element of choices
int r = loc.row;
int c = loc.col;
// check if maze[r][c] exists and is dirt
if (in_maze(r, c) && maze[r][c] == Tile::dirt) {
maze[r][c] = Tile::water;
// add 4 neighbors
choices.push_back(Location{r-1, c});
choices.push_back(Location{r+1, c});
choices.push_back(Location{r, c-1});
choices.push_back(Location{r, c+1});
}
}
}
// Sets all locations reachable from maze[r][c] to water. Uses recursion
// instead of an explicit loop. Notice that the Location class is not
// needed because the row and column values are stored as the parameters
// in the calls to flood_recursive.
void flood_recursive(int r, int c) {
if (in_maze(r, c) && maze[r][c] == Tile::dirt) {
maze[r][c] = Tile::water;
flood_recursive(r-1, c);
flood_recursive(r+1, c);
flood_recursive(r, c-1);
flood_recursive(r, c+1);
}
}
}; // class Maze
void test_flood() {
Maze maze(30, 18);
maze.set(1, 1, Tile::dirt); // ensure starting point is dirt
maze.flood(1, 1);
maze.println();
}
void test_flood_recursive() {
Maze maze(30, 18);
maze.set(1, 1, Tile::dirt); // ensure starting point is dirt
maze.flood_recursive(1, 1);
maze.println();
}
int main() {
// this initializes the random number generator with a value based on the
// current time (which is effectively) a random number
srand(time(NULL));
test_flood();
// test_flood_recursive();
}