A Maze can be defined in a file using X characters to represent walls, space characters to represent paths, and a $ character to represent the goal. The starting point is assumed to be location (1, 1) and the maze is assumed to have a border (walls). For a maze loaded from an external text-file, this program will show the sequence of positions to reach the goal or, if there is no solution, will indicate that no path is available. Additionally, this program has the option for the user to show the solve-state of the maze over time, with various speeds, as the program recursively searches through adjacent positions until it meets a terminating condition.
Choice of search algorithm is DFS; maze and individual cells of the maze were implemented using classes, consisting of separate .h and .cpp files. The graph class has the functionality to load in a maze configuration from an external text file into a multi-dimensional vector of vectors to pointers to cells. This configuration can then be displayed in the console window with a related member function in the graph class. The graph class has an in-built DFS function to search through the maze and determine the sequence of ordered positions from start to end if the maze is solvable; otherwise, the function indicates the maze has no solution. The cell class has the functionality to return the protected cell contents (row, column and symbol) to the graph class in the DFS function. The cell class also has the functionality to revise or amend cell contents, specifically the cell symbol, which is necessary to allow backtracking and prevent infinite recursion in the DFS.
The maze will be initially displayed on the console screen and the user will have the option to toggle the maze animation. When the maze is in the process of being solved, the new states of the maze configuration will be output to the console screen with appropriate delay length for the user to monitor each changing state, if active. An interesting feature of the “visited” symbols is that they indicate how many times a particular cell has been visited; whenever a cell is visited, the associated counter is incremented, starting from 1 for every visited cell. At the end, the final state will be shown and the path sequence and path length of the final path will be displayed. The percentage and number of cells visited in the maze of all possible path positions will also be shown.