The Game of Life is an example of cellular automata---that is, it is the result of a collection of simple entities (cells) that behave automatically by following simple rules. It is, thus, not really a game in any usual sense. This particular cellular automata exhibits some surprisingly complex behavior, as groups of cells can move in definite directions and then interact with other groups of cells that they encounter. That is, higher-level, more complex behavior emerges from the simple, lower-level rules that control the cells.
Here is how the game works: Consider a rectangular grid of size n x m (rows by columns), known here as a universe. Each of the nm positions in the grid is occupied by a cell. Each cell is either in the state of being dead or of being alive at any given time. Time itself moves in discrete steps, which we will call generations. Thus, at generation 0, there are nm cells, some of which are alive, and the rest are dead. This state, at generation 0, is the initial state of the game.
When time advances from generation g to generation g+1, each cell must take the two following steps to evolve:
Count live neighbors: The cell must examine each adjacent cell in the grid (there are 8 of them) and count how many of them are current (in generation g) alive.
Apply rules: The cell must then apply the following rules to determine its state in generation g+1:
If the cell is currently alive and has exactly 2 or 3 live neighbors, then it will be alive in the next generation.
If the cell is currently dead and has exactly 3 live neighbors, then it will be alive in the next generation.
Under all other circumstances, the cell will be dead in the next generation.
A game consists of advancing time through the generations until one of the following things occurs:
A predetermined maximum generation number is reached.
The universe becomes static---that is, in going from one generation to the next, none of the cells changes state.
Note that it is possible for a universe to enter a cycle of repeating states, where some sequence of states repeats indefinitely. Detecting such a case would be difficult (although not impossible!), and we will ignore that as a possible way of ending a game. [Question for the curious: Is it possible for a universe not to repeat?]
Write a program that carries out a Game of Life. Specifically, a run of your program will look like this:
(remus)[79]> java PlayLife tests/X-pattern.init 4 Generation = 0, Population = 21 +---------+ -+-------+- --+-----+-- ---+---+--- ----+-+---- -----+----- ----+-+---- ---+---+--- --+-----+-- -+-------+- +---------+ Generation = 1, Population = 20 ----------- -+-------+- --+-----+-- ---+---+--- ----+++---- ----+-+---- ----+++---- ---+---+--- --+-----+-- -+-------+- ----------- Generation = 2, Population = 24 ----------- ----------- --+-----+-- ---+++++--- ---++-++--- ---+---+--- ---++-++--- ---+++++--- --+-----+-- ----------- ----------- Generation = 3, Population = 20 ----------- ----------- ---+++++--- --+-----+-- --+-----+-- --+-----+-- --+-----+-- --+-----+-- ---+++++--- ----------- ----------- Generation = 4, Population = 44 ----------- ----+++---- ---+++++--- --+-+++-+-- -+++---+++- -+++---+++- -+++---+++- --+-+++-+-- ---+++++--- ----+++---- -----------
In order to get started with this code, you will need to copy a directory of pre-written, pre-compiled classes from my directory into your home directory, like so:
cp -r ~sfkaplan/public/cs11/project-3 .
There are two classes provided. We first describe what each class provides and how to use them. However, these classes also make some assumptions about your code and the methods that you will write, so we also describe below the Game class that you must write, specifying what methods it must contain.
This is the class that is responsible for kicking off the game. It contains the main() method, and it will handle the command-line arguments. It is from main() that a Game object is created and then called. More on that below, where the Game class is described.
This class just provides some methods that should, ideally, make your life easier. To understand them, you must first observe that your code will be passed Scanner object. Until now, we've used Scanner objects to read things from the keyboard. This time, however, we'll be using them to read data from a file. For a variety of reasons that we won't go into, using a Scanner in this manner is a bit different, and so these Support methods make the task easier.
Here are the Support methods for your use:
public static boolean Support.hasNextInt (Scanner scanner)
Return whether the file being read by the Scanner contains another integer that you can read.
public static int Support.nextInt (Scanner scanner)
Read the next integer from the file being read by the Scanner. If there isn't one, the program will crash, so be sure to call Support.hasNextInt() first to be sure that calling this method is safe.
public static void Support.printGrid (int generation, int population, boolean[][] grid)
Print the current state of the game. That is, show which generation number this is, how many cells are alive, and the current layout of the grid by printing a plus sign for live cells and a minus sign for dead ones.
You must write the Game class (in a file named Game.java) that carries out a Game of Life. There is only one method that you game class must contain (although you should create others for your own internal use). This method is called from PlayLife in order to get the game started:
public static void play (Scanner initialStateFile, int maxGenerations)
This method actually carries out the Game of Life. In particular, it (or other methods that it calls) must perform these steps:
Read initialStateFile to find out the dimensions of the grid and the locations of the initially live cells. (See Testing your code, below, for more information on what one of these files contains and how to read it.)
Make a grid of the dimensions that the file indicated. I would recommend a 2D array of boolean values, where true represents a live cell and false represents a dead cell.
Call Support.printGrid, passing the initial grid before any evolution has occurred, to show what it looks like at generation 0.
Loop through the requested number of generations. At each generation, apply the rules to each cell that determines whether it should be dead or alive in the next generation. Once the rules have been applied and the liveness of each cell has been appropriately changed, call Support.printGrid again to show what the grid looks like in this new generation.
You copied, from my directory, useful files that will help in testing your code. In particular, within your project-3 subdirectory, there is another subdirectory named tests. Go look inside it. You will find two types of files:
.init: Files ending with this suffix are initial state files. One might look like this:
5 7 0 2 2 5 4 1 3 2
This file describes a universe that is 5 rows tall and 7 columns wide (as described by the first line of the file). There are four cells, at coordinates (0, 2), (2, 5), (4, 1), and (3, 2), that are initially alive.
.results: This file contains, for the corresponding initial state file, the output that should be produced for some number of generations. For example, the file simple.results contains the output that should appear when entering the following command:
java PlayLife tests/simple.init 5
There are three pairs of these files:
simple: A small universe with only a few live cells that immediately enter a repeating pattern of period 2. This is a good case for debugging, since it's behavior is so simple.
X-pattern: A medium-sized universe with a neat little pattern of cells. The universe becomes static after just a handful of generations, but the movement of the cells before that is a little complex. Once the simple case works, this is a good, secondary debugging and testing case.
grading-test: I use this one (among others) to really test your code for grading purposes. It is a larger universe with many initially live cells and very complex patterns for well beyond 100 generations. This test case is for use when you really think you have it working, but you want to put it through its paces.
How to use the files for testing: It's too hard, beyond the simple case, to check the output of your program against the .results files with your eyes; doing so may cause blindness, seizures, or insanity. Instead, you can use some automation to do the comparing for you. To do so, follow these steps:
Store the output in a file: When you run your program, don't let the output just dump onto a screen; instead, redirect the output into a file for later examination and comparison, like this:
java PlayLife tests/X-pattern.init 9 > run.results
The > symbol will redirect the output of your Java program into the file whose name follows that symbol---in this case, a file named run.results. You can open this file (e.g., in emacs) to see the output after the program is done.
Compare: You can now compare the results of your program with the standard results that I provided, like so:
cmp run.results tests/X-pattern.results
If the two files are exactly the same, cmp prints nothing at all. Thus, no news is good news. If it finds a discrepency, it will tell you on what line(s) and at what position(s) on the line(s).
From within your project-4 subdirectory, use the following command to submit you work (all of your Java code files) when you are done:
cs11-submit project-4 *.java