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.

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 partially taken by 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 below:

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 (which we imagine as consisting of a huge wall) jump to step n; otherwise, go on with the next instruction in sequence.

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. 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 program in darwin.jar, also in the labs/darwin common directory, to run a sample solution. This will give you a chance to see how the program is supposed to behave. Run it with a command line like

   java -classpath darwin.jar:$CLASSPATH Darwin Hop.txt Rover.txt
   

   while inside a directory that has Creatures as a subdirectory.
3. Write the World class. This should be straight-forward 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 that 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 that 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 that 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 15, 2004 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 23, 2004 at 3:50 PM:
   • Final version of World.java
   • Final version of Species.java
   • Creature.java
   • Darwin.java
   • A 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.

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 ifenemy dir n. This variation on on the ifenemy instruction can check if there is an enemy two steps in front of a creature (this can help make fly traps much more lethal) or to either side (peripheral vision). To do this, the extra parameter dir is interpreted to mean "look one square ahead" for dir==0, "look two squares ahead" for dir==1, "look left" for dir==2, and "look right" for dir==3. Similar variants make sense for the other tests as well.
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. None of these instructions should end a turn. 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. Implement any other extension you find interesting.

Competition

In lab on Wednesday, December 1, we will have two competitions. Everyone is invited to enter one or two creartures into each tournament. The first will allow creatures that use only the basic features of Darwin. The second will allow creatures that also use the extra features described above (better vision, memory, and communication, but not mutation).

Each entry for each competition will be placed into a double-elimination tournament bracket with seedings determined by random draw. Each head-to-head matchup will be decided by the best of three runs, where each run will have the following parameters:

• The universe is 15 ×15.
• Each species starts with 10 creatures, randomly placed on the board facing in random directions.
• A third species (one of rover, flytrap, or food) will also have 10 creatures placed on the screen. The third species will also be determined randomly.
• The order that each creature gets to take its turn on each iteration is determined randomly. There will be a 200 millisecond pause between each iteration.
• A run ends in a win for a species if any of the following occur:
  • all 30 creatures remaining are of that species.
  • 90 seconds elapse and that species has at least 20 creatures on the board.
• A run ends in a draw if any of the following occur:
  • all 30 creatures remaining are of the third randomly-selected species.
  • 90 seconds elapse and neither competing species has at least 20 creatures on the board.

A darwin.jar file will be available in the CS136 common directory that will let you test your creatures with the extended features and the stopping conditions implemented. It will also simulate based on the rules of our game. If you give one of the species names as "random" on the command line, it will randomly choose one of rover, flytrap, or food for that species.

Feel free to practice against each other and discuss your creature ideas with each other, if you'd like.

The decisions of the judge (your favorite CS 136 instructor) are final.