CMSC 201
Programming Project Three
Wa-Tor

Released on Thursday March 31 and due before Midnight, Thursday April 14.

The design document for this project, design3.txt, is due before Midnight, Friday April 8.

Extension - New due date : before midnight, Friday April 15

The Objective

The Background

Living organisms are probably the most complex things in the universe. They are extremely difficult to understand, let alone model mathematically, chemically, biologically or computationally. It's even harder to understand and model communities or ecologies of living organisms that interact and effect one another. The invention of modern computers have given us a new tool to model systems of living things and doing so is an important and popular subfield known as artificial life or sometimes just alife. Chris Langton, the computer scientist who coined the term in 1987, defined artificial life as follows.

Artificial life is the study of artificial systems that exhibit behavior characteristic of natural living systems. It is the quest to explain life in any of its possible manifestations, without restriction to the particular examples that have evolved on earth. This includes biological and chemical experiments, computer simulations, and purely theoretical endeavors. Processes occurring on molecular, social, and evolutionary scales are subject to investigation. The ultimate goal is to extract the logical form of living systems.

Microelectronic technology and genetic engineering will soon give us the capability to create new life forms in silico as well as in vitro, This capacity will present humanity with the most far-reaching technical,theoretical and ethical challenges it has ever confronted. The time seems appropriate for a gathering of those involved in attempts simulate or synthesize aspects of living systems.

Computational models of living things goes back further, of course. In 1984, A. K. Dewdney published an article Sharks and fish wage an ecological war on the toroidal planet Wa-Tor in the Computer Recreations column of Scientific American. It was an early example of a predator-prey simulation and has been implemented many times. Google for "wator" or "wa-tor" and you'll find lots of Java applets that stem from this article. The interactions of populations of predators and prey was a very early example of modeling living systems and can be modeled mathematically using Lotka-Volterra equations. Implementing a simulation system and experimenting with it is another way to explore the dynamics.

The Task

You are part of an advance team surveying the planet Wa-Tor and tasked with deciding whether or not it is suitable for a human colony. Wa-Tor is an unusual planet in two respects: it's shape is not the usual sphere, but a torus and it is completely covered by water. An initial bio-scan reveals that there are just three kinds of living things on Wa-Tor: a yellowish-green algae that gets energy from Wa-Tor's star and grows slowly, and two kinds of fish-like creatures which we'll call sharks and tuna. Tuna are small fish-like creatures that eat algae and are eaten by sharks. Sharks are large shark-like creature that eat the smaller tuna. Your job is to try to understand the Wa-Tor's food web and make sure that the planned human colony will not upset Wa-Tor's natural environment. You decide to build a simulation that you can use to study the interactions of the algae, tuna and sharks. As you learn more about the algae's growth rate and how often the sharks and tuna bare young and how much they have to eat, you can update the parameters in the simulation and better understand Wa-Tor's environment.

Wa-Tor is a torus shaped planet completely covered in water and inhabited by sharks, tuna and algae.	Wa-Tor sharks eat Wa-Tor tuna. Nothing eats Wa-Tor sharks.	Wa-Tor tuna eat Wa-Tor algae and are eaten by Wa-Tor sharks	Wa-Tor algae just need starshine, which is plentiful, and are eaten by Wa-Tor tuna.

Your simulator

Simulate Wa-Tor using an array ocean with ROWS rows and COLS columns. For testing purposes, we will expect this to be 15x15. You can treat the rectangular array as a torus easily by having it wrap around. Moving a fish off the right edge, for example, will have it reappear on the left. The model is governed by the following parameters. All but the first two (the size of the ocean) are inputs to be read in from the user.

Each cell in the ocean array will hold a structure that represents what is in the cell. In general, a cell can hold one shark, one tuna and one alga. We will give you the structure you must use for a cell (see the partial wator.h header file).

The simulation progresses in a series of "steps", one per timeClick (a unit of measure similar to what called a day in the distant past). For each step, you should iterate over all of the array cells and if one is filled with a living thing (fish or algae) decide what it will do for that step using the following rules.

At each step, each fish (shark or tuna) will

• Pick a random direction (out of four: north, east, south, west) and try to move in that direction.
  • If the move is off an edge, it "wraps around" to the opposite edge.
  • The move succeeds if the new cell is empty, or contains only algae, or contains a different kind of fish.
  • The fish only gets one chance per turn; it does not try more than a single direction.
  • If a shark moves onto a tuna, it eats it. If a tuna moves into a cell with a shark, it gets eaten. This is "Nature, red in tooth and claw."
  • If a tuna moves onto algae, it eats the algae.
  • A fish cannot move to a location containing a fish of the same type.
