CSE 8B: Introduction to Computer Science: Java (Winter, 2006)

Programming Assignment 4

Last modified: February 6 at 5:30 PM Updated explanation of Doodlebug dying (it looks a lot more like dying after 4 time periods)

Previous modifications:

• February 6 at 9:15 AM Added Plan of Atack
• February 1 at 9:15 AM Major change: you are now given Simulation and TestSimulation source code.
• January 31, at 2:20 PM Hint on using Scanner.nextLine.
• January 31, at 2:15 PM (No, it isn't OK to hardwire your program to spit out solutions when it sees our input).

Overview

.........D
...A......
A.DD....A.
.....D...A
.A...A..AD

• Ant: Has 2 actions it takes:
  • Moves in a random direction (left, bottom, right, or top). If there is another critter in the desired position, it does not move. Similarly, it won't move off the edge of the board.
  • Gives birth. Every three timesteps, the ant will give birth. The new ant will be placed in a random direction from the birthing ant. If there is another critter in the new place, no new ant is birthed. If the new place is off the edge of the board, no new ant is birthed.
• Doodlebug: Has 3 actions it takes:
  • Dies. If a Doodlebug goes more than three timesteps without eating, it dies (See testinput 4 for details on how that works. If you have a new doodlebug in step 0, it'll die in time period 5).
  • Moves in a random direction (left, bottom, right, or top). If there is an Ant in the desired position, it moves onto it and eats it. If there is a Doodlebug in the desired position, it does not move. It won't move off the edge of the board.
  • Gives birth. Every eight timesteps, the Doodlebug will give birth. The new doodlebug will be placed in a random direction from the birthing Doodlebug. If there is an ant in the new place, the doodlebug is birthed and the ant is eaten. If the new place is off the edge of the board, no new doodlebug is birthed.

Input/Output

the number of rows in the board
the number of columns in the board
the number of timesteps to simulate
board

• . to represent an empty location
• A to represent an ant
• D to represent a doodlebug

10
5
10
.........D
...A......
A.DD....A.
.....D...A
.A...A..AD

At time 0:
.........D
...A......
A.DD....A.
.....D...A
.A...A..AD

At time 1:
...A....D.
..........
.DD.......
....DA..AA
A.......AD

At time 2:
.......D..
.DDA......
....D...A.
......A..A
A.......AD

At time 3:
..........
.DD.AA.D.A
...D.....A
.....AA.AD
A.......A.

At time 4:
.D...A...A
.D....D...
..D.AA..A.
.......AA.
A......A.D

At time 5:
.D...A...A
..........
...A..AA.A
..........
A.....A.D.

At time 6:
......AA..
.........A
.....AAA.A
A..AA.AA.A
A......D..

At time 7:
......AA..
........A.
...A.AAA.A
.A...AADA.
A.........

At time 8:
......AA..
......AA.A
.A..AA.AA.
.....AA...
.A....DD..

At time 9:
......AA.A
A...AAA.A.
A..A.AA...
AA.A.ADAAA
......D...

At time 10:
A.....A..A
....AAAA.A
A..AAAA...
A...ADA...
.A....D.AA

java Simulation < testInput.txt > myOutput.txt
diff myOutput.txt testOutput.txt

Provided files

There are four Java files provided: a Random number generator in Rand.java, and a class representing pairs of integers in Pair.java.

I've also provided you Simulation.java and TestSimulation.java. You can choose to use these files as-is, use them as a starting point for your code, or write your own code from scratch. You'll still need to turn in the Simulation.java file (even if it is unchanged).

The random number generator has one method: nextDirection which returns an integer from 1 to 4. The direction should be interpreted as:

• 1: right
• 2: down
• 3: left
• 4: up

The Rand class has two constructors, a default one, and one taking an array of integers. You need to use the default constructor to solve this exercise, however, the other one can be useful for your unit testing (see Unit Testing section).

The Rand object will always generate the same sequence of random directions. That way, the directions the critters move is reproducible; it'll be the same in each student's application, as well as in my solution.

In addition to the Java files, there are test input and output in ~/../public/P4/tests. For each test, there are three files:

• Testtest#in.txt: the input to the Java Simulation
• Testtest#out.txt: the desired output
• Testtest#outdebug.txt: the output along with lots of debugging information, showing when movement happens, births, deaths, etc. This is useful to see how the internals of my simulation is working.

Unit Testing

This assignment is large enough that unit tests will help in writing your application tremendously. In order to use unit tests, you'll be testing the functionality of your classes, and not doing much testing of the actual input/output of this program (that's a form of acceptance testing, rather than unit testing).

In order to make your critters move in exactly the direction you want (for testing purposes), you can use the Rand class with one constructor that takes an array of directions. So, if you want to test placing an ant on the board, and having it move right, you could create a Rand object with:

    int [] arr = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, };
    Rand r = new Rand(arr);

