Introduction to Computer Science II by James Tam Return to the course web page

CPSC 233: Assignment 4 (Worth 7%)

Due Monday November 1st.

This page is best viewed with Internet Explorer version 5+ and a computer with a sound card and a darn good set of speakers. 

New concepts to be applied to the assignment

  1. Writing a moderately sized object-oriented program.
  2. Learning problem-solving skills using the object-oriented approach

 

Introduction

The "Game of Life" that I am referring to in this assignment is not the board game created by The Parker Brothers ™ (http://www.hasbro.com) but instead is a biological simulation created by the Cambridge mathematician John Conway.   The simulation consists of a finite sized "biosphere" that is divided into cells.  Each cell is inhabited by a life form that I will refer to as "the Critter".  Critters will live or die depending upon a simple set of rules (described below).   The initial placement of the critters, can result in the cells forming various patterns throughout the course of the simulation (game) as new critters are born into empty cells and existing critters die off.

 

Assignment description

For this assignment you will simulate the biosphere with a 10  x 10 array.   My example executable displays critters using  a "*" (star) while a " " (space) represents an empty square. 

*                  
    *              
                   
  * *              
  *                
                   
            *      
  *       * *      
  *       *        
                   

Each square of the biosphere is always inhabited by a reference to an instance of class Critter.    The difference between the squares that appear full (display a star) vs. the ones that appear empty (display a space) is that the "appearance" field of Critter is either set to a space or star depending upon whether or not the Critter should be displayed or not:

class Critter

{

    private char appearance;

    /*

        Make critter appear: Your solution won't implement this exact method I am including it to illustrate how to make a critter appear.

    */

public void methodOne ()

{

appearance = '*';

}

 

    /*

        Make critter disappear: Your solution won't implement this exact method I am including it to illustrate how to make a critter not appear.

    */

public void methodTwo ()

{

appearance = ' ';
}
}

An alternative to this approach is create an array of references to Critters and only have the inhabited squares contain a Critter and to have the uninhabited squares contain null references.  If you choose this second approach be very careful that you do not call the methods of a null reference!

Your program is to simulate the births and deaths of the critters over time.  Time will pass on a turn-by-turn basis. The user will signal the end of a turn by a key press (e.g., pressing return to continue the simulation or 'Q' to quit).  For each turn that passes your program must scan the entire biosphere:

  1. For squares that currently contain a critter the program must determine which critters die and which critters are unaffected by the turn change. 
  2. For squares that are currently empty the program must determine or if a new critter will be born into that square.

The births and deaths of critters is based solely upon the number of neighbors that a particular critter has. To make things simpler you are to assume that all births and deaths occur simultaneously as a turn passes.  Thus you need two arrays of type Critter.  One array, which I call "previous" in the Biosphere.java file, contains the positions of the critters previous to the turn and is used to determine how many critters are neighbors of a particular square.  The second array, which I call "current" in the "Biosphere.java" file, will initially contain the same pattern of critters as the other array.  However as your program scans the previous array, critters will die in and be born into the "current" array.  Make sure that you do not change the pattern of critters of the previous array while you are scanning the biosphere because as I said earlier births and deaths are assumed to occur simultaneously.

Birth and death conditions for Critters:

1) If there is already a critter in the square (a star is current displayed):

a) The critter will die if: 

    i) It has 0 or 1 neighbors - it dies of loneliness.

    ii) It has 4 to 8 neighbors - it dies of overcrowding. 

b) The critter will go on living as is (won't die) if: 

    i) It has 2 - 3 neighbors - the critter continues as-is.

2) If the square is empty - a critter will be born there (a space is currently displayed) if :

a) There are there are exactly three neighboring critters in the adjacent squares.

How do you determine how many critters neighbor a particular square? Picture the following two dimensional array as a subset of the biosphere array:

     
  X  
     

The square marked with an "X" is a square where we are trying to determine if a birth or death will occur.  In the cases below I will use a "*" (star) to represent the neighboring critters.  The squares that you need to scan will then be the squares adjacent to the square in middle (i.e., above, below, left side, right side, and the four diagonals).  Note: In the examples below I assume that the square to be scanned is an inner square, you will have to write up the exceptional conditions for other cases (e.g., the top and bottom rows, far left and far right edges as well as the four corners - see below when I talk about different grade levels for a more in-depth explanation).

What are the row and column coordinates for the 8 squares relative to the center square above?  If the coordinates for the center square is row = r, column = c then the general formula for determining the row and column coordinates for the neighboring squares is shown below:

General formula:                                                                           

[r-1][c-1]  [r-1][c] [r-1][c+1]
[r][c-1] [r][c] [r][c+1]
[r+1][c-1] [r+1][c] [r+1][c+1]

Example:

 [4][4]  [4][5] [4][6]
[5][4] [5][5] [5][6]
[6][4] [6][5] [6][6]

