Bit-Packed Conway's Game of Life in GLSL

Evaluating Conway's Game of Life using bit-packed integers in GLSL accelerates simulation performance by representing individual cell states as single bits within integer types such as uint. Instead of executing one shader invocation per cell, a single thread updates 32 horizontal cells simultaneously using parallel bitwise logic, full-adder arithmetic, and bit shifts. This approach drastically minimizes texture memory bandwidth, bypasses per-cell branching, and maximizes GPU arithmetic throughput.

Memory Representation and Word Layout

In a standard floating-point or byte-per-cell implementation, a 2D texture allocates 8 to 32 bits per cell. In a bit-packed implementation, an R32UI texture format is used where each 32-bit unsigned integer (uint) holds a contiguous row of 32 binary cells. A live cell is represented by 1 and a dead cell by 0.

To evaluate a row, a fragment or compute shader fetches the target word along with its neighboring words:

  • The current 32-cell word: \(C\)
  • The words directly to the left and right: \(W\) and \(E\)
  • The corresponding words in the row above: \(N\), \(NW\), and \(NE\)
  • The corresponding words in the row below: \(S\), \(SW\), and \(SE\)

Boundary Alignment and Bit Shifting

Calculating the neighbors of all 32 cells requires horizontal alignments across word boundaries. Within the central word \(C\), a cell's left neighbor corresponds to a right bit-shift (C >> 1u), and its right neighbor corresponds to a left bit-shift (C << 1u).

Because bits shift off the edges, the boundary bits must be restored using the adjacent words \(W\) and \(E\):

// Horizontal neighbors for the current row
uint left_C  = (C >> 1u) | (W << 31u);
uint right_C = (C << 1u) | (E >> 31u);

// Horizontal neighbors for the northern row
uint left_N  = (N >> 1u) | (NW << 31u);
uint right_N = (N << 1u) | (NE >> 31u);

// Horizontal neighbors for the southern row
uint left_S  = (S >> 1u) | (SW << 31u);
uint right_S = (S << 1u) | (SE >> 31u);

This yields eight 32-bit masks representing the states of all eight neighbors (\(N\), \(S\), \(left\_C\), \(right\_C\), \(left\_N\), \(right\_N\), \(left\_S\), \(right\_S\)) corresponding precisely to the 32 cell positions in \(C\).

Parallel Bitwise Addition (Bit-Slicing)

A cell can have between 0 and 8 active neighbors, requiring a 4-bit accumulator (\(b_3, b_2, b_1, b_0\)) to count neighbors across all 32 cells simultaneously. Performing regular integer addition (+) would cause carries to bleed into neighboring cell positions. Instead, the addition is implemented using bitwise boolean logic gates representing half-adders and full-adders.

A half-adder combines a bit \(A\) and a running total \(S\), updating the sum bit and producing a carry \(C\):

\[\text{Sum} = A \oplus S\] \[\text{Carry} = A \land S\]

A full-adder combines an input bit \(A\) with an existing sum bit \(S\) and an incoming carry bit \(C_{in}\), producing a new sum bit and an outgoing carry \(C_{out}\):

\[\text{Sum} = A \oplus S \oplus C_{in}\] \[C_{out} = (A \land S) \lor (C_{in} \land (A \oplus S))\]

By chaining these logic operations across four 32-bit registers (\(b_0, b_1, b_2, b_3\)), the shader tallies the eight neighbor masks into a 4-bit parallel vertical counter without any bit bleeding.

State Transition Logic

Conway’s Game of Life rules state:

  1. Any live cell with 2 or 3 live neighbors survives.
  2. Any dead cell with exactly 3 live neighbors becomes a live cell.
  3. All other live cells die, and all other dead cells stay dead.

Expressed in terms of the neighbor count: \[\text{Next State} = (\text{Count} == 3) \lor (\text{Alive} \land (\text{Count} == 2))\]

Because neighbor counts are held in the bit-slice planes \(b_3, b_2, b_1, b_0\), conditions for counts of 2 and 3 are extracted using bitwise operations:

  • Count is 2 (Binary 0010): \(\sim b_3 \land \sim b_2 \land b_1 \land \sim b_0\)
  • Count is 3 (Binary 0011): \(\sim b_3 \land \sim b_2 \land b_1 \land b_0\)

Factoring these terms allows the evaluation to be simplified:

// Common factor: no 8s, no 4s, and has a 2
uint count2_or_3 = ~b3 & ~b2 & b1;

uint count2 = count2_or_3 & ~b0;
uint count3 = count2_or_3 &  b0;

// Apply Game of Life rule
uint next_C = count3 | (C & count2);

The resulting next_C integer contains the updated states of all 32 cells and is written directly to the target output texture or buffer in a single write operation.