University of Toronto
CSC148F--Introduction to Computer Science, Fall 1996

Assignment 3: Object-Oriented Simulation

 
Due:     Thursday December 5th, 6:00 p.m.
Weight:  13% of your mark in this course

The purpose of this assignment is to give you practise writing recursive code and to teach you about object-oriented programming.

We will provide a very large program that already runs; your assignment will be to modify it in various ways. On assignment 1 you had the experience of working with someone else's code. This time, the code is much larger - over 3,200 lines long. Many of you won't like working with such a large program, particularly one written by someone else. But working on code written by someone else is very common in industry, and it is something that you need to be able to do.

As you start to look at the code, you will inevitably notice shortcomings, particularly in the comments. Documenting a program this large and complex so that it will be easy to read is very difficult. And keeping comments up to date in a changing program is notoriously difficult.

We hope that assignment 1 taught you the very important lesson that abstraction makes it easier to cope with complexity. If you were to attempt to understand the assignment 1 code by thinking of all the details at once -- how the circular car queue worked, what the pointers in the student set module were up to, and so on -- you would find it virtually impossible. But by thinking just of module signatures and not of all the little implementation details, it was possible to absorb the simulation. And at a lower level, subprograms allow you to forget about how they work and just focus on what they do. This lesson will be driven home on assignment 3. You simply will not be able to manage 3,200 lines of code without abstracting away from the details.

We have designed this assignment carefully, so that it will be doable despite the size of the program. The general idea of computer simulation will be familiar to you from assignment 1, as will the idea of simulating a crosswalk. The code you will start with already runs, and so provides a good starting point. And some of its structure mirrors the structure of the code from assignment 1. Finally, the tasks which we have laid out for you are all quite modest, and they do no rely on each other -- so can be done in any order. Getting stuck on one should not prevent you from completing the others.

Part 1 of this assignment can be done without knowing very much about object-oriented programming, and before really digesting any of our code, so it is a good place to start.  

Introduction

We will revisit the crosswalk simulation from assignment 1, but with a number of changes and improvements:

• The code will be object-oriented. This allows us to break the program down into very small pieces while avoiding some of the stylistic flaws that occurred in the assignment 1 code. (See the questions in Part 2 below.) Object-oriented code makes extensions such as those you'll make in Part 4 easier.
• We'll still have one type of intersection, but it will be a more realistic crosswalk, with two-way car and people traffic.
• There will be a whole street with multiple crosswalks along it. We will have to keep track of where people and cars are along the street.
• There will be buildings along the street, and people will be generated by the buildings. Each person will have a destination that they will move towards.
• Cars will be generated at the two ends of the street. Every car will be heading towards the other end of the street.
• There will be animated graphical output.
• The simulation in assignment 1 was time-driven: the clock moved ahead in equal, fixed-length ticks. In this assignment, the code is event-driven, meaning that the simulated clock moves ahead in leaps according to the time of the next event that we know is going to happen.

The program's input and output

The program requires no input. Output is a graphical animation of the cars and pedestrians moving along the street. Currently, no performance statistics are gathered or output.

Pick up the code from the course web site and run the file ``main.t''. Neat, eh?  

Architecture of the program

The program is broken up into a large number of small units:

module Globals:

Defines types and constants used throughout the program.

class StreetObject:

Every physical entity modeled by the simulation (e.g., pedestrians, cars, buildings) is a StreetObject. This class defines the attributes (e.g., a name and a location) and methods (e.g., the ability to be printed) that they all share.

class Location:

Defines a location on the screen. Every StreetObject has a location, and an instance of this class can keep track of it, as well as provide methods such as one for determining the distance from the present location to another.

class ActiveObject:

An ActiveObject is a StreetObject, but one that takes turns doing things in the simulation. It therefore has a frequency with which it takes turns, and also knows when its next turn will be. It also has a method for taking a turn, but this method is ``deferred'' because only specific subclasses of ActiveObject (such as Pedestrian) can define what it means to take a turn. Currently all StreetObjects (Pedestrian, Car, etc.) are ActiveObjects.

class Building:

A Building is an ActiveObject. This is because it needs to take turns in the simulation so that it can generate pedestrians. When a building takes a turn, it simply generates a single pedestrian of a random sort, with a random destination.

class Car:

A Car is an ActiveObject. When it takes a turn, it moves an appropriate number of spots along the street, as determined by its speed and direction. It must, however, not run into cars ahead of it, or go through closed crosswalks. Cars currently ignore any pedestrians who ``jaywalk'': cross the street without using a crosswalk. (But no pedestrians currently jaywalk.)

