ICS 23 / CSE 23 - Project #1: Dark at the End of the Tunnel

Introduction

When I was a little kid, I was fascinated by mazes. Whenever I saw a maze printed on a piece of paper, I had to grab it and try to solve it. I had soft-covered books full of them. I even tried drawing my own, though with the undeveloped skills I had at the time -- both in terms of being able to design a challenging maze, and also the more fundamental skill of being able to draw a straight line -- it proved to be a difficult proposition. As I got older, I discovered that software could do an excellent job of generating a challenging maze, and that it could also rather easily figure out a solution for one, though it wasn't until I was an undergraduate that I understood how.

For this project, you'll write a Java class that generates a two-dimensional maze of arbitrary size, and another Java class that solves one. This will give you more practice with understanding and using recursion to solve real problems. It will also provide you with an opportunity to make heavy use of pre-existing classes for which you have no source code; this is perhaps the most valuable real-world programming skill of all.

The program

This program displays a maze and a solution to it. It is capable of animating the maze generation process, as well as animating the search for a solution. Here is a screenshot of the GUI:

The maze is displayed on the left side of the GUI. Along the right side are the options. You can select either your own maze generator class or the one that I've provided; similarly, you can select either your own maze solver class or mine. (By providing you with a maze generator and a maze solver, you can test each of your classes separately.) You can also select the size of the maze before generating it, as well as decide whether you'd like to animate the maze as it's being generated and the solution as the maze is being solved.

Try running the program and using the provided generator and solver to create and solve a maze, including the animation. That will show you roughly how the program should behave when you've finished your own generator and solver (though my maze generator uses a different algorithm than yours will).

Starting point

All of the code that you'll need to complete this project is included in this Zip archive. Much of the code is provided in compiled (i.e. .class) form. The provided .java files are heavily commented.

You'll only need to work on two classes: StudentMazeGenerator and StudentMazeSolver. Everything else is to be left as-is.

How to run the program

The Dark class contains a main( ) method. To run the program, execute the Dark class.

Generating a maze

In the StudentMazeGenerator class, you'll implement a maze generation algorithm. There are lots of ways to generate mazes, but you'll implement one (relatively simple) algorithm in particular. Our algorithm will 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. As a consequence of this definition, all cells in a perfect maze are reachable from the starting point by some path, meaning that perfect mazes are guaranteed to have a unique solution.

To generate a perfect maze, you'll use a recursive algorithm that is a variant of depth-first searching. Recall depth-first tree traversals, in which one path in a tree is followed to completion before another path is followed. We'll generate a maze in much the same way. We'll start with a maze in which all of the possible walls exist (i.e. a wall exists on every side of each cell), then continue removing walls until we have a perfect maze. The algorithm goes like this:

Mark the current cell as "visited."
If 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 the algorithm, with the chosen cell becoming the current cell.

As you generate your maze, make sure that you make the appropriate calls to the given MazeGeneratorListener object. Essentially, any time your maze is altered, you should call a method on the MazeGeneratorListener. This notifies the GUI that a change has been made, causing the maze to be redrawn each time. Without making the right calls to the MazeGeneratorListener, the GUI will not animate the maze generating process.

(You may notice when watching the animated version of both your maze generator and the provided one, the provided maze generator uses a very different algorithm from the one I described above. This is intended. For fun, I implemented the provided maze generator using a "smarter," but more complicated, maze generating algorithm that generates mazes with more branches and, as a result, more difficult solutions.)

Solving a maze

In the StudentMazeSolver class, you'll implement a maze solving algorithm. Our algorithm will be a recursive one 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 place where the "mistake" was made and trying another path.

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 with the maze generating process, in addition to solving the maze, your method should make the appropriate calls to the given MazeSolverListener object. The MazeSolverListener should be notified whenever the solution has changed. This will allow the GUI to animate the solution.

Deliverables

You need only turn in your StudentMazeGenerator.java and StudentMazeSolver.java files, along with any additional classes you created, if any. You do not need to turn in any of the other files that were provided to you. Follow this link for an explanation of how to turn in your project.

Additional Work for Advanced Students

Do some research in maze building; find and implement an algorithm that produces more complicated mazes than the one we had you use here. Submit your new generator (in a file with a different name, of course) along with the required one. Don’t forget to comment your work well and to cite your sources.

Do the same with the solver; that is, use a strategy that produces a correct result but in a faster or more memory-efficient manner than the one provided. Submit your new solver along with the required one. Again, cite your sources and comment your work well.

Some additional minor rewrites by Alex Thornton, Summer 2004.
Incorporated a few phrases written by Norman Jacobson, Spring 2003.
Originally written by Alex Thornton, Fall 2002.