Project 4: Mazes

CSE 143
Summer 1998

Introduction

For this project, you will write a program that generates a random maze and solves it. This will involve the construction of several interesting classes. The dimensions of the maze will be taken as input to the program, and are not bounded by any fixed maximum. Therefore, it will be necessary to use dynamic memory to manage the maze data structures.

Mazes are a challenging and satisfying computer science problem. The algorithms for generating and solving them have deep roots in computer science and come up again and again in different disguises. But the best part of this project is that we'll apply these algorithms to generate mazes! Take a look at an example of the kind of output you'll be able to generate from this program.

There are lots of people who have done maze-related programming out in the world. Here are some links that might be of interest if you want to learn about mazes:

Olin Shivers's maze generation page: A good but technical explanation of the algorithm we'll be using in this assignment. Also comes with a really nice program for generating mazes.
Mazes: An excellent online maze-generation web page.
Peter's maze page: claims to have a Java maze applet, but it seems to be missing.
The Amazing Maze Generator: a nice web interface to maze generation.
Maze Applet: you'll need Java for this one. A simple maze applet which allows you to visualize the solution process.

A Note

The specification for this homework is very long. But don't panic! It's long so that we can give you lots of details about every aspect of the assignment, not because this assignment is suddenly so much more difficult. In fact, this web page is a lot longer than the solution to the project!

Working in Pairs

You are permitted to work in groups of at most two for this assignment. Here are the rules for working in groups. Please read them carefully.

The rules that applied to you as an individual for previous assignments apply to you as a pair for this assignment. That means that although you will share all knowledge and code with your partner, you are not permitted to share code with other groups. Of course, you are still encouraged to think about the project in groups of any size, as long as your discussion is abstract and no code is produced.
If you work with a partner, hand in only one assignment. You should absolutely not both hand in the assignment. Please coordinate with your partner before turnin to make sure that only one of you submits the assignment.
Both of your names and student IDs should appear at the top of every file you submit.
All partnerships must be approved by the TAs of both partners, no later than Monday, July 27th, 1998. Partnerships not declared by July 27th will not be allowed. Please contact your TAs if you are interested in working with a partner.

Working With Mazes

We'll only be working with rectangular mazes. Conceptually, a maze is a grid of cells. The object of the maze is to find a connected path from the top left corner to the bottom right corner. Every pair of neighbouring cells is either connected with a path or separated by a wall. For example, in the following maze

		+-+-+-+-+-+-+-+
		|   |A|B|   | |
		+-+ + + +-+ + +
		|   |C    |   |
		+-+ + +-+-+-+ +
		|             |
		+-+-+-+-+-+-+-+

The cells A and C are connected with a path, but A and B are separated by a wall. Of course, not every configuration of walls and paths will be a very satisfying maze. Here are two examples of "bad" mazes:

		+-+-+-+-+-+ 		+-+-+-+-+-+
		| | |     | 		|         |
		+-+-+-+-+-+ 		+ + + + + +
		|   |     | 		|   |     |
		+-+ +-+-+-+ 		+ + + +-+ +
		|     |   | 		|         |
		+-+-+-+-+-+ 		+-+-+-+-+-+

The maze on the left is "too hard" (impossible, really) because there is no unblocked path from start to finish. The one on the right is "too easy" because there aren't enough walls.

To complete the definition of a maze, we need to specify that for every two cells in the maze, there is a unique path between those cells that doesn't retrace any steps. It turns out that this will guarantee that there are neither too few nor too many walls.

Generating Mazes

How would you go about generating a maze? There are a number of possible solutions, but I'll present one in particular here. Of course, you're not required to use this technique, but I strongly encourage you to do so.

Start with a maze that's completely filled in with walls:

	+-+-+-+
	| | | | 
	+-+-+-+
	| | | |
	+-+=+-+
	| | | |
	+-+-+-+

