Creative Tinkering


WebGL Conway’s game of life on 1024×1024 world
Go To Demo

Conway’s game of life falls into the category of simple algorithm that has complex results. I is really a legendary programming / math concept that is still relevant today. So naturally, the time has come to initiate myself with creating an implementation of the algorithm.

In short the algorithm works like this:


"For each cell in the world:"
"	count adjecent live cells"
"	if current cell is alive:"
"		if adjecent live cells count is not equal to 2 or 3:"
"			kill the cell"
"	if current cell is dead:"
"		if adjecent live cells count is exactly 3:"
"			make the cell alive"

Depending on the starting conditions this simple algorthm iterated N times can produce intricate and awesome formations and processions of live cells. The difficulty with visualizing this algorithm in real-time (60fps) lies in optimised implementation.

As it is with most things, the most straightforward way to implement the game of life is with utilising Bitmap structure. The “world” consists of all the pixels of a given bitmap and the color pixels determines if the pixel are “dead” or “alive”.

0
1
0

0
0
0

1
0
0

The main hurdle when creating a realtime iteration of the game of life, is the performance. For example if we create a world that has 1024 x 1024 pixels, the program would have to iterate through and count neighbours 1048576 times per frame and desireably do that at least 60 times per second. At lower world sizes(64×64) modern CPUs don’t have any problem with running this at 60 frames per second but as the world size increases the processing time increases exponentially.

Cure for performance woes is moving the procesing to GPU instead of CPU. On a gpu it is rather trivial to process 1024×1024 bitmap with such a simple algorithm. But if GPU processing is so fast and great everybody would be doing it. The difficulty with implementing even as simple an algorithm as the game of life, comes from the fact that creating programs that run on GPU is not as straight forward as creating for CPU. This is especially true for WebGL as it uses OpenGL 1.0 / OpenGL 2.0 equivalent API which do not have native methods for GPU Compute.

As WebGL does not have a read-write buffer type ( RWStructuredBuffer in DX10 for example ) we have to hack a workaround. Most common method is to setup a render-to-texture framework which applies given GLSL shader to each pixel of our world and outputs the result as a texture map. (In a way it is very similar to how more modern GPU Compute programs work.)

To illustrate the structure would look something like this:


	// 1:
	// setup renderTarget
    // 2:
    // create shader program in a way that
    // it works in a pixel coordinate system rather than
    // normalized UV as normal.
    // 3:
    // render a scene with given shader program applied on a simple Quad plane
    // 4:
    // optionally render another scene which will actually be visible

The above flow would be useless without actual samples so here is the code from my implementation using ThreeJS as base:



/* this will be used to switch render targets every frame
 * because webgl complains if a buffer is simultaneously used
 * for reading and writing data
 */
var currentTarget = 0;

/* create two renderTargets with the size of the world */
var comp_target0 = new THREE.WebGLRenderTarget(comp_width,
		comp_height, {
		magFilter:THREE.NearestFilter,
		minFilter:THREE.NearestFilter,
		wrapS:THREE.RepeatWrapping,
		wrapT:THREE.RepeatWrapping
});

var comp_target1 = new THREE.WebGLRenderTarget(comp_width, comp_height, {
        magFilter:THREE.NearestFilter,
        minFilter:THREE.NearestFilter,
        wrapS:THREE.RepeatWrapping,
        wrapT:THREE.RepeatWrapping
});
/* create a scene with single quad mesh */
var comp_scene = new THREE.Scene();
var comp_camera = new THREE.OrthographicCamera(-0.5,0.5,0.5,-0.5, 0.1,10);
comp_camera.position.set(0,0,5);
      
/* material which uses the Shader code to Compute
 * rather than render lighting and other normal things
 */
var comp_material = new THREE.ShaderMaterial({
        uniforms:{
          R:{value:0},
          time:{value:0},
          res:{ value:[comp_width,comp_height] },
          map:{value:comp_target1},
          pattern:{value:patterns[0]},
          addRandom:{value:0},
          firstFrame:{value:0}
        },
        vertexShader:document.getElementById('compute_vertex').innerHTML,
        fragmentShader:document.getElementById('compute_fragment').innerHTML
});
var comp_mesh = new THREE.Mesh( new THREE.PlaneGeometry(1,1,1,1), comp_material );
comp_scene.add(comp_mesh);

// in the render loop the "compute scene" will be rendered
// before the actual visual scene

