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).