class CarGenerator:

A CarGenerator is an invisible object that is the source of cars appearing in the simulation. It is an ActiveObject, because it needs to take a turn in order to generate cars. When it takes a turn, it simply generates a single car, but only if there isn't already a car at its location.

There are two instances of this class in the program (and thus two sources of cars): the west end of the street and the east end of the street. These sources are kept track of in main.t.

class Pedestrian:

A Pedestrian is an ActiveObject. On its turn, it moves towards its destination, at its own speed. If it needs to cross the street, its strategy is to cross at the first crosswalk available, even if that crosswalk is currently not open.

class Vampire:

A Vampire is a Pedestrian, but it has fangs. And when it takes a turn, it tries to find a neighbour on the sidewalk and suck their blood. When this happens, they lose one unit of girth, which the vampire gains.

class NiceVampire:

NiceVampires behave slightly differently from other Vampires. See question 5 in Part 2 of the assignment.

class Crosswalk:

A Crosswalk is an ActiveObject. When it takes a turn, it may open or close the street to pedestrians, as appropriate.

class Street:

The Street class keeps track of everything. A street is made up of a north and a south sidewalk, and a north and south lane. Each of these is an array of spots along the street - chunks of sidewalk and road. And each chunk of sidewalk or road is a set containing the people and cars at that spot. A street also has a list of crosswalks a list of buildings, and two endpoints that generate cars.

There is exactly one street defined in this program, in main.t.

This class is broken into a stub and body (in files ``street.tu'' and ``street.tb'') to avoid circularity in the relationships among the classes.

class ObjectRemover:

The class ObjectRemover maintains a list of objects that have asked to have their memory freed. At any point, or at desired regular intervals, the FreeAll method can be used to free them all.

This class is needed because only a pedestrian knows when it has reached its destination and is ready to disappear from the animation and have its memory freed as well. The same holds for cars. But an object cannot free itself. Instead, objects register with the ObjectRemover, which can be asked at any time to free them all. Currently, the main event loop frees all such registered objects once per iteration, so the we don't waste memory for very long.

class List:

Implements a list of StreetObjects, using an array. Lists are used in a number of places in the simulation, for example, to keep track of the list of buildings on the street and the list of objects that have asked to be freed.

class Set:

Implements a set of StreetObjects, using a linked list. Sets are used to keep track of the people and cars on each piece of sidewalk and road, and to keep track of the people waiting at each side of each crosswalk.

class PriorityQueue:

Implements a ``priority queue'' -- an ADT much like a queue, but in which all elements have a priority. Elements of the highest priority are the first to leave the queue, but within priority levels, elements leave in first-in first-out order. (See Barnard, Holt, and Hume, chapter 7, for a discussion of priority queues.)

In this program, we use a priority queue to hold the events that we know are going to happen in the future. Each event has a time at which it should happen, and that time is used as its priority level. So when we dequeue an item from the event queue, we get the item with the lowest (i.e., next) time. If there are several events in the queue scheduled for that time, the first one that went in is the first one out.

class main.t:

The main program. It declares and initializes all the objects on the street. Then it runs a main simulation loop that, on each iteration, takes the next scheduled event from the event queue and gives it a turn. This continues until a time limit is exceeded. On every iteration, objects that have asked the ObjectRemover to free them are freed, and on every so many iterations, the street is redrawn. When the main loop is done, all items left in the event queue are removed and freed.

Your assignment

Your assignment consists of 4 parts. As stated above, these are not dependent on each other, and can thus be done in any order.

Part 0: Start to get familiar with the assignment

Get the program from the web site and run it a few times to see what it does. If you find that the simulation runs a little too quickly (which may happen if you have a fast machine), you can add a delay statement, e.g., delay(25), to the main loop in file main.t. Play with the delay amount to get a suitable speed.

Then read the rest of this handout. You will probably not understand everything that we say the first time through, but these two things are by far the best way to quickly get familiar with the assignment.

Hand in:

• The amount of time you spent on this part of the assignment.

Part 1: Change and extend the implementation of the Set class

This step can be done immediately -- before you have learned much at all about object-oriented programming, and before you have digested the ideas presented above to do with the new, more sophisticated simulation. This step involves only the Set class. It does, however, require that you be comfortable with recursion and that you know how to create instances of a class. (The latter is very easy to do, using new.)

