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:
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:
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:
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 HumLife.tkn file.
[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: