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 objective of this assignment is to give you practice with arrays and
structures, with using call by reference and using random numbers. It also shows
the power of using a discrete simulation to model, explore and understand complex,
dynamic systems.
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
Your simulator will have a model that is initialized with some life forms and
simulates change in the world over a number of discrete time steps specified by
an input parameter. Periodically, the model will be displayed by printing a representation
on the standard output.
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.
rows |
integer number of rows in the ocean array |
cols |
integer number of columns in the ocean array |
numSharks |
integer number of sharks when the simulation begins |
numTunas |
integer number of tunas when the simulation begins |
numAlgae |
integer number of algae when the simulation begins |
starveShark |
integer number of timeclicks until a shark dies of starvation if it has
not eaten |
starveTuna |
integer number of timeclicks until a tuna dies of starvation if it has
not eaten |
reproShark |
integer number of timeclicks until a shark is ready to reproduce |
reproTuna |
integer number of timeclicks until a tuna is ready to reproduce |
grow |
integer number of timeclicks until an alga is ready to grow |
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.
At each step, each alga will:
- 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
We've developed a module (creation.o) that defines
a function PopulateOcean( ) that you should call to populate your array with an
initial set of sharks, tuna and algae. You should copy this file (a copy can also
be found at /afs/umbc.edu/users/f/i/finin/pub/201/s05/proj3/creation.o) into your
Proj3 directory and compile it along with your proj3.o and wator.o files to produce
your final executable. The file creation.h must be #included
in both the proj3.c and wator.c files. See the comments in creation.h
to find out what arguments it will require. If you are curious, see the source
code: creation.c. Note that When the ocean is originally
populated there are fish with varying times left until starvation and varying
times left until reproduction. This is why you won't see all sharks that haven't
eaten yet to die of starvation at the same time.
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.
character |
cell state |
' ' |
nothing in the cell |
'>' |
cell contains only a shark |
'>' |
cell contains a shark and algae |
'~' |
cell contains only a tuna |
'*' |
cell contains only algae |
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:
- shark
- tuna
- 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
Actually, if you are doing this in a directory that only contains your project
three files, you may be able to use Unix's ability to expand a file name with
wild cards to do the following
% 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
Wator is a popular programming project and you can find many implementations on the
Internet. As originally defined and usually implemented, it involves just two life
forms: a predator and a prey. This three species version was inspired by an assignment
developed by Dr. David Matuszek of the University of Pennsylvania. Thanks Dave.
References
If you find
this project interesting, you might look into the following references. This could
be a good topic for an independent study project in the future.
- 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.
CSEE
|
201
|
201 S'05
|
lectures
|
news
|
resources
|
help |
|