Assignment Goal
The goal of this assignment was to write a method that could find a path through a randomly generated
maze. Given that the maze was generated recursively, I felt it was appropriate to make the solver
recursive as well.
Design Process
The biggest issue with the randomly generated mazes was that most of them were unsolvable. That is,
there was no path from the top left corner (defined as always being the starting point) and the bottom
right corner (always the ending point). I placed a special “start” character and an “end” character in the
respective positions, instead of the normal blank. However, I realized that this was not needed as start is
always maze[1][1] (maze[0][0] is the corner of the outer wall), and the end is always
maze[LEVEL_HEIGHT – 2][LEVEL_WIDTH – 2] (subtract 1 for 0 index, and subtract 1 again to get out of
the corner for the outer wall), and so I could check for the ending value, rather than need a special
character. The special character could still be useful if we wanted to allow any position to be the end
point.
The algorithm essentially checks each adjacent position in the matrix in a clockwise fashion.
Base Cases
The first base case is to check if we are at the end of the maze. If we are, we have successfully traversed
the maze. The second is to ensure that we are checking a blank spot. If the current spot is a wall, we
cannot go this way and must back up. If the current spot is marked as part of the path, we are already
considering this spot and must back up, otherwise we may get in a loop of continually checking the same
spot over and over.
Clockwise Recursive Order Checking
If neither base case is true, we mark the current position as part of the path. We then do a recursive call
to the position maze[currentY][currentX + 1], which is the position to our right. If it returns false, we
repeat the call on the spot below us. If that fails, we check the spot to our left, and then above us. In this
way, we check all four possible moves from our current position. If all four fail, we re-mark the current
position as a blank to remove it from the path before returning false.
Testing
First, I ran the provided code without any edits to ensure it compiled.