BitLife - A Bitwise Stack of Life Games

See the SF project page for the standard things, mainly downloads.

Contents

News

2005-03-20 - Release 0.9.5

Python version:
  • License change: the Python part is now under the GNU Lesser General Public License (LGPL).

    It was previuosly under the GNU General Public License (GPL). This change can be only good for users as LGPL is more relaxed. I changed it because:

    • Nobody really knew whether importing a Python module is linking under the GPL.
    • I don't feel that requiring people to use GPL only because they import my module makes any sense.

    I also clarified the license section to say which directories have which license and made this common document dual-licensed.

X version:
  • Minor changes to compile against xscreensaver-4.20; no other visible changes.

2004-01-10 - Release 0.9.4

X version:
  • Minor changes to compile against xscreensaver-4.14; no other visible changes.

2003-04-25 - Release 0.9.3

X version:
  • Minor changes to compile against xscreensaver-4.09; no other visible changes.

2003-02-12 - Release 0.9.2

Python version:
  • Fixed bug in connections of cube sides. Now the neighbors are correct across edges.
X version:
  • Intelligent colormap support.
  • Integration with xscreensaver-demo gui configurator.
  • Initial man page.
  • Other tiny twiddling.

What is it?

It's a simple idea: implement Conway's Game of Life using boolean logic operations (and, or, not, xor); do so by blits, thus running a Life game in every bitplane in parallel.

Currently 2 implementations are available: a proof-of-concept (with a life-covered 3d cube!) one in Python (with Numeric/pygame) and a useful one in C (X-Windows screensaver, potentially accelerated).

If you understood all this skip directly to the Installation or the Algorithm description.

Screen Shots

2D python version screenshot:

screen2d-1.png

3D python version screenshot:

screen3d-1.png

Reminder: Conway's Life

Life runs on (ideally) infinite rectangular grid. A generation is defined by the value (alive or dead, 0 or 1) of each cell of the grid. Given a generation n the rules tell you how to produce the next generation n+1.

The state of a given cell in generation n+1 depends only on the states of this cell and it's 8 neighbors in generation n. More precisely it only depends on it's own previous state and the number of neighbors that were alive:

0, 1
The cell becomes dead, no matter the previous state ("death from loneliness").
2
The cell stays as it was.
3
The cell becomes alive, no matter the previous state ("birth").
4-8
The cell becomes dead, no matter the previous state ("death from overcrowding").

Why is this good/interesting?

The next state of a cell is a function of 9 bits. Doing boolean operations on 2-D arrays of bits is supported by most graphics libraries (they call it blitting) and is very optimized (frequently it is accelerated in hardware). The operation is done in parallel on all pixels: corresponding pixels in two images are combined according to some boolean operation. If I take an image representing a generation and also take 8 views on it that are offset by one pixel in each direction (easily supported by all graphics platforms), I can then combine them by blits to generate the image of the next generation.

This is interesting because it is very fast and can even be done mostly on the graphic co-processors without loading the CPU. This is very good for a screensaver.

Blits are actually typically done on 3-D arrays, where the third dimension is the depth of the image - the 8, 16, 24, etc. bits that one needs to represent each pixel's color. The high bit of a pixel in one image is combined with the high bit of the corresponding pixel in the second image, etc. Thus if I only do blits, no information is exchanged between the bitplanes. Parallel Life games will run in each bitplane.

