CSE 382 Algorithms and Data Structures

Barbara Nostrand, Ph.D.

Electrical Engineering and Computer Science


Laboratory 2 - Conway's Game of Life

The game of life was invented by mathematician John Conway as a simple model representing a society of organisms. It was introduced to the world in 1970 by Martin Gardner in his Scientific American column.  Life is a specific instance of a class of computational machines known as cellular automatae. 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:

  1. If a cell has exactly three neighboring "organisms," then an "organism" is "born" in that cell.
  2. If a cell has fewer than two neighboring "organisms," then an "organism" in that cell "dies of loneliness."
  3. If a cell has more than three neighboring "organisms," then an "organism" in that cell "dies of overcrowding."

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.

Program Specifications

Program Implementation

This project is adapted from a project designed to accompany an introductory Java programming text.  The program specification above includes a few easy extensions beyond the original project description.  Also,  the code skeletons have been omitted.  Otherwise,  the remainder of this document has been taken verbatim from the original laboratory module. 

Attributes

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.)

Constructor

In order to define and initialize a LifeGame object with a starting configuration, we need

  1. The initial configuration; and
  2. A constructor method to initialize gameArray to that configuration.

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 the String fileName.
   1. Open configurationFile, as a FileReader connected to fileName.
   2. Create the scanner src and connect it to configurationFile. 
   3. Read rows and cols from src. 
   4. Create a 2D array of size rows+2 by cols+2
   5. 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.
   6. For each index r in the range 1..rows:
      a. For each index c in the range 1..cols:
          A. Read value from src.
          B. Set gameArrayr,c to value.
      End loop.
   End loop.
   7. Close configurationFile.

Steps 1 - 3 are new.  You can easily read integers from a file by using a Scanner. 


	FileReader configurationFile = new FileReader(fileName);
	Scanner src = new Scanner(configurationFile);
	int rows = src.nextInt();		
	int cols = src.nextInt();		

Step 4 is new and is accomplished by the line:


	gameArray = new int[rows+2][cols+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 5 guarantees that all the cells including the extra ones are initialized to zero.

Step 6 then initializes the actual cells we will be using to the values stored in the data file.

Step 7 releases the file so that it can be used by other programs.


	configurationFile.close();	// the FileReader was created in Step 1

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:

 

Accessors

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.

Generating The Next Generation

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.

Output

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.

 

Creating the GUI

Sample Applet

Before begining to implement the GUI for this assignment you may wish to look at a sample interactive applet at Clemson University.  Applets are executed inside browsers or viewers and have an init instead of a main method.  However,  the graphics package works the same for both. 

Layout Design

As is usual in a GUI, one 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.

 

Coding the GUI

There are a number of tasks that we need to complete for the GUI. We will take this in three steps.

  1. Create and test the picture.
  2. Create the interface.
  3. Get input from the user.
  4. Create a controller class.
  5. Add in the actions.

Create and Test the Picture.

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.

Create the Interface Components

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.)

Get Input from the User

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.

Create and Use a Controller Class

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;
	
}

Constructor

Finish a constructor that has the prototype:

   public GameController (LifeGame game, LifeDrawer picture) 

run()

This class needs to implement its actions in a run() method. Remember that it needs to do the following in an infinite loop:

  1. Sleep for some amount of time.
  2. Do the next generation.
  3. Repaint the picture.

Speed control methods.

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.

Add in the Actions

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.

actionPerformed()

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 Life Game

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.

CollaborationYou will complete this project with your lab partner. 
ImplementationYou must implement your system as a Java application.  You may use Jgrasp.  Do not use netbeans or produce a Java applet. 
EnvironmentYour program must execute on the podium computer in our classroom.
Turn inYou must turn in both a report containing complete program sources and an executable electronic version of your program.

Last modified: 2008 JAN 24
bnostran@syr.edu