As mentioned earlier, the most common cellular automaton game (by far) is Conway’s Game of Life. In fact, I had to program a Conway’s Game of Life (heretofore called simply Life) program in my assembly language class back in 1987 (egads, I’m old). The cells in this automaton contain only two states, dead and alive. The fate of each cell in a turn depends on its eight neighbors—three above, three below, and one each to the immediate left and right. If a cell is alive and has two or three alive neighbors in turn x, then that cell will remain alive in turn x+1. A living cell with fewer than two alive neighbors dies of starvation; a cell with more than three living neighbors dies of overcrowding. Furthermore, cells that are dead will suddenly spring to life in turn x+1 if they contain exactly three living neighbors in turn x. Figure 5-2 shows a block of cells on the left and how that same area looks one turn later.
Figure 5-2: Life cell state in turn x (left) and turn x+1 (right)
Describing the rules of Life does the process no justice whatsoever. The only way to understand and learn about the patterns and complexity formed out of these seemingly simple rules is to watch a Life program run through multiple clock ticks in succession. If you’re new to the Life scene, compile the source code for this project and play with it for a while before studying the code so you can better understand the intent of the classes described. Discovering all of the rule variations and amazing patterns in Life can be (and often is) the subject of entire books, so this one makes no attempt to cover such a complex topic with any depth.
To implement a cellular automaton variant in the program, you must create subclasses of the CellularAutomataGame and CellularAutomataCell classes.
In the game class, you must override two methods minimally. The first of these methods is CreateOneCell, and its job is to return an initialized instance of the game-specific cell class to the caller. If you’ll recall, the caller is the CellularAutomataGame class itself—specifically, the CreateData method shown in Listing 5-3. This method calls CreateOneCell, which can vary widely from subclass to subclass. Listing 5-6 shows this method for the Life class.
Listing 5.6: The CreateOneCell Method in the Life Class
Protected Overrides Function CreateOneCell(_ ByVal oPos As Point) As CellularAutomataCell Dim oC As ConwaysLifeCell fSetupNeighbors = False oC = New ConwaysLifeCell(oPos, Me.CellRadius) oC.Alive = oRand.Next(0, Int32.MaxValue) Mod 5 = 0 Return oC End Function
Given a point parameter, this method creates a single instance of the ConwaysLifeCell class, initializes the Alive property to True about 20 percent of the time, and returns this instance to the caller. It also sets a class-level variable named fSetupNeighbors to False. This variable indicates that a process that defines each cell’s eight neighbors needs to execute before the next clock iteration occurs. The idea is that if a new cell is being created via a call to this method, then the lattice has changed enough so that all of the cells need their neighbors set up again before a clock cycle can happen.
| Tip |
How does the CreateOneCell code create a 20-percent chance of something occurring? To obtain a result 20 percent of the time, you can take a random integer, divide it by 5, and then look at the remainder using the Mod operator. The remainder of dividing a number by 5 will be 0, 1, 2, 3, or 4. Because each of the five possible remainders of a random integer divided by 5 is equally likely, you have a 20-percent chance of getting any one of them. In the CreateOneCell method, you can test that the remainder is 0, and if it is, you set the Alive property to True. |
The cell neighbor setup process is fairly slow, so it isn’t beneficial to perform it more often than required (certainly you wouldn’t need or want to perform this neighbor setup on every clock tick, for example). Listing 5-7 shows the code for the neighbor setup process.
Listing 5.7: Defining the Neighbors of Each Cell
Private Sub SetupNeighbors() Dim i As Integer Dim iRow, iCol As Integer 'loop variables Dim iLRow, iLCol As Integer 'loop variables Dim oCn As ConwaysLifeCell Dim oC As ConwaysLifeCell For i = 0 To FCells.Count - 1 oC = FCells.Item(i) oC.ClearNeighbors() IndexToRowCol(i, iRow, iCol) For iLRow = -1 To 1 For iLCol = -1 To 1 If iLRow = 0 And iLCol = 0 Then 'nothing, same cell Else oCn = RowColToCell(iRow + iLRow, iCol + iLCol) If Not (oCn Is Nothing) Then oC.AddNeighbor(oCn) End If End If Next Next Next fSetupNeighbors = True End Sub
The neighbor setup process iterates through each cell in the FCells ArrayList. You can use an integer-based For loop as opposed to a For..Each construct so the index of each cell is needed to determine the cell’s row and column position within the lattice. You find the row/column position using the IndextoRowCol method, which is declared as protected in the base class and therefore available to call. Once you find the row/column position, create a nested loop pair to loop between all cells –1 and +1 away from the current cell. Figure 5-3 shows the cell indexes for a cell. The center cell is at position iRow, iCol.
Figure 5-3: The center cell’s eight neighbors and their indexes
Within this nested loop, the eight neighbor cells are determined using the starting row/column added to the loop indexes, and the protected method RowColToCell method is called to translate this row/column pair back to a cell in the lattice. This method returns nothing if the passed-in indexes are out of range (the cells on the left edge have no left neighbor, for example). Each cell that’s successfully returned is set to be a neighbor of the original cell using the AddNeighbor method. The last line sets the neighbor setup Boolean flag to True. This prevents this code from running again, unless of course more cells are added to the lattice later—say, when the game form is resized.
The final method for the ConwaysLifeGame class is the overridden RunAGeneration method, shown in Listing 5-8.
Listing 5.8: Running One Tick of Conway’s Game of Life
Protected Overrides Sub RunAGeneration() Dim oC As ConwaysLifeCell If Not fSetupNeighbors Then SetupNeighbors() End If 'clear neighbor count For Each oC In FCells oC.PreCountReset() Next 'if I'm alive, updated neighbor count on all 8 neighbors For Each oC In FCells oC.UpdateNeighborsBasedOnMe() Next For Each oC In FCells oC.UpdateAliveBasedonNeighbors() Next End Sub
As hinted at earlier, the beginning of the RunAGeneration method sets up the neighbor cells but only if the Boolean flag is False. If the flag is True, then the neighbors of each cell have already been defined and this call is skipped.
To determine what happens to each cell in this generation, one must loop through all the cells and count neighbors. Then, according to the rules of the game, each cell will live or die based on these neighbor counts. The algorithm that most Life programmers first attempt loops through every cell, living or dead. For each cell, the code checks all eight neighbors and sums them if living to create a total. This neighbor count is then stored until all the cells have been counted (you can’t change the state of this cell now or else its new state would incorrectly affect the neighbor count of the cells bordering this one). Once all the cells have had their neighbors counted, each cell is iterated again to have its state changed if required by the rules and its neighbor count.
This algorithm works but turns out to be inefficient because every cell in the lattice is accessed multiple times. A given cell is passed through in the main loop and then checked for its life/death state up to eight times because it serves as the neighbor to eight other cells.
A much more efficient algorithm is to first initialize all cell neighbor counts to 0. Then the main cell loop begins. If a cell is alive, the program adds 1 to the neighbor count of all eight neighbors of that cell. If a cell is dead, the program takes no action. At the end of the loop, the neighbor counts will all equal the number of living neighbors as desired, and the rules can then be applied to determine the state of each cell. This algorithm is faster because no action is taken when a cell is dead, so the process accesses the total lattice far fewer times.
The code in Listing 5-8 carries out this algorithm. Three For..Each loops are iterated upon the lattice. The first merely resets the neighbor cell count of each cell to 0. The second calls the UpdateNeighborsBasedOnMe method of each cell, which adds 1 to the neighbor count of the eight neighboring cells if the given cell is alive. The third loop calls UpdateNeighborsBasedOnMe, which changes the living/dead state of each cell based on its neighbor count.
The ConwaysLifeCell class descends from the CellularAutomataCell class. The ancestor class handles the location information for a cell and most of the drawing functionality. One thing the ancestor class doesn’t handle, however, is determining the color of the cell to be drawn. That method, called GetColor, is declared on the ancestor as MustOverride and must be implemented in the subclasses. That method is quite simple in the ConwaysLifeCell class:
Overrides Function GetColor() As Color Return IIf(Not Alive, Color.Black, Color.Yellow) End Function
A Life cell can only display one of two colors, which are yellow for a living cell and black for a dead cell in this example.
The other required MustOverride member in the ancestor cell class is the OnMouseDown method, which describes what’s to happen when a user clicks a cell. That too is quite simple in this variation—you merely want to toggle the alive/dead state of the cell when it’s clicked:
Public Overrides Sub OnMouseDown(ByVal e As _ System.Windows.Forms.MouseEventArgs) Me.Alive = Not Me.Alive End Sub
The remainder of the cell class handles the neighbor storage and the functionality of updating neighbor counts and state. Listing 5-9 displays the remainder of the cell class (omitting a few trivial members such as the Alive and NeighborCount properties).
Listing 5.9: The Remainder of the ConwaysLifeCell Class
Public Class ConwaysLifeCell Inherits CellularAutomataCell Protected FNeighbors As ArrayList Public Sub AddNeighbor(ByVal oC As ConwaysLifeCell) If FNeighbors Is Nothing Then FNeighbors = New ArrayList End If FNeighbors.Add(oC) End Sub Public Overridable Sub PreCountReset() NeighborCount = 0 End Sub Public Overridable Sub UpdateNeighborsBasedOnMe() Dim oC As ConwaysLifeCell If Me.Alive Then For Each oC In FNeighbors oC.NeighborCount += 1 Next End If End Sub Public Overridable Sub UpdateAliveBasedonNeighbors() If Not Alive Then 'not alive now, comes to life if 3 neighbors Alive = (NeighborCount = 3) Else 'alive now, stays alive w/ 2 or 3 neighbors Alive = (NeighborCount = 2 Or NeighborCount = 3) End If End Sub End Class
The neighbors of each cell are stored in an ArrayList named FNeighbors. The implementation of the AddNeighbor method is pretty straightforward—all that’s required is to initialize this ArrayList if it hasn’t already been done and then add the passed-in neighbor to it. The method UpdateNeighborsBasedOnMe is also quite simple. This method increments the alive neighbor count of all the neighbors of this cell, but only if this cell is currently alive (dead cells don’t affect neighbor counts, remember). Finally, the method UpdateAliveBasedOnNeighbors implements the living/dead rules for a cell—alive cells with two or three neighbors stay alive, and dead cells with exactly three neighbors spring to life. I particularly like how the code in this method resembles English: “If not Alive, Alive is true if NeighborCount equals three….”
Note that the methods PreCountReset, UpdateNeighborsBasedOnMe and UpdateAliveBasedOnNeighbors are defined as Overridable, meaning that their functionality can be changed in any subclasses created from the ConwaysLifeCell class. But do you really intend to create a subclass from this cell class, which is already itself a subclass?