In this post, I'm going to discuss the basic parts to code the Game of Life using list data structure to hold the sets of grid points that may become alive or may die in the next generation. This modification can reduce the amount of processing needed by focusing the computation on the volatile areas of the grid and leaving those parts that are empty or that have achieved a stable configuration of cells. This approach and algorithm comes from the book Data Structures & Program Design in C (Second Edition) by Robert Kruse, C.L. Tondo, and Bruce Leung (Prentice-Hall, 1997), which I'll shorthand as DSPDC.

As I said in my last post, this variation needs two grids: one to hold the status and position of live cells in the current generation and one to hold the count of the neighbors for corresponding cells. In addition, the algorithm requires four lists of grid points. The global declarations for the code are below.

Grid Map;                // array holding cells
Gridcount numNeighbors;  // array holding neighbor counts
List newlive,            // cells that have just been vivified
     newdie,             // cells that have just died
     maylive,            // candidates to vivify in next generation
     maydie;             // candidates to kill in next generation
int maxrow, maxcol;      // user defined grid size

My user-defined data type Grid and Gridcount are simply two-dimensional arrays. Elements in the Map array hold one of two enumerated states (DEAD, ALIVE) and the numNeighbors array holds integers. The dimensions of the arrays are both maxrow+2 by maxcol+2.

The List type is an abstract data type (ADT) implementing a simple list structure. DSPDC is teaching abstract data types and implements different versions of the List type. Keeping with the spirit of ADTs, I won't give out the implementation details for the List type (and leave that as an exercise to the reader). Each list holds elements (of type Cell) that contain two integers: the row and column index of a notable grid point. The operations defined for the List structure can create a new empty list (CreateList), clear the list of all contents (ClearList), check if the list is empty (ListEmpty) or full (ListFull), return the number of items on the list (ListSize), add an item to the list (AddList), pass through the list and execute a given function on each item (TraverseList), and make a copy of the list onto another list (CopyList).

The main() routine first initializes the Map and numNeighbors grids from an input file (assumed to be given on the command line) of initial live cells. Each of the four lists is also initialized. The WriteMap() routine prints out the current configuration of live cells. (I originally had a call to WriteMap() in the body of the loop to watch the progress of the cells on the grid, but I’ve taken it out for simplicity.)

   Initialize(map, numNeighbors, &newlive, &newdie, &maylive, &maydie, argv[1]);
   WriteMap(map,gencount);
   while (gencount < GENS) {
         gencount++;
         TraverseList(&maylive, Vivify);
         TraverseList(&maydie, Kill);
         ClearList(&maylive);
         ClearList(&maydie);
         TraverseList(&newlive, AddNeighbors);
         TraverseList(&newdie, SubtractNeighbors);
         ClearList(&newlive);
         ClearList(&newdie);
      }
   }

Once the initial set up is done, a while loop runs over the computation steps for each new generation until the target number of generations (GENS) has been computed. To explain the processing required, I like to think that the computation involved in determining the status of the current generation has two phases. The first phase traverses the list of possible new cells (maylive) and possible cells that will be dead (maydie). For each element in the lists, the number of neighbors of the cell is consulted and the appropriate action (new live cell or kill overcrowded cell) is taken. The two lists are cleared in preparation of the next generation. (Note: I'm using lists and not stacks or queues, so the traversal of a list will not remove or change any elements, which is why the separate list clearing function is needed).

For the second phase, the other two lists are then traversed. This is the list for newly live cells (newlive) and those grid points that just had a live cell die (newdie) as found in the first phase. The traversal of these lists updates the numNeighbor counts and determines if an updated count points toward a cell that should become alive or dead in the first phase of the next generation computation. The two traversed lists are cleared at the end of the second phase.

So far I've kept the details of the code at a high level and only hinted at how items are added to the respective lists. Before I get into the details of the computation and functions used to process each list item during a list traversal, ensure that you understand the general idea behind the main generation computation loop.

(In the years that I've been writing code, I have found that assuming your functions work as they are intended is a basic principle of my program design process. Once you have the functionality well defined, you can write code that calls those functions without knowing the details of how the function is implemented. This is the fundamental reason ADTs are so useful. It doesn’t matter if your list is implemented as a statically allocated or linked structure, or an expandable structure, as long as the interfaces perform as defined.)

The Initialize() routine, after initializing each of the four new lists, reads in the locations of each live cell of the starting state. The size of the grids can be read in as part of the input file or preset to some fixed values. Each valid cell that is contained in the input file is added to the newlive list and marked as ALIVE on the Map array. This list is traversed with the AddNeighbors() function to set the initial values for the numNeighbors. Finally, the contents of the newlive list are copied into the maydie list (and the newlive list is cleared) since any one of the initial live cells may have too many neighbors to survive into the first computed generation.

Because AddNeighbors() is used to initialize the numNeighbors array with the proper starting values of the starting cell configuration, you must ensure that there are no duplicate cells in the newlive list. (I'll deal with the potential hazard of duplicate cell entries on lists during the generation computation later in this post.) As you'll be able to see from the AddNeighbors() code below, to get an accurate initial count of the neighbors, I need to watch the file input to remove duplicates or grid points outside of the range of the boundaries.

My code for this version of Game of Life is written in C. Parameters of functions in C can themselves be functions. This feature allows me to write a single TraverseList() function that can apply a different computation to items on the list depending on the function given as the second parameter. My implementation of TraverseList() simply walks down the list and calls the given function on each element of the list. If you use a predefined list structure (say, one that is thread-safe, nudge nudge) and there is no equivalent traversal functionality, you might need to write a "meta" traversal function that can apply the desired function to each element of the list.