How does all of this scanning relate to the 10 x 10 biosphere? You must perform all of the above scans for each of the 100 squares. If there is already a critter living in the square, then you must determine if the number of neighbors allow that Critter to continue living. If the square is currently empty, then you must determine if a critter will be born into the empty square.

How do you start the simulation? You must have a biosphere that starts out with a predetermined number of critters which are in set positions and you run the simulation on a turn-by-turn basis in order to determine what happens to the life forms in the biosphere.  I suggest that you start by using the simpler biospheres first and work your way up to the more complex ones.   The more biospheres that your program can properly handle, the higher your grade will be for this assignment.

 

Grading

There are two ways to handle edges and corners. With the A- (and lower level assignments) you essentially create a 10x10 array in your assignment but only use 8 x 8 squares. The outer border of squares will appear empty (i.e., the Critter displays a space)  and you use rows 1 - 8 and columns 1 - 8 as places where Critters can live (can display a star or a space).   Row 0 and 9 and column 0 & 9 will be filled with critters whose appearance field is set to a space (or null references).   Because no critters live in any of these locations, they will have a value of zero (they won't count when you do a critter count for adjacent squares). The boxes labeled with a question mark are part of the biosphere (which may or may not contain a critter).

i.e.,

E E E E E E E E E E
E ? ? ? ? ? ? ? ? E
E ? ? ? ? ? ? ? ? E
E ? ? ? ? ? ? ? ? E
E ? ? ? ? ? ? ? ? E
E ? ? ? ? ? ? ? ? E
E ? ? ? ? ? ? ? ? E
E ? ? ? ? ? ? ? ? E
E ? ? ? ? ? ? ? ? E
E E E E E E E E E E

The reason why I suggest that you make the array bigger than the simulated biosphere is so that when apply the formula for critter births and deaths you don't have to make a special exception for the corners and edges (making it more efficient). But if do follow this suggestion, you must make sure that you don't traverse the whole array when checking for births and deaths, just the inner part  that is capable of supporting life (rows & columns 1 - 8).

Grades for working assignments:

Biosphere 1 (The Barren Realms: The empty biosphere): C-

Program can only handle the empty biosphere (i.e., the person selects the option called "The barren realms" while running my sample executable).  It's a 10x10 world that is completely empty. Run it thru a few turns. If ever a critter suddenly appears in this barren wasteland then you are doing something wrong with your births algorithm.  A good basic starting test.

Biosphere 2 (Doomed for extinction: The deaths biosphere):  C+

Program meets the "C-" requirements plus it can properly handle the "deaths" biosphere (i.e., the person selects the option called "Check deaths" while running my sample executable).  The three critters scattered throughout the biosphere should all die in one turn :-(. If they don't go away then you again know that something is wrong with the algorithm that checks for deaths. 

Biosphere 3: ("The stork's day": The births biosphere): B

Program meets the "C+" requirements plus it can properly handle the "births" biosphere (i.e., the person selects the option called "Check births" while running my sample executable).  This biosphere starts out with three critters.  On the first turn the three critters die off but they give birth to a new critter.  This critter dies off during the next turn.

Biosphere 4 (You make my head spin):  A-

Program meets the "B" requirements plus it can properly handle the "spinning/stable" biosphere (i.e., the person selects the option called "Spinning around" while running my sample executable).  The biosphere consists of 3 critters in a vertical line. From turn-to-turn this line should appear to rotate from vertical to horizontal (and back again) endlessly. A very good complex test to of the "critter is born" and "critter dies" algorithms.   Also it checks if you can properly copy your arrays between multiple turns.

Biosphere 5 (Four friends forever - The advanced test case):  A+

Program meets the "A-" requirement plus it can deal with cases where Critters inhabit the outer fringes of the biosphere (the top and bottom rows, the left and right-most columns as well as the four corners).  With this biosphere,  you cannot make the outer fringes of the biosphere empty and you must be able to figure out how to handle the special cases. You cannot make an oversized (12x12) array because this is a more advanced test.  After 25 turns the pattern of Critters should stabilize into a rectangle consisting of 4 Critters.

In all cases your program must draw a numbered grid around the biosphere.  This will not only make marking of your programs easier but also simplify your debugging process.

Design requirements for all grade levels: You need to implement five classes: Driver, CommandProcessor, Debug, Critter and Biosphere:

  1. Class Driver: The starting point of execution in the program (contains the main method).

  2. Class CommandProcessor: The purpose of this class to provide an interface to the user: it shows the available menu options as prompting the user for his or her selection. 

  3. Class Debug.  To fulfill the assignment requirements you demonstrate that you have implementing some sort of debugging mechanism within your program.  This could take the form of output statements to display the state of the biosphere at various points in the program or something that checks that your births and deaths algorithms are working properly.  (Select option "-1" at the menu of sample executable to turn on some sample debugging messages).  The Debug class could prove useful because the static flag can be set to "on/true" to display these debugging messages when you are trying to fix a bug and set to "off/false" when you are no longer fixing bugs and have finished your assignment.

  4. The Critter class: Your implementation of the Critter class must include an attribute that is used to store information about the critter's appearance.  Whenever the your program runs through the loops to display individual squares of the biosphere, the character that is displayed for a particular square will be determined by the appearance attribute of the critter (in the case of this assignment it will either be a star or a space).

  5. The Biosphere class:  It is almost certain that most of your code for this assignment will end up in the methods of this class.  One important task that should be handled by this class will be the maintenance of the biosphere: scanning the squares in order to determine where Critters will be born and where they will die.  Break down this main task into sub-methods as much as possible e.g., the main job of scanning the biosphere should be broken down into smaller jobs such as: i) scanning the inner parts of the biosphere (rows 1 - 8 and columns 1- 8) ii) scanning the top row only (row 0) iii) scanning the bottom row (row 9) iv) scanning the left-most column (column 0) v) scanning the right-most column (column 9) vi) scanning the four corners.   Your grade could be adversely affected if you only implemented one very large method that handled all the above tasks.

