Searching a maze using DFS in C++

Question

I have started learning recursion and search algorithms, especially DFS and BFS. In this program, I have tried to make an implementation of a maze-solving algorithm using DFS. The program is working functionally, but as a beginner I am fully aware there are many possible areas of improvement.

If not in a specific way, what are some of the more general and possibly theoretical criticisms of my program? Keep in mind that the current product is based on an elementary understanding of C++ and search algorithms.

I have a Graph class for loading in the maze from an external text file:

#include <fstream> //ifstream
#include <iostream> //standard c output modes
#include <iomanip> //setprecision()
#include <vector> //vectors, including 2-dimensional
#include <cstdlib> //system("cls") to clear console
#include <stack> //stacks
#include <math.h> //sqrt()
#include <ctime> //clock in DelayFrame()
#include "Cell.h" //Class for individual unit "cells" of maze
class Graph
{
 public:
 Graph();
 virtual ~Graph();
 void LoadGraph(const std::string &fileName);
 void DisplayGraph();
 void DFS(int r, int c);
 void DelayFrame(clock_t millisec);
 private:
 int height; //# of rows of maze
 int width; //# of columns of maze
 int numPaths; //# of possible path positions in maze
 int pathDistance; //Total distance of correct position sequence
 char buffer; //To store char elements from external text-file
 const char obstacle, goal, path; //Constant chars to represent elements of maze
 double cellsVisited; //# of cells visited; does not contain duplications of cells
 std::vector <std::vector<Cell*> > maze; //Stores maze
 std::vector <Cell*> cells; //Stores individual rows of maze to be allocated into maze 2-dimensional vector
 std::stack <Cell*> cellSequence; //Stack of cells to store sequence of positions in use
};

I have also implemented a Cell class for the individual "cells" in the maze:

class Cell
{
 public:
 Cell(int r, int c, char symbol);
 virtual ~Cell();
 int GetRow();
 int GetColumn();
 char GetChar();
 void SetChar(char toReplace);
 char GetCounter();
 void IncrementCounter();
 protected:
 int r; //Row of cell
 int c; //Column of cell
 char symbol; //Symbol of cell
 int counter; //Number of visits; initialized to be 1 in cell constructor
};

Here is the loading member function in the Graph class (I am wondering if I can detect a new line and skip the extraction without extracting first and then redoing it):

//Loads in the maze from an external text-file
//Gets # rows, # columns and all symbols for all elements in maze
void Graph::LoadGraph(const std::string &fileName)
{
 std::ifstream fileData(fileName.c_str());
 //# rows
 fileData >> height;
 //# columns
 fileData >> width;
 //Don't skip blank spaces
 fileData >> std::noskipws;
 //Adds elements from external text-file to one row of the maze
 for (int row = 0; row < height; row++)
 {
 for (int col = 0; col < width; col++)
 {
 fileData >> buffer;
 //If there is a new line character, take the next character
 if (buffer == '\n')
 {
 fileData >> buffer;
 }
 cells.push_back(new Cell(row, col, buffer));
 //If there is a new path position, increment the counter
 if (buffer == path)
 {
 numPaths++;
 }
 }
 //Pushes the row into a 2-dimensional vector
 maze.push_back(cells);
 cells.clear();
 }
 //Close file
 fileData.close();
}

Most critically, here is the implementation of DFS I am using to try to search the maze. The end (goal) of the maze is represented by a $ symbol. Walls are represented as Xs and paths are represented by the blank space ' ' symbol.

Basically, it keeps searching until it reaches the goal, starting from position (1,1). It searches in all 4 directions, as long as the direction is not blocked by an obstacle and there is a neighboring unvisited cell; if neither is met, then it backtracks. If the goal is not reached once the stack is empty, then there is no solution. I realize this implementation is again not the most efficient, but I think it is relatively robust and has some additional functionality.