/* render compute scene
 * and choose alternate render target as target
 * on each frame
 */

if(currentTarget == 0){
	comp_material.uniforms.map.value = comp_target1.texture;
	comp_material.needsUpdate = true;
	renderer.render(comp_scene, comp_camera, comp_target0, false);
	currentTarget = 1;
}

if(currentTarget == 1){
	comp_material.uniforms.map.value = comp_target0.texture;
	comp_material.needsUpdate = true;
	renderer.render(comp_scene, comp_camera, comp_target1, false);
	currentTarget = 0;
}

/* render visual scene which uses previous render target in a scene
 * as texture map on mesh
 */
 
renderer.render(scene, camera);

Once the “GPU Compute” framework is setup and running. The next step is to work on the GLSL fragment shader that will actually direct the computing.

GLSL uses normalized float data type for texture sampling, so a pixel with a value : (255,128,0,255) becomes ( 1.0, 0.5, 0.0, 1.0 ) when sampled in a fragment shader. This means that it is good to adopt a mindset of ‘analoque’ programming.

Instead of concidering pixels as exact values we can think of them as “high” or “low” with a float value of either greater or less than 0.5. In my shader I have used a “low” value as a “dead” pixel and “high” value as “alive”. Of course this method leaves a lot of data precision potential totally unused, but in a case of the Game of Life there is not much data or precision needed and WebGL cannot use 1-bit texture maps for some reason.

I’ll just dump my fragment shader here and lets take it apart below:


      uniform float time;
      uniform float R;
      uniform vec2 res;
      uniform sampler2D map;
      uniform sampler2D pattern;
      uniform int addRandom;
      uniform int firstFrame;
      varying vec2 vUv;
      
      float rand(vec2 co){
        return fract(sin(dot(co.xy ,vec2(12.9898,78.233))) * 43758.5453);
      }
      
      vec4 getNeighbour( vec2 uv, vec2 offset, sampler2D map ){
        vec2 puv = uv + (offset / res);
        vec4 result = texture2D( map, puv );
        return result;
      }
      
      void main(){
        vec4 tex = texture2D( map, vUv );
        float cell = tex.x;
        float cellAge = tex.y;
        
        
        
        if(firstFrame == 0){
          int numAdjecent = 0;
          for(int ix = -1; ix <= 1; ix++){
            for(int iy = -1; iy <= 1; iy++){
              if(!(ix == 0 && iy == 0)){
                vec4 adjecentCell = getNeighbour( vUv, vec2(  float(ix),float(iy)), map );
                if(adjecentCell.x > 0.5){
                  numAdjecent += 1;
                }
              }
            }
          }
          if(cell > 0.5){
            if(numAdjecent > 3 || numAdjecent < 2){
              cell = 0.0;
              cellAge = 0.0;
            }else{
              cell = 1.0;
              cellAge += 1.0/255.0;
            }
          }
          if(cell < 0.5){ if(numAdjecent == 3){ cell = 1.0; cellAge = 0.0; } }
          
        }
        
        vec2 randomOffset = vec2(
          rand(vec2(time*0.0984,time)*time*0.984 + R),
          rand(vec2(time*0.65,time)*time*0.684 + R)
        );
        cell = max( cell, texture2D(pattern, vUv * res/8.0 - randomOffset*res/8.0).x);
        
        //if(addRandom == 1){
        //cell = max(cell, texture2D(pattern, (vUv * res) / 4.0 ).a);
        //}
        
        gl_FragColor = vec4(cell,cellAge,0.0,1.0);

The first vital thing to do is to create a pixel space coordinate system. This can be done quite easily if we have a uniform variable of the resolution of the texture that needs to be sampled. So when the input UV for given fragment is vec2(0.4, 0.2) the corresponding pixel coordinate would attained by this:


	uniform vec2 resolution; // for example vec2( 1024.0, 1024.0 );
    varying vec2 uv; // normalized coordinate in range of vec2(0.0,0.0) - vec2(1.0,1.0);
    
    example:
    	// get pixel coordinate from normalized uv
    	uv = vec2(0.1,0.5);
        pixelCoordinate = floor(uv * resolution);
        // get normalized uv coordinate from pixel coordinate
        pixelCoordinate = vec2( 213.0, 651.0 );
        uv = pixelCoordinate / resolution;

As the algorithm requires the counting of neighbouring pixels it we have to create a function to do just that. Here is where the previous example of pixel - uv coordinate conversions become in handy.


    // function from the shader to get pixels with certain offset from current uv coordinate
    vec4 getNeighbour( vec2 uv, vec2 offset, sampler2D map ){
        vec2 puv = uv + (offset / res);
        vec4 result = texture2D( map, puv );
        return result;
    }
    
    // the above is used like this to count the "living" cells around current cell
    int numAdjecent = 0;
    for(int ix = -1; ix <= 1; ix++){
    	for(int iy = -1; iy <= 1; iy++){
        	if(!(ix == 0 && iy == 0)){
                vec4 adjecentCell = getNeighbour( vUv, vec2(  float(ix),float(iy)), map );
                if(adjecentCell.x > 0.5){
                  numAdjecent += 1;
                }
            }
        }
    }

After we know how many adjecent living cells there are we can apply the final part of the algorithm.


// float cell = current sampled pixel's R component
// float cellAge = current sampled pixel's G component
if(cell > 0.5){
	// current cell is alive
	if(numAdjecent > 3 || numAdjecent < 2){
    	// cell dies if it has more than 3 adjecent living cells
        // or if it has less than 2 adjecent living cells
		cell = 0.0;
		cellAge = 0.0;
	}else{
    	// if cell has exactly 2 or 3 adjecent living cells
        // it survives
		cell = 1.0;
		cellAge += 0.01;
	}
}
if(cell < 0.5){
	// current cell is dead
	if(numAdjecent == 3){
    	// if the cell has exactly 3 adjecent living cells
        // the cell will become alive
    	cell = 1.0; cellAge = 0.0; 
		} 
	}
}