Grades for non-functional assignments

D level assignment

Student has invested considerable work in the assignment and the code compiles but it doesn't fulfill any of the above requirements (it can't properly handle any of the above biospheres).

D- level assignment

Student has invested considerable work in the assignment but it doesn't compile.

 

Other submission requirements

  1. Good coding style and documentation:  They will play a role in determining your final grade for this assignment.  Your grade can be reduced by a letter step or more e.g., "A" to "A-" for poor programming style such as employing poor naming conventions for identifiers, insufficient documentation, the use of global variables (other than the debugging flag) or by not assigning the proper operations and attributes to classes.

  2. Include a README file in your submission:  For this assignment your README file must indicate what functions you have completed as well as the grade level that you are aiming for.  This will allow your marker to quickly determine what he or she must look for and speed up the marking process.  

  3. Assignments (source code and the README file) must be electronically submitted via submit.  In addition a paper print out of the source code must be handed into the assignment drop box for the lab that you are registered in (located on the second floor of the Math Sciences building).  Electronically submitting the assignment allows your marker to run the code in order to quickly determine what features were implemented.  Providing a paper printout makes it easier for your marker to read and flip through your source code.

  4. A demonstration of your working program with your TA will be required.  The demonstrations will take place in lab time but you must book a specific period of time with your TA.  If you do not demo your code to your TA, then the maximum grade that will receive is a "D".  Further details will be provided in the tutorials about the demos.

 

Suggested Approaches to this Assignment:

1) Start early!  For what it might be worth this was one that stumped me when I had to do it in first year - for a while at least but even I got through it eventually :-).

2) Take it in small steps 

  1. Make sure you are manipulating the arrays properly - start by initializing the arrays and display the results to the screen just to make sure that this part is fully working before you move on. 
  2. Start out with simple cases  and work your way up the following hierarchy of test cases.

3) Make liberal use of debugging aids such as including output statements in your program. Try to isolate your test cases (e.g., . test the "critter dies" and "critter is born" algorithm separately if you get really stuck).   Make liberal use of "print's" and "println's" to view your happy little biosphere.  Doing things like this really helps you figure out where things are going wrong, this is why I listed it as one of the assignment requirements.

4) If you need help and can't seem to get any (e.g., if my office hours really suck and you have a knack for catching me away from my desk then try email and I might be able to sit down with you some time).  Of course I must warn you all that I am more of a night person that a more person though so those 8 AM appointments are rather bad for me...

5) Have fun! Remember this is only one assignment folks and not the whole semester. 

Relevant files

Source code files can be found in Unix in the directory /home/233/assignments/assignment4:

  1. Debug.java: A class that you can use to fulfill the debugging requirement and to help you debug your program.
  2. Critter.java: Instances of this class represent the inhabitants of the biosphere.  All squares, empty or not, will be inhabited by critters.  The difference is that empty squares will have the Critter's appearance set to a space while non-empty squares will have the Critter's appearance set to a star.  My source code file has a private field called "appearance" to get you started off.
  3. Biosphere.java:  This will be the largest class that you implement for this assignment.  It includes all information about the biosphere including the critter positions before and after the deaths and births have occurred for a turn.   Also includes the code for scanning the biospheres.  The source code file automatically initializes the different biospheres for you and you have to figure out how to implement everything else. 

The sample executable for this assignment can also be found in the above directory:

  1. "gameOfLife"

Note: This is a regular binary file not a byte code file so it cannot be run through the Java interpreter.  To run the executable type "./gameOfLife" at the command line where this file resides.

Relevant links

  1. http://www.math.utk.edu/~conway/ (John Conway's faculty web page at the University of Tennessee)
  2. http://www.bitstorm.org/gameoflife/ (An online version of the game of life)