Groups	Advanced Groups Search    Preferences    Groups Help

Implementing the game of life without examining neighboring cells.

I haven't coded this yet, but I'll provide some benchmarks once I do.

When implementing the game of life and similar cellular automata the most
frequent operation performed is examining the cells in the neighborhood of
the cell being updated.  A total of 9 array access operations must be
performed for every cell in the arena.  But there is another way of
computing the next generation that never looks at neighboring cells, and
seldom accesses neighbors at all.  This can be accomplished by inverting the
way the rules are implemented.  Instead of a cell examining its neighbors
learn its state, each occupied cell sends a single message to each of its
neighbors.  Since unoccupied cells never send a message they never access
their neighbors and so if the population of the arena is, say, 20% of the
total area then 80% of time no neighbor cells need to be accessed at all
leading 1/9th as many array accesses and computation speeds up to 9 times
faster per generation.

In addition, this alternate way of computing the next generation is computed
in place without the need to use a second copy of the arena to hold the
intermediate results.

This is accomplished by using 18 states per cell instead of 2 states.
Instead of just being alive or dead cells can be alive in 9 different ways
or dead in 9 different ways.  These states are numbered 0 through 17.

During the first pass through the arena the current state of each cell is
fetched, and if the rule for that state calls for it, 1 is added to the
state of each neighbor of that cell.  In a sparse arena most of the cell
states will not call for a contribution to be made to the neighbors and so
the work on that cell is done as soon as the cell itself has been examined.

After the entire arena has been updated in pass one a second pass is made
during which each state found in a cell is replaced by the state called for
in the rules.  This completes the updating of the next generation.  Each
cell ends up either in state 0 (empty) or state 9 (full) and cells of any
other state occur only during the generation loop, but never after it has
been completed.  This sedcond pass can be done at virtually no additional
cost by making it part of the loop that updates the display.

The inverse rule set is:

st = current state.
add = how much to add to each neighbor's state in pass one
next = state to change to in pass two

st add next

 0  0  0
 1  0  0
 2  0  0
 3  0  9
 4  0  0
 5  0  0
 6  0  0
 7  0  0
 8  0  0
 9  1  0
10  1  0
11  1  9
12  1  9
13  1  0
14  1  0
15  1  0
16  1  0
17  1  0

Verifying that it works:

If a cell is in state 0 and has 3 neighbors its state will become 3 by the
end of pass one which will transition to state 9 in pass 2.  Thus, an empty
cell with three neighbors will give birth to a cell with state 9.

An empty cell with other than 3 neighbors will become some state less than 9
and other than 3.  All of these states contribute nothing in pass one and
transition to state 0 in pass two.

If a cell is in state 9 or higher it will contribute 1 to each of its
neighbors.

If a cell is in state 9 and has 2 or 3 neighbors its state will become 11 or
12 in pass one, both of which transition to state 9 in pass two.

If a cell is in state 9 and has other than 2 or 3 neighbors it will become a
state greater than or equal to 9, but not equal to 11 or 12.  All of these
states transition to state 0 in pass two.

Therefore at the conclusion of the generation loop there will be only two
states, 0 and 9, which correspond exactly to the two states in GOL, and
which follow the same birth and death rules as GOL.

Pseudo code:

// pass one

for x =  0 to arenaMaxX
   for y = 0 to arenaMaxY
      if ruleAdd[arena[x,y]] not zero
         for dx = -1 to 1
            for dy = -1 to 1
               if dx not zero OR dy not zero
                  arena[x,y] = arena[x,y] + 1
            next dy
         next dx
   next y
next x

// pass two

for x =  0 to arenaMaxX
   for y = 0 to arenaMaxY
      arena[x,y] = ruleNext[arena[x,y]]
      update display for cell[x,y]
   next y
next x

Post a follow-up to this message