Organization

• Simulation: Responsible for storing the board, reading in the initial board, looping, running a timestep of the simulation by sending messages to each object on the board, and printing out the board contents. The only thing a Simulation should know about an Ant or Doodlebug is that if the input is an A to make an Ant, and if the input is a D to make a Doodlebug. All other code in Simulation should treat Ants and Doodlebugs as Critters, oblivious to their actual runtime type.
• Critter: An abstract class responsible for capturing the commonality between Ants and Doodlebugs. It should support running one time step, moving, providing the character (A or D) for this Critter.
• Ant: should be a subclass of Critter, and override methods and/or set Critter instance variables that capture how an Ant is different from a generic Critter.
• Doodlebug: should be a subclass of Critter and override methods and/or set Critter instance variables that capture how a Doodlebug is different from a generic Critter.

Plan of Atack

1. Get the thing to compile and pass its first test
   1. I'd comment out the code in readBoard; there's a lot to do before trying to deal with reading in boards and running time steps. I'd comment out the code because it tries to instantiate Ants and Doodlebugs, and I don't want to worry about Doodlebugs until sometime down the road.
   2. Create a Critter class with the 2 needed abstract methods (trying to compile Simulation.java will tell you what those methods are).
   3. At this point, Simulation.java should compile.
   4. Comment out tests but the first in TestSimulation.java. We do this because the tests won't work, and we want to build up working tests.
   5. Comment out the code that instantiates a new ant in the setUp method of TestSimulation.
   6. Comment out the declaration of the Ant in TestSimulation.
   7. At this point, you should be able to pass the first test: testEmptySimulation.
2. Get the second test, testWithOneCritter, to pass by uncommenting out the code dealing with Ants from TestSimulation you commented out in the last step. You'll also need to actually write an Ant class that overrides the two methods from Critter. Your oneTimeStep doesn't need to do anything yet!
3. At this point, lots of other tests probably work (all the ones that test the Simulation up through testMoveCritterUpLeftAtEdge).
4. Get the testSimpleStep to work. You'll need to actually make oneTimeStep do something in the Ant, but it need not worry (yet) about anything in the way).
5. Get testSimpleStepWithImpediment working. You'll need to check before moving to see if there's anything in the way.
6. Get testManySteps to work. That'll require writing a Doodlebug class that implements the two abstract methods from Critter. The Doodlebug will also need to move. Once you get this test working, refactor by moving common code shared between Ant and Doodlebug to a common method in Ant. For example, if you have a move method in Ant and a move method in Doodlebug that both do the same thing, create a single move method in Critter.
7. Get testDoodlebugEat to work. That'll require separate code for Doodlebugs and Ants because Ants can't move onto other critters, but Doodlebugs can move onto Ants. Most of the code for moving will be the same between the two classes, but the code for checking whether it's valid to move onto a space will be different. So, make a method in Critter for doing that checking. Override it one way in Ant and another way in Doodlebug.
8. Get testDoodlebugBreed to work. You'll need to keep track of timesteps in order to do this.
9. Note that there are no unit tests for ants breeding or for doodlebugs dying. You'll probably want to write these and get them working.
10. Now you're in a position to start testing with input. Uncomment out the code in readBoard and start testing the overall program rather than the unit tests. If you find that the sample output doesn't match your output, trace through the detailed dump and find how it works differently than yours. Write a unit test based on that analysis and get the unit test working. Then, try testing with the input again. One very important note: you've got to be calling the randomDirection method the same number of times and in the same order as the test did, otherwise you'll get out of sync.
11. When your code is handling all the inputs correctly, refactor. Find any common code you can that's shared between Ant and Doodlebug and move it into methods in Critter. Find any common code in Critter and put that in new methods. Remember, don't repeat yourself.