Choose a wall at random (but don't choose a wall from the boundary of the maze). If breaking down that wall doesn't make the maze too easy, break it down. The maze becomes too easy when it contains a loop (a path from a cell back to itself), because for any two cells in the loop, there are two distinct paths between those two cells.
```
	+-+-+-+
	| |   | 
	+-+-+-+
	| | | |
	+-+-+-+
	| | | |
	+-+-+-+
	
```

Repeat this process for each wall in the maze:

	+-+-+-+    +-+-+-+    +-+-+-+    +-+-+-+    +-+-+-+    +-+-+-+    +-+-+-+    +-+-+-+
	| |   |    | |   |    | |   |    | |   |    | |   |    | |   |    | |   |    | |   | 
	+-+-+-+    + +-+-+    + +-+-+    + +-+-+    + +-+ +    + +-+ +    + +-+ +    + + + +
	| | | | -> | | | | -> | | | | -> | | | | -> | | | | -> |   | | -> |   | | -> |   | |
	+-+-+-+    +-+-+-+    +-+-+-+    +-+ +-+    +-+ +-+    +-+ +-+    +-+ + +    +-+ + +
	| | | |    | | | |    |   | |    |   | |    |   | |    |   | |    |   | |    |   | |
	+-+-+-+    +-+-+-+    +-+-+-+    +-+-+-+    +-+-+-+    +-+-+-+    +-+-+-+    +-+-+-+

To know whether breaking a wall would cause a cycle, we use a special set-like data structure. Every cell belongs to some group of cells in the grid. Two cells are in the same group if there's a path between them in the maze. When we break down a wall, we check whether the cells on either side of that wall are in the same group. If they are, there's already a path between those cells, so we don't break the wall. If they're not, we break the wall, and combine the two groups.

Given all the details above, here's a simple maze-generating algorithm:

Initialize the maze so that every wall is on
For each wall in the maze (in random order)

If the cells on either side of that wall are not in the same group

Break down the wall
Combine the groups of those two cells

To walk across all the walls in random order, it's convenient to put them all in a big collection and then walk through the collection in random order.

Solving Mazes

Once you've generated a maze, you need to know how to solve it. It's possible to solve a maze using a stack-based algorithm. The basic idea is use a stack to remember the path you've taken so far in the maze. Then, while the stack is not empty, you try to extend the current path by one step, by finding an unvisited cell adjacent to the current cell (of course, you've got to be careful to avoid trying the direction you came from - that could cause you to go into an infinite loop!)

If you ever reach the goal cell, you can just unwind the stack, following the path in reverse, marking your steps as you go. When the stack is empty, you've returned to the start cell and the path to the solution should be marked.

Interestingly, this stack-based approach becomes an even more elegant recursive solution. We haven't talked about recursion yet in this course, so you're not required to attempt a recursive solution. But if you're comfortable with recursion, you're welcome to think about this approach.

Detailed Specification

Here's a breakdown of all the files associated with this project:

dir.h

To navigate around in a maze, you'll need some abstraction of direction. If you look inside maze.h, you'll notice that functions like isClear and move refer to a Dir type. In dir.h, you'll say exactly what the Dir type is. You're free to decide on any method for representing the Dir type. Remember - there are several ways of creating new types in C++. Which one is right for this task? Of course, there are several possible answers.

dir.cpp

You may decide to define some functions that operate on variables of type Dir. If you do define any functions, put them in here.

cell.h

The Cell class is the class you should use to store information about one cell in the maze (in other words, a maze will be some sort of collection of Cells). A cell needs to contain at least the following information:

From this cell, in what directions can you go?
Has this cell been marked?

You are free to modify any part of this file. You can add new public and private members. In fact, you will need to add new public members so that the maze solver can work. Of course, it's still important to design a reasonable abstraction, so you should think carefully about what the interface to a cell should be.

We provide you with three member functions: inSameGroup, combineGroups and getGroup. These functions rely on the private data field parent. These functions will help you implement the maze generation algorithm.

cell.cpp

The implementation of the Cell class. This file comes with the implementations of inSameGroup, combineGroups and getGroup. You should fill in the rest of your Cell implementation here.

maze.h

The specification of the Maze class. This class provides a maze abstraction with a simple navigation facility. Maze navigation is not unlike list navigation, except that from any cell in the maze, it's possible to move in any of four directions (with lists, it was only possible to move forward, using List::advance()).

