Question

MazeEscape in C++

pseudocode:

Push self on answer stack and mark self processed.

for each exit, Recurse on it

if any recurse returns true, yay! just keep returning true all the way back.

if none return true, pop us off answer stack and die quietly

Use the project in the files section to start


Have main output the path like N E S S E E E N E E N W N.
You need to change Cell or Maze or what you put on the stack to store the direction you took.

Also, write the main that creates the maze.
Read a file that looks like the text in the Files section. S is start, E is the exit. The border will always be walls as shown - S and E are inside.

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

This is file .txt for the maze :

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X XXXXXXXXX     XX    X    X       XEX
X X       X XX XXX XXXX XXXXXXXXXX X X
X X XXX X X XX X     X               X
X X   X X X XX X XXX   XXXXXXXXXXXXXXX
X XXX X X X XXXX XXXXXXXXX     XXXXXXX
X     X X X      X   X   X XXX       X
X XXXXX X X XXXXXX X X X X XXXXXXXXX X
XSX     X          X          X      X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

--------------------------------------------------------------------------------------------------------------------------------------------------------------

This is file .h of class maze:

#pragma once
#include <stack>
#include <list>

class Maze
{
public:
   class Cell
   {
       friend Maze;
       //       std::list<Cell*>mAdjacent;
       Cell* mNorth = nullptr; // While this "hardcodes" four directions, it is hella easier and 99% of mazes are flat and square
       Cell* mSouth = nullptr;
       Cell* mEast = nullptr;
       Cell* mWest = nullptr;

       bool mIsExit = false;
       bool mProcessed = false;// Prevent loops Treat finding a processed cell as just not there. Like a dead end.
   };

private:
   bool MazeRecursive(Cell* tCurrent, std::stack<Cell*>* tPath);
   Cell* mStart;

public:
   Maze();// Making a constructor with a file name would be cool for the extra credit.
   ~Maze();
   std::stack<Cell*> SolveMaze();

};

--------------------------------------------------------------------------------------------

This is file .cpp of class maze:

#include "Maze.h"

Maze::Maze()
{
   // Making a test maze by hand to make testing easy without giving away the extra credit of the maze maker.

   mStart = new Cell;
   mStart->mNorth = new Cell;
   mStart->mNorth->mNorth = new Cell;
   mStart->mEast = new Cell;
   mStart->mEast->mEast = new Cell;
   mStart->mEast->mEast->mNorth = new Cell;
   mStart->mEast->mEast->mNorth->mNorth = new Cell;
   mStart->mEast->mEast->mNorth->mNorth->mIsExit = true;
   // This is the big U I drew on the board.
}

Maze::~Maze()
{
   // Totally leaks
}

bool Maze::MazeRecursive(Maze::Cell* tCurrent, std::stack<Maze::Cell*>* tPath)
{
   // This is the main part. Just keep in mind the single sentence recursive definition:

   // "To exit a maze, I take a step and if I'm not done I exit the maze."

   // Use Processed to prevent loops. The last cell is marked IsExit. Using the four direction pointers
   // versus the list is up to you. "tPath" is there for you to push cell pointers as you move. If
   // it turns out you didn't find the exit that direction then pop it back off. The return value
   // of true-false is how you communicate success backwards.

   return false;//stub
}

std::stack<Maze::Cell*> Maze::SolveMaze()// Driver
{
   // Don't need to change this.
   std::stack<Maze::Cell*> tAnswer;
   MazeRecursive(mStart, &tAnswer);
   return tAnswer;
}

----------------------------------------------------------------------------------------------------------------------------------------

This is main():

// MazeEscape.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <iostream>
#include "Maze.h"

int main()
{
   Maze tTestMaze;
   std::stack<Maze::Cell*> tPath;
   tPath = tTestMaze.SolveMaze();

}

Answer 1

Program Files:

Maze.h

#pragma once
#include <stack>
#include <list>
#include <string>
#include <vector>

class Maze
{
public:
class Cell
{
friend Maze;
Cell* mNorth = nullptr;   
Cell* mSouth = nullptr;
Cell* mEast = nullptr;
Cell* mWest = nullptr;
bool mIsExit = false;
bool mOnPath = false;
bool mProcessed = false;
  
};

private:
bool MazeRecursive(Cell *tCurrent);
Cell* mStart;
int mLength;
int mWidth;
std::vector<std::vector<Cell*>> mCellMatrix;

public:
Maze();
Maze(std::string tFilePath);
~Maze();
void SolveMaze();

};

Maze.cpp

#include "Maze.h"
#include <iostream>
#include <fstream>
#include <vector>

Maze::Maze()
{

mStart = new Cell;
mStart->mNorth = new Cell;
mStart->mNorth->mNorth = new Cell;
mStart->mEast = new Cell;
mStart->mEast->mEast = new Cell;
mStart->mEast->mEast->mNorth = new Cell;
mStart->mEast->mEast->mNorth->mNorth = new Cell;
mStart->mEast->mEast->mNorth->mNorth->mIsExit = false;
}

