MazeGenerator (c++ program)

Using DFS to define a MazeGenerator and MazeSolver

maze generator
The required algorithm
The required algorithm must generate a ​perfect maze​. Viewing a maze as a two-dimensional
matrix of square cells, a perfect maze is one in which any two cells are connected by a
single unique path. An important consequence of a maze being perfect is that all cells in a
perfect maze are reachable from the starting point by some unique path, meaning that
perfect mazes are guaranteed to have a solution. They’re also guaranteed to have a unique
solution, which makes them more interesting to solve.
To generate a perfect maze, you’ll use a recursive algorithm to “dig tunnels” of various
lengths. It starts with a maze in which all of the possible walls exist (i.e., a wall exists on
every side of every cell), then continues removing walls until a perfect maze has been
constructed. Naturally, it requires some care not to remove walls that would cause the maze
to be imperfect; in our tunnel-digging algorithm, we have to be sure we stop digging before
we knock out walls that would lead to places we’ve already been.
The algorithm works, then, by starting at a particular cell (and it doesn’t matter, ultimately,
which cell you start from), and does the following:
●
●
Mark the current cell as “visited.”
While the current cell has any adjacent cells that have not yet been visited…
○ Choose one of the unvisited adjacent cells at random. Randomness is
important here, or your algorithm will always generate the same maze.
○ Remove the wall between the current cell and the cell you just chose.
○ Recursively call this algorithm, with the chosen cell becoming the current cell.
As you generate your maze, you’ll need to call member functions on the ​Maze​ object that
was provided as a parameter. Don’t assume anything in particular about that ​Maze​ object,
other than it has the correct width and height; make any changes you need to make in order
to achieve the correct result, and make sure it works regardless of what walls are in place (or
not in place) when your algorithm is called
maze solution
The required algorithm
The required algorithm must solve the maze using a recursive algorithm with ​backtracking​. A
backtracking algorithm is one that recursively investigates all of the possibilities by moving
down a path that hopefully leads to a solution and then, if that path fails, backing up to the
nearest place where some untried alternative is available and trying another path. While you
could potentially implement an algorithm like this iteratively, it turns out to be a lot less work
to do so recursively, as the process of recursion will naturally and automatically manage
details that you would otherwise have to manage yourself.
I’ll leave the details of this algorithm as an exercise for you to figure out. If you understand
the maze-generating algorithm above, it should not be a big step to design the maze-solving
algorithm.
As your algorithm seeks a solution, you’ll need to call member functions on the ​Maze​ and
MazeSolution​ objects that were provided as parameters, though note that the ​Maze​ has
been passed as a constant (because you shouldn’t have to change a maze in order to solve
it).