Question

RECURSIVELY FINDING PATHS THROUGH A MAZE in C++

INTRODUCTION

Recursion is a programming technique in which a function calls itself. This project applies recursion to a new problem, and illustrates the recursive implementation of backtracking.

DESCRIPTION

Consider finding all paths from an entrance on the top of a maze to an exit on the bottom. This task can be accomplished recursively, so in this project, you design, implement, test, and document a program that calls a recursive function to find a path through a maze.

An array of characters represents a maze: blanks represent corridors, and `+' characters represent walls. Indicate the steps along a path with some other character. The program will read a maze from a data file, identify the path(s) through the maze, and print out each path. There may be more than one path.

INPUT

The program will read the name of a data file from the terminal. A data file will contain the dimensions of a maze and an array of `+'s and blanks that represent the maze. This array must be no larger than 22 rows by 76 columns, so that it can be displayed on a standard terminal screen. The entrance to the maze will always be the second position on the top row, which must therefore be blank. The exit must be on the maze's bottom row. Except for its entrance and exit, the entire perimeter of the maze will be "wall;" there will be no other entrances or exits.

OUTPUT

The program's output will be the maze with a path through it indicated, one such picture of the maze for each path. Direct output to the terminal.

ERRORS

The program should recover gracefully if the user enters the name of an input file that does not exist. Otherwise, it may assume that the input is correct; it need not detect any errors.

EXAMPLE

This is a typical instance of this problem. The input file maze.dat is on the left. Corresponding output might look like the right figure.

20 20                            
+ ++++++++++++++++++               
+          +  ++ +++              
+++ ++++++   ++   ++
+ +++    +++    ++++
+   + ++ ++++++    +
+++   ++     ++ ++ +
+   +++ ++++ ++ ++ +
+ ++++  ++   +++++ +
+    + +++ +++     +
+ ++ + +++ ++++++ ++
+  +++++   +++    ++
+ +++    ++++  ++ ++
+   ++++      +++  +
+++    +++++++++++ +
++  +++++++        +
++ +++    ++++++++ +
++ ++++++        + +
+    +++  ++++++ +++
++++     +++     +++
+++++++++++++ ++++++

A path through the maze:

+@++++++++++++++++++

+@@@@@@@@@@+  ++ +++
+++ ++++++@@@++   ++

+ +++@@@@+++@@@@++++
+   +@++@++++++@@@@+
+++@@@++@@@@@++ ++@+
+@@@+++ ++++@++ ++@+
+@++++  ++@@@+++++@+
+@   + +++@+++   @@+
+@++ + +++@++++++@++
+@ +++++@@@+++@@@@++
+@+++   @++++@@++ ++
+@@@++++@@@@@@+++  +
+++@   +++++++++++ +
++@@+++++++        +
++@+++    ++++++++ +
++@++++++@@@@@@@@+ +
+ @@@+++@@++++++@+++
++++@@@@@+++ @@@@+++
+++++++++++++@++++++

OTHER REQUIREMENTS

Use a recursive function to identify each step of a path through the maze. Your program should be able to handle mazes of any dimensions up to 22 by 76; read the dimensions of each maze from its file. (The example above is 20 by 20.) Test the program with examples that are at least 16 by 16. Note that larger examples are more entertaining.

Answer 1

CODE:

#include "Cell.h"
#include
#include
#include
#include

using std::cout;
using std::vector;

// Create constants (ROWS, COLS) to store the size of the maze.
const int ROWS = 20;
const int COLS = 20;

// Create an enum named DIR to keep track of the four directions (NORTH, EAST, SOUTH, WEST)
enum DIR { NORTH, SOUTH, EAST, WEST };