At this point we have everything to make the game of life algorithm work on any given input bitmap data. The next step to set data in the bitmap at random to create a consistent flow of graphics ( a kin to adding energy to closed system ).

Setting a patch of pixels with certain pattern is supprisingly harder than one might think. Glsl operates only one pixel at any given time, so it is not possible to simply set a number of adjecent pixels as well, even more: the notion of pixel unit does not exist in glsl shader. The solution for this problem has to be achieved by using inputs that are constant over all pixels of the bitmap world.

given constants for all fragments in this shader are:

uniform float time;
uniform float R;
uniform vec2 res;
uniform sampler2D map;
uniform sampler2D pattern;
uniform int addRandom;
uniform int firstFrame;

per fragment variable is:

varying vec2 vUv;

It is not enough to simply set random pixels alive at every frame. It is more interesting to add known patterns shown below.

So in order to insert a bitmap into the world bitmap in GLSL shader we need to caculate an UV coordinate for the pattern bitmap so that it will match the pixels in the world bitmap.


cell = max( cell, texture2D(pattern, vUv * res/8.0 - randomOffset*res/8.0).x);

This took a bit of trial and error but as it can be seen, the patterns uv has to be sized (multiplied) with certain values depending on the pixel size of the pattern bitmap. In this case my pattern bitmap is 8x8. Then the random offset is also added to "stamp" the pattern on random positions on the world bitmap.

The only thing is to pass a pattern bitmap to the uniform variable of the sader now.


    // library of patterns
    // 8x8 textures holding 
	var patterns = [
        new THREE.DataTexture(
          new Uint8Array([
              0,  0,  0,  0,  0,  0,  0,  0,
              0,  0,255,  0,  0,  0,  0,  0,
              0,255,  0,255,  0,  0,  0,  0,
              0,  0,255,  0,  0,  0,  0,  0,
              0,  0,  0,  0,  0,  0,  0,  0,
              0,  0,  0,  0,  0,  0,  0,  0,
              0,  0,  0,  0,  0,  0,  0,  0,
              0,  0,  0,  0,  0,  0,  0,  0
          ]),
          8,
          8,
          THREE.LuminanceFormat,
          THREE.UnsignedByteType,
          THREE.UVMapping,
          THREE.ClampToEdgeWrapping,
          THREE.ClampToEdgeWrapping,
          THREE.NearestFilter,
          THREE.NearestFilter
        ),
    ...

In the long run it would be better to format the patterns to a single atlas texture and then create another UV offset to choose patterns from that atlas. But for the time being this array of datatextures will do.


WebGL Conway's game of life on 256x256 world
Go To Demo

Leave a Reply

Your email address will not be published. Required fields are marked *