Re-implement the given Set class using a binary tree rather than a linked list. In addition, extend the class so that it exports subprograms for these binary set operations: set intersection, set union, and set difference. (These operations are not currently used by the simulation program, but could be helpful if we wanted the program to answer questions like ``How many students, on average, are on the sidewalk but not at a crosswalk?'' They also make the Set class more complete.)

On the course web page you will find a partial solution to this problem, including declarations of the constants, types, and variables needed to store the binary tree, headers for all exported subprograms, and bodies of some of the subprograms. You must not change the signature of the Set class, or any of the code provided.

To test your new implementation, write a small driver program. The concept of a driver should be familiar to you from assignment 1. You need only test your own subprograms, not the ones that we have written for you. It is your job, in your testing, to provide evidence that will convince the grader that your revised set class works. If you hand in no test runs, or poor testing, you will get few or no marks for correctness of your class.

Hand in:

• a printout of your revised and extended Set module
• a printout of your driver program
• a written description of your testing strategy
• annotated test runs that show how you applied your testing strategy
• The amount of time you spent on this part of the assignment.

Part 2: Answer questions about the software we've provided

The purpose of this step is to help you get familiar with the very large piece of software that you will be working on in subsequent steps. It takes you through some of the code, pointing out interesting things and asking a lot of questions. You are to hand in answers to only those that are labelled Hand-in questions.

First, print out the code. (It is long, so print double-sided if you can, and don't print it more than once.) Highlight the signature of each class. As you begin to look at the code, try at first to focus as much as possible on the signatures. Although the program is very long, the signatures are not. Hand-in question 1: Draw the object hierarchy - a tree showing what objects inherit what.

Things are moving around on our simulated street, so naturally, everything has a location. We've chosen to represent that as an (x,y) pair of coordinates, and since locations occur frequently we've made a Location object. It has methods to set and get the x and y values, but others as well. What does LocDiff do?

All the moving objects know how to move themselves - but how do they know where they are? The street keeps track of them. It can answer questions like ``What's the farthest point west?'' and ``Is this location that I'm looking at on the sidewalk, or is it on the road?'' The methods in the Street module are divided into six sections. Look at the six sections and see what each is for.

LocDiff is important to Pedestrians, which are one type of object on the street. It's especially useful in the method CanReachDest, which determines whether a Pedestrian can reach its destination during its current turn. What type of thing is its destination? Why do you think we chose not to make it a simple (x,y) pair, using the Loc object?

Skim file ``main.t''. Read the procedure headers; don't worry about what's inside them. Now skim the main program. Notice the big loop in the main program; that's what drives the whole thing. Each time through the loop, an object, called aobj, is pulled off the front of the PriorityQueue and told to take a turn. The loop stops when the current time (aobj->GetNextTurnTime) is greater than maxTime. We don't use the loop counter, i, to decide when to stop because i doesn't correspond to the current time. Hand-in question 2: What does i correspond to, and why is that not equal to the current time? It may help to trace the code and look at some values of GetNextTurnTime.

Somehow, objects need to be created. Pedestrians walk out of Buildings in real life, so we simulate that by having Buildings create Pedestrians. Where are the Buildings and Crosswalks created and initialized? How about Cars?

Compare the Set class to the studentSet module in assignment 1. (In this case, do look at the implementation details.) Recall that we were unhappy about the fact that ``a few student-specific things do appear in the module, preventing it from being an implementation of a general set.'' (This was why we called the module studentSet -- we didn't want to mislead the reader into thinking it was a completely general set module.) What exactly were the student-specific things that appeared in the studentSet module, and why does this not have to happen in the Set class?

Compare the Pedestrian class to the Stud module in assignment 1. In the Stud module, we had to export the StudentType, which we also didn't like to do because it leaked out some secrets about our implementation of the module. Hand-in question 3: Why don't we have to export a type from the Pedestrian class?

The algorithm for opening and closing the crosswalk is different from that used on assignment 1. Under what conditions does the crosswalk open? Under what conditions does it close?

Both cars and pedestrians get a turn to move every so often, determined by their ``frequency''. When a pedestrian takes a turn, he moves towards his destination and then schedules his next turn in the event queue. But when a pedestrian arrives at a crosswalk, he does not schedule his next turn because he doesn't know when he'll get to move -- that depends on when the crosswalk opens. Hand-in question 4: How does the pedestrian ever get another turn?

Currently, there are three types of people in the simulation: pedestrians, vampires, and nice vampires. They are related by inheritance. The Vampire class inherits Pedestrian, which means every instance of a Vampire automatically has all of the instance variables and methods of Pedestrian. But Vampire overrides three of the methods defined in Pedestrian. Drawing a Vampire is just like drawing a Pedestrian, but it also involves drawing fangs. And taking a turn in the simulation is the same for Vampires as other Pedestrians, except that it includes a separate step wherein the Vampire picks a victim from the same spot on the sidewalk and attacks them. The victim's girth is thus reduced by 1 and the Vampire's is increased. Also, when a Vampire is initialized it is set to be red (vs brown), and is given a higher walking speed. NiceVampire inherits Vampire, and overrides two of its methods. Hand-in question 5: What makes a nice vampire nice? That is, how is it different from a regular vampire?

Currently all StreetObjects (Pedestrian, Car, etc.) are ActiveObjects. ActiveObject and StreetObject are distinguished because we might later want to add InactiveObjects -- objects that do not take a turn -- such as a trees or park benches. Why would we bother making such things objects? Each StreetObject defines a TakeTurn method which was declared in an inherited class higher up the hierarchy, but whose body was deferred at that point. Hand-in question 6: Is TakeTurn inherited from StreetObject or ActiveObject? Why?

In the present program, we have only one street. How might you extend it so that there could be a bunch of streets that might intersect each other in various places? This is an open-ended question.

Hand in:

• written answers to the questions above.
• The amount of time you spent on this part of the assignment.

Part 3: Extend the hierarchy of people types

Currently, there are three types of people in the simulation: pedestrians, vampires, and nice vampires. Here, your job is to add more types of pedestrian to the simulation.

First, add an AnxiousUndergrad class. Anxious undergrads are just like other pedestrians, except that they move faster. This should be a very easy task, especially once you've understood how Vampires and NiceVampires are related to Pedestrians.

Then make up three other subclasses of Pedestrian, each with significantly different behaviour. At least one must be a subclass of a subclass of pedestrian. This is a chance for you to be creative and have fun. Suggestions: A CleverComputerScientist might use a better strategy for crossing the street than ordinary Pedestrians -- she might not wait at the first crosswalk encountered if it were closed. A PiedPiper might, on his turn, pick a random neighbour on the sidewalk and reset their destination so that they follow him wherever he goes. (He'd better not disappear though, when he reaches his destination, or they will have nowhere to go.)

You should test your new classes, but you will not hand in any testing for this part of the assignment.

Hand in:

• printouts of your new classes. Your comments on each new class should clearly explain how it is different from the other types of pedestrian.
• a tree diagram showing the inheritance relationships among the various Pedestrian classes.
• a written description of any bugs or other flaws in your new classes that you have not been able to fix. If there are none, say so.
• The amount of time you spent on this part of the assignment.

Part 4: Fix a bug

There is a bug somewhere in the software. You may have noticed that when some pedestrians reach their destination, they don't disappear. They wiggle back and forth in front of the building until the simulation ends. Your task here is to find the bug and fix it.

Hand in:

• A short written description of what the problem was and how you fixed it.
• A printout of the unit(s) that you changed to fix the bug. Hightlight the exact lines of code that were changed.
• The amount of time you spent on this part of the assignment.

How long will this assignment take?

The amount of time required will vary from student to student, but our head TA has suggested estimates:

 
	Part O: Start to get familiar with the assignment    2-4 hours
	Part 1: Change the implementation of the Set class   4-8 hours
	Part 2: Answer questions about the software          2-4 hours
	Part 3: Extend the hierarchy of people types 	     4-8 hours
	Part 4: Fix a bug 		 		     2-4 hours
	TOTAL 		 				     14-28 hours

We do not want to take up much more of your time than this. Keep track of the time you spend on the various parts. If you find yourself exceeding any of our time estimates, you are probably going around in circles -- please come ask us questions!  

How to submit your assignment

This assignment is to be handed in completely on paper. Do not hand in a diskette.

To help the marker identify the parts of your assignment, staple each part, and include a front page that identifies which part it is.

As always, put everything into an 8.5 by 11 inch envelope. The cover sheet provided here (or a photocopy or facsimile of it) must be filled out, signed, and taped to the envelope containing your assignment.  

Draft grading scheme

Below is the grading scheme that we currently expect to use. It may be changed somewhat as the assignment unfolds, but should give you an idea of where to focus your efforts.

 
	Part 1: Revised set class
   	     Does it work? 		 		25
   	     Testing strategy and annotated test runs 	10
	Part 2: Answers to hand-in questions  		10
	Part 3: Extended class hierarchy 		20
	Part 4: Bug fix	 		 		10
	Programming style 		 		10
	Comments 		 			10
	Overall quality of writing 		 	5
	TOTAL         		 		 	100