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: 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:
(temp2)[79]~/classes/current/intro-II/projects/development/game-of-life> java PlayLife tests/X-pattern.init 4 Text 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/cs12/project-3 .
There are four 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 will next describe 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 pair of classes is responsible for displaying the state of the game onto the screen. Our first concern is how to create an object of this type. Specifically, your Game object should, at some point, create one with a line that looks something like this:
UserInterface ui = UserInterface.create("Text", this);
There are two things worth explaining here: First, note that we don't use the new keyword. I will ask that you ignore this detail for now, knowing that we will address it in a later project when we create a graphical interface for this program. Second, note the use of this. The variable this, which you never declare, is always available inside any object, and is an object's pointer to itself. Thus, we are passing, to the UserInterface.create method, a pointer of the Game object that is creating the UserInterface object in the first place. By doing so, methods inside the UserInterface object can call on methods within the Game object, about which we say more below.
The UserInterface object that you create has one critical method:
public void display ()
This method will take care of displaying the state of the game for you. In this case, it does so by printing the grid to the screen. Whenever you want the state of the game to be show (e.g., after evolving to the next generation), just call this method and it will take care of the rest.
This class just provides some methods that should, ideally, make your life easier. The first two are intended to prevent you from needed to deal with exceptions. (If you recall, you often must append throws IOException to methods that use file operations, and then any methods that call those methods, etc. Using the following two methods will eliminate that need, at least within this program.)
public static Scanner makeScannerForFile (String filename)
public static boolean hasNextInt (Scanner sc)
public static int nextInt (Scanner sc)
So, to understand how to use these two methods, let's consider a sample method:
public static int foo (String someFileName) throws IOException {
Scanner sc = new Scanner(new File(someFileName));
int x = 0;
if (sc.hasNextInt()) {
x = sc.nextInt();
}
return x;
}
In this example, any method that calls foo must also declare that it throws IOException. To avoid that mess, we can use the Support methods, like so:
public static int foo (String someFileName) {
Scanner sc = Support.makeScannerForFile(someFileName);
int x = 0;
if (Support.hasNextInt(sc)) {
x = Support.nextInt(sc);
}
return x;
}
Additionally, there is a rather general method to make your code cleaner when you encounter problems. Specifically, when you encounter an error, your program should likely print an error and end the program. The following method does both of those steps for you, given an error message to display:
public static void abort (String message)
Thus, you write something like the following in your code:
if (row < 0) {
Support.abort("ERROR: Rows numbers must be non-negative: " + row);
}
Some of the code in the four classes above assume that there is a Game class from which a Game object can be made. It will further assume that there are certain methods in the Game object on which it can call. Here is the list of those methods and the things that they are expected to do:
The constructor. The initialStateFilename is the name of a file that contains a initialization state file, which is one that contains the size of the grid and coordinates of initially live cells. The interfaceType specifies the kind of user interface to create---in this case, either Text or Graphic, where only the former currently works.
It is the responsibility of this method to set up the Game object. Specifically, it must, based on the initial state file, create the grid and its cells, and then set the appropriate ones to be alive. It must also create a UserInterface object (as described above) and keep a pointer to it.
Drive the game, evolving through generations (and displaying each through the user interface's display() method). The evolution should stop either whether maxGenerations generations have been processed, or when the universe becomes static.
Provide the current generation number.
Provide the number of live cells in the current generation.
Provide the number of rows in this universe.
Provide the number of columns in this universe.
Provide the Cell at the requested row and column coordinates.
The rest is up to you. That is, the specific manner in which you store the grid and interact with each cell is up to you. So long as the methods described above perform as specified, the program will work.
The TextUserInterface depends on cells being stored in Cell objects that it can access through the Game class's getCell method. Moreover, it depends on the following method existing within each Cell object:
Return a textual representation (as a single char of the state of the cell. Specifically, if it is alive, return '+', and otherwise return '-'.
In class, we will go over, in detail and with examples, how to create new types of data, known as instantiable classes. It is from such classes that objects can be made. Our new trick, starting now, will be to divide our computation into objects. So, in thinking of how the Game of Life should be programmed, think of the elements of the program and how they can be divided into objects. We already have a Game object to represent a whole Game of Life. Certainly there should be Cell objects. You may wish to break down the task further, defining other object types (classes!) -- that is up to you!
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 Text
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 10 Text > 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 test/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-3 subdirectory, use the following command to submit you work (all of your Java code files) when you are done:
cs12-submit project-3 *.java