• If the fish has gone for its starvation period without eating anything, it "dies" and is removed from the ocean.
  • Any time a shark eats a tuna, or a tuna eats algae, it is full, and won't starve until the full starvation period passes.
  • At the beginning of a step, if a fish has not yet starved, it has a chance to move. If it does move and finds something that it can eat, it does so and its starvation time is reset. If it moves and its new location has nothing to eat it's starvation time is decremented. If it tries to move into a cell and is blocked (because there is a similar fish there), its starvation time is decremented.
  • If decrementing a fish's starvation time makes it zero,the fish dies immediately.
  • Note that movement is blind in that a fish does not sense what are in adjacent cells to move toward food or avoid predators.
• If it is time for the fish to reproduce, and if the fish was able to move, create a new fish of the same type in the just vacated cell. The new fish is born with a full stomach.
  • If a fish is ready to reproduce but cannot move, it does not reproduce; but it will reproduce the next time it can move.
  • Both the parent and the baby fish begin a new gestation period, i.e., their reproduce field is reset to the appropriate initial value.
  • The baby fish is not hungry at all, i.e., its starve field is set to the appropriate initial value.
  • Note that the reproduction happens before a move, so long as the move is possible. A tuna, for example, may decide to move North, give birth to a baby tuna which is left behind, make the move and be immediately eaten by a shark in the new location. The new baby tuna is on its own.

• If it is time to reproduce, it will try to "grow" into a randomly chosen adjacent cell (N, E, S, W).
• If the cell already has algae, the growth is blocked and the alga's grow counter is not reset, so that the alga will try to grow on the next timeClick.
• If the new cell does not contain algae, the growth does occur and the grow counter in both the original and the new algae is set to its initial value.
• If the alga happens to have grown into a cell that contains a tuna, it is immediately eaten.

Genesis

Interfacing to creation

We've provided a partial header file for Wator. Your actual header file wator.h will include, of course, any additional structures or function prototypes that you might want or need for your simulation module. We are specifying this much since it is needed to specify the interface between your program and the creation.o module.

The partial header file we provide includes constants, structures that you must use in order to work with creation.o, the package that initializes the simulation by populating the world. You must use these structures as defined and in the way intended. In principle, you can modify them by adding additional, new fields, but please ensure you have a good reason to do so. This partial header file also includes the prototypes of three functions that you must implement. You may not change the prototypes of these functions.

Displaying the model

You will have to write a function that prints a representation of the model. This is pretty simple and basically involves iterating over the cells in the ocean array and printing one character to represent what is in the cell. Here's what to print.

Note that a shark and an alga can coexist in the same cell of the ocean, but for display purposes, we only show the shark. Tuna and algae do not coexist, because the tuna always eats the algae, so if a cell is displayed as an alga, then an alga is all it contains.

Random notes and suggestions

