Instructions
Objective
Write a program to implement a maze generator in C++ language.
Requirements and Specifications
This week, you will write a C++ homework that generates random mazes and finds a path in there from a beginning to an end position, and then prints the maze on the screen. To give you an idea, this is how the output of your program is supposed to look like:
./mazegen 5 6
+---+---+---+---+---+---+
| . . . | |
+---+---+ +---+---+ +
| | . . . | |
+ +---+---+---+ + +
| | . | |
+ +---+---+ + + +
| | | | . | |
+ + + +---+ + +
| | . . |
+---+---+---+---+---+---+
Your program should perform the following major steps:
- Read from the program's command line parameters either 2 or 3 integer values. The first one is the number of rows of the maze, the second one is the number of columns. The third parameter is optional. (But you must implement handling it.) If present, the third parameter must be used as seed value for the random generator. (So you can decide to always generate the same maze for testing purposes.) When called with two parameters only, the program must generate a different maze, each time it is run. Hint: you can convert a string from argv[] to an int using std::stoi.
- Generate a random maze of the given size, using the algorithm called Recursive backtracker (see below). The core of this assignment is using classes in a meaningful way. Before you start implementing, first decide what are the "things" in your program, and create classes for them. (Example things are the maze, coordinates, cells in the maze, or even the command line parameters.) Your program must implement at least two classes. But more are likely helpful for achieving good structure.
- Find a path inside your random maze, from the top-left corner -- we refer to as position (0,0) --, to the bottom right corner. For details, see below.
- Print your maze with the path to cout. (Details, see below)
Maze generation
The maze consists of walls and cells. The maze must be closed, so there must be no openings in the outer walls. Initially, all cells are separated from each other by walls. Inside the maze, some walls must be removed to connect the cells to each other. All cells must be connected to each other; from any cell it must be possible to reach any other cell by following paths that have been created by removing some of the internal walls. Cycles inside the maze are forbidden. So, the number of removed walls must be equal to the number of cells, minus 1. Fortunately, there is an algorithm, called Recursive backtracker, that does this for us.
Path finding
Once you have generated your maze (and stored inside a beautiful, class-based data structure), it is time to find a path through your maze. By convention, the path must always start in the top left corner, and must end in the bottom right corner. The finally identified path must not include any detours. For path finding, not having cycles in the maze makes our lives much easier!
Path finding can be done by a (recursive) technique called backtracking. But all you need is implement the following pseudo code, using your own class data structures:
Function findPath, given a maze M, and two coordinates, from and to, returns true if a path could be found, false otherwise:
- M.at(from).visited <- true
- if from equals to, return true
- neighbours <- list of all direct neighbours of from that can be reached (that are not blocked by walls)
- for all n in neighbours:
- if M.at(n).visited == false
- if findPath(n,to) == true, return true
- M.at(from).visited <- false
- return false
Maze printing
Maze printing must be done very precisely, according to this description. Otherwise, the automated tests will fail. This means, no other characters, no extra characters, no extra spaces or newlines. Let's consider the following 2-by-2 example maze:
+---+---+
| . . |
+---+ +
| . |
+---+---+
Each cell is 5 characters wide and 3 characters high. Walls and corners are shared among neighbouring cells. Each corner is denoted as +. A horizontal wall is denoted as 3 minus signs: --- A vertical wall is denoted by |
The contents of a cell are either three spaces: ' ' ,
or two spaces with a . in the middle: ' . ' ,
the latter if the cell is part of the path from the top left corner to the bottom right corner.
Source Code
#include
#include
#include
#include
using namespace std;
int EAST = 0;
int SOUTH = 1;
int WEST = 2;
int NORTH = 3;
int DIRS[4][2] = {{0,1}, {1,0}, {0,-1}, {-1, 0}};
class Cell {
private:
int row;
int col;
bool marked;
bool wall[4];
public:
Cell() {
}
Cell(int r, int c) {
row = r;
col = c;
marked = false;
for(int i = 0; i<4; i++) {
wall[i] = true;
}
}
int getRow() const {
return row;
}
int getCol() const {
return col;
}
bool isMarked() {
return marked;
}
void setMarked(bool m) {
marked = m;
}
bool hasWall(int dir) {
return wall[dir];
}
void setWall(bool w, int dir) {
wall[dir] = w;
}
bool operator==(Cell const& rhs) const {
return row == rhs.getRow() && col == rhs.getCol();
}
string to_string() {
if (marked) {
return ".";
}
else {
return " ";
}
}
};
class Maze {
private:
int height;
int width;
Cell** cells;
void generateMaze() {
vector visited;
| stack stack;
| visited.push_back(cells[0][0]);
stack.push(cells[0][0]);
while(!stack.empty()) {
Cell current = stack.top();
vector ns;
| for(int i = 0; i<4; i++) {
int r = current.getRow() + DIRS[i][0];
int c = current.getCol() + DIRS[i][1];
if (r >= 0 && r < height && c >= 0 && c < width) {
Cell n(r, c);
if (std::find(visited.begin(), visited.end(), n) == visited.end()) {
ns.push_back(n);
}
}
}
if(!ns.empty()) {
random_shuffle(ns.begin(), ns.end());
Cell next = ns[0];
visited.push_back(next);
stack.push(next);
if (current.getRow() - next.getRow() == -1) {
cells[current.getRow()][current.getCol()].setWall(false, SOUTH);
cells[next.getRow()][next.getCol()].setWall(false, NORTH);
}
if (current.getRow() - next.getRow() == 1) {
cells[current.getRow()][current.getCol()].setWall(false, NORTH);
cells[next.getRow()][next.getCol()].setWall(false, SOUTH);
}
if (current.getCol() - next.getCol() == -1) {
cells[current.getRow()][current.getCol()].setWall(false, EAST);
cells[next.getRow()][next.getCol()].setWall(false, WEST);
}
if (current.getCol() - next.getCol() == 1) {
cells[current.getRow()][current.getCol()].setWall(false, WEST);
cells[next.getRow()][next.getCol()].setWall(false, EAST);
}
}
else {
stack.pop();
}
}
}
void solveMaze() {
vector visited;
| visited.push_back(cells[0][0]);
solveMazeStep(0, 0, visited);
}
bool solveMazeStep(int row, int col, vector& visited) {
| if (row == height - 1 && col == width - 1) {
cells[row][col].setMarked(true);
return true;
}
for(int i = 0; i<4; i++) {
if (!cells[row][col].hasWall(i)) {
if (std::find(visited.begin(), visited.end(), cells[row + DIRS[i][0]][col + DIRS[i][1]]) == visited.end()) {
visited.push_back(cells[row + DIRS[i][0]][col + DIRS[i][1]]);
bool result = solveMazeStep(row + DIRS[i][0], col + DIRS[i][1], visited);
if (result) {
cells[row][col].setMarked(true);
return true;
}
}
}
}
cells[row][col].setMarked(false);
return false;
}
public:
Maze(int h, int w) {
height = h;
width = w;
cells = new Cell*[height];
for(int i = 0; i cells[i] = new Cell[width];
for(int j = 0; j cells[i][j] = Cell(i, j);
}
}
generateMaze();
solveMaze();
}
~Maze() {
for(int i = 0; i delete cells[i];
}
delete cells;
}
string to_string() {
string s = "";
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
s += "+";
if (cells[i][j].hasWall(NORTH)) {
s += "---";
} else {
s += " ";
}
}
s += "+\n";
for (int j = 0; j < width; j++) {
if (cells[i][j].hasWall(WEST)) {
s += "|";
} else {
s += " ";
}
s += " " + cells[i][j].to_string() + " ";
}
s += "|\n";
}
for (int j = 0; j < width; j++) {
s += "+---";
}
s += "+\n";
return s;
}
};