The public section of maze.h is fixed: you may not provide additional public members! You may add anything you like to the remainder of the file. That includes extra #include directives, global variables or functions, and private member data and functions.

At the bottom of maze.h is an inline function definition. The exact meaning of the keyword inline is beyond the scope of the course. Suffice it to say that by declaring the function to be inline, you make it possible to define it inside the header file.

maze.cpp

The implementation of the Maze class. You are required to implement the following methods of Maze:

Maze::Maze( int width, int height )

The constructor for the Maze class. This constructor takes the desired width and height of the maze as parameters, and constructs a new, random maze with those dimensions.

void Maze::print( ostream& os )

Write a textual representation of the maze to the output stream os. The representation of the maze should be (2*width+1) characters wide and (2*height+1) characters tall, and made up entirely of the characters ' ', '|', '-', '+' and '#'.

The best way to understand exactly what needs to be drawn is to look at some sample output. For reference, here's a brief explanation. Each cell in the maze will be associated with nine characters in the printed representation:

+	a	+
b	c	d
+	e	+

The corners will always be filled with plus signs. If there is a passage to the north from this cell, then a will be a space. If there's a wall to the north, a will be a minus sign. e is similarly defined for passages to the south. b and d are also defined this way except that we would use a vertical bar ('|') for vertical walls. Finally, if the given cell is marked, c should contain a hash ('#'). Otherwise, c should contain a space.

Note that in the printed representation, a cell shares the eight characters forming its boundary with its neighbours in the maze.

void Maze::reset()

Reset every cell in the maze. Note that the shape of the maze itself does not change. But the marks in each cell get cleared.

void Maze::start()

Like List::start(), reset the maze cursor to the start cell of the maze. The start of the maze is always defined as the top left corner.

bool Maze::move( Dir dir )

Attempt to move the maze cursor in the direction given by dir. Of course, moving in some direction might not be possible at the current position in the maze. This method should return a boolean indicating whether the move was successful. If the move was unsuccessful, the maze instance shouldn't change in any way.

Cell& Maze::getCell()

Return a reference to the Cell instance associated with the current cursor position. You want to return a reference so that the maze solver can mark that cell when it's part of the solution path.

bool Maze::isClear( Dir dir )

Is it possible to move from the current position in the maze in the direction given by dir?

bool Maze::isGoal()

Is the current position the goal position? The goal position is always the bottom right corner of the maze.

bot.h

In this file, you should declare a class Bot. The bot's job is to roam around a maze and eventually find the solution path. It should make sure to mark every cell in the solution path so that when the solved maze is printed out, the path is visible.

If you look at main.cpp, you'll see how bots are used. You'll need to provide at least two public functions inside the Bot class:

A constructor that takes a reference to a Maze.
A solve method that takes no arguments, and returns a boolean indicating whether it successfully solved the maze.

You're free to define any other functions or data you choose inside the Bot class.

bot.cpp

The implementation of the Bot class. Note that you'll need to hold on to the Maze reference passed to the constructor inside the Bot instance. I recommend that you use a private variable of type Maze&, and assign to it from the constructor using memberwise initialization.

collections.h

The suggested maze-solving algorithm relies on a stack. If you define your own stack class, put its declaration in this file. If you decide to use any other collection classes to implement other parts of the homework (this is certainly conceivable), then put their declarations in this class as well.

collections.cpp

Put the definitions of any classes declared in collections.h in this file.

main.cpp

The client program. This file is provided to you in finished form. You will not be asked to modify it or submit it. Of course, you are free to change main.cpp as much as you like while working on the project. You might find it useful to change main.cpp to help with debugging, for instance by writing the maze output to a file instead of to the screen.

The client accepts three numbers from the user. The first two are the width and height (in cells, not in characters) of the maze. The third number is a seed for the random number generator. The seed is just an arbitrary number that's used to initialize the function that generates random numbers. It's not important to know how the seed works. What's important is that you call srand with that seed (main.cpp does exactly that). Using the same seed twice will result in the same sequence of random numbers (and therefore the same mazes, which is useful for debugging).

The client's job is simple: create an instance of Maze, print it without the solution, then solve it and print it out with the solution.

Suggested Approach

Here's a suggested order of things to do. You are in no way required to do things in this order.