Hints

• Store your critters in a two-dimensional array of Critter.
• Your critters will probably need to have an instance variable referring to their simulation (so they can move, etc.). When a critter is either constructed or added to the board, tell it what its simulation is.
• You can move lots of functionality out of the Ant and Doodlebug classes into the Critter class. For example, my Ant class has two overridden methods, each one line long, and a constructor that sets two instance variables.
• Consider having a top-level public method in Critter like oneTimeStep that then calls protected methods to move and to give birth.
• It can be useful to have an option for your simulation (and critters) print out lots of information as they go about their business when in debug mode. The easiest way to do that is have your Simulation take an extra command-line argument to turn on debugging. Here's how to check for a command-line argument:

    public static void main(String[] args) {
      if (args.length > 0 && args[0].equals("-debug"))
        debug = true;
  

  Then, in code in Simulation, you can check for the debug flag before printing:

    public void addCritter(Critter c, int col, int row) {
     if (Simulation.debug) 
       System.out.println("adding critter to " + col + " " + row);
     ...
    }
  

  This way, you can run java Simulation to run your program quietly, or java Simulation -debug to run with lots of debugging output.
• When you are running one time step in the simulation, keep in mind that you'll need to figure out what critters are on the board and their order before starting to move them. That is, you can't just iterate through the cells of the board, telling each critter you find to run one timestep. You can't do that because critters move. If you tell a critter to move down one row, you don't want to run into that critter again as you're iterating through the board (learn from my mistake:)). Instead, create an array of all the critters to deal with (in order), and then iterate through that array (which won't change). Here's how my Simulation.oneTimeStep works (note that this is not actual java code, but is pseudo-code:

    public void oneTimeStep() {
      arrayOfCrittersToDealWith = getCritters();
      foreach critter in arrayOfCrittersToDealWith
        if critter is not null
          tell critter to do one time step
      } 
    }             
  

• You may find it useful to have a location() method in Critter that returns the Pair representing row and column. It might call a Simulation method findCritter that does the actual work.
• Be consistent in how you treat rows and columns. Make sure all methods that take a row and column take them in the same order. Make sure that you access and set the two-dimensional array consistently.
• When running one timestep for a Critter, keep in mind that the critter may already be dead (eaten or died from starvation). Don't try to move it, etc. if it has isn't on the board.
• Store a Rand object in your Simulation object. Always get a new direction from that Rand object.
• Grow your program incrementally using unit tests to guide you. Start with an empty board and one Ant on the board. Verify that if you find the ant's location, it matches where it is supposed to be. Then, move the ant and verify it's new position is where it is supposed to be. Add in the random movement later; make sure deterministic movement works first!
• To read in the input, use the Scanner class (Scanner in = new Scanner(System.in)). You'll find that nextInt, which reads the next integer, and nextLine, which reads the next string (up to a newline) are useful methods.

Turnin

• Simulation.java
• Critter.java
• Doodlebug.java
• Ant.java

  bundleP4

Grading

The assignment is worth 20 points:

• 8 points: Simulation that runs the sample input we've provided correctly. Note that it must be solving the predator/prey problem, not just hardwired to look for our sample input, and regurgitate the needed output.
• 8 points: Simulation that runs some new input correctly.
• 4 points: Style points for your classes. Good naming, not repeating yourself, correct indentation, not exceeding 80 characters per line, good organizing of methods into classes, etc.