CS 101 (Spring 1999)
Lab 7: Mazes and Monsters (Part 1)

Lab Assigned Design Due
(Mondays 2 PM)
Lab Due
(Fridays 2 PM)
19 Mar 22 Mar 26 Mar

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 in the next lab to interconnect two specific nodes of the network.

Another view of this assignment: In this lab you create a maze. In the next lab, you will help a monster look for cheese in the maze.

OK, I confess: the true nature of this lab is to teach you the design and use of an ADT (abstract data type) for a set. But the maze and network applications will make this more fun. Moreover, the maze serves as a visualization that can help you debug and test your set ADT.


Goals:

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

The design will be discussed Monday in class. In Lab, your graded design will be returned. No other handouts or code will be issued. So, think carefully about your design!


Before starting:

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

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

import cs101.terminal.*;
import cs101.canvas.*;

Particulars

A new building has been constructed on our campus. This building is unusual, in that its inhabitants will consist of robots without eyes. 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.

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?)

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. 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

Startup.java
This class is provided for you.
  1. The List class is tested.
  2. The RoomSet class is tested. For this test, two rows of rooms are created. The transcript will show the order in which rooms are unioned. When your code works properly, the rooms will become the same color when their sets are unioned.
  3. The Maze class is tested. A 3x5 maze of rooms is generated. Ten times, the doors are closed and randomly opened according to the instructions of this lab. When your code works properly, each iteration should show you a valid maze.
Room.java
This class is provided for you.
Room(int row, int col, int pixs, CS101Canvas canvas)
Constructs a room for the maze. The address of the room is specified by the row and col. The location of the room on the canvas is determined by its row and column. The pixs parameter specifies the size of the room's rectangle.
void init()
Resets the room to its initial state. Doors are closed and the room is in its own RoomSet.
void nowMemberOf(RoomSet set)
Makes the room now part of the specified set. The room and its (potential) hallways turns the color of the set.
The class also contains methods for connecting the room to each of its neighbors; see the code for details.

List.java

This class is provided for you, as described in class. It is a generic list, suitable for subclassing. Its public methods can be called on any subclass of List. Its protected fields and methods are available only within the subclasses.


What to turn in:

Design (due Monday)
  1. Complete a design cover sheet.
  2. Complete the code (on paper is fine) for RoomList.java that extends List.java. Specifically, fill in the methods
    • RoomList(Room, RoomList) (constructor)
    • Room getRoom() returns the room contained in this list element. Be sure to cast appropriately!
    • RoomList getRestRooms() returns a reference to the rest of the rooms in the list.
    • Room findRoom(int n) finds the nth room. For this, you must use List.java's find method, callable from the subclass as find(int)
  3. Think about (but don't turn in) what must be done to complete HorizHall and VertHall, classes that respectively represent horizontal and vertical hallways betwee rooms.

    Design (and turn in) the superclass Hall that can be extended to create HorizHall and VertHall. As a hint, consider the following questions:

    • What do the two kinds of hallways have in common?
    • How do we want the two kinds of hallways to behave differently?
    This will be discussed Friday in lecture.
  4. Describe how you will pick a random Color for a RoomSet. You will have to learn how Java encodes a color, which is similar to how we enocde a Card in Lab 6.
Implementation (due Friday)
  1. Complete a code cover sheet.
  2. Provide a transcript from your self-tests.
  3. Provide a printout of any files you have modified (see approach below).
  4. Be prepared to demo in lab.

Suggested implementation approach:

(The files contain some more specific instructions.)

  1. Implement and test RoomList.
  2. Implement and test RoomSet.
  3. Implement and test RoomListList.
  4. Implement and test Hall, VertHall, and HorizHall.
  5. Complete your testing.


Last modified 21:16:01 CST 20 March 1999 by Ron K. Cytron