We have seen that the Java array type allows us to construct objects in which we can conveniently store a sequence of values. For example, the statement:
double anArray[8];
defines the object anArray as a container capable of storing eight values:
We visualize such an object as a linear sequence of values that has one dimension: the length or size of the array. There are, however, objects that are more naturally visualized as having two dimensions, such as a tic-tac-toe game, which is organized by rows and columns:
One way to build a software model of such an object is by defining it as as a one dimensional array that stores other one dimensional arrays:
char ticTacToeGame[][];
Where a single index is needed to specify an element of a one-dimensional array, two indices are needed to specify an element of a two-dimensional array; the first to specify the particular row being accessed, and the second to specify the particular column within that row. For example, we could access the X in the upper left corner of ticTacToeGame with the expression:
ticTacToeGame[0][0]
we could access the X in the lower left corner with the expression:
ticTacToeGame[2][0]
the O in the upper right corner with the expression:
ticTacToeGame[0][2]
and the X in the lower right corner with the expression:
ticTacToeGame[2][2]
In today's exercise, we will use this idea to build a class that allows us to play an interesting game known as the game of life.
The game of life was invented by mathematician John Conway as a simple model representing a society of organisms. It is a specific instance of a class of computational machines known as cellular automaton. In these machines we have a grid of cells that can be occupied by a symbol. We also have some rules that we use to change the contents of a cell depending on neighboring cells. For the game of life, we create a rectangular grid of cells, and consider neighbors to be the eight nearest cells:
That is, if a cell's row-index is r and its column-index is c, then its northwest neighbor has the index [r-1][c-1], its northern neighbor has the index [r-1][c], its northeast neighbor has the index [r-1][c+1], its western neighbor has the index [r][c-1], its eastern neighbor has the index [r][c+1], its southwest neighbor has the index [r+1][c-1], its southern neighbor has the index [r+1][c], and its southeast neighbor has the index [r+1][c+1].
Each cell may or may not contain an "organism," designated by an asterisk (*).
The game consists of a series of generations, with the "organisms" in any given generation determined by the "organisms" of the preceding generation, and these rules:
These three simple rules are sufficient to observe some fascinating behaviors. For example, suppose that we begin with this configuration of three "organisms":
If this is our first generation, then the second generation is produced by applying our three rules to each cell in the grid:
The second generation thus appears as follows:
To get the third generation, we reapply the same rules to the second generation. As a result, "organisms" are born in cells [1][2] and [3][2], while the "organisms" in cells [2][1] and [2][3] give birth, returning us to the original configuration!
This particular configuration continues to oscillate back and forth from generation to generation. It can be thought of as representing a "society of organisms" that while changing from generation to generation, remains stable if it is not disturbed by outside influences. Other configurations grow larger and larger with each generation until the entire grid is nearly filled; and thus model "societies" with population booms. Others grow smaller and smaller until all organisms are dead, modeling "societies" that lead to the extinction of their "organisms." We will see examples of each of these at the end of this exercise.
The program that we will be converting is contained in the files Life.java and LifeGame.java. As in the last program, we have split the code in the model and the interface code. Lets take a look at the code for LifeGame.java and see how it models the problem.
Each cell in a game of life may or may not have a living "organism" within it, and this can change over time. There are a variety of ways to represent such an object (e.g., a char, a bool, an int, ...). However, implementing the game's rules requires that we count the number of neighboring cells containing living "organisms." Since counting is easily accomplished by adding numbers, we will represent a cell containing a living "organism" with the integer 1, and represent a cell without a living "organism" with the integer 0.
Since a game of life involves a grid of cells, we need a two-dimensional structure of cells. We name that grid gameArray.
There are also two variables which hold the number of rows and columns in the array. (These two variables are not strictly needed since we could get that information directly from the array using size, but they are convenient.)
In order to define and initialize a LifeGame object with a starting configuration, we need
For convenience, we have chosen to store the initial configuration in a file. Our program Life.java begins by reading the name of the file from the user, and then passes this to the LifeGame constructor method, which reads the contents of the file and uses them to initialize the gameArray attribute.
For simplicity, we will assume that the first line of the file contains two integers: the number of rows and the number of columns in the grid of cells. The remainder of the file will then be a grid of starting values for the cells. For example, our test.life input file provides the starting configuration for the three "organism" oscillating pattern, and it is structured as follows:
5 5 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0
In this five-by-five grid, each 1 represents a cell containing an "organism," and each 0 represents a cell without an "organism."
From the perspective of the LifeGame, we can specify the behavior of this operation as follows:
Receive: fileName, a String.
Precondition: fileName contains the name of an input file,
the first line of that file specifies the rows and columns,
and the remainder of the file is a life configuration.
Postcondition: gameArray has been initialized to the configuration
given in the input file.
This turns out to be a nontrivial method, so open LifeGame.java and find the LifeGame constructor method. The algorithm for this method is:
0. Receive fileName.
1. Open in, an ReadFile to fileName.
2. Read rows and cols from in.
3. Create a 2D array of size rows+2 by cols+2
4. For each index r in the range 0..rows+1:
a. For each index c in the range 0..cols+1:
A. Set gameArrayr,c to 0.
End loop.
End loop.
5. For each index r in the range 1..rows:
a. For each index c in the range 1..cols:
A. Read value from in.
B. Set gameArrayr,c to value.
End loop.
End loop.
6. Close in.
Step 3 is new and is accomplished by the line:
gameArray = new int[myRows+2][myCols+2];
One question you might have is why did we make the array larger than what was specified in the file? The answer is that eventually we will want to add up the values in all of the cells surrounding each cell. But consider the cell in the upper left hand corner. Five of those neighbors don't exist! This leads to complications in that calculation. What we will do instead is to add in an extra cell around all the edges which will always contain the value 0. Then we won't have to do any special computations for the cells on the edge.
Step 4 guarantees that all the cells including the extra ones are initialized to zero.
Step 5 then initializes the actual cells we will be using to the values stored in the data file.
If we invoke the constructor with the configuration stored in test.life, as our program in Life.java does, the state of the object referred to by the variable theGame can be visualized as follows:
We have three accessors.
int rows() - returns the number of rows in the life game. Notice that this is different from the number of rows in the private array we use.
int columns() - returns the number of columns in the life game.
int cellValue(int row, int col) - returns the value of the cell at the given row and col. We need to add one to the argument values to find the position in our internal array.
The method nextGeneration() is the workhorse of the class, since it must encode "the rules of the game." We can specify what it does as follows:
Postcondition:
For each live cell c in gameArray:
If c had exactly three neighboring cells containing 1s:
Then c contains a 1.
Otherwise, if c had less than two neighbors containing 1s, OR
c had more than three neighbors containing 1s:
Then c contains a 0.
This post condition gives us a great deal of insight into the problem. We will need two nested for loops to process the rows and columns of gameArray. Within the inner loop, we will need to count the number of neighbors for the currently referenced cell, and set its value appropriately as required to satisfy the post condition.
One subtle part is that we must compute the number of neighbors containing ones using the current configuration of cells. That is, if we compute the number of neighbors of gameArray[r][c], and then change gameArray[r][c] according to the rules above, then the "neighbor-computation" in each of the cells that neighbor gameArray[r][c] will be modified accordingly. To avoid this problem, we must have a second array in which we record the new generation and then copy that back into the old array.
Since each cell is an integer, with 0 representing an empty cell and a 1 representing a cell with an "organism" in it, we can simply add the values in the surrounding cells to compute the number of neighbors.
We override the toString() method to provide a more useful print representation of the life game. We will construct a string that shows the current state of the cells. The algorithm is as follows
0. Initialize the String representation to be empty.
1. For each index r in the range 1..rows:
a. For each index c in the range 1..cols:
If gameArray[r][c] is 1:
Append "X " to representation.
Otherwise
Append " " to representation.
End if.
End loop.
b. Append a new line to representation (end of row).
End loop.
As is usual in a GUI, on of the first tasks is to decide on the layout. Clearly we would like to have a graphical representation of the life game and a couple of buttons to make the simulation run either faster or slower. Here is one possible design:
To implement this design we will use one panel to hold the two buttons we need. We will place that panel in the south position of the contentPane for our application. We will use a LifeDrawer class to create the picture and will place it in the center of the contentPane for our application.
There are a number of tasks that we need to complete for the GUI. We will take this in three steps.
There is a skeleton for the class LifeGUI.java already in place. Take a moment to look at it and then add it to your project.
We already have a functioning constructor for this class. We just need to complete the paintComponent() method so that it draws the current state of the life game. We can use the following algorithm to accomplish the task:
0. Get the number of rows in myGame.
1. Get the number of cols in myGame.
2. Set the pen color black.
3. For each index r in the range 0..rows-1:
a. For each index c in the range 0..cols-1:
A. If the cell value in location r, c is 1
i. Compute the x position of the circle.
ii. Compute the y position of the circle.
iii. Draw a circle at the position x, y.
End loop.
End loop.
Using what you have learned before, complete and test this code.
We will create all of the interface components and verify that the interface is how we desire it to be before we make the components functional.
In the appropriate place declare
and then add them into the interface.
Don't forget to set the layout for the JPanel.
Keep working on this code until all of the components are visible and in the appropriate places. (You may need to resize the window for very small test cases.)
Currently we are setting the value of the strings fileString and sizeString in the code. Use a JOptionPane to read in these strings from the user.
Test and debug your code.
We need to have some method of periodically telling the life game to compute the next generation and then informing our LifeDrawer object that it needs to paint the picture again. This roll is filled perfectly by a thread.
At the bottom of the file LifeGUI.java add the following partial class
class GameController extends Thread
{
private int myDelay = 100;
private LifeGame myGame;
private LifeDrawer myPicture;
}
Finish a constructor that has the prototype:
public GameController (LifeGame game, LifeDrawer picture)
This class needs to implement its actions in a run() method. Remember that it needs to do the following in an infinite loop:
Eventually we will want to be able to control the speed at which generations occur. We will implement two methods faster() and slower() which do these tasks. You may wish to put an upper limit on the delay. You must put a lower limit of zero on the delay.
After you have implemented the parts of the Controller class, uncomment the code that declares, creates and then starts the thread. Test and debug your code. If all has gone well you should see generations pass before you eyes.
We now need to make the buttons operational. Make sure that you have added the LifeGUI object as the listener for each of the buttons.
Put in the code to handle the events. If the faster button was pressed, send the faster() message to myController. If the slower button was pressed, send the slower() message to myController.
Test your code thoroughly and fix any bugs that you find.
Playing the game of Life consists of creating initial configurations of "organisms," and then running the program and stepping through the generations to see what happens to the society as time passes. While test.life gave us a simple way to see if our program was working correctly, that particular configuration is actually quite dull, because very little changes as time passes.
To see an even more stable configuration, try the configuration in stable.life. The "organisms" in this configuration don't change at all from generation to generation, and are effectively "immortal" under the rules of the game. (This indicates why the old phrase, "May you live in interesting times!" is generally regarded as a curse -- stability tends to be dull.)
By contrast, some initial configurations are very unstable, and the "society of organisms" quickly breaks down, resulting in their extinction. Try quick.life for an example.
With other configurations, the "society" seems to flourish for a while, and then extinction occurs quite suddenly and unexpectedly. Try cross1.life.
Sometimes a few "individuals" make all the difference between whether a society flourishes or becomes extinct. The initial configuration in cross1.life is the following "iron cross":
* * *
*
* * *
* * * * * *
* * *
*
* * *
cross2.life simply adds another organism at the end of each cross:
*
* * *
*
* * *
* * * * * * * *
* * *
*
* * *
*
How does this "society" fare compared to that of cross1.life?
Each of our configurations has thus far been symmetric, but there is no requirement that this be the case. Some asymmetric configurations are more interesting than the symmetric ones. For example, try out glider.life. This particular "society" goes through a periodic cycle of four configurations, and each generation moves a space across the grid. The result is a "migratory society" that moves through the grid as time passes. This behavior is similar to that of some insect colonies, or flocks of birds.
When two gliders collide, the results are unpredictable. Sometimes they lead to extinction of both "societies" and sometimes they result in something entirely different. Which is the case for gliders.life?
Using your text editor, modify the configuration in blank.life to create your own original configuration. Then run it using life. Keep experimenting until you find a simple initial configuration that after 100 generations is still changing.
The game of Life thus provides a simple, interesting model of the relationships in a society.
Cellular automaton, Conway's game of life, 2 dimensional array, row, column, generation.
A hard copy of your final version of LifeGUI.java.
Back to This Lab's Table of Contents