Optimizing Conway's 'Game of Life'

Question

To experiment, I've (long ago) implemented Conway's Game of Life (and I'm aware of this related question!).

My implementation worked by keeping 2 arrays of booleans, representing the 'last state', and the 'state being updated' (the 2 arrays being swapped at each iteration). While this is reasonably fast, I've often wondered about how to optimize this.

One idea, for example, would be to precompute at iteration N the zones that could be modified at iteration (N+1) (so that if a cell does not belong to such a zone, it won't even be considered for modification at iteration (N+1)). I'm aware that this is very vague, and I never took time to go into the details...

Do you have any ideas (or experience!) of how to go about optimizing (for speed) Game of Life iterations?

Answer 1

I am going to quote my answer from the other question, because the chapters I mention have some very interesting and fine-tuned solutions. Some of the implementation details are in c and/or assembly, yes, but for the most part the algorithms can work in any language:

Chapters 17 and 18 of Michael Abrash's Graphics Programmer's Black Book are one of the most interesting reads I have ever had. It is a lesson in thinking outside the box. The whole book is great really, but the final optimized solutions to the Game of Life are incredible bits of programming.

Answer 2

There are some super-fast implementations that (from memory) represent cells of 8 or more adjacent squares as bit patterns and use that as an index into a large array of precalculated values to determine in a single machine instruction if a cell is live or dead.

Check out here:

http://dotat.at/prog/life/life.html

Also XLife:

http://linux.maruhn.com/sec/xlife.html