| Introduction to Computer Science II by James Tam | Return to the course web page |
This page is best viewed with Internet Explorer version 5+ and a computer with a sound card and a darn good set of speakers.
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 form various patterns throughout the course of the game as new critters are born into empty cells and existing critters die off.
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 one instance of class Critter. The difference between the squares that appear empty (display a star) vs. the ones that appear full (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:
ie.,
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 Critters but to 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 try to use 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 "y" to continue the simulation or "n" to quit the program). For each turn that passes your program must scan the entire biosphere:
- For squares that currently contain a critter, the program must determine, which critters die and which critters are unaffected by the turn change.
- For squares that are currently empty the program must determine or if a new critter will be born into a square or not.
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 neighbor 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 from 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!
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.
2) If the square is empty - a critter will be born there if (a space is currently displayed):
a) There are there are exactly three neighboring critters in the adjacent squares.
How do you determine what the neighbors for a particular critter are? Picture the following two dimensional array that is 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).
e.g., (critter already in square to be scanned) - critter dies of loneliness (no neighbors or just one neighbor).
e.g., (critter already in square to be scanned) - critter dies from overcrowding (in this example the critter has four neighbors - it also dies if there are more than four neighbors)
e.g., (empty square) - critter will born into the square containing the "happy critter" (there is exactly 3 neighbors).
e.g., (critter already in square to be scanned) - no change to the critter (two or three neighbors)
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 or not.
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 (shown below) and work your way up from the simplest ones to the more complex ones. The more biospheres that your program can properly handle, the higher your grade will be for this assignment.
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 9 x 9 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 spaces (or critters whose appearance field is set to a space). Because no critters live in any of these locations, they will have a value of zero (won't count when you do a critter count for adjacent squares). This value will be used by it's neighbor squares when trying to determine births and deaths. The boxes labeled with a question mark are part of the biosphere (which may or may not contain a critter).
i.e.,
| SP | SP | SP | SP | SP | SP | SP | SP | SP | SP |
| SP | ? | ? | ? | ? | ? | ? | ? | ? | SP |
| SP | ? | ? | ? | ? | ? | ? | ? | ? | SP |
| SP | ? | ? | ? | ? | ? | ? | ? | ? | SP |
| SP | ? | ? | ? | ? | ? | ? | ? | ? | SP |
| SP | ? | ? | ? | ? | ? | ? | ? | ? | SP |
| SP | ? | ? | ? | ? | ? | ? | ? | ? | SP |
| SP | ? | ? | ? | ? | ? | ? | ? | ? | SP |
| SP | ? | ? | ? | ? | ? | ? | ? | ? | SP |
| SP | SP | SP | SP | SP | SP | SP | SP | SP | SP |
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).
Program can meet the C+ level requirements plus it can properly handle the "deaths" biosphere (i.e., the person selects the option called "Check deaths" while running my sample executable)..
Program can meet the B- level requirements plus it can properly handle the "births" biosphere (i.e., the person selects the option called "Check births" while running my sample executable).
Program can meet the B level 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).
Program can meet the B+ requirements plus it can properly handle the first of the advanced biospheres required for Assignment 3. If your program is running properly then the biosphere should reach a stable pattern, a rectangular box of 4 critters by about turn 20.
Program can meet 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). This means that your program can handle the second of the advanced biosphere for this assignment. With this biosphere, you cannot make outer fringes of the biosphere empty and you must be able to figure out how to handle the special cases.
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).
Student has invested considerable work in the assignment but it doesn't compile.
e.g., If your program can handle the births biosphere and it draws a numbered grid around the biospheres then it may qualify for a B+ level submission (assuming it meets all the "other submission requirements" listed below).
3. Breaking down the assignment: Since one of the things that you should learn from this assignment is how to work with larger programs that consist of more than just two classes you must learn how to split the implementation among several classes. The breakdown shown below includes things that you have to do in your assignment (labeled "mandatory") as well some suggestions for how you could handle other parts (labeled "optional").
Classes that your program must include (i.e., they are all mandatory):
A class that your program may include: (the class itself is optional but employing a built-in debugging mechanism is not - see the explanation below)
a) The Critter class:
Your implementation of the Critter class must include an attribute that is used to store information about the critter's appearance
e.g., private char 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 of the critter (in the case of Assignment 3 it will either be a star or a space).
b) The Driver class:
How you choose to implement your driver is largely up to you but obviously it must include a main method. More than likely this method will be responsible for running the main loop that continues running until the person decides to quit the program. Also you will probably be instantiating instances of the other class (at least the Biosphere) here.
c) 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 because of the style requirement if you only implemented one very large method that handled all the above tasks.
d) The Debug class:
Whether or not you choose to implement a debugging class yourself or if you plan to use my class is entirely up to you. What you must do for this assignment is to 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. 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.
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
Biosphere 1 (The Barren Realms: The empty biosphere): C+
It's a 10x10 world that is completely empty. Run it thru a few turns. If you ever have a critter suddenly appear in this barren wasteland then you are doing something wrong. A good basic starting test.
Biosphere 2 (Doomed for extinction: The deaths biosphere): B-
The three critters scattered throughout the biosphere that 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
This biosphere starts out with three critters. On the first turn the three critters die off but a new critter is born. This critter dies off the turn after that.
Biosphere 4 (You make my head spin): B+
The biosphere consists of 3 critters in a vertical line. From turn to turn this line should rotate from vertical to horizontal (and back again) endlessly. A very good test to see if "critter is born" and "critter dies" algorithm works properly for more than one turn. Also it checks if you can properly copy your arrays between turns.
Biosphere 5 (First advanced test case): A-
A more advanced test. After 20 turns or so the pattern of Critters should stabilize into a rectangle consisting of 4 Critters.
Biosphere 6 (Second advanced test case): A
This test requires that your program can handle the special cases (extreme top, bottom, left, right and the corners). If you're program can handle this one then you know that you've made the cut folks.
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 requirments.
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.
Source code files can be found in Unix in the directory /home/233/assignments/assignment3:
The sample executable for this assignment can also be found in the above directory:
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.
Writing a moderately sized object-oriented program.
John Conway's faculty web page at the University of Tennessee:
http://www.math.utk.edu/~conway/