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.
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.
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 reset()sets the Cell state to its default value (not 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 " " for dead. This will override the default toString method in the Object class.
Implement the methods, and test them with a main method.
Create a java class called Landscape, which will hold a 2D grid of Cell object references. 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 void reset()calls the reset method for each cell.
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.
Make it possible to visualize your Landscape.
- Download and Analyze Java Swing Code
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. Before you can compile the LandscapeDisplay class, you will need to add those draw() methods.
- Drawing a Cell
Add a method to your Cell class:
public void draw( Graphics g, int x, int y, int scale ). It draws the Cell on the Graphics object at location x, y with the size scaled by scale. It should draw the cell differently depending on whether it 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.
For drawing a Cell, you can use an Oval or a Rectangle. If the Cell is alive, use the setColor method to set the color to some useful value (like Color.darkGray), the call something like fillOval(), which takes x, y, dx, and dy and draws an oval that fits into the specified rectangle.
The Cell's draw method just needs to draw one cell (itself) at the specified location, which is defined by the row and column indices multiplied by the gridScale.
- Drawing a Landscape
Add a method to your Landscape class:
public void draw( Graphics g, int gridScale ). It should loop through the cells in Grid, calling their draw() methods at positions calculated from their positions in the grid.
Use a nested for loop to draw all of the cells. For each cell at position row i, column j, call its draw method, passing in i*gridScale for the vertical coordinate, j * gridScale for the horizontal coordinate, and gridScale for the scale.
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 creating some initial cases, running the simulation for one step, and making sure the results are correct.
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 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.
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)
After the display is repainted (in the loop you wrote above), add the following line to save the current display:
display.saveImage( "data/life_frame_" + String.format( "%03d", i ) + ".png" );
The output should be a series of images of the simulation, using zero-padding to make sure that numeric and alphabetical orders are the same (e.g. 002 comes before 010 alphbetically, but 2 does not come before 10 alphabetically). Then, create a data directory in your project directory, run your program, and make the animated gif using convert (an ImageMagick program).
mkdir data java LifeSimulation convert -delay 60 data/life_frame_*.png mysim.gif
Another way to get your animation is to record a screen video. It does not matter which way you use. But you are expected to show your animation in your write-up.
- 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.
- 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.
- 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.
- Be creative with the visual representation.
- 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.
- For any assignment, a good extension will be to implement a Java class yourself and demonstrate that it has the same functionality as the Java class.
- Another good extension for any assignment is to identify in comments
when dynamically allocated memory is being "lost." Dynamic memory is any memory created with a
newcommand. Indicate the line of code in which the last reference to an object referencing dynamic memory is removed.)
Your intended audience for your report are your peers not in the class, but who have taken a CS course. Your report should explain the core CS concept used, present the results of your program, and discuss the meaning of the results: what did you discover and does it make sense?
Your project report should contain the following elements. Please include a header for each section.
A brief summary of the project, in your own words. This should be no more than a few sentences. Give the reader context and identify the key purpose of the assignment. Each assignment will have both a core CS purpose--usually a new data structure--and an application such as a simulation or analysis.
Writing an effective abstract is an important skill. Consider the following questions while writing it.
- Does it describe the CS concepts of the project (e.g. writing well-organized and efficient code)?
- Does it describe the specific project application?
- Does it describe the data structure you used?
- Does it describe the results of your simulation or analysis?
- Is it concise?
- Are all of the terms well-defined?
- Does it read logically and in the proper order?
The methods section should be a high level explanation of your solution. Give an explanation of the main CS concept or data structure for the project. Then explain how you used it as part of a simulation or analysis and why the data structure was appropriate for that task. One paragraph for each should be sufficient.
Present your results. Include text output, images, tables, graphs, or qualitative descriptions, as appropriate. Include a discussion as to whether the results make sense and what they mean. This week, be sure to present the percentages for dealer wins, player wins, and ties. Does the house always win (it should)?
Describe any extensions you undertook, including text output, graphs, tables, or images demonstrating those extensions. If you added any modules, functions, or other design components, note their structure and the algorithms you used.
A brief (1-3 sentences) description of what you learned. Think about the answer to this question in terms of the stated purpose of the project. What are some specific things you had to learn or discover in order to complete the project?
A list of people you worked with, including TAs and instructors. Include in that list anyone whose code you may have seen, such as those of friends who have taken the course in a previous semester.
Make your report for the project a wiki page in your personal space. If you have questions about making a wiki page, stop by my office or ask in lab.
Once you have written your report, give the page the label:
You can give any wiki page a label using the label field at the bottom of the page. The label is different from the title.
Do not put code on your writeup page or anywhere it can be publicly accessed. To hand in code, put it in your folder on the Courses fileserver. Create a directory for each project inside the private folder inside your username folder.