Program to Implement Recursion to Create a Maze in C++

Instructions

Objective

Write a program to implement recursion and create a maze in C++ language.

Requirements and Specifications

In this homework you will be combining use of recursion as well as a bit of OO design.

What you should provide:

Two cpp files and a .h file

maze.cpp – the Implemtation for the Maze and Maze Elements

maze.h – header file

test.cpp - Test driver that reads in the ‘maze’ data file and drives the test

The assignment ( just the bare bones) ( suggestions and hints follow)

You are given a maze represented by a data file.

At the top of the file are two integers which is the row and column values for the array

Next are two integers which provide the starting point of your search.

Walls are noted by a ‘#’ mark.

You may move to any space which is not a ‘#’ and that does not take you outside of the map

The objective is to find a shortest path through the maze to the exit ( noted on the map by a ‘o’ character)

You may move up / down / left / right ( but not on a diagonal)

Then you will print out the maze.

Screenshots of output

program to implement recursion to create a maze in C++

Source Code and Solution

#include <iostream>
#include"maze.h"
using namespace std;
MazeElement::MazeElement() {
 row = -1;
 col = -1;
 type = 0;
 path = false;
 distance = -1;
}
MazeElement::MazeElement(int _r, int _c, char _t) {
 row = _r;
 col = _c;
 if (_t == '#') {
  type = 0;
 }
 else if (_t == ' ') {
  type = 1;
 }
 else {
  type = 2;
 }
 distance = -1;
 path = false;
}
int MazeElement::getType() {
 return type;
}
int MazeElement::getDistance() {
 return distance;
}
void MazeElement::setDistance(int _d) {
 distance = _d;
}
bool MazeElement::isPath() {
 return path;
}
void MazeElement::setPath(bool _p) {
 path = _p;
}
char MazeElement::toChar() {
 if (type == 2) {
  return 'o';
 }
 else if (path) {
  return '.';
 }
 else if (type == 0) {
  return '#';
 }
 return ' ';
}
Maze::Maze(int _h, int _w) {
 height = _h;
 width = _w;
 cells = new MazeElement*[height];
 for (int i = 0; i<height; i++) {
  cells[i] = new MazeElement[width];
 }
}
Maze::~Maze() {
 for (int i = 0; i<height; i++) {
  delete[] cells[i];
 }
 delete[] cells;
}
void Maze::setCell(int _r, int _c, char _t) {
 MazeElement me(_r, _c, _t);
 cells[_r][_c] = me;
}
void Maze::print() {
 for (int i = 0; i<height; i++) {
  for (int j = 0; j<width; j++) {
   cout << cells[i][j].toChar();
  }
  cout << endl;
 }
}
void Maze::visit(int _r, int _c, int len) {
 MazeElement me = cells[_r][_c];
 if (cells[_r][_c].getDistance() < 0 || cells[_r][_c].getDistance() > len) {
  cells[_r][_c].setDistance(len);
 }
 else {
  return;
 }
 if(canVisit(_r+1, _c)){
    visit(_r+1, _c, len + 1);
  }
  if(canVisit(_r, _c+1)){
    visit(_r, _c+1, len + 1);
  }
  if(canVisit(_r-1, _c)){
    visit(_r-1, _c, len + 1);
  }
  if(canVisit(_r, _c-1)){
    visit(_r, _c-1, len + 1);
  }
}
bool Maze::canVisit(int _r, int _c) {
 if (_r < 0 || _r >= height || _c < 0 || _c >= width) {
  return false;
 }
 if (cells[_r][_c].getType() == 0) {
  return false;
 }
 return true;
}
void Maze::findPath(int _r, int _c) {
 visit(_r, _c, 0);
 int currR = -1;
 int currC = -1;
 for (int i = 0; i<height; i++) {
  for (int j = 0; j<width; j++) {
   if (cells[i][j].getType() == 2) {
    currR = i;
    currC = j;
   }
  }
 }
 while(currR != _r || currC != _c) {
  int dist = cells[currR][currC].getDistance();
  if(canVisit(currR+1, currC) && cells[currR+1][currC].getDistance() + 1 == dist){
     currR++;
   }
  else if(canVisit(currR, currC+1) && cells[currR][currC+1].getDistance() + 1 == dist){
     currC++;
   }
  else if(canVisit(currR-1, currC) && cells[currR-1][currC].getDistance() + 1 == dist){
     currR--;
   }
  else if(canVisit(currR, currC-1) && cells[currR][currC-1].getDistance() + 1 == dist){
     currC--;
   }
  cells[currR][currC].setPath(true);
 }
 print();
}

Program to Implement Recursion and Create a Maze in C++ Language Assignment Solution.

Instructions

Requirements and Specifications