CS 101 (Fall 2000)
Lab 10: Mazes

Authors: Sergey Klibanov and Ron K. Cytron
Lab Assigned Design Due
(In class)

1 PM
Implement
(In Lab)
Demo
(In Lab)
Lab Due
(In class)
Friday
1 PM
13 Nov None 15-16 Nov 28-29 Nov 1 Dec

class-sponsored design

Overview:

You are surrounded by interconnnection networks: the Internet, the network serving your dorm room, the POTS (plain old telephone service) network. In this lab, you create a network structure that will be used to interconnect two specific nodes of that network.

Another view of this assignment: In this lab you create a maze and then help a mouse find the cheese in the maze.

OK, I confess: the true nature of this lab is to give you experience with the ADT we have been discussing in class: the set. But the maze and network anaologies are accurate. Moreover, the maze serves as a visualization to help you debug and test your solution.


Goals:

By the end of this lab, you should This lab contains two parts, design and implementation, due on the dates shown above.


Before starting:

[[[ Download PC zip ]]]
Zip includes:

Remember to type the following lines at the top of any files that use the canvas classes.

import canvas.*;

Particulars, Maze Construction

A new building has been constructed on our campus. This building is unusual, in that its inhabitants will consist of robots without eyes. This building contains a rectangular grid of square rooms. Each room has four walls, and each wall is equipped with a door for exit from the room. When the doors of two adjecent rooms are opened, a hallway is formed, so people can travel freely between the two rooms.

However, this building has a strange property: if ever a set of rooms is interconnected to form a loop, the world as we know it would cease to exist. (How's that for a strict building code?) Actually, a robot navigates the building by always keeping one of its "hands" in contact with a wall surface.

If

then a robot can start at any room and eventually reach each room in the building by maintaining contact with a wall surface.

When the building was constructed, the rooms were placed in the buildings with their doors closed. Then, a painter was airdropped into each room to paint the room.

Currently, there is a painter inside each room. Strangely, each painter is busily busily painting his or her room a unique color. Unexpectedly, the roof arrives and is placed on the building. Consequently, with all doors closed, each painter is trapped inside his or her room, as shown below

Initially
Each solid square is a room. You can see the outline of the potential hallways, but in the picture, all doors are closed.

The picture shows there are 15 sets, with one room in each set.

Suddenly, each painter is overcome by an urge to escape and paint the entire set of rooms his or her unique color. Frustratingly, each painter is trapped and does not know which doors to open, given the strange properties of this building. (You know: if ever a set of rooms is interconnected to form a loop, the world as we know it would cease to exist.) Randomly, painters in adjacent rooms call to each other to see if the doors between them should be opened. How do they decide if it is safe?

If the two rooms are currently in different sets (painted different colors), then the doors between them can and should be opened. Otherwise, the doors must not be opened because a loop would be formed.
When the doors are opened, the two painters are necessarily in rooms of different colors.
Above, you see two rooms with their doors closed. The potential hallways are shown in outline form. Above, the left room has opened its East door and the right room has opened its West door. As a result, a hallway is formed and people can move between the two rooms.

To save time, the painters agree to paint the smaller set of rooms the color of the larger set. If both sets contain the same number of rooms, the painters arm-wrestle or throw a fair coin to see who wins.

The process of opening doors and painting rooms continues.

Before
After
This picture shows an intermediate point in the computation.

Here, there are three sets of rooms: light-green, black, and dark-green.

One step later, two rooms in the bottom row are adjoined.

As a result, two of the sets have been merged. Because the dark-green rooms outnumber the black ones, the black rooms are painted dark-green as they are merged into the same set.

The process of opening doors continues until all the rooms are interconnected and painted the same color. At this point, all rooms are in the same set.

The computation is finished, and the potential hallways are erased.
  • There is one path between each pair of rooms.
  • A robot traverse the maze by keeping one "hand" on a wall.
Finally


Particulars, Maze Traversal

Let's assume that the new, robot-occupied, loop-free building has been successfully constructed. It is now time to simulate the progress of a robot through the rooms, as it starts in the upper-left room and tries to find the lower-right room.

The robot, being a methodical creature, eseentially does the following:

Upon entering a room, the robot knows which door it used to enter the room. It then (recursively) uses the room's other open doors to explore the rest of the building.
The maze is formed. There is a unique path between any pair of rooms. In particular, it is possible to traverse the maze, moving from the upper-left corner to the lower-right corner.

Above, you see the robot beginning to explore the rooms. As the robot makes progress through a room, the room is brightened (the robot turns the lights on). When the robot is done with a room, knowing it cannot be on a path to its final destination, the room is darkened.

The robot has found the destination. The dark rooms are abandoned and the bright rooms are on the path from the source to the destination. The robot traces its steps back to the beginning, making each room red as it goes.

Extra Credit:

You can use MyWorld, which in turn uses Java3D, to augment the display of your Room.explore() method. Download the zip containing a small demo package, as well as the texture images used by MyWorld.

You will probably want to see the javadoc of the classes included in the .zip file:

What to turn in:

Design
  1. Complete a design cover sheet.
  2. Describe the classes in your design. For each class, give its API.

    It may help to think about how you will represent a Maze, its Rooms, and its Hallways. Try to hide the representation as best you can; however, it may help to think of the Maze as a two-dimensional array of Rooms.

    Ideas for the design will be discussed in class.

Implementation
  1. Complete a code cover sheet.
  2. Provide a transcript from your self-tests.
  3. Provide a printout of any files you have modified.


Last modified 12:39:03 CDT 28 August 2000 by Ron K. Cytron