2
\$\begingroup\$

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);
            }
        }
    }
}
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – A Coder Apr 27 '16 at 22:48
  • \$\begingroup\$ 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 :) \$\endgroup\$ – user104030 Apr 27 '16 at 23:07
  • \$\begingroup\$ 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); }' \$\endgroup\$ – A Coder Apr 27 '16 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.