Fast GOL alogrithm that doesn't examine neighbors.
fiziwig
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
fiziwig
// 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+dx,y+dy] = arena[x+dx,y+dy] + 1
Kent Paul Dolan
> Implementing the game of life without examining neighboring cells.
I like it! And so a glider moves out into empty cellular space by
doing the CA equivalent of "phone ahead, E.T."! ;-)
xanthian.
Rik Blok
population density but since it is so low for GoL in "the wild" (~3%) it
really helps. I got a 30%+ speed boost in my simulation (with only about
10 minutes work of re-coding). Not quite the boost you were hoping for but
significant nonetheless.
Thanks much!
Rik
"fiziwig" <fiz...@starband.net> wrote in
news:ZAU7a.2679$KZ3.68...@twister2.starband.net:
> Implementing the game of life without examining neighboring cells.
>
> I haven't coded this yet, but I'll provide some benchmarks once I do.
[...]
fiziwig
non-neighbor counting overhead than I assumed.
Glad it helpd somewhat though :)
--gary
"Rik Blok" <rikblok@-DoNtSpAmMe-shaw.ca> wrote in message
news:Xns9331D08C5A5D...@24.69.255.211...
Tim Tyler
: That's interesting. Apparently there's more computation time involved in
: non-neighbor counting overhead than I assumed.
Consider - it requires over four times as much memory to be moved around -
since there are many more states per cell.
That means you can typically only process an area of 1/4 the size
before your processor's cache fills up.
The technique of caching the number of neighbours looks like it would be
of most benefit in automata where the number of neighbours is unlikely to
change - e.g. because of a prevalance of still-life configurations.
--
__________
|im |yler http://timtyler.org/ t...@tt1.org
Owen Rees
in <ZAU7a.2679$KZ3.68...@twister2.starband.net>:
>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.
That is not how the good implementations work. For example, see Alan
Hensel's description of his life applet which describes life universes
as 'blobby' <http://hensel.lifepatterns.net/lifeapplet.html>.
I remember seeing a very good description of CA implementation
techniques some time ago, but I can't find it now. One thing it
mentioned is that neighbourhoods of adjacent cells overlap, so you
arrange to re-use the existing analysis of the 6/9 you have just
studied.
--
Owen Rees - opinions expressed here are mine; for the full disclaimer
visit <http://www.users.waitrose.com/~owenrees/index.html#disclaimer>
for e-mail use "owenrees at waitrose.com" instead of the From address
Frank Buss
> I remember seeing a very good description of CA implementation
> techniques some time ago, but I can't find it now. One thing it
> mentioned is that neighbourhoods of adjacent cells overlap, so you
> arrange to re-use the existing analysis of the 6/9 you have just
> studied.
Perhaps you mean this page:
http://cell-auto.com/optimisation/
--
Frank Buß, f...@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Tim Tyler
: I remember seeing a very good description of CA implementation
: techniques some time ago, but I can't find it now.
The documents closest to that description that I'm aware of are:
http://public.planetmirror.com/pub/gpbb/gpbb17.pdf
...and...
http://public.planetmirror.com/pub/gpbb/gpbb18.pdf
Owen Rees
wrote in <b43itu$i34$1...@newsreader2.netcologne.de>:
>Perhaps you mean this page:
>
>http://cell-auto.com/optimisation/
A very good page, thanks for the link. A lot of good information, but it
did not seem familiar. However, that page had the term 'flywheel', which
I had forgotten, for the technique I remembered. With that as an extra
search term, I found <http://cafaq.com/soft/index.shtml> which did seem
familiar in parts, but it would not be suprising for the page to have
been updated since I last saw it.
Owen Rees
<HB9qA...@bath.ac.uk>:
>The documents closest to that description that I'm aware of are:
>
>http://public.planetmirror.com/pub/gpbb/gpbb17.pdf
>
>...and...
>
>http://public.planetmirror.com/pub/gpbb/gpbb18.pdf
They are not the document I was thinking of, but look very interesting.
Thanks for the links. (I noticed that the index page says it is an
Australian mirror - its 'link to the original' did not work, but I found
it at <http://www.byte.com/abrash/>.)