Cellular Automata
Machine Problem

BACKGROUND

Conway's game of Life is intended to model a population of cells that reproduce and die off. You've probably seen the game played on a screen saver of a PC. Life is played on a two dimensional "Grid" (a 2D array), and is an example of a cellular automata.

The game begins with an initial configuration of "cells" (called a "generation") which are input by the user. We then update the cells over a sequence of generations. The rules used to calculate the next generation are simple.

Given an array called "Grid" we produce a new array called NewGrid as follows. For each point Grid[i][j] we count the number of neighboring locations that are occupied by a cell. We include all 8 neighbors:

Once we have tallied the number of neighbors for a location Grid[i][j], we apply the following rules to produce NewGrid[i][j]:

1. If the number of neighboring locations that are occupied by a cell is exactly equal to 3, then we place a cell at NewGrid[i][j]. (If Grid[i][j] was previously empty, then we have a "birth." If it was occupied, then we have a "stable configuration.")
2. If 0 or 1 neighbors were occupied then we set NewGrid[i][j] to 0. (If Grid[i][j] was previously occupied than we say that that the cell "died of loneliness.")
3. If there are 4 or more neighbors, then we set NewGrid[i][j] to 0. (If Grid[i][j] was previously occupied, then we say that the cell "died from overcrowding.")
4. If the number of neighbors is exactly two, then we copy Grid[i][j] in NewGrid[i][j] (a "stable configuration.")

If we are examining a location on a boundary or a corner, then we find neighbors by WRAPPING AROUND to the opposite side or corner (an opposite corner is opposite across a diagonal going through the middle of the world. Thus, if we have an M x N array, then if we are looking at location row 0, column 3 ([0][3]), then the upper neighbor is at row M-1, column 3 ([M-1][3].) If we are at the upper left corner [0][0], then the left hand upper neighbor (0 in the above diagram) is [M-1][N-1] and so on:

      0                Side-1 
      0+---------------+ 
      |                | 
      |                | 
      |                | 
      |                | 
      |                | 
      |                | 
Side-1+---------------+ 

THE ASSIGNMENT

Your assignment is to implement the game of Life. You will actually build two versions, one of which will use the generation rules described above, and the other will provide a way to input any arbitrary generation rule set. The starter code provided already functions and implements the standard rule set, assumes a square N-by-N grid, and randomly initializes the cells in the grid. Your job for Phase I is to implement the user interface described below, allow for a non-square grid, and the improve the "calculate-and-copy" world methodology into a double-buffered scheme.

Phase 1: Double-buffered world

The provided starter code calculates the next generation in the NewGrid structure, and then copies from NewGrid back to Grid on each generation. Obviously, this is a lot of unnecessary copying. Instead we can use a form of double buffering. Rather than having two, unrelated 2D arrays Grid and NewGrid, for the current and next generation, we can have one 3D Grid array, with the first dimension controlling whether Grid[0] is the "old" generation and Grid[1] is the new, or vice versa.

Change the code to reflect this strategy. You can use a single variable for the indexing, since if the current generation is in index i the next goes in (1-i).

Once you have Phase 1 working, save a copy of your code and move on to Phase 2. This is quite a bit more complex.

Phase 2: Generalized transition table

Notice that the generation rule set described at the start of the assignment is concerned only with the number of neighbors, and not how they are distributed. We can imagine a case where the exact location of the occupied cells in a neighborhood makes a difference as to what happens - maybe the direct north and south neighbors will count for more than the diagonal neighbors.

Conway's Game of Life is only one possible way to specify the "transition" a CA makes from one state to the next. The most general specification is to specify, for each possible state of NEIGHBOR in the NEIGHBORHOOD what the next state is. For this assignment, we will stay with the same binary (two state) CA and 9-neighborhood (called the "Moore " neighborhhod) as used in the version of Life.java provided.

For Phase II of this assignment, you will extend your Phase I code to allow for any arbitrary rule set based on the 9-neighbor Moore neighborhood. Look again at the numbering of the locations of the neighbors, from 0 to 8. If each of these locations is considered a location in a bit string, then we can represent any arbitrary configuration of these 9 numbers as a 9-place bit string, with 1s representing occupied locations and 0s for empty slots. Under this scheme, the configuration with only the upper-left-corner location occupied (position 0) can then be represented with the bit string 100000000. Similarly, the configuration with only the center location occupied (position 4) would be 000010000. Bit strings are really nice in that they have a natural interpretation as a binary number, which can then be used as an index into an array or table. We recommend writing a simple
public static int bitarr2int (int b[])
routine to help with this transformation.

For Phase II, you will implement this generalized transition table. You will need an array of length 512 (=2⁹, since there are 9 positions in the neighborhood, each of which can be in either of two states). The contents of each element of this array will be either 0 or 1, depending on whether a particular configuration will cause a cell to be occupied in the next generation or not. Make this change to your code; you will want to do it in a routine called recalc2() so you don't overwrite your Phase I code.

WHAT WE'LL PROVIDE

We'll provide you with source for the simpler version, using recalc() in .../public/mp1/Life.java. It contains many of the routines you will need.

To help get you started, here is a string that generates the same behavior as recalc().

static String TranTblString =
	"000000010001011000010111011111100001011001101000011111101110100" + 
	"000101100110100001111110111010000110100010000000111010001000000" + 
	"000101100110100001111110111010000110100010000000111010001000000" + 
	"011010001000000011101000100000001000000000000000100000000000000" + 
	"000101100110100001111110111010000110100010000000111010001000000" + 
	"011010001000000011101000100000001000000000000000100000000000000" + 
	"011010001000000011101000100000001000000000000000100000000000000" + 
	"100000000000000010000000000000000000000000000000000000000000000" ;

WHAT TO TURN IN.

PLEASE verify that your assignment compiles properly before you turnin, and document any known bugs. Points will be taken off for undocumented "features" or code which doesn't compile. Comments about bugs, known problems, and any other information which you wish to convey to the person who grades your assignment may be put in a file called README.

In your turnin package, the only types of files we want are *.java, makefile, and the HTML documentation files generated by javadoc. You should also turnin*.class files. Please do not turnin executables, or anything ending in ~ or % (i.e. editor files) and ESPECIALLY don't hand in any core files!

If you have some interesting initial states which produce some interesting outputs, by all means include the random number seedthat generated them.

Similarly, if you experiment with other transition tables that produce some interesting behaviors, by all means include those files also.

You must provide javadoc for all major routines. In additon, use every other trick you can (good variable names, comments describing tricky passages, etc.) to make your code as comprehensible.

Also write a brief README file which documents novel features of your implementation, problems your encountered, and anything else you think we should know about your code. Also mention briefly how the duties were divided between the two members of your programming team.

If you like Science Fiction, the novel Glory Season by David Brin uses the Game of Life in an interesting way -- don't read it now, it's a long book, but keep it in mind for Summer.

Last updated by rik on 7 Jan 99.