CSE 132 (Spring 2010)
Lab 3b: Mazes

Apply this change to your code (I sent email about this):
In the demo() method of the Maze class, move the call to initMaze() inside the loop, so the maze resets each time. Run your code and make sure things work. Commit.

Warning: While the amount of code you have to write to finish this lab is relatively small, a good deal of thought must go into the code, or the lab won't work. You are unlikely to succeed by guessing or trying many things in succession without understanding how locks and synchronization really work.
Start early and work steadily to ensure success.
Work collaboratively and get help where needed. Make sure you understand what is happening because the midterm exam will cover what you should understand from doing this lab.
Copying code in which you lack any hand in its development or any ownership in its concepts is unacceptable.
Working collaboratively is highly encouraged.

Abstract:

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 could be used to route message between a set of nodes. The network you create is in fact an unrooted tree.

Another view of this assignment: In this lab you create a maze that could be used to have a mouse find some tasty cheese food.

OK, I confess: the true nature of this lab is to give you experience with threads, concurrency, visualizations, and components. You will explore the nature and causes of deadlock as well as the deadlock avoidance. But the maze and network anaologies are accurate.


Overview, Maze Construction (analogy for our assignment)

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?)
The reason for this strange constraint is as follows. 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.
Also, there is exactly one sequence of hallways between any two rooms. This yields a unique way to direct somebody (or an Internet packet) from one room (or computer) to another.

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. (Remember? 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 might 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, play rock, paper, scissors, 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:
  • There is one path between each pair of rooms.
  • A robot traverse the maze by keeping one "hand" on a wall.
Finally


Notes:


Procedure

The suggested approach for this lab is as follows.

Having trouble?

If your solution is mostly working but occasionally comes up with a Maze with a loop, there's a good chance that you need to read the following:

Consider Room r1 and Room r2. Suppose you have a lock on them. Suppose also you have a lock on Set s1=r1.getSet() and Set s2=r2.getSet(). There are two conditions under which you can definitely act:

  1. s1 == s2
    Once this holds, the thread should never try to join the rooms. Thus the thread is done.
  2. Once you get the locks, if you verify that it is still the case that then you are in a good position to act because you have a lock on the sets associated with the rooms.
    If s1 != s2, you should join the rooms. This thread is done.
However, it is possible that after waiting for the locks on s1 and s2, those sets are no longer the sets associated with Rooms r1 and r2.
That is, s1 != r1.getSet() or s2 != r2.getSet().
In this case, you cannot definitely join or not join the rooms, and you need to loop around the run method, releasing the locks you have and trying again.
Eventually, one of the good conditions must happen.

Demo

The code you hand in should be as clean and simple as possible. Don't duplicate code unnecessarily. Don't use .equals where == suffices. You can earn a C for a lab that works but is very poorly written. To get an A on this lab, your code must show that you know what you are doing. A B will be awarded to labs that fall in between.
  1. Commit your code and have a TA come by to demo you.
  2. Demo your code to a TA with your CheckMaze's runCheck() method, showing that it works on 10 mazes.
  3. Next demo it with our CheckMaze (get the TA to type the password), running the Maze 100 times. When it's done, assuming no exceptions were thrown, show the console output to the TA and have him/her verify that it worked.


Last modified 08:59:22 CDT 03 June 2010 by Ron K. Cytron