• If a fish (either kind) can't move then it can't reproduce at that time click, since it has to move and leave its baby where it was. So you can't just treat it like a birth and shouldn't reset the reproduce counter until the birth actually occurs. As soon as it can move though, it should reproduce and its counter reset.
• Your program should start, as usual, by calling PrintGreeting( ) -- a function that will print the initial greeting and briefly explains what the simulation is all about.
• Do not use any Unix system calls in this program.
• Your functions to move a fish or grow algae will need to generate a random direction. The creation.o module has a function GetRandomNumber( ) that you can use. See creation.h for details.
• For grading purposes, you would like your simulation to mimic our sample output somewhat. Certainly your output will not match ours due to the complexity of the simulation, but if you do things in the same order as we did them, then your simulation should show the same population trends.
  For each location, the creatures were handled in the following order:
  1. shark
  2. tuna
  3. alga
  To further aid you in achieving similarity, we are providing the pseudocode for handling a tuna at one location. This pseudocode was generated from the comments within my code and could be used as your comments. Just add the code, stir ... :)
  Here's the detailed and complete Pseudocode for Tunas Only:

  if there is a tuna in this cell
     adjust age
     get the new position
  
     if there is no tuna in the new position
        move the tuna
        adjust timeLastMoved
  
        if there is an alga in the new position
           eat it (remove alga & reset starvation)
        else
           get closer to starving
           if she starved
              remove the tuna
  
        if she didn't starve - look into reproduction
           adjust reproduction time
           if it's time to reproduce
           reset reproduction time
           leave a baby behind
  
        if there is a shark
           the tuna gets eaten (remove tuna & reset shark starvation)
  
     else (there was a tuna in the new position, so the tuna can't move)
        adjust reproduction counter, but can't reproduce now
        adjust starvation counter
        if tuna starves
           remove it
  
  

  You can mimic this same order for the code for sharks, which are simpler than tuna, since they can't be eaten.

Dealing with the complexity

While the complexity of this program may seem high, it's manageable when you break things down. The basic tasks you have to do include: reading the parameters from the user; creating the initial model; displaying the current state of the model; and advancing the model by one step. As an initial goal, consider reading the parameters, creating the model and displaying it. Once you have that working you can tackle the harder problem of advancing the model by one timeClick.

When advancing the model one timeClick, think about writing separate functions to move a shark, move a tuna, and grow algae. Considering each as a separate case reduces the complexity.

While you are debugging, you will find it useful to have several data files that provide input to test your program. Use I/O redirection to apply your program to a test case. Using the same test cases, as opposed to randomly entering input data, helps you recognize when something unexpected has changed. But, be sure to have several test cases so that different parts of your program are exercised. You can use the test files we've created, of course.

Sample Run

Here's a sample run that shows the output your program should generate. Ideally, your output should match this exactly, except for your greeting message and very minor differences (e.g., an extra newline here or there). In particular, for the sample data, your program and our reference program should lead to the same final state or at least a very similar final state (e.g., "the sharks all die off around step 200 and the tuna and algae live on" or "the sharks eat the last tuna around step 500 and then die off quickly. the algae then grow to occupy every cell.") Note that we represent a cell with a shark in it with the > character, a cell with a tuna in it using ~, and a cell with just algae in it with *. We have some test files that can be fed to your program using unix's input redirections. For example, if you have copied the directory /afs/umbc.edu/users/s/b/sbogar1/pub/wator/tests into the directory containing your project 3, then you should be able to type

% a.out < test/noSharks

Instead of reading input from the terminal window, your program will get its input from the file test/noSharks. Our output for these test files can be found here. We generated the output files by redirecting both the input and output, as in

a.out <tests/noAlgae >output/noAlgae

As you develop and debug your program, you might find it useful to run these and other test files though your program, capturing the output for later examination. You can read about our set of test files in tests/README.

Compiling your program

You will want to do something like the following to compile your program

% gcc -ansi -Wall -c proj3.c
% gcc -ansi -Wall -c wator.c
% gcc proj3.o wator.o creation.o

% gcc -ansi -Wall -c *.c
% gcc *.o

Test data

We will test your program using a special input file that should generate an identical end state if you have implemented things correctly. You can use the files in tests to exercise your program if you like. The test file we will use will be similar to these.

Submitting the Program

Since you must use separate compilation for this project, you will have several files that must be submitted for this project. The source file that contains main( ) MUST be called proj3.c, the file containing your simulation functions MUST be called wator.c, and the header file MUST be called wator.h. You don't need to submit creation.o. We'll find a copy somewhere. To submit your project, type the following at the Unix prompt. Note that the project name starts with uppercase 'P'.

submit cs201 Proj3 proj3.c wator.c wator.h

Do NOT forget to submit your wator.h file. Your program will NOT compile without it.

To verify that your project was submitted, you can execute the following command at the Unix prompt. It will show all files that you submitted in a format similar to the Unix 'ls' command.

submitls cs201 Proj3

Cool stuff

If this project interests you, here are some things you might think about or do.

One thing you can discover in such a simulation is that not all parameter settings will lead to a stable environment, i.e., one in which sharks, tunas, and algae can all co-exist. If the algae completely die out, the entire food chain collapses. If some shark eats the last tuna, the sharks are doomed. If the parameters do allow for a stable ecology, the numbers of sharks, tuna and algae will go up and down and do so following a pattern. Here's an interesting question: can you characterize the parameter sets that lead to a stable environment? Does it depend on the size of the ocean?

In a large ocean you may also see some structures emerge -- like schools of tuna with sharks along the edge, feeding on them. Some of these "emergent phenomena" are difficult to model with mathematical equations and can best be explored through simulations like these.

There is a lot more you can do with this program to make it more interesting, like add simple graphics (using the curses library) or generating data that can be graphed with Microsoft Excel to see how the three populations grow and shrink over time. You must submit a basic program following the specifications we give and without any additional features. We'll grade you on this. But, we do encourage you to produce an enhanced version of your program. We won't give out extra credit for also making an advanced version. But if you do one, we promise that you will (1) have fun; (2) learn a lot; (3) have something you can add to your portfolio to impress prospective employers and friends; and (4) be stimulated. It beats watching TV. We will be happy to review your Proj3++ version, should you create one and to offer suggestions and advice on what to do to make an enhanced version.

Acknowledgements

References

• Sharks and fish wage an ecological war on the toroidal planet Wa-Tor, Computer Recreations, Scientific American, Dec: 14-22, 1984.
• The Computational Beauty of Nature – Computer Exploration of Fractals, Chaos, Complex Systems, and Adaptation, by Gary William Flake. MIT Press, Cambridge (1999). This is an interesting book that has about 20 different chapters, each covering a natural phenomenon that is modeled with a simple C program (included).
• Games of Life: Explorations in Ecology, Evolution and Behavior, Karl Sigmund, Penguin, 1995. A good introduction to lots of alife related topics by Austrian mathematician Karl Sigmund. Well written and funny, but out of print. You can find used copies on amazon and ebay, though. Highly recommended.
• The Selfish Gene, Richard Dawkins, Oxford University Press; 2nd Ed edition (September 1, 1990), ISBN: 0192860925. This classic book by famous evolutionary theorist Richard Dawkins offers a view on how complexity can arise out of natural phenomena.
• The Artificial Life Games web page.
• Exploring Emergence is an "active essay" that demonstrates the concept of emergent behavior using the Conway's Game of Life and a simple Java applet.