EagleCell

EagleCell is an Android app that uses the graphics framebuffer to run the Game of Life on the graphics chip directly. Using OpenGL fragment shaders and vertex shaders, it is possible to render to textures and count surrounding “cells” (pixels) and update a step in the Game of Life completely within OpenGL itself.

Shader performance is dependent on many things, and on mobile devices it is even more fickle. One way to immediately speed up shaders is to not have any branches. If your shaders do not have any if statements, they will typically run faster.

float evolve1(float count, float center) {
  if (count == 3.0 || (count == 2.0 && center == 1.0)) {
    return 1.0;
  } else {
    return 0.0;
  }
}

float evolve2(float count, float center) {
  return step(3.4, -(count*count) + 5.5*count - 4.0 + center);
}

float evolve3(float count, float center) {
  return step(0.97, sin(0.6 * count) + 0.1 * center);
}

float evolve4(float count, float center) {
  return step(7.4, count * (5.5 - count) + center);
}

The evolve1 function above is an implementation of the Game of Life update rule. If a cell is dead, then it will become alive if it has exactly 3 live neighbors. Otherwise, it stays dead. If a cell is alive, it will die if it has fewer than 2 or more than 3 neighbors. If it has exactly 2 or 3 neighbors, then it stays alive. But it has branches! I wanted to see if it was possible to write a version of the function without branches. This turned out to be code golf at its finest and did not result in so much speedup (though it did help), but I am still proud of this code.

The built-in step function is key. For values step(edge, x), it returns 0 for x < edge, and 1 otherwise. The trick then is to use count and center in such a way that too small values return 0 and too large values return 0. Only the proper values in the sweet spot return 1. And I wanted to try to only have one call to a function like step. The idea is to have a curve that goes up and then down (unimodal), with the proper values above and below the edge of the step function. Quadratic expressions like \(-x^2 + 10\) give a nice up-and-down curve. Sine curves also have an up-and-down curve.

And then I sat down and worked. I kept multiple versions of the evolve function as a record of my thought process. I was trying to create the smallest expression possible for computing the function. Check it out! evolve4 is completely inscrutable, but for the proper range of inputs, it computes the same function as evolve1. Until the OpenGL shader language comes with a built-in evolve function for the Game of Life, I think that I’m done with this.

EagleCell is open source!