[Haskell-cafe] Game of life in haskell.

[Tony Finch]

On Tue, 2 Feb 2010, Serguey Zefirov wrote:
>
> Creation of new Array is (without knowing some subtle details) is
> O(max coordinates difference between live cells). Creation of new Set
> (X,Y) is O(NlogN) (N = number of live objects). Most of the cells in
> Life are empty, so the Set/Map approach is faster. Also it leads to
> very concise code.

I have a small and relatively quick Life algorithm that's based on lists,
so it should translato to Haskell quite nicely.

The basic representation of the Life universe is a sorted list of the
co-ordinates of live cells. You can compute a new generation in one scan
of the list, or rather a kind of zip3 that scans a 3x3 box along three
adjacent rows, skipping empty space. It's much faster if, instead of
storing one live cell in each list element, you store a small word-sized
bitmap. You can then use SIMD-within-a-register to combine the three rows
of cells and emit a new bitmap if it is non-zero.

Have a look at http://dotat.at/prog/life/life.html for the story of how I
developed the algorithm, including C source (about 40 lines of code).
I've written a couple of other articles about SWAR techniques for Life:
http://fanf.livejournal.com/81169.html
http://fanf.livejournal.com/93032.html

Getting the bits onto the screen quickly is the hardest part :-)

Tony.
-- 
f.anthony.n.finch  <dot at dotat.at>  http://dotat.at/
GERMAN BIGHT HUMBER: SOUTHWEST 5 TO 7. MODERATE OR ROUGH. SQUALLY SHOWERS.
MODERATE OR GOOD.