CS 101 (Spring 2000)
Lab 10: Design for Mazes

Lab Assigned
Design Due
(In class)

10 AM
(In Lab)
(In Lab)
Lab Due
(In class)
10 AM
4 Apr 10 Apr 11-12 Apr 18-19 Apr 21 Apr

This document contains the class-sponsored design, which you are free to use if you wish. You can take some or all of it---it's really up to you.

[[[ Download PC zip ]]]

Given to you:

This class is provided for you. You can use it like Line: it makes a rectangle object that can be added to a CS101Canvas. The API is different from rectangle objects we have used, so beware!
Rect(double c1x, double c1y, double width, double height)
Although the API takes doubles, you can supply int values for theese parameters.
void setColor(Color c)
Changes the rectangle's color to the supplied value.
This is a beefed-up version of what you have used previously. It now offers 256 colors.
Crayon(int which)
Supply which as an integer 0 <= which < 256, and a crayon is constructed with that color. These colors are randomly generated each time the program is run, so the nth color will change from run to run.
Color getColor()
returns the java.awt.Color that corresponds to this crayon.
This is provided for you. It is an interface that specifies what a set element can do.
boolean elEquals(Element other)
returns true iff this element equals the supplied one.
Set belongsTo()
returns the Set that currently contains this element.
This is provided for you. It is an interface that specifies what a set can do.
int sizeOf();
returns the number of elements in the set.
boolean isEmpty();
returns true iff the set is empty.
void insert(Element x);
inserts x into the set without duplication.
void delete(Element x);
deletes x if it is in the set.
boolean hasElement(Element x);
returns true iff x is an element of the set.
void union(Set other);
sets the set equal to the union of itself with the other set.
void intersection(Set other);
sets the set equal to the intersection of itself with the other set.
void difference(Set other);
sets the set equal to the difference of itself with the other set.
Element[] getContents();
returns an array containing the elements of the set.
This is the implementation of a set based on unordered lists, as discussed in class. It is provided to you in the Examples, so it is included in this Lab. It implements the Set interface.
As given in class.

Designed classes that you might complete

represents a maze, as discussed in class.
Maze(int rows, int cols, int pixsPerRoom)
constructs a resuable maze. That is, the maze can recreate itself (see create in the API below).
ListOfObjects getSolution()
solved the maze and returns the solution as a ListOfObjects of Rooms. The maze is solved by invoking explore(...) on the maze's starting room (upper, left-hand corner).
Room getRoom(int row, int col)
returns the room at the specified row and column. No error-checking is performed on the input parameters.
int getRows()
returns the number of rows in this maze.
int getCols()
returns the number of columns in this maze.
void create()
is responsible for setting up the maze.
  • Each Room is initialized by calling its init(). method.
  • The potential hallways (stored in a Halls object) are shuffled using the object's shuffle method.
  • The potential hallways are then considered, and openedUpHallway() is attempted on each one.
  • Each room is then told to drop its representation of unused hallways by calling dropEmptyHalls().
represents a room.
Room(int row, int col, int pixs, CS101Canvas canvas) implements Element
This constructs a room at the specified location (row and column). The room is pixs wide and tall, and is to be drawn on the specified canvas. You will have to place the Room so there is space for the rectangles that represent the room's doorways (potential hallway adjoining the Room with one of its neighbors.

The doorways appear on the screen, but are not represented in the class. Instead, each room can be connected to its neighboring rooms using the methods shown below (connectNorth, etc).

RoomSet getSet()
returns the RoomSet to which this Room currently belongs.
resets the room. It belongs to a unique set at this point, and it is not connected to any of its neighboring rooms.
nowMemberOf(RoomSet set)
tells the room that it is now part of the specified Set. The room should respond to this message by changing the color of its representative Rect and the Rectangles that represent its hallways.
void dropEmptyHalls()
causes those hallways not in use for this room to disappear. The easiest thing to do is to make them white.
void connectNorth(Room r)()
makes this room connect via its North "door" to the specified Room.
void connectSouth(Room r)()
makes this room connect via its South "door" to the specified Room.
void connectEast(Room r)()
makes this room connect via its East "door" to the specified Room.
void connectWest(Room r)()
makes this room connect via its West "door" to the specified Room.
boolean explore(Room prev, Room end, ListOfObjects ans)
initiates a search using this room. The previous room is specified as a parameter, and the search can continue (recursively) using any other room to which this room is connected. The method returns true if the treasure (end Room) was found further in the recursion.

On entry to this room, the room should be made a brighter color. On exit from this room, the room should be red if the treasure was found; otherwise, the room should be made a darker color (than it was originally).

boolean elEquals(Element other)
are we the same room as other? This can be based on our location.
Set belongsTo()
Necessary for the Set interface. Here we can just return the set to which the room currently belongs (i.e, return getSet()).
RoomSet extends SetA
RoomSet(Room singleton)
constructs this set with the supplied Room as its only element. Be sure you understand subclassing here! You don't need to make another Set, as RoomSet is already a Set.
Color getColor()
returns the Color of this RoomSet.
void insert(Element x)
overrides the superclass's definition, so that the supplied Element, which is really a Room, can bet old it is now a member of this set.
represents the potential hallways.
Halls(Maze m)
constructs the halls for the specified maze. You need the Maze so you can get to the information about the size of the maze and its rooms. The constructor should make a represenation of all potential hallways.
int getNumHalls()
returns the number of potential halls.
Hall getHall(int i)
returns the ith Hall
randomly rearranges the order of the potential halls
This is an abstract class, which means you cannot instantiate it. But it has two usful subclasses, described next. Even though this class cannot be instantiated, you can still call methods on any Hall, as detailed below.
Hall(Room r1, Room r2)
can be called from a subclass constructor. The rooms are the ones connected by this Hall.
returns the first room specified in the constructor call.
returns the second room specified in the constructor call.
boolean openedUpHallway()
This method determines if it is safe to open up this Hall. If so, then it
  1. performs the union of the sets of the two rooms now adjoined
  2. calls openDoors, defined by the subclass for this Hall
  3. returns true
Otherwise, it returns false
represents a horizontal hallway. Such a hallway adjoins the East door of its first room with the West door of its second room. This class must define openDoors() accordingly.
represents a vertical hallway. Such a hallway adjoins the South door of its first room with the North door of its second room. This class must define openDoors() accordingly.

Last modified 07:12:12 CDT 10 April 2000 by Ron K. Cytron