int main(void){
// variables
int ran_dir;

// Randomize the random number function.
srand(time(NULL));

// Create a 2-D array ([ROWS][COLS]) of Cell objects.
Cell maze[ROWS][COLS];

// For each Cell in the maze:
for(int row = 0; row < ROWS; row++)
for(int col = 0; col < COLS; col++) {
// set visited to false
maze[row][col].setVisited(false);
// set its position to its row and column in the maze
maze[row][col].setPosition(row, col);
// set the Cell's walls to Cell::WALL_ALL
maze[row][col].setWalls(Cell::WALL_ALL);
}

//Create curX and curY variables and set them to a random position in the maze.
int curX = rand() % ROWS;
int curY = rand() % COLS;

// Create a vector of Cell objects named trail which will be used as a stack.
vector trail;

// Create a vector of DIR values named live.
vector

live;

// Grab the Cell at the curX, curY position and push it on the trail stack.
trail.push_back(maze[curX][curY]);

// While the trail stack is not empty do the following:
while(trail.empty()==false) { // stay in here till display
// Empty the live vector.
live.clear();
// Check the neighbors of the current cell to the north, east, south, and west.
// If any of the neighbors have all four walls, add the direction to that
// neighbor to the live vector.
if(curY)
if(maze[curX][curY-1].getWalls()==Cell::WALL_ALL) // West has all walls
live.push_back(WEST);
if(curY if(maze[curX][curY+1].getWalls()==Cell::WALL_ALL) // east has all walls
live.push_back(EAST);
if(curX)
if(maze[curX-1][curY].getWalls()==Cell::WALL_ALL) // North has all walls
live.push_back(NORTH);
if(curX if(maze[curX+1][curY].getWalls()==Cell::WALL_ALL) // South has all walls
live.push_back(SOUTH);
// If the live vector is not empty:
if(live.empty()==false) {
// Choose one of the directions in the live vector at random
// ran_dir=rand() % live.size();
// cout << "Random dir " << ran_dir << " out of " << live.size() << "\n";
// Remove the walls between the current cell and the neighbor in that direction
// and Change curX and curY to refer to the neighbor
maze[curX][curY].setVisited(true);
switch(live[rand() % live.size()]) {
case 0:
maze[curX][curY].removeWall(Cell::WALL_NORTH);
curX--;
break;
case 1:
maze[curX][curY].removeWall(Cell::WALL_SOUTH);
curX++;
break;
case 2:
maze[curX][curY].removeWall(Cell::WALL_EAST);
curY++;
break;
case 3:
maze[curX][curY].removeWall(Cell::WALL_WEST);
curY--;
break;
}
// Push the new current cell onto the trail stack
/*cout << "Maze " << curX << ", " << curY << "\n";
cin.ignore(); */
trail.push_back(maze[curX][curY]);
} //If the live vector was emtpy:
else {
// Pop the top item from the trail stack
trail.pop_back();

// If the trail stack is not empty, set curX and curY to refer to the
// position of the top item in the trail stack.
if(trail.empty()==false) {
curX=trail[0].getRow();
curY=trail[0].getColumn();
}
}
}

// Do the following to display the maze:
int r, c;
for (c=0; c if (c == 0) cout << " _";
else cout << "__";
}
cout << '\n';
for (r=0; r for (c=0; c cout << maze[r][c];
}
cout << "|\n";
}
return 0;
}

Cell implementation:
cell.h

#ifndef __CELL_H_
#define __CELL_H_

#include
#include

class Cell {
private:
int row;
int col;
bool visit;
int walls;
void init(const int r, const int c, const int walls, const bool v = false);
public:
enum WALL { WALL_NORTH = 0x0008, WALL_EAST = 0x0004,
WALL_SOUTH = 0x0002, WALL_WEST = 0x0001,
WALL_ALL = 0x000f, WALL_NONE = 0x0000 };
Cell();
Cell(const int r, const int c);
Cell(const int r, const int c, const int stat);
bool visited() const;
void setVisited(const bool v = true);
int getRow() const;
int getColumn() const;
void removeWall(const int w);
int getWalls() const;
void setWalls(const int w);
void setPosition(const int r, const int c);
friend std::ostream& operator<<(std::ostream& strm, const Cell& c);
};

#endif

cell.cpp

#include "Cell.h"
#include
#include
#include
#include

void Cell::init(const int r, const int c, const int walls, const bool v) {
setPosition(r, c);
setWalls(walls);
setVisited(v);
}
Cell::Cell() { init(0, 0, 0); }
Cell::Cell(const int r, const int c) { init(r, c, 0); }
Cell::Cell(const int r, const int c, const int walls) { init(r, c, walls); }
bool Cell::visited() const { return visit; }
void Cell::setVisited(const bool v) { visit = v; }
int Cell::getRow() const { return row; }
int Cell::getColumn() const { return col; }
void Cell::removeWall(const int w) {
if (w!=WALL_NORTH && w!=WALL_EAST && w!=WALL_SOUTH && w!=WALL_WEST)
throw std::string("Illegal wall argument");
walls &= ~w;
}
int Cell::getWalls() const { return walls & WALL_ALL; }
void Cell::setWalls(const int w) { walls = w & WALL_ALL; }
void Cell::setPosition(const int r, const int c) { row = r; col = c; }

std::ostream& operator<<(std::ostream& strm, const Cell& c) {
if ((c.getWalls() & Cell::WALL_WEST) != 0) strm << '|';
else strm << ' ';
if ((c.getWalls() & Cell::WALL_SOUTH) != 0) strm << '_';
else strm << ' ';

return strm;
}

---