Re-read the assignment, paying particular attention to the conceptual sections on how to generate and solve mazes.
Download and run the sample solution, to get a better idea of what we expect.
Step away from the computer. Go somewhere where there aren't any computers, and think about mazes. Try to visualize the algorithms for generating them and solving them. If you sit down in front of the computer with some intuition for how you intend to solve the problem, you'll find that the programming part is less painful.
One way to build up your intuition is definitely to try this stuff on paper. Get some graph paper and try to draw some mazes. Print out some mazes from the sampole executable and try to solve them. Think about how you solve a maze as you're solving it.
When you're ready to program, start by laying things out at a high level. Decide on the names of any classes you intend to write, and write the parts of the header files you know you'll need. This is the easy part of programming, and simply writing it in correctly the first time makes life easier later on.
Write dir.h and dir.cpp. Choose a way to build a type that represents compass directions, and write its declaration. Then write any functions you think might make manipulation of directions easier.
Modify the Cell class so that it stores information about what neighbouring cells are connected by passages.
Start writing the Maze class. Start by choosing a representation of a grid of cells. Remember that your representation has to allow for arbitrary width and height. If you want to put off the difficulties of dynamic memory, try starting with a fixed width and height for now.
Try getting constructor to create a maze with no broken walls -- a maze where every cell is disconnected from every other. Then get the print method working.
Implement maze generation. Read the "Generating Mazes" section of this document again. Note that you'll need to iterate across all the walls of the maze in random order. That means you'll probably need some sort of data structure that represents a wall of a maze. Of course, you don't need to keep instances of this struct around after the maze is generated. You should consider designing a structure whose instances exist only to help the maze generation algorithm (hint: what information completely specifies a wall of the maze?)
As was mentioned above, a good way to iterate across all the walls of the maze in random order is to put them all in a collection of some kind and randomly remove items from the collection until it's empty. What kind of collection would be good here?
A quick note about random numbers: computer-generated random numbers are almost never really "random". In fact, they're usually completely deterministic! But the important thing is that they don't follow any predictable pattern. The rand() function will generate integers that are distributed uniformly across their range. You can use it to generate numbers that are "random-like", or random enough for our purposes. The srand function intializes the random number generator so that it produces a repeatable sequence of random integers. This is really useful for debugging your program.
Design your maze-solving algorithm. That means sit down, away from a computer, and decide how the algorithm is going to work. Write down an informal description of the algorithm that you can refer to when coding up the solution. Practice using the algorithm on some randomly-generated mazes to see if it works. Decide what helper ADTs you'll need to implement maze solving.
Implement the helper ADTs in collections.h and collections.cpp. For the most part, this code can be adapted directly from code presented in lecture.
Implement bot.h and bot.cpp.

Executable

To verify that your solution is working correctly, we encourage you to compare it against our sample solutions. The following links will allow to download sample Windows and x86 Linux executables.

Turn-In

Homework 4 is due on Monday, August 3rd, 1998, at 8:00pm. You will turn in your homework using a form on the course web, and you will be unable to submit your homework after 8:00pm. Please plan your time so that you will not be trying to submit your assignment at 7:59.

When you're finished writing your solution, you can use the electronic turn-in form to submit it. Follow the instructions on that form (especially with regards to file naming conventions), print the receipt, and submit the receipt at the start of section, Tuesday, August 4th, 1998. For full credit, you must turn in electronically, print the receipt, and hand in that receipt in your section. You may also be able to drop your receipt in the drop box located on the first floor of Sieg hall, across from room 127. More details on this will follow.

If You Get Stuck

If you're having problems, there are a number of resources available for you.

If you need help with the lab environment or the online resources, go talk to a consultant in the IPL.

If you can't make progress in the actual assignment, please talk to the instructor or a TA. They are available during posted office hours, and sometimes by appointment. They will also occasionally help you out over email. You are invited to seek help from any available TA, not just your own.

You can discuss the assignment in general terms with other students. You can ask general questions on the student discussion list for this course, cse143@cs. But any code you write must be your own. For more details about what is and is not allowed, see the Software hygiene page.

cse143-webmaster@cs.washington.edu