Maze Traversal

Introduction

In this assignment you are required to simulate a maze traversal using so called recursive backtracking (the algorithm is given below).

The grid of #s and 0s in the following Figure is a two-dimensional array representation of a maze. The #s represent the walls of the maze, and the zeros represent locations in the possible paths through the maze. In the maze, you can move one step at a time in the following four directions: up, down, right, left, no “diagonal” moves are allowed. A move can be made only to a location in the array that contains a zero.

# # # # # # # # # # # #
# 0 0 0 # 0 0 0 0 0 0 #
0 0 # 0 # 0 # # # # 0 #
# # # 0 # 0 0 0 0 # 0 #
# 0 0 0 0 # # # 0 # 0 0
# # # # 0 # 0 # 0 # 0 #
# 0 0 # 0 # 0 # 0 # 0 #
# # 0 # 0 # 0 # 0 # 0 #
# 0 0 0 0 0 0 0 0 # 0 #
# # # # # # 0 # # # 0 #
# 0 0 0 0 0 0 # 0 0 0 #
# # # # # # # # # # # #

Write a recursive function called mazeTraversal, to walk through a maze like the one shown above.

The function mazeTraversal should attempt to locate the exit, it should also place the character 'x' in each square in the path.

In mazeTraversal you are required to implement the following recursive algorithm:

• From the current location in the maze, try to move one space in one of the four directions (down, right, up or left).
• If it is possible to move in at least one direction, call mazeTraversal recursively, passing the new location in the maze as the current location.
• If it is not possible to go in any direction, return to the previous location in the maze and try a new direction from that location

This recursive algorithm finds the exit (assuming there is an exit). If there is no exit, you will arrive at the starting location again.

Program the function to display the maze after each move so that the user can see how the maze is solved. The final output of the maze should display the path that solves the maze.

Class Maze. The Maze class should have:

• Two private instance variables – int size, char **maze;
• Constructor “Maze(char **c, int size)” – takes as an argument an n-by-n two-dimensional character array that contains only #s and 0s.
• Public function void mazeTraversal(int a, int b)” – tries to “solve” the maze. Parameters a, b represent the entry point to the maze. Recursive algorithm for the mazeTraversal is described in the previous section.
• friend ostream &operator<<(ostream &stream, Maze &m) – to print maze m in a tabular format.
• Private function void mazeGenerator()” – randomly creates an n-by-n (3010≤≤n) Maze object which has an entry point on the left side. The algorithm for mazeGenerator should be as follows:
  • You start with 2-dimensional n-by-n array maze containing only #s, and then you “dig” your way through it until reaching a border, marking the visited cells with 0s.
  • The entry point is maze[n/2][0]
  • First move is to the right, after that you chose randomly any of four possible directions to move.
  • The function stops when it reaches a border.
• Default constructor Maze() – calls the mazeGenerator.

main() function.

In the main function you should create three Maze objects:

• One on the figure in the section 0.
• A 12-by-12 maze that has an entry point but does not have an exit. You should design it yourself.
• A randomly generated maze object

Then the mazeTraversal function should be called on each of the created objects.