ICS 23 / CSE 23 Summer 2012, 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 and, when those weren't satisfying enough, 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.

While I became less enamored with mazes as I got older, I became more interested in computer science, which provided a fresh reason to consider mazes again; in particular, I considered how software could generate a challenging maze and also solve one. As I learned more about computer science, the solutions became evident.

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 along with its solution. It is capable of animating the maze generation process step by step, so you can see a maze come to life; similarly, it can animate the search for a solution. This functionality is contained within a graphical user interface (GUI) that looks like this:

Screenshot of Project #1 GUI

The maze is displayed along the left side of the GUI and takes up the lion's share of the screen real estate. Along the right side are options that you can set. 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 — your generator with my solver, your solver with my generator.) 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, using the provided generator to create a maze and the provided solver to solve it, including the animation. That will show you roughly how the program should behave when you've finished your own generator and solver, though you should be aware that my provided generator and solver use different algorithms than yours will, so don't be surprised when you're finished if your versions and my versions appear very different when you animate them.

Starting point

All of the code that you'll need to complete this project is included in this zip archive. Some of that code is provided as .java files in a directory called src, along with comments that will help you to understand it; this is the code that you'll need to understand in order to finish the project. Most of it, however, is provided in compiled form as a file called Dark.jar in a directory called lib. Dark.jar is what is called a JAR.

What is a JAR?

JAR is short for Java ARchive, which is a format for distributing a collection of compiled Java classes as a single file. JAR files typically have names that end in .jar. The file format itself is actually nothing special: it's actually just a zip file containing .class files (i.e., compiled Java classes). (If you don't believe me, try to unzip it using whatever tool you typically use to unzip files. You might first need to change its name to end in .zip, depending on how your tool is configured.)

There are other things you can put into JARs (such as manifest files), but we didn't end up needing them here. Ours is just a collection of compiled Java classes.

Setting up an Eclipse project to use a JAR

If you're using Eclipse, setting up an Eclipse project for your work here will require a couple of unfamiliar steps. Here's what you should do to get started:

Extract the provided Dark.zip starting point somewhere temporarily. You should see two directories: src and lib.
Create an Eclipse project, as you normally would.
Copy the .java files from the src directory in your temporary area into the src directory of your Eclipse project.
Create a lib directory in your Eclipse project.
Copy the Dark.jar file in the lib directory in your temporary area into the lib directory of your Eclipse project.
Right-click on your project in Package Explorer within Eclipse and select Refresh. You should now see the .java files and the lib directory listed within your Eclipse project. Notice, too, that you'll see a handful of errors in the Problems window in Eclipse; the program won't compile until we add Dark.jar to the "build path" (i.e., the things that Eclipse includes in the program when it compiles it and prepares it to be executed).
In Package Explorer within Eclipse, expand the lib directory in your Eclipse project so you can see Dark.jar within it. Right-click Dark.jar, select Build Path from the menu, then Add to Build Path.
You should no longer see errors in the Problems window. The program now compiles and is ready to run.

How to run the program

The provided Dark.java file contains a main() method that launches the user interface. To run the program, execute the Dark class.

What you need to work on

You'll only need to work on two classes: StudentMazeGenerator and StudentMazeSolver, though you can feel free to write additional classes if you want. Everything else is to be left as-is.

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. 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 unique solution, which makes them more interesting to solve.

To generate a perfect maze, you'll use a recursive algorithm that appears 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 each 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 make our maze imperfect.

The algorithm works by starting at a particular cell (and it doesn't end up mattering 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 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 along the way. 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.

(When watching the animated version of both your maze generator and the provided one, you may notice that the provided maze generator uses a very different algorithm from the one I described above. This is intentional; don't feel like yours has to work like mine. 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. Toward the end of this quarter, time permitting, we'll talk in lecture about how this algorithm works.)

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. 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. (Note that the provided maze solver, again, uses a very different algorithm than the one you'll be aiming for here. Later this quarter, when we talk about tree traversals, we'll characterize the difference between your approach and mine more concretely.)

As with the maze generating process, in addition to solving the maze, your method should make the appropriate calls to the given MazeSolverListener object as your potential solutoin changes, so that the GUI will animate the process.