Conway's Game of Life

This week we'll explore the simulation of entities on a 2D grid. The entities will interact with each other to determine how they change over time. The overall concept is called cellular automata, and you'll implement a specific version of cellular automata that implement Conway's Game of Life. Please at least skim the wikipedia page if you have not seen the Game of Life before.

Project Checklist: Before submitting your project, make sure you have completed all of the following!

• All of the coding work listed under tasks
• Your report describing the work you did in the project
• Your reflection questions with any writing in the reflection section of the report, and code included in your code files Expect to allocate a decent chunk of time to these! They're worth 1/4 of your project grade
• Your extensions should you choose to do any

Tasks

This week you'll develop three classes: a Cell, a Landscape, and a LifeSimulation. The Cell will represent a location on the Landscape. The Landscape will represent a 2D grid of Cells, and a LifeSimulation will control the rules and actions of the simulation. We will use the Java Swing graphical user interface package in order to display our landscape. The end result of the project will be a window that displays Conway's Game of Life.

Cell Class

First, download Cell.java. A Cell object represents one location on a regular grid. The Cell class should store whether or not it is alive and implement the following methods.

• public Cell( ) constructor method. (By default, the Cell is dead.)
• public Cell( boolean alive ) constructor method that specifies the Cell's state. A True argument means the Cell is alive, a False argument means the Cell is dead.
• public boolean getAlive( ) returns whether the Cell is alive.
• public void setAlive( boolean alive ) sets the Cell's state.
• public String toString() returns a string that indicates the alive state of the Cell as a one-character string. For example, you could use a "0" for alive and "1" for dead. This will override the default toString method in the Object class.

Implement the methods, and test them with a main method.

Testing Your Landscape Class

As always, it's best to write good tests for your code. We've started a testing suite for the Landscape class you're about to write here, your job is to complete it. Make sure to do this! It's a required and graded part of the project It will also help you debug your Landscape class more easily! We recommend moving back and forth between this step and the Landscape Class description to better understand what you're testing.

Landscape Class

First, download Landscape.java. The Landscape class should have a field to hold the array of Cell object references and implement the following methods. You may also want to have fields to hold the number of rows and the number of columns in the grid.

• public Landscape( int rows, int cols ) sets the number of rows and columns to the specified values and allocates the grid of Cell references. Then it should allocate a Cell for each location in the Grid.
• public Landscape( int rows, int cols, double chance) operates the same as the above, except that each cell independently starts with a chance of being alive equal to chance.
• public void reset() recreates the grid via the same method as it was originally created.
• public int getRows() returns the number of rows in the Landscape.
• public int getCols() returns the number of columns in the Landscape.
• public Cell getCell( int row, int col ) returns a reference to the Cell located at position (row, col).
• public String toString() converts the Landscape into a text-based string representation. At the end of each row, put a carriage return ("\n").
• public ArrayList<Cell> getNeighbors( int row, int col ) returns a list of references to the neighbors of the Cell at location (row, col). Pay attention to the boundaries of the Landscape when writing this function. The returned list should not contain the Cell at (row, col).

Implement the methods, and test them with a main method.

Landscape Visualization

Make it possible to visualize your Landscape.

1. Download and Analyze Java Swing Code

   Use Java's Graphics class as reference. Particularly setColor() and drawOval().

   Download the code for the LandscapeDisplay class. Read the code and note its fields and methods. Its job is to display a Landscape. To do so, it stores a Landscape object in a field. It opens a window and calls the draw() method on the Landscape, which, in turn, calls the draw() method on the Cells.

2. Drawing the Cells

   You'll notice that we've already filled in the code for the Landscape's draw() method. Take a minute to observe how it works: it iterates through the Cells in the Landscape and draws ovals to the Graphics object whose color depends on whether the Cell is alive or dead.

   + (more detail)

   A Graphics object enables you to set drawing parameters, such as the color, and to draw shapes into the current window. See the Java documentation for the complete set of capabilities.

Test your visualization by running LandscapeDisplay as your main program. Your default initial Landscape should be all zeros/dead cells. Make sure to test a case where some of the grid cells have been set to alive.

Updating Cell States

Add a method to the Cell class: public void updateState( ArrayList<Cell> neighbors ). This method updates whether or not the cell is alive in the next time step, given its neighbors in the current time step.

The updateState() method should look at the Cell's neighbors on the provided Landscape and update its own state information. The default rule should be if a live Cell has either two or three live neighbors, then it will remain alive. If a dead Cell has exactly three living neighbors, it will be set to alive. Otherwise, the Cell will remain dead.

Correctly writing these rules is important, so test out your system by downloading CellTests.java. You should also create tests for the Landscape class.

Advancing the Game

Add a method to the Landscape class: public void advance(). The advance() method should move all Cells forward one generation. Note that the rules for the Game of Life require all Cells to be updated simultaneously. Therefore, you cannot update the Cells in place one at a time (why not?).

Instead, create a temporary Cell grid of the same size. For each grid location create a new cell and copy over the alive status of the original cell in that location.

Go through each Cell in the temporary grid, using a nested loop, and call updateState(), passing the list of neighbors of the Cell in the original grid to the Cell. When the code has updated all of the Cells, you need to transfer the information back. You can just assign the temporary grid back to the original grid field.

LifeSimulation Class

Create a new LifeSimulation.java class that is modeled on LandscapeDisplay.main(). It should include a loop that calls the advance() method of the Landscape, calls the repaint() method of LandscapeDisplay, and calls Thread.sleep( 250 ) to pause for 250 milliseconds before starting the next iteration. Each iteration of the loop is one time step of the simulation.

Test your simulation with random initial conditions. Consider using a command line argument to control the grid size and the number of time steps in the simulation. It's useful to test your code by first just visualizing the initial board. Then have your simulation go forward by one time step and stop. See if the results make sense before going further.

Required Pictures 1 and 2: include in your report a picture of your board's initial state and the following state after one update.

If you want to test your program using a known pattern, go to the Wikipedia page on the Game of Life and look up an example. Then create a new initialization method that sets the Landscape to the specified pattern.

Required Animation; make a short video or animated gif of your simulation and include it in your report.

+ (more detail)

display.saveImage( "data/life_frame_" + String.format( "%03d", i ) + ".png" );

mkdir data
java LifeSimulation
convert -delay 60 data/life_frame_*.png mysim.gif

Exploration

How do the parameters of grid dimensions and initial status chance affect the number of living cells after a sufficiently long time (say, 1000 rounds)? In your report's results section, develop a hypothesis, test it, and back up your results with sufficient experimental evidence. That means we expect to see specific results from your experiments! In particular, create a graph that shows the average number of living cells after 1000 rounds with initial probability values ranging from 0 to 1. Make sure to tell us what you ran to get those results too!

Reflection Questions

Please answer the following 2 questions. Put any written responses numbered in the Reflection section of your report, and include any code with your other code files. This section is worth a substantial portion of your project grade, and generally includes the type of more conceptual exercise you can expect to see on exams, so it's good preparation for that!

Question 1: Looking to the Future

Your first task is to create some method of determining if your current simulation has entered an infinite loop. Basically, this means checking to see if our current grid's state is a copy of a previous state. There are a number of ways of things to decide when thinking about a problem like this:

• Do I always check to see if my grid is a copy of a previous one? Or do I just do it sometimes?
• Do I remember every grid I have created so far? Do I only store some of them?
• Of the previous grids I decide to store, how should I store them? Do I need to remember the entire grid? Is there a way of 'compressing' the data to take up less space?

1. Demonstrate they work as expected
2. Include in your report a discussion of how you answered the above questions
3. Include in your report a discussion of the efficiency of the code you implemented: how efficient is it with respect to space usage? what are the asymptotic runtime of your methods?

Question 2: Looking to the Past

Suppose I wanted to take away the automatic running of the simulation and instead implement a forward and backward button for the display. The forward button would move to the next grid state, the backward button would move to the previous.

Discuss your answers to the following questions in your report:

1. Would it make more sense to use a Stack or a Queue as a supporting structure for implementing the backwards button? Describe how you would use the Stack or Queue methods to control the flow of the program.
2. When going backwards in time, I could maintain a second structure so that I wouldn't have to recalculate the grids I had previously advanced to. As an example, suppose I had started with grid G1, then advanced to grid G2, then advanced to grid G3, then moved backwards twice to G1. At this point, if I clicked forwards, I would again move to G2. As I went backward, I could save copies of G3 and G2, or I could just recalculate them again starting from G1 (using the advance method). Discuss the trade-off between storing these grids (so that I wouldn't need to recalculate them) and just recalculating them again.

Extensions

1. Modify the main method in LifeSimulation to make use of command line parameters. For example, it would be nice to control the size of the Landscape, the density of the initial board, and the number of iterations used in the simulation. If you do this, we will expect to see usage statements and informative README files!
2. Try modifying the updateState() function in the Cell class to implement different rules. Think about how to do this using good design rather than having many copies of the Cell class or commenting/un-commenting blocks of code.
3. Create more than one type of Cell and give each type different rules. Be sure to explain your design in the report and discuss what you expected as well as the results.
4. Be creative with the GUI. Add buttons or other controls to the window. These might let the user start, stop, or pause the simulation, set the density of the start situation, and reset the simulation.

Congrats, you're done with everything except for your project report where you will communicate your findings from all that code! Make sure to write up your report in the project report file in the Google Classrooms assignment. The project report is an important part of the work in this project, so don't forget to do it!