9 4/7: Cellular worlds

Introduction

In this lab, we will implement something called cellular automata. According to Stephen Wolfram, it is a a new kind of science. More seriously though, a cellular automaton is essentially a grid-based game where certain cells become "live" according to some simple rules. These rules give rise to complex behavior despite their simplicity.

If you’ve heard of Turing machines or the lambda calculus, cellular automata can actually be powerful enough to model these too. Theoretically speaking, you can build automata that can compute anything you could compute using your computer. Then again, you can do the same thing with billiard-balls so maybe that’s not that special.

Warmup

We will be using the Java World library again in this lab. If you didn’t get a chance to use it in the last lab, take some time to warm yourself up with it.

The World library is on the web here. See the last lab if you don’t remember how to use it.

Exercise 1. As a warm-up, write a world program that represents an m x m grid of cells that start out blank. When you click a cell, it should activate and be colored (choose your favorite color).

Conway’s Game of Life

To start out, we will implement a cellular automaton called Conway’s Game of Life. In this game, we start out with a grid of m x m cells. Each Cell should be either live or dead. You will choose later what cells start out live or dead.

Cells keep track of its neighboring cells (there are eight neighboring cells) and they behave differently based on how many of its neighbors are live. If a cell is already live, then if it has only 0 or 1 live neighbors, it dies. If there are 2 or 3 live neighbors, it stays alive. Otherwise, it is overcrowded and shrivels.

If the cell is dead to begin with, it will come to life only if there are 3 live neighbors. Otherwise, the cell stays barren and dead.

In the game, cells update their liveness at each time step or tick.

Here are some examples (you can use these for tests later):

Exercise 2. Design an interface, data definition, and class definition for a Cell.

You should be able to figure out if a cell is live or dead. Cells should keep track of its neighbors and neighbor liveness. You should also be able to update the cell’s liveness and neighbors.

You may also want to have a method that draws a Cell for later when you build a World.

Now, design a World that keeps track of the cells. Make sure to parameterize the world over the size of the board.

Exercise 3. Design a data and class definition for the World. It should keep track of all the cells in the game. At each tick, all cells should update their live or dead state appropriately.

One option for designing this is to use ArrayLists containing ArrayLists to represent rows and columns. You may want to use a ListIterator to update the board and set up Cells. When setting up the board, you will want to make sure that Cells actually keep track of their neighbors.

For now, have your world start out with some default set of cells live.

Make sure that your cells update correctly. In particular, be careful that you don’t accidentally use the wrong values of neighbors when updating liveness. A Cell should only change its state based on the current states and not the future states of neighbors (you may need to keep track of extra information to do this).

Exercise 4. Add GUI buttons or add key shortcuts to your world that will start, pause, and reset the world. Also add the ability to click on a cell and change it from live or dead (but only when the game is paused).

The world should start out paused so you can set the initial cell configuration.

Exercise 5. Now that you can set up the board interactively, try various initial configurations. Can you find any patterns that do interesting things?

Extending the game

So far, the rules you have implemented are just the plain Game of Life rules. When you think about it, there’s really no reason to hardcode these rules into the game though. What if we abstracted and made the liveness rules parameters of the game?

Exercise 6. Add parameters to your World via its constructor that control how the rules of the game work.

For example, you should be able to set the thresholds at which a cell becomes overcrowded and dies. Or the number of live cells that cause a barren cell to become live again.

Exercise 7. Add either GUI elements or key presses that will change the parameters of the game as you run it.

Are there any interesting variations on Conway’s rules that you can find?

Here are some more ideas that you can try if you’ve gotten this far:

Exercise 8. Make barren cells randomly come to life with a low probability. Make the probability of random mutation tunable.

Exercise 9. Add a parameter to your simultation that will change how large a cell’s neighborhood is. For example, Conway’s game of life has a 1-distance neighborhood (only immediate neighbors). Make the game able to support 2-distance neighbors (so each cell would have 25 neighbors) and so on.

This parameter affects how your other parameters should behave (like the liveness thresholds) so you should keep that in mind when adding it.