/*Depth First Search
Maze search starts at r = 1, c = 1
*/
void Graph::DFS(int r, int c)
{
 //Displays state of maze as it is being solved
 //Clears the console screen to make room for an "updated display"
 std::system("cls");
 DisplayGraph();
 //Pause for 200 milliseconds so user can monitor progression of search
 DelayFrame(200);
 //If goal is reached, stop
 if (maze[r][c] -> GetChar() == goal){
 //Declare array to hold 'solution set' for valid path
 int stackSize = cellSequence.size();
 Cell** solutionSet = new Cell*[stackSize];
 //Fill array with path positions
 for (int i = 0; i < stackSize; i++)
 {
 solutionSet[i] = cellSequence.top();
 //Remove the topmost cell once it has been added to array
 cellSequence.pop();
 }
 //Write dimensions of maze solved
 std::cout << std::endl << "# Rows: " << height << std::endl;
 std::cout << "# Columns: " << width << std::endl;
 std::cout << std:: endl << "Path Sequence: " << std::endl;
 //Display valid path positions in correct order as array elements
 for (int j = stackSize - 1; j >= 0; j--)
 {
 std::cout << "(" << solutionSet[j] -> GetRow() << ", " << solutionSet[j] -> GetColumn() << ") -> ";
 //Makes the display more optimal for viewing by approximately "equalizing" display x and y dimensions
 int interval = sqrt(stackSize);
 if ((stackSize - j) % interval == 0)
 {
 std::cout << std:: endl;
 }
 }
 //Don't forget position of goal at the end which is not in stack
 std::cout << "(" << r << ", " << c << ") = $" << std:: endl;
 //Delete dynamically allocated array
 delete solutionSet;
 //Total distance of path is the stack size + 1 for the goal cell
 pathDistance = stackSize + 1;
 //Writes path length
 std::cout << std:: endl << "Solved | # Steps in Path: " << pathDistance;
 //Writes #cells visited
 std::cout << std:: endl << " | % Cells Visited: "
 << std::setprecision(4) << cellsVisited / numPaths * 100 << " ("
 << cellsVisited << " / " << numPaths << " possible path positions)";
 }
 else {
 //Otherwise, push current cell to stack
 if (maze[r][c] -> GetChar() == path)
 {
 cellSequence.push(maze[r][c]);
 cellsVisited++;
 }
 //Set current cell as visited and mark it with #times visited - 1 (know how many repeats)
 maze[r][c] -> SetChar(maze[r][c] -> GetCounter());
 //Increment the number of times visited (prior)
 maze[r][c] -> IncrementCounter();
 //Goes through all 4 adjacent cells and checks conditions
 //Down
 if (r+1 < maze.size() && ((maze[r+1][c] -> GetChar() == path) || (maze[r+1][c] -> GetChar() == goal)))
 {
 r++;
 DFS(r, c);
 }
 //Up
 else if ((r-1 > 0) && ((maze[r-1][c] -> GetChar() == path) || (maze[r-1][c] -> GetChar() == goal)))
 {
 r--;
 DFS(r, c);
 }
 //Right
 else if (c+1 < maze[0].size() && ((maze[r][c+1] -> GetChar() == path) || (maze[r][c+1] -> GetChar() == goal)))
 {
 c++;
 DFS(r, c);
 }
 //Left
 else if (c-1 > 0 && ((maze[r][c-1] -> GetChar() == path) || (maze[r][c-1] -> GetChar() == goal)))
 {
 c--;
 DFS(r, c);
 }
 else
 {
 //No neighboring cells are free and unvisited, so we need to backtrack
 //Sets current cell to obstacle
 maze[r][c] -> SetChar(obstacle);
 //Remove current (top) cell from stack
 cellSequence.pop();
 if (cellSequence.empty())
 {
 //If the stack is empty, there are no neighboring cells that can be used and there is no solution
 std::cout << std::endl << "No solution: -1";
 }
 else
 {
 //Get row and column of last valid cell in stack and use those to resume search
 r = cellSequence.top() -> GetRow();
 c = cellSequence.top() -> GetColumn();
 DFS(r, c);
 }
 }
 }
}

Answer 1

Just a remark: every (or only most?) C lib has a corresponding C++ header with the name cNAME where NAME.h is the C equivalent (<ctime> and cstdlib are the C++ equivalents of <time.h> and <stdlib.h> respectively, but <iostream> is not a C lib). You can use <cmath> instead of <math.h>.

You don't need to write default ctor or dtor, only when you want a nondefault (in which case you no longer have an automatic default ctor, you have to write it if you want to use).

A virtual destructor is only needed when deriving from a class to make sure that the appropriate destructor is called when the derived object is deleted through a pointer to the base class.

If you write using std::string, you can spare writing std:: in front of string (same for the other std classes).

Use pre-increment instead of post-increment in the for condition (no useless copying).

Cell** solutionSet = new Cell*[stackSize];

You should/could use vectors here as well.

You could put all the display parts into a dedicated display function for sake of clarity.

When checking neighbours, you can only write DFS(r,c) after the four conditions (instead of 4 times in every condition). You need to terminate in the case that there is no solution (write return).

• A Coder: Thanks for the remarks! Some of the formatting conventions you have listed are quite useful. The destructors are virtual when you use the default class template, but they do not need to be virtual. I used an array instead of a vector since the size was predetermined by the size of the stack and an array is more memory-efficient; I took that into account when I was writing the code initially. There is no need to write return since the function is void. I had a dedicated display function which I did not include in this post since it was non-essential here, but yes you can trust it does exist.
• user104030: you don't need to write return in void but you can if you need the function to not execute the remaining code. You can start the next DFS only once after the r c changings, instead of 4 times, but in order to be able to put it after them, you have to prevent the branch that has no solution from executing that DFS, which happens by returning. That's what I meant :)
• A Coder: I rewrote a portion of it: if (cellSequence.empty()) { //If the stack is empty, there are no neighboring cells that can be used and there is no solution std::cout << std::endl << "No solution: -1"; } else { /*Otherwise, perform DFS again with the new values for r and c Note that by placing DFS(r,c) outside of the above conditions, it is possible to spare the need for separately calling DFS(r, c) multiple times*/ DFS(r, c); }'