This gives an interesting visual effect: many life games superimposed translucently, each with a different color/brightness (recall that bit k in a binary number contributes (2 to power k) to the number's value, linearly and independently of the other bits). On a True-Color display you will see 8 red lives, 8 blue ones and 8 green ones. Actually you will have hard time seeing all but the ~3 higher bits of each color (unless they stop changing, then the lower planes become visible) because the power-of-2 law results in very strong masking by the highest bits...

If you don't have a TrueColor display, it can be simulated (and even very flexibly, e.g. with other colors, slower than powers-of-2 value decay, etc.) by suitably changing the colormap (a.k.a. palette). So even on TrueColor displays, choosing a DirectColor visual might be better... Note: currently, the colors of the original image are distorted when applying the pallete change.

License

The Python version (everything under python/) is distributed under the GNU LGPL (other LGPL formats).

The xsreensaver hack (everything under xscreensaver/) is distributed under same X11-like licence as rest of xscreensaver:

Permission to use, copy, modify, distribute, and sell this software and its documentation for any purpose is hereby granted without fee, provided that the above copyright notice appear in all copies and that both that copyright notice and this permission notice appear in supporting documentation. No representations are made about the suitability of this software for any purpose. It is provided "as is" without express or implied warranty.

Files in this directory (presently - this README document and screenshots) are dual-licensed under both LGPL and the X11-like license: you can use them under either of the licenses at your choice.

Installation

The python version requires Python 2.2 (at least) and the Numeric and Pygame extensions. Be sure to build/get the surfarray optional component of Pygame for interfacing with Numeric! Note that the newer Numarray replacement for Numeric is not supported by Pygame (correct me if I'm wrong), so you should get the numpy module on the Numeric download page.

The pygame2d.py, pygame3d.py files should run out of the box (bitlife.py is the module used by them). See source for more options and keys (in particular try the arrows with the 3d version; 'q' for exit).

The C version is intended to integrate into xscreensaver (and hopefully will in the future). You first need to get xscreensaver source distribution. This version of bitlife was slightly changed to work against 4.09. bitlife-0.9.2 worked well with older versions (tested with 4.07); there are no other differences, so choose according to your xscreensaver version (but the new "flyingtoasters" screeenhack in 4.09 is worth the upgrade anyway ;-).

Assuming you unpacked both under your home directory, resulting in ~/bitlife-0.9.5 and ~/xscreensaver-4.20:

cd ~/xscreensaver-4.20/
patch -p 0 < ~/bitlife-0.9.5/xscreensaver/patch
cp -rv ~/bitlife-0.9.5/xscreensaver/hacks .
./configure
make -C hacks bitlife               # check our part early
hacks/bitlife                       # test it...
make                                # compile everything else
sudo make install                   # will install all of xscreensaver!

If the Makefile.in patch doesn't apply cleanly, you can do it by hand (it's very simple); you can also make the changes directly to Makefile if you prefer.

If you want to debug (or understand the workings), add -DDEBUG to CFLAGS at top of Makefile. It will be particularly verbose about colormap manipualtion; when running it will denote blit operations by somewhat cryptic one-two letters - read the code (search for dprintf) to understand it.

Algorithm

[C notation: & is and, | is or, ^ is xor, a&=b means take a&b and store back into a...]

There are 2 demands on the algorithm: high speed and low number of intermediate arrays. The later is important if we have hardware blits and hope to fit all the arrays into video memory.

The costly operation is counting the neighbors (done 8 times). Note that it's enough to saturate the counting at 4 (all values >=4 have same result). So the counters need 5 distinct states.

The brute-force approach is to count in binary. We need 3 bits for the counter itself. Then we need at least one bit for the carry (we can get away with computing the second carry directly into bit 2; it helps to store bit 2 reversed):

carry1 = input
carry1 &= bit0
bit0 ^= input
carry1 &= bit2not   # protect bit 2 once it is "on" (0)
bit1 ^= carry1
bit2not ^= bit1
bit2not ^= carry1

Thus we would need 7 operations.

The simpler approach I implemented is a shift register of 4 bits that starts full of zeros and a 1 is shifted in every time the input is 1. It's easy to see that it has 5 states, locking into the last one. The interesting part is that the shifting process can be done without extra bits if performed starting from the MSB:

bit[i+1] |= input
bit[i+1] &= bit[i]

The LSB doesn't need the and, so we need 7 operations again. I chose it since it is simpler to think about, uses only two operations and satisfies a nice property: bit[i+1] => bit[i].

Some additional simplifications can be applied to both methods, notably instead of clearing the arrays each iteration, one replaces the operations involving them -- for example or-ing onto something that is intended to be zero, just copy into it...

The search for faster ways is not over. In particular I didn't try blits from the life array onto itself (this might be able to parallelize things that are impossible under the counting approach).

Another possible direction is using lookup table (LUT) operation as the main "engine", rather than blits with logical operation. If you combine / interleave bits of different operands into one image, you can effectively compute logic functions of serveral operands by a LUT. Particularly, the counting could be done in one lookup! I'm not sure what platforms / libraries provide access to accelerated LUT operations, however.


Hosted by SourceForge:

SourceForge.net Logo