Channels ▼

Clay Breshears

Dr. Dobb's Bloggers

Game of Life — Using Lists to Focus Processing

March 19, 2013

When I wrote the generation computation loop in the main() routine, I assume that each of the functions used in a TraverseList() call does what it needs to do. Now we can look into each of those functions to see how the lists are processed to cover the computation of each generation. First, Vivify(), which, for each item on the maylive list, brings a qualifying dead cell ALIVE.

void Vivify(Cell cell)
{
   if (Map[cell.row][cell.col] == DEAD &&
       numNeighbors[cell.row][cell.col] == 3)
         if (cell.row >= 1 && cell.row <= maxrow &&
             cell.col >= 1 && cell.col <= maxcol) {
         	Map[cell.row][cell.col] = ALIVE;
         	AddList(cell, &newlive);
         }
}

The function first ensures that the cell under consideration is DEAD and that it has the correct number of neighbors to become ALIVE. If these conditions are met, the position of the cell is checked to ensure that it is within the valid portion of the grid. If the cell is not one of the border cells, it is set to ALIVE on the Map. Since this cell has just been changed from DEAD to ALIVE, this cell is added to the newlive list for processing in the second phase of the generation computation.

After processing all the possibly new cells, the next list traversal will examine those locations that are ALIVE but may die out in the generation being computed. This is done by processing items from the maydie list with the Kill() function. Like Vivify(), the cell is first checked to ensure it is ALIVE and that the current number of neighbors is too low or too high for the cell to remain ALIVE. For those list items that pass these conditions, if the cell is not in the border area, it is marked DEAD and the cell is added to the newdie list. (As in DSDPC, the code is left as an exercise.)

After the newly born and killed cells have been dealt with, the second phase of the generation loop updates the numNeighbors grid points around those changed cells held in the newlive and newdie lists. First the newly ALIVE cells are handled by traversing the newlive list with the AddNeighbors() function applied to each element on the list. This function is given below.

 void AddNeighbors(Cell cell)
{
   int R,              // loop index for row of neighbor loops
       C;              // column loop index
   Cell neighbor;      // structure form of a neighbor

   for (R = cell.row-1; R <= cell.row+1; ++R)
      for (C = cell.col-1; C <= cell.col+1; ++C)
         if (R != cell.row || C != cell.col) {  //skip cell itself
            numNeighbors[R][C]++;
            switch(numNeighbors[R][C]) {
               case 0:
                  Error("Impossible case in AddNeighbors.");
                  break;
               case 3: 
                  if (Map[R][C] == DEAD) {
                     neighbor.row = R;
                     neighbor.col = C;
                     AddList(neighbor, &maylive);
                  }
                  break;
               case 4:
                  if (Map[R][C] == ALIVE) {
                     neighbor.row = R;
                     neighbor.col = C;
                     AddList(neighbor, &maydie);
                  }
                  break;
            }  // switch

         }
}

The double-nested loop circulates through the eight neighboring grid points that surround the newly live cell and increments the neighbor count of each. Based on the updated count, the switch statement considers the potential state of the neighboring cells in the next generation. If a neighbor cell is DEAD and the new live neighbor has incremented the neighbor count to exactly 3, then the cell might become live in the next generation. This neighbor of the new cell is added to the maylive list. Conversely, if the neighbor cell is ALIVE and the new live cell has pushed the count to 4 (which means that is was 3 and still viable before the newly live cell was born), then the cell might be killed in the next generation. This neighbor is added to the maydie list.

The SubtractNeighbors() function is similar in structure to AddNeighbors(). For each of the eight cells adjacent to the cell the corresponding value of numNeighbors is decremented. If the updated number of neighbors has decremented to 3 and the neighbor is DEAD, it is added to the maylive list; or, if the updated neighbor count is 1 and the cell is ALIVE, it is added to the maydie list. (As with Kill(), the code is left as an exercise.) Once the newdie list has been traversed, the newlive and newdie lists are cleared in anticipation of the computation for the next generation.

If all of the above is clear, there's one last little piece of business to deal with. Consider a DEAD cell whose neighbor count is already 1. Two new neighbor cells will increment the count to 3 and add the cell to the maylive list. One more neighbor puts the count at 4 and the cell under consideration clearly does not belong on the maylive list. A cell that is ALIVE whose neighbor count gets to 4 is added to the maydie list, but if another neighbor is killed, the SubtractNeighgbors() function will reduce the count to 3, which means that the cell should not be on the maydie list since it has just the right amount of neighbors to remain ALIVE. Do I need to code up my list methods to deal with these potential situations? The answer is "No."

There is a clue in the names of the lists populated in the second phase and processed in the subsequent first phase of the main loop. The maydie list is a set of cells that could be killed in the next generation and the maylive list is the set of cells that might be made alive in the next generation. It is only when traversing these two lists in the first phase of the main loop, when the numNeighbors values have stabilized, that the determination on whether a cell remains as is, becomes ALIVE, or is set to DEAD will be made. Even if the same cell is on both the maylive and maydie lists, we know that the conditions to make that cell both live and die in the same generation will not occur. DSDPC spends a couple of pages proving that the correct outcome will result for each cell considered in a generation.

In the next post, I'll look at how to parallelize this new version of Game of Life. While you're waiting for that to be published, try to determine if, when running the serial code, the same cell can appear more than once on either the maylive or maydie lists. Can it happen in parallel, how would the work be divided among threads to create such a situation, and how would you avoid it (or do you need to actively avoid that case)?

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video