Maze::Maze(std::string tFilePath)
{
std::string rawText = "";
std::string lineIn = "";
mWidth = 0;
mLength = 0;
std::ifstream inFile;
/////////////////////////////////
inFile.open(tFilePath.c_str());
if (inFile)
{
while (!inFile.eof())
{
std::getline(inFile, lineIn);
rawText += lineIn;
mLength++;

}
mWidth = lineIn.length();
mCellMatrix = std::vector<std::vector<Cell*>>(mLength, std::vector<Cell*>(mWidth, nullptr));
int row = 0;
int col = 0;
for (int i = 0; i < rawText.size(); i++)
{ // Create Nodes
if (!(rawText[i] == ' ' || rawText[i] == 'S' || rawText[i] == 'E')) continue;
if (mWidth > 0) row = i / mWidth;
col = i % mWidth;
if (mCellMatrix[row][col] == nullptr) mCellMatrix[row][col] = new Cell();
if (rawText[i] == 'S') mStart = mCellMatrix[row][col];
if (rawText[i] == 'E') mCellMatrix[row][col]->mIsExit = true;
}
for (row = 0; row < mLength; row++)
{ // Link nodes and print nodes to console
for (col = 0; col < mWidth; col++)
{
if (mCellMatrix[row][col] == nullptr)
{
std::cout << "||";
continue;
}
else if (mCellMatrix[row][col]->mIsExit) std::cout << "EE";
else std::cout << " ";
if (row - 1 >= 0 && mCellMatrix[row - 1][col] != nullptr)//North in bounds
{
mCellMatrix[row][col]->mNorth = mCellMatrix[row - 1][col];
}
if (row + 1 < mLength && mCellMatrix[row + 1][col] != nullptr)//South in bounds
{
mCellMatrix[row][col]->mSouth = mCellMatrix[row + 1][col];
}
if (col + 1 < mWidth && mCellMatrix[row][col + 1] != nullptr)//East in bounds
{
mCellMatrix[row][col]->mEast = mCellMatrix[row][col + 1];
}
if (col - 1 >= 0 && mCellMatrix[row][col - 1] != nullptr)//West in bounds
{
mCellMatrix[row][col]->mWest = mCellMatrix[row][col - 1];
}
}
std::cout << std::endl;
}
std::cout << std::endl;

  
}
else std::cout << "File Not Found!";
if (inFile) inFile.close();
}

Maze::~Maze()
{
for (int row = 0; row < mLength; row++)
{
for (int col = 0; col < mWidth; col++)
{
if (mCellMatrix[row][col] == nullptr)
{
continue;
}
delete mCellMatrix[row][col];
}
}
}

bool Maze::MazeRecursive(Maze::Cell* tCurrent)
{
if (tCurrent == nullptr || tCurrent->mProcessed) return false;
tCurrent->mProcessed = true;
if (tCurrent->mIsExit
|| MazeRecursive(tCurrent->mNorth)
|| MazeRecursive(tCurrent->mSouth)
|| MazeRecursive(tCurrent->mEast)
|| MazeRecursive(tCurrent->mWest))
{
tCurrent->mOnPath = true;
return true;
}
}

void Maze::SolveMaze()
{

if (MazeRecursive(mStart))
{
for (int row = 0; row < mLength; row++)
{
for (int col = 0; col < mWidth; col++)
{
if (mCellMatrix[row][col] == nullptr)
{
std::cout << "||";
continue;
}
else if (mCellMatrix[row][col]->mIsExit) std::cout << "EE";
else if (mCellMatrix[row][col]->mOnPath) std::cout << "~~";
else std::cout << " ";
mCellMatrix[row][col]->mProcessed = false;
}
std::cout << std::endl;
}
std::cout << "Exit Found! Path:" << std::endl << std::endl;
Cell* tTempCellPtr = mStart;
while (!tTempCellPtr->mIsExit)
{
if (tTempCellPtr->mNorth != nullptr && tTempCellPtr->mNorth->mOnPath && !tTempCellPtr->mNorth->mProcessed)
{
std::cout << "N ";
tTempCellPtr->mProcessed = true;
tTempCellPtr = tTempCellPtr->mNorth;
continue;
}
if (tTempCellPtr->mSouth != nullptr && tTempCellPtr->mSouth->mOnPath && !tTempCellPtr->mSouth->mProcessed)
{
std::cout << "S ";
tTempCellPtr->mProcessed = true;
tTempCellPtr = tTempCellPtr->mSouth;
continue;
}
if (tTempCellPtr->mEast != nullptr && tTempCellPtr->mEast->mOnPath && !tTempCellPtr->mEast->mProcessed)
{
std::cout << "E ";
tTempCellPtr->mProcessed = true;
tTempCellPtr = tTempCellPtr->mEast;
continue;
}
if (tTempCellPtr->mWest != nullptr && tTempCellPtr->mWest->mOnPath && !tTempCellPtr->mWest->mProcessed)
{
std::cout << "W ";
tTempCellPtr->mProcessed = true;
tTempCellPtr = tTempCellPtr->mWest;
continue;
}
}
}
else std::cout << "No Exit Found";
  
}

MazeEscape.cpp

#include <iostream>
#include "Maze.h"

int main()
{
Maze tTestMaze("SampleMaze.txt");
tTestMaze.SolveMaze();
}

SampleMaze.txt

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X XXXXXXXXX XX X X XEX
X X X XX XXX XXXX XXXXXXXXXX X X
X X XXX X X XX X X X
X X X X X XX X XXX XXXXXXXXXXXXXXX
X XXX X X X XXXX XXXXXXXXX XXXXXXX
X X X X X X X XXX X
X XXXXX X X XXXXXX X X X X XXXXXXXXX X
XSX X X X X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compile the program with the SampleMaze.txt file in the same directory.

Hope this helps!

Please let me know if any changes needed.

Thank you!