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 X
s 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);
}
}
}
}