CSCI 301 Computer Science 2 Spring, 2018 TITLE RECURSIVELY FINDING PATHS THROUGH

Question

CSCI 301
Computer Science 2
Spring, 2018

TITLE

RECURSIVELY FINDING PATHS THROUGH A MAZE

Language: 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.

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.

HINTS

The main program should read a maze from a file into an array and call the recursive function that identifies paths. Include a function that reads a data file and another that prints out the array thay represents a maze. The recursive function will call the latter function.

Each legal step moves closer to a complete path or a dead end, so that after that step, the problem is smaller. At each position, there are four directions that must be checked for the next step (which will be passed to a recursive procedure call). No more than three of these steps will be possible (the previous step will occupy one adjacent position), but the code must contain four recursive calls in independent if statements.

The base cases of the recursion occur when the path (the current position) reaches a dead end and no move is possible and when the path reaches the bottom row of the maze/array. In the first case, simply return. In the second case, print the array, which will include the path just completed

The maze array will be automatically passed by reference, so that all instances of the path-finding function will be operating on one copy of the array. Thus, the function will have to ``take back'' each move it makes after the corresponding recursive call has returned.

Blocks of open spaces in a maze will allow many paths and may produce more output than you expect. It's best to avoid them.

HAND IN

See About Programming Assignments for a description of what to hand in: design document, user document, code, tests, and summary.

Explanation / Answer

#include "Cell.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>

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<Cell> trail;

// Create a vector of DIR values named live.
vector<DIR> 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<COLS-1)
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<ROWS-1)
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() << " ";
// 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 << " ";
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<COLS; c++) {
if (c == 0) cout << " _";
else cout << "__";
}
cout << ' ';
for (r=0; r<ROWS; r++) {
for (c=0; c<COLS; c++) {
cout << maze[r][c];
}
cout << "| ";
}
return 0;
}

Cell implementation:
cell.h

#ifndef __CELL_H_
#define __CELL_H_

#include <string>
#include <iostream>

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 <iostream>
#include <stdlib.h>
#include <time.h>
#include <vector>

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;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects