Beginners Programming

Demos

It's a lot easier to play computer games involving cellular automata than it is to describe it, but let me give it a shot. Hopefully, this definition will work well for our purposes:

Cellular automata is a math game which uses mathematical rules to manage the "life" and "death" of individual virtual cells on a rectangular grid.

John Horton Conway, a professor of mathematics at Cambridge University and Princeton, is the one who is generally credited with elevating cellular automata to what became--dare I say--a "field of study". In 1970, Conway published an article in Scientific American about a game that he was creating involving cellular automata. This game was called "Life" (and later "Conway's Life") because game progress creates patterns that, to some, resemble the growth of one-celled creatures.

*Cell grid with live cells in black, *

*dead cells in white*

Conway's Life is played on a two-dimensional grid of cells. The grid can be any size. Each cell in the grid has a state. A cell's state can either be live or dead. The state of each cell is subject to change with each new generation of the cell colony. Whether a live cell remains live (or changes to dead), and whether a dead cell remains dead (or changes to live) depends on how many live neighbors each cell has.

The number of cells required to convert a live cell to dead, or a dead cell to live, is defined in the rules of the game.

Computing resources were minimal when Conway and his students first began to study the game. At that time, they typically used checkers to produce new generations of cells. In the late 80's, however, computers became more powerful, and email use became more widespread. Computer enthusiasts began writing new life programs, and emailing patterns to each other.

Before we look at BASIC code to determine the state of a cell in the next generation, let's identify the most common set of rules for Life.

If you look at any single cell on the grid, it is bounded by eight cells, any of which can be dead or alive. These eight cells are the subject cell's neighbors. With each new generation of the game, every cell in the grid is evaluated to determine how many live neighbors it has. A live cell that has too many or too few neighbors will convert into a dead cell. A dead cell with the right number of neighbors will convert into a live cell. Otherwise, it will remain dead.

Conway and his students looked at many different sets of rules, trying to find those rules that would produce the most interesting results. After much experimentation, they decided that the following rules worked very well:

- A cell that is alive will remain alive in the next generation if it has 2 or 3 neighbors that are also alive. If it has more than three neighbors, the cell will die. Likewise, if it has 0 or 1 neighbor, the cell will also die.
- A cell that is dead will come alive in the next generation if it has exactly 3 neighbors. Otherwise, the cell will remain dead.

Since Conway and his students ultimately converged on this set of rules, games employing these rules are sometimes generically called "Conway's Life". On other occasions, this set of rules is referred to as "23/3", because it takes two or three living neighbors for a live cell to remain living, and three live neighbors for a dead cell to give birth.

*Cell grid with live cells in black, *

*dead cells in white*

How might we use BASIC to determine the state of a cell in the next generation? Take a look at the figure on the right. The white cells represent cells that are dead, while the black cells are live. Notice also that I've numbered nine of the cells for purposes of this discussion.

To determine the state of a cell in the next generation, we determine how many live neighbors that cell has, then apply the "23/3" rules. Look at Cell 1. Cell 1 is a dead cell in the current generation. But like all cells, Cell 1 has eight neighbors. However, only one of Cell 1's eight neighbors is live. Since a dead cell requires 3 live neighbors to become live in the next generation, Cell 1 will remain dead in the next generation.

Now look at Cell 3. Cell 3 is currently dead, but it has 3 live neighbors. In the next generation, it will be live.

Now look at Cell 5. Cell 5 is currently live, and it has 2 live neighbors. By the "23/3" rules, any live cell with 2 or 3 live neighbors will remain alive in the next generation.

Last, look at Cell 9. Cell 9 is currently dead, and has 5 live neighbors. Since 3 live neigbors is the only condition which will allow a dead cell to become live in the subsequent generation, Cell 9 will remain dead.

The grid in the figure bears a resemblance to a two-dimensional array. In fact, two-dimensional arrays are very good instruments for calculating the status of a cell. Let's establish two 2-dimensional arrays to track cell generations. One array, xyold(12,10), will represent cell states in the current generation. The second array, xy(12,10), will represent cell states in the next generation. If a cell is currently live, the array value representing the cell will hold the value 1. Otherwise, the cell is dead its array value will hold the value 0.

The location of each and every cell can be identified by its ith column and its jth row. The cell represented by ** xyold(i,j)** has eight neighbors. These neighbors are:

xyold(i-1,j-1) ' xyold(i ,j-1) 'These three in the row above xyold(i+1,j-1) ' xyold(i-1,j) 'These two in the same row xyold(i+1,j) 'as xyold(i,j) xyold(i-1,j+1) ' xyold(i ,j+1) 'These three in the row below. xyold(i+1,j+1) '

To determine the state of each and every cell in the subsequent generation, we need a counting routine that looks something like this:

NumRows = 10 NumCols = 12 [Calculate.Next.Generation] for i = 2 to (NumCols - 1) for j = 2 to (NumRows - 1) NumLiveNeighbors = 0 NumLiveNeighbors = xyold(i-1,j-1) + xyold(i,j-1) + xyold(i+1,j-1) NumLiveNeighbors = NumLiveNeighbors + xyold(i-1,j) + xyold(i+1,j) NumLiveNeighbors = NumLiveNeighbors + xyold(i-1,j+1) + xyold(i,j+1) + xyold(i+1,j+1) If ((xyold(i,j) = 0) and (NumLiveNeighbors = 3)) then xy(i,j) = 1 else if ((xyold(i,j) = 1) and ((NumLiveNeighbors < 2) or (NumLiveNeighbors > 3))) then xy(i,j) = 0 end if end if next j next i

There are two things to note here:

- I am not calculating the future state of the cells in the very first row or the very first column of xyold(i,j). This is because my life grid is finite, and the perimeter cells do not have eight neighbors each, like all of the interior cells do. So, I start with the cell in the second row and second column.
- The new status of a cell in the next generation must be store in a second array, xy(i,j), not in the array in which live neighbors are being counted, xyold(i,j). This is because if we change the state of a cell now while we are counting its live neighbors, then that will effect the correct state of the neighbor when it comes time to count it!

Of course, what we've just done above is determine the state of each and every cell in the next generation. Once the next generation is calculated, it's interesting to plot the live cells to a grid so that we can get a visual picture of how the cell community is changing generation by generation. But the plotting operation is a bigger challenge than just calculating the state of cell, so this article will not delve into it. However, the reader is invited to disect the code of the demo program (discussed below) which is open source.

Once the newest generation of live cells has been plotted to grid, this new generation becomes the basis for calculating the state of each cell in the next generation. To set the stage for this, we need to replace all of the values in xyold(i,j) with those values in xy(i,j):

for i = 1 to NumCols for j = 1 to NumRows xyold(i,j) = xy(i,j) xy(i,j) = 0 next j next i

With that accomplished, we can send program control to the code that begins at the branch label, ** [Calculate.Next.Generation]** (see above), and begin the process all over again.

*Humble Life* written with [Liberty BASIC]

Humble Life (screenshot on right) is a [Liberty BASIC] program written using the "23/3" rules, which are the rules favored by John Conway. Humble Life has the following features:

- The user can create his own patterns by clicking and dragging the mouse around the life grid.
- Humble Life comes with a large collection of pre-made life patterns.
- Data files created by Humble Life are readable by other Life programs.
- The user can vary the granularity of the life grid, "granularity" referring to the number of life cells per unit distance.
- Humble Life features both automatic regeneration of cells, and manual regeneration of cells. In other words, the user can manually step through successive generations.
- Humble Life comes with a very nice help application written in HTML, which contains much more information about Conway's life, and cellular automata in general.

If you are interested in trying Humble Life, download the ** HumLife.zip** archive. For those of you who may not have Liberty BASIC licenses, you may play with Humble Life by running the

[Editor: The HumLife.zip archive is in the newsletter archive and is available when the newsletter is downloaded.]

If you would like to learn a little bit more about Conway's Life and cellular automata, visit these places on the web:

- Paul's Page of Conway's Life Miscellany -- Among other things, this site has links to an illustrated catalogue of life patterns.
- Life Lexicon (Introduction) -- This is a fascinating web page which provides definitions of all the terms that have arisen as a result of the Game of Life.
- Stephen Silver's Life Page -- This is a good, general-purpose Life page. It contains many links to Life resources, including a link to Life for PalmOS.
- Home Page for Life32 by Johan Bontes -- Life32 is probably the best Life program for Windows systems. Hey, it's freeware, too!
- The WinLife32 Page -- WinLife32 is another excellent Game of Life program, ranking up there with Life32.
- Jason's Life Page -- This page has many links to collections of Life Patterns.
- Cellular Automata file formats -- Comprehensive discussion of file formats, residing on the same University of Wisconsin server as Life32
- Life written in Java -- You don't need to download a life application to play the game. There are a number of fine Java Applets ready to go right now:
- [http://world.std.com/~bgw/applets/1.02/Life/Life.html]
- [http://www.bitstorm.org/gameoflife/]
- [http://www.ibiblio.org/lifepatterns/]
- [http://membres.lycos.fr/ldavid/indexe.html] (This one is a particularly interesting java applet in which groups of cells which move to the edge of the Life grid actually wrap around to the opposite side of the grid.)