Posted on Sun 11 March 2012

LifeSaver - Game of Life as Screensaver

Recently, I promised you that I'd write my own screensaver. Well, here it is - an implementation of [cached]Conway's Game of Life using [cached]xscreensaver and OpenGL. It's based on the Python implementation I wrote, but quite a bit faster thanks to some trickery. Here's how it looks like:

Screenshot of the Screensaver

Since I need to blit a lot of pixels for each frame (all changed cells + all those that died recently and are fading away), I decided to use an OpenGL texture for drawing. That way, my dense array gets painted directly to the screen. To avoid unecessary copying, I've interleaved the game state with the texture data.

The texture itself is a one-dimensional array of unsigned int (one byte for RGBA each), but I add additional pointers so I can use it like a normal 2D-Array. height-first (y-first) is important so OpenGL draws correctly.

/* to allow faster calculation, we have 1 char padding around
 * our world, so we need to add that here */
int i;
unsigned int **world = calloc(height+2, sizeof(int *));
/* calloc will set all bits to 0 */
world[0] = calloc((length+2) * (height+2), sizeof(int));

for(i = 1; i < height+2; i++)
  world[i] = world[0] + i * length;

return world;

Now I don't really need an Alpha channel, and so I have space to store my game state information:

| MSB                                                                             LSB |
| 4 bits alive status | 4 bits neighbor status | 8 bit blue | 8 bit green | 8 bit red |

What's with the 4 bits for alive and neighbor status each? To speed up calculation of the next generation, I don't check for alive neighbors for each cell, but rather save in the cell itself how many of its neighbors are alife. This cached value only needs to change when one of the neighbors dies / is born, which doesn't happen very often.

The alive status would only need 1 bit, but I use 4 for animation, so I can fade out newly deceased cells over a few frames. All 4 bits one is alive (0xf), everything else is dead and also an index into my color array. This status is also used when updating cells - we don't need to check if an already alive cell will start to live, and vice versa:

/* bit twiddling to get alive state and neighbor count */
int state = bp->old_world[y][x] >> 24;
int alive_count = state & 0x0f;
int cell_alive = state >> 4;

if(alive(bp->old_world[y][x])) {
  /* cell alive - turn off if not enough neighbors */
  if((alive_count > R[2] || alive_count < R[3]))
    set_cell(x, y, 0, mi);
else {
  /* cell dead - turn on if correct neighbors */
  if(alive_count >= R[0] && alive_count <= R[1])
    set_cell(x, y, 1, mi);
  /* animation of newly deceased cells */
  else if(cell_alive > 1) {
    bp->world[y][x] -= ONE_LIFE;
    bp->world[y][x] &= 0xff000000;
    bp->world[y][x] += DEAD_COLOR[16-cell_alive];
  /* completely clear out cells after they reach the end of animation
   * so we don't animate them again */
  else if(cell_alive == 1)
    bp->world[y][x] &= 0x0f000000;

Maybe you've also noticed the comment about padding in the very first source snippet - this is purely so we don't need any modulo operations when setting alive/dead status in our neighbors.

As always, [cached]the source is on GitHub, check it out and play with it!

Tags: programming, graphics

© Julian Schrittwieser. Built using Pelican. Theme by Giulio Fidente on github. .