Computer Science 136 Data Structures and Advanced Programming Williams College Fall 2005

Short Answers

Complete the following problems from the book, and the extra questions below, and turn them in as a text file lab9.txt at the start of lab.

Extra Question: Under what circumstances would a get method as described in question 10.13 be more useful than the existing contains method? Write a get method for OrderedVector.

Lab Program

Darwin

In this assignment, your job is to build a simulator for a game called Darwin invented by Nick Parlante. The assignment has several purposes:

1. To give you more practice writing large, multi-class programs.
2. To illustrate the importance of modular decomposition and information hiding. The entire program is broken down into a series of classes that can be developed and tested independently, without revealing representational details.
3. To have fun with a problem that is algorithmically interesting in its own right.

Since this is a larger program than the previous labs, and since next Wednesday's lab period will be used for the second exam, you will have two weeks to complete it.

The Darwin World

The Darwin program simulates a two-dimensional world divided up into small squares and populated by a number of creatures. Each of the creatures lives in one of the squares, faces in one of the major compass directions (North, East, South, or West) and belongs to a particular species, which determines how that creature behaves. For example, one possible world is shown in Figure *.

The sample world in Figure * is populated with twenty creatures, ten of a species called Flytrap and ten of a species called Rover. In each case, the creature is identified in the graphics world with the first letter in its name. The orientation is indicated by the figure surrounding the identifying letter; the creature points in the direction of the arrow. The behavior of each creature-which you can think of as a small robot-is controlled by a program that is particular to each species. Thus, all of the Rovers behave in the same way, as do all of the Flytraps, but the behavior of each species is different from the other.

As the simulation proceeds, every creature gets a turn. On its turn, a creature executes a short piece of its program in which it may look in front of itself to see what's there and then take some action. The possible actions are moving forward, turning left or right, or infecting some other creature standing immediately in front, which transforms that creature into a member of the infecting species. As soon as one of these actions is completed, the turn for that creature ends, and some other creature gets its turn. When every creature has had a turn, the process begins all over again with each creature taking a second turn, and so on. The goal of the game is to infect as many creatures as possible to increase the population of your own species.

Species programming

In order to know what to do on any particular turn, a creature executes some number of instructions in an internal program specific to its species. For example, the program for the Flytrap species is shown below:

Programs are executed beginning with the instruction in step 1 and ordinarily continue with each new instruction in sequence, although this order can be changed by certain instructions in the program. Each creature is responsible for remembering the number of the next step to be executed. The instructions that can be part of a Darwin program are listed below:

hop:

The creature moves forward as long as the square it is facing is empty. If moving forward would put the creature outside the boundaries of the world or would cause it to land on top of another creature, the hop instruction does nothing.

left:

The creature turns left 90 degrees to face in a new direction.

right:

The creature turns right 90 degrees.

infect n:

If the square immediately in front of this creature is occupied by a creature of a different species (an "enemy") that creature is infected to become the same as the infecting species. When a creature is infected, it keeps its position and orientation, but changes its internal species indicator and begins executing the same program as the infecting creature, starting at step n of the program. The number n is optional. If it is missing, the infected creature should start at step 1.

ifempty n:

If the square in front of the creature is unoccupied, update the next instruction field in the creature so that the program continues from step n. If that square is occupied or outside the world boundary, go on with the next instruction in sequence.

ifwall n:

If the creature is facing the border of the world along one side (which we imagine as consisting of a huge wall) jump to step n; otherwise, go on with the next instruction in sequence. Note that the world wraps around from north to south, but not east to west.

ifsame n:

If the square the creature is facing is occupied by a creature of the same species, jump to step n; otherwise, go on with the next instruction.

ifenemy n:

If the square the creature is facing is occupied by a creature of an enemy species, jump to step n; otherwise, go on with the next instruction.

ifrandom n:

In order to make it possible to write some creatures capable of exercising what might be called the rudiments of "free will," this instruction jumps to step n half the time and continues with the next instruction the other half of the time.

go n:

This instruction always jumps to step n, independent of any condition.

A creature can execute any number of if or go instructions without relinquishing its turn. The turn ends only when the program executes one of the instructions hop, left, right, or infect. On subsequent turns, the program starts up from the point in the program at which it ended its previous turn.

The program for each species is stored in a file in the subdirectory named Creatures in the assignment folder. Each file in that directory consists of the species name and color, followed by the steps in the species program, in order. The program ends with an empty line. Comments may appear after the blank line or at the end of each instruction line. For example, the program file for the Flytrap creature looks like this:

Food: This creature spins in a square but never infects anything. Its only purpose is to serve as food for other creatures. As Nick Parlante explains, "the life of the Food creature is so boring that its only hope in life is to be eaten by something else so that it gets reincarnated as something more interesting."

Hop: This creature just keeps hopping forward until it reaches a wall. Not very interesting, but it is useful to see if your program is working.

Flytrap: This creature spins in one square, infecting any enemy creature it sees.

Rover: This creature walks in straight lines until it is blocked, infecting any enemy creature it sees. If it can't move forward, it turns.

You can also create your own creatures by creating a data file in the format described above.

Your Assignment

Your mission is to write the Darwin simulator and get it running. The program is large enough that it is broken down into a number of separate classes that work together to solve the complete problem. You are responsible for implementing the following classes:

Darwin: This class contains the main program, which is responsible for setting up the world, populating it with creatures, and running the main loop of the simulation that gives each creature a turn. The details of these operations are generally handled by the other modules. New creatures should be created in random empty locations, pointing in random directions.

Species: This class represents a species, and provides operations for reading in a species description from a file and for working with the programs that each creature executes.

Creature: Objects of this class represent individual creatures, along with operations for creating new creatures and for taking a turn.

World: This class contains an abstraction for a two-dimensional world, into which you can place the creatures.

Skeletons of these classes are provided in the starter folder. You should not need to add any additional public methods to these classes (although you may if you think it improves the design). You will, however, probably want to add additional protected methods as you implement the classes. In addition, we provide you with three helper classes that you should use without modification:

Instruction: This simple class represents one instruction out of the instruction set of the Species.

Position: This class represents (x,y) points in the world and constants for compass directions.

WorldMap: This class handles all of the graphics for the simulation.

Strategy

Here is a suggested course of action to implement Darwin:

1. Copy the starter files contained in darwin-startup.tar under labs/darwin from the CS136 common areas on cortland or FreeBSD.
2. You can use the command darwin to run my version of the simulator on the FreeBSD systems or TCL 217a Macs. This will give you a chance to see how the program is supposed to behave. Run it with a command line like

   darwin Hop.txt Rover.txt
   

   while inside a directory that has Creatures as a subdirectory containing those two creature instruction files.

3. Write the World class. This should be straightforward if you use a Matrix object or a 2-dimensional array to represent the world. Test this class thoroughly before proceeding. Write a main method in the World class and verify that all of the methods work.
4. Write the Species class. The hardest part will be parsing the program file and storing it in the Species. Note that the first instruction of a program is at address 1, not 0. Test this class thoroughly before proceeding. Write a main method in the Species class and verify that all of the methods work.
5. Fill in the basic details of Creature class. Implement only enough to create creatures and have them display themselves on the world map. Implement takeOneTurn for the simple instructions (left, right, go, hop). Test the basic Creature thoroughly before proceeding. Write a main method in the Creature class and verify that all of the methods work.
6. Begin to implement the simulator in the Darwin class. Start by reading a single species and creating one creature of that species. Write a loop that lets the single creature take 10 or 20 turns.
7. Go back to Creature and implement more of the takeOneTurn method. Test as you go-- implement an instruction or two, and verify that a Creature will behave correctly, using your partially written Darwin class.
8. Finish up the Darwin class. Populate the board with creatures of different species and make your main simulation loop iterate over the creatures giving each a turn. The class should create creatures for the species given as command line arguments to the program when you run it. See Darwin.java for more details. Run the simulation for several hundred iterations or so. You can always stop the program by pressing control-C in the terminal window or closing the Darwin Window.
9. Finally, finish testing the implementation by making sure that the creatures interact with each other correctly. Test ifenemy, infect, etc.

What to Turn In

You will submit the program in two phases:

1. You must turn in preliminary versions of World.java and Species.java by Monday, November 14, 2005 at 9:00 AM. You should test these classes by themselves and provide tests to demonstrate that they work properly.
2. You must turn in the following five files by Tuesday, November 22, 2005 at 3:50 PM:
   • Final version of World.java
   • Final version of Species.java
   • Creature.java
   • Darwin.java
   • One or two Species of your own design. It can be as simple or as complex as you like. We will pit your creatures against each other to watch them battle for survival. Fabulous prizes will be awarded. We will run all simulations on a 15 ×15 grid populated with 10 creatures from each of 4 species.

Possible Extensions

There are many ways to extend the program to simulate more interesting Species behavior. Here are just a few ideas if you wish to extend Darwin for extra credit:

1. Give creatures better eyesight.
   • Add if2enemy n. This instruction checks if there is an enemy two steps in front of a creature. This can help make fly traps much more lethal.
   • Add ifenemyleft n and ifenemyright n. These variations on the ifenemy instruction can check if there is an enemy to either side.
   You can add similar versions of the other tests too.
2. Give creatures memory. This can be as simple as permitting each creature store a single integer. You can then add the following instructions to the instruction set:
   • set n to set a creature's memory;
   • ifeq v n to jump to address n in the program if a creature's memory contains v; and
   • inc and dec to add and subtract from memory.
   You can get more coordinated activity by using this type of memory.
3. Give creatures the ability to communicate. Once creatures have memory, let them ask the creature on the square infront of them what is on its mind with the ifmemeq v n. This instruction reads the memory of the creature in the square infront of a creature and jumps to n if that value is v. You can also add copymem that copies the value in the memory value of the creature in front of you to your own memory. These instructions permit creatures to form quite successful "phalanx" formations.
4. Make creatures mutate. Perhaps copies of creatures aren't quite the same as originals-- when a creature infects another creature, make there be a chance that the infected creature will be a mutation of the infecting creature's species. This will require creating new Species that are close, but not quite exact, copies of an existing Species. Taken to its extreme, you can make species evolve over time to become better and better at surviving in the Darwin world.
5. Add "configurable" walls. This requires changes to the World to support walls, likely with an interface that both Creature and a new class Wall implement. Given this, you could make the universe wraparound in all directions, placing walls along border (or anywhere else that you wish to have creatures unable to go), possibly read in from a configuration file or selected among a set of preconfigured setups.
6. Implement any other extension you find interesting.

Note that when we have our competition, we will use a Darwin simulator with the original rules, so the creatures you enter should not make use of any extensions.