Channels ▼

Clay Breshears

Dr. Dobb's Bloggers

Conway's Game of Life In Parallel

December 05, 2012

Game of Life is a cellular automata exercise created by mathematician John H. Conway in 1970. It's not really a game in the traditional sense since the outcome is decided solely by the initial set up and there aren't any players. A better description might be that it is a simulation.

A popular notion is to think of the automata as biological cells that can live, die, and procreate all within a rectangular-grid region, one cell per grid point. The simulation updates the status of the grid points according to the rules of the game in successive generations. Conway used a go board and stones to track how starting configurations of cells played out while he was developing the rules of the game. This is an obviously tedious and error-prone method of tracking changes from one generation to the next. Computer programs of the simulation (as in Figure 1) are both faster and assure correct results (when programmed correctly, of course). Without computer simulations, all of the interesting aspects and patterns within the realm defined by the simulation rules might never have come to light.

The rules for Game of Life are simple. They determine when a live cell remains alive from one generation to the next, when a living cell dies, and when an empty grid point can birth a new cell. The number of surrounding grid points, or neighbors (which will be 8 or fewer), that hold a live cell is summed and that value is used to determine what is contained in the surrounded cell in the next generation according to the following:

  • A cell that is alive remains alive if there are 2 or 3 live neighbors,
  • A live cell dies if the number of live neighbors is less than 2 (loneliness) or greater than 3 (starved for food), and
  • An empty (dead) cell will birth a new alive cell if there are exactly three live neighbors.

It is possible for a cell to be birthed and for some or all the "parent" cells to be dead in the next generation. This feature of the rules leads to some interesting patterns and behaviors of groups of cells over the course of several generations. One of the simple periodic patterns is the blinker. Start with a horizontal row of three consecutive live cells with no other live cell neighbors. For the next generation, these cells will birth a new cell into the empty cell above and empty cell below the center cell while the end cells will be dead since they each have only one live neighbor (the center cell, which remains alive due to the two live neighbors). The new generation pattern will be three consecutive cells in a vertical row. This pattern will oscillate between three cells in a horizontal and vertical arrangement. Watching such an oscillation at a modest refresh rate between displays of consecutive generations gives the grouping the appearance of a light blinking on and off. More complex patterns have been discovered, some of which appear to be able to move under their own power and others that can generate such moving cell structures.

Implementing a Game of Life application is a good exercise to teach 2-D array manipulation to first-time programmers. Each element of the array corresponds to a grid point (cell) that may be either alive or dead. Two 2-D arrays are allocated: one for the current generation and one for the next generation. Starting with the initial live cell configuration, the application counts up the number of live neighbors for every element in the array and populates the elements of the next generation according to the rules stated above.

Since the arrays are of a finite size, the code needs to deal with what happens around the borders of the grid, which have less than 8 neighbors. A simple solution is to add border cells around all four edges of the grid. These cells are never part of the simulation, except to be grid points that can be read in order to make the neighbor counting code not have to deal with special conditions at the border and corner cells.

A serial implementation will be a loop over the generations that are to be simulated that contains a doubly nested loop over the two-dimensional grid space. Here is pseudo-code for implementing the simulation for Game of Life.

initialize grids;
while (more generations) do {
   for i = 1,maxrow
      for j = 1,maxcol {
            count neighbors of cell(i,j) from current generation;
            set next generation status of cell(i,j);
      }
   make next generation the current generation;
}

Because the computation of one generation to another is a time series, you can't parallelize that outermost loop. However, since the counting of neighbors and the decision of what to do with any cell into the next generation is independent of any other cell, you can parallelize the cell computations within a generation.

For shared memory threads, this is almost a trivial exercise. Using a domain decomposition, put an OpenMP for pragma around one of the inner loops. It's a more interesting exercise to do the parallelization in a distributed memory model where the grid is strewn across the nodes of a cluster. In my next post, I'll discuss the ins and outs of that parallel computation.

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