Figure 1: Two family trees headed by h1 and h2.
University of Toronto
CSC148H: Introduction to Computer Science
Summer 1997
Assignment 5: Herbivores and carnivores
Due: Thursday, August 7, 6pm.
The purpose of this assignment is to teach you about object-oriented programming, to give you some practice with recursion, and to give you some experience working with a ``real'' program. We will provide a large program--over 1900 lines of code--that already runs; your assignment will be to modify it in various ways. Some of you won't like working with such a large program, particularly one written by someone else. The reality, though, is that this is a common task in industry. Maintaining, extending, and rewriting existing programs is far more common than writing a new program from scratch.
You will no doubt notice shortcomings in the code. We've tried to be consistent in its style, and we've tried to include many comments, but it is difficult to document a program as large and complex as this, and some comments inevitably fall out of date. So be careful when you read the code.
You will find it virtually impossible to understand the code by thinking of all the details at once. Luckily, you are all now well-versed in abstraction so that you can work with the class interfaces and ignore the implementation details. You need only look at the details when it's absolutely necessary.
We have designed this assignment carefully, so that it will be doable despite the size of the program. The tasks that we have laid out are all modest, and can be completed independently of one another, and in any order you wish.
Perhaps you played the game of Herbivores and Carnivores when you were young. The game is usually played in a forest with a large group of people. Some are carnivores and some are herbivores. The herbivores must find feeding stations in order to collect food while avoiding the carnivores. Meanwhile, the carnivores hunt down the herbivores. If a herbivore has no food left when a carnivore finds him, then the herbivore dies. Otherwise, the carnivore takes some of the food. Some games even include a human hunter that goes after the carnivores.
The point of the game is to illustrate the food chain in nature, but it's not all fun and games. Biologists actually run serious simulations of this type on computers in order to study real animal populations. For example, biologists could run a simulation of the codfish stocks in Atlantic Canada in order to figure out how the stocks ran out, and to predict what will happen to them in the future.
In this assignment, you will work with a simulation that is based on the Herbivores and Carnivores game.
The program that we have provided will run a simulation of herbivores and carnivores (without the carnivores yet, because that's one of the things you have to write). The basic idea of simulation software is to loop through a bunch of objects that can each make a move, or take a turn. For example, if you had one carnivore and one herbivore, then the carnivore might move one step closer to the herbivore on its turn, and the herbivore might just stay in the same spot and eat some grass on its turn. If this pattern repeated, then eventually the carnivore would reach the herbivore and kill and eat it on its turn. Fortunately, herbivores can also decide to move on their turn. Each type of object in the simulation has its own way of taking turns.
The class called World runs the simulation. Every object that wants to take a turn schedules the time it wants to take its turn with the world. Since the world manages a clock, it can tell the object to take its turn when the time comes. And part of taking a turn is to schedule oneself for another turn; thus, the simulation keeps going. The simulation is event-driven. That means that if no events (i.e., turns) are scheduled for a period of time, the clock gets advanced past this period to the time of the next scheduled event. Actually, there will usually be an event scheduled for every time unit, so you won't see the clock jumping ahead. Also note that several objects can take a turn at the same time.
The implementation of event-driven simulations is quite simple. The world stores the objects (actually, pointers to objects) in a priority queue, which is like an ordinary queue except that its elements are ordered from high priority to low priority. The highest priority object is the one with the soonest event time (i.e., the lowest time-stamp), and it is dequeued first.
The simulation algorithm goes like this: loop until the queue is empty or until time runs out. In each iteration, dequeue an object from the priority queue and tell the object to take a turn, which might involve enqueuing the object for another turn.
The program requires no input. However you can set several simulation variables that will make the simulation behave differently. These are all defined in the module SimVar. For example, you can set how long the simulation will run for, how much energy an animal can get by eating on the plains, or how fast a herbivore moves.
The output is a graphic animation of the world that shows herbivores (as green circles) interacting. The world has different kinds of terrain that affect the herbivores in various ways. When finished, the program will output some statistics into the file stats.out.
Download the code and run it. (See web site for the instructions.) Neat, eh!
Now that you've got the code, and seen it run, here are some details. It is composed of the following classes. Some are quite small.
Before continuing, you should fully read this handout, get the code from the web site, and run it a few times. Then, print out the code, double-sided if possible, because it could take over 35 single-sided pages.
This part will help you get familiar with the code. It takes you through some of the details, and asks a lot of questions that we consider very helpful to understand the program. You should try to answer these questions before you do any coding. If you're having trouble with any of these, talk to your instructor or TA. Hand in answers to the 7 questions that are marked by ``Question X:''.
Look at each unit and highlight the interface (i.e., the export/import items and the subprogram headers). Focus on the interfaces. Look at the import and inheritance relationships between the classes. One can draw these relationships with a box-and-arrow diagram called a landscape. Boxes represent the units of the program, and arrows the relationships of inheritance or import between the units. (See page 201 of BHH for an example of a landscape that has only `import' arrows.)
Question 1: Draw the landscape for this program. Include inheritance and import arrows, and label each arrow accordingly. Try to minimize the number of arrows that cross over each other.
Have a look at the main program. It does three things. First, it creates and initializes the world. Trace through the Init procedure of the World. What variables does it initialize, and why? Second, the main program creates some animals and other objects and adds them to the world (by calling the JoinWorld method of the objects). Third, it starts the simulation. The procedure Simulate of class World is the main loop for the whole program. It dequeues objects from the queue, and asks them to take their turn by calling their TakeTurn method. It is then the responsibility of TakeTurn to schedule another turn. How does it do this?
Question 2: How does an object get its first turn? I.e., when and how does it get into the priority queue in the first place?
All active objects can take a turn. What kinds of active objects are there in the system? What inactive objects are their in the system? Notice that TakeTurn is deferred in class ActiveObject. Why is this?
Now look at the Animal class.
Question 3: What does an animal do when it takes a turn?
Question 4: What does a mouse (class Mousey) do when it takes a turn?
What is the initial destination of the mouse? Find where it is set. Will the mouse ever stop moving? (Note: the mouse is so simple that it doesn't even use most the methods provided by its parent class Animal.) As an experiment, you could try to temporarily modify the main program so that it creates several mice.
The Move code in class Animal is fairly complex. It determines the distance and direction of a move, and then computes the next location. How does it use the speed of the animal in this computation? How is it that animals never move into water? How is their movement affected in the mountains?
Part of moving is to erase the old image of the animal by calling EraseImage. Notice that images are erased by actually redrawing the terrain over the image. What unfortunate side effect does this have on some other nearby animals? This is remedied by the Refresh class. Do you see how?
Now, for the big one: class Herbivore. The herbivore has many helper functions for doing things that herbivores do. What kinds of things can herbivores do? The TakeTurn procedure is the most complex. It will do different things during each turn depending on a few boolean functions (such as OutOfEnergy and Hungry) and on some variables. How do you know if a herbivore should die? Notice how if a herbivore dies, it (`it' because they are hermaphrodites in our simulation) is not scheduled for another turn, but its image is changed to a cross (in the DrawImage procedure) and displayed immediately.
The basic life of a herbivore is to move around looking for mates, and to pause to eat grass once in a while.
Question 5: Under what conditions can or does a herbivore eat grass?
Herbivores can mate to create new herbivores. How does a herbivore choose a mate? Unlike the mouse, who moves to random destinations, the herbivore always moves toward its mate's current position.
Question 6: How does the herbivore figure out the current location of its mate?
Finally:
Question 7: Which subprogram updates the clock of the simulation, and how does it do it?
HAND IN: Short written answers to the seven questions. Answers to 2 through 6 should fit on one page.
Since herbivores can mate and produce offspring, who can produce more offspring, and so on, it might be neat to see a family tree of the herbivores. You are to write a class for building and printing family trees. We have provided the interface for the class, which you should not change. The class is already integrated into the program, but its procedures are just empty for now. Notice how the Herbivore code calls the AddMember procedure of its family tree whenever it creates a new baby. And the main program calls the Prnt procedure after the simulation is over to print out the family trees into several files (ftree1.out, ftree2.out, ...).
Every herbivore in the simulation, except the initial ones, has two parents. One is the principal parent who created the herbivore, and the other is the mate, who is involved only incidentally. The family trees should record only the principal relations, otherwise they will become too complex. Thus, every herbivore ends up having one family tree, the same one as its principal parent. Since the initial herbivores have no parents, they will each start a new family tree, which they will be at the root of. So, if there are four herbivores to begin with, there will be four family trees in the simulation. Since a family tree is a class, there will be no problem instantiating more than one tree object for the simulation. Look in the main program to see how family trees are created and initialized.
For example, let's say there are two herbivores at the beginning, h1 and h2. Now, h1 mates with h2 to create h3. Then h1 mates with h2 again to produce h4. Both h3 and h4 are added to h1's family tree. Then h2 mates with h3 to produce h5, who is added to h2's family tree. If h4 then mates with h5 twice, the herbivores produced (h6 and h7) will be added to h1's family tree. See figure 1 to see how this would look.
Figure 1: Two family trees headed by h1 and h2.
Your first task here is to design and implement the data structure of the family tree using pointers for the relations between a parent and its children. The details of the implementation are up to you, but you can assume a maximum branching factor per node, after which point more children cannot be added.
There are two procedures to implement. AddMember takes three parameters: the principal parent (parent1), the child ( member), and the mate (parent2), all of which are pointers to objects of class Animal (so you could have family trees of any kind of animal). The procedure should locate parent1 in the family tree, and add the child to its children. It is easiest to do this search recursively. You may not have a reason to use the pointer to the mate (parent2); it is provided just in case you want to do something fancy.
Prnt takes a single parameter, the file stream on which to output the tree. You can assume that the file has already been opened, and is ready for output. You should traverse the tree recursively to print it out. It is easiest to print trees on their side, with the root on the left, and children to the right, but the formatting is left up to you. All that is required is that you print the names of each member in the tree (by calling their Prnt method) in an easily visible tree structure.
Testing your two procedures will be difficult, so you don't need to hand in comprehensive test output. Instead, hand in a complete testing strategy that someone else could use to test your family tree class. Of course, you should hand in a few family trees to prove that it works.
HAND IN: Your tree class, your testing strategy, and several family trees output by your program.
Bonus: for a few bonus marks, print the tree in a very fancy format, and include mates as well. Don't spend time on this until you've finished the other parts of the assignment.
Develop two new classes of objects for the simulation. You could implement a new type of terrain, a new animal, a subclass of an existing animal (like a special kind of herbivore), or any other kind of class you can think of. The new classes don't have to be very complex--they can be as simple as the mouse class--but they should each exhibit some kind of unique behaviour or interaction with another class; something that no other object in your system does. Marks will be awarded for creativity, with bonus marks going to the most creative classes. Modify the program to run with the new classes. If you work within the conventions of object-oriented programming, the modifications should be minimal. For example, if you add a new kind of terrain, then you'll have to modify the World.BuildTerrain procedure, but probably nothing else.
To prove that your new classes work, they should generate some statistics as they run. They can do this by calling the AddStatistic method of class World. (Study the Herbivore class to see how it does this.) The statistics will be output automatically when the simulation is over.
HAND IN: Your two classes. Make sure you document them well. Several statistics reports from different runs of the simulation. Also, include the new classes in your landscape of part 1 above. If you modified any other units of the code, then hand in those units and highlight the modifications.
Develop a Carnivore class. The design is left up to you, but you may find it easiest to model it after the Herbivore class. The requirements for its behaviour are the following:
Any other features are left up to you, but they are not required. You should define new simulation variables in module SimVar to control the carnivore's behaviour. You should also make appropriate calls to AddStatistic to gather statistics about your carnivores in order to prove that the class works properly. One final problem you'll have to solve: how/when do carnivores come into existence?
HAND IN: Your documented carnivore class. Some statistics reports output by different runs of the simulation. If you modified any other units of the code, then hand in those units and highlight the modifications.
You are to write a minimal report on this assignment. It should include an introduction, a `Method' section for all the code that you wrote (the family tree, the two new classes, and the Carnivore class), a `Status' section explaining any parts you couldn't finish and any leftover bugs, and the answers/solutions to all the HAND IN parts above. Since there are several parts to the assignment, organize and label everything to make your TA's job of marking easier. It should be about 3 typed pages long.
