# Game of Life on the GPU

> An advanced pass computes Game of Life: compute on WebGPU and fragment shaders on WebGL2. R resets both halves; drag to paint cells.

Example `gpu-pass`, running at https://nacatamalon.com/en/examples/gpu-pass. The whole catalogue: https://nacatamalon.com/llms/examples.md.

An advanced pass computes Game of Life: compute on WebGPU and fragment shaders on WebGL2. R resets both halves; drag to paint cells.

## Code

`index.ts`:

```ts
import { createGame } from 'nacatamalon';
import { Life } from './scenes/life';
import { CELLS_X, CELLS_Y, CELL } from './settings';

// Both games deliberately share one brush, so painting either side paints the same cells.
const brush = {
    x: -100,
    y: -100,
    down: false,
    over: ''
};

// The same game twice, on each backend, with the same rules. WebGPU takes longer to start, so at
// first the two are a few generations apart. R sows the same board on both in the same frame, and
// from then on the two halves are the same picture, cell for cell.
const root = document.querySelector<HTMLElement>('#app');

if (root === null) {
    throw new Error('There is no #app to put the two canvases in.');
}

root.style.cssText = 'display:grid;grid-template-columns:1fr 1fr;gap:8px';

const side = (renderer: 'WEBGPU' | 'WEBGL2', note: string): void => {
    const wrap = document.createElement('div');

    wrap.style.cssText = 'display:flex;flex-direction:column;gap:4px;min-width:0';

    const tag = document.createElement('div');

    tag.textContent = renderer + '  ·  ' + note;
    tag.style.cssText = 'font:11px ui-monospace,monospace;color:#8ee6a0;letter-spacing:.08em';

    const host = document.createElement('div');

    wrap.append(tag, host);
    root.appendChild(wrap);

    if (renderer === 'WEBGPU' && !('gpu' in navigator)) {
        tag.textContent = renderer + '  ·  unavailable here';
        tag.style.color = '#e0663c';
        host.style.cssText = 'height:228px;display:grid;place-items:center;border:1px dashed #3a3f4b;' +
            'color:#6b7280;font:12px ui-monospace,monospace';
        host.textContent = 'this browser has no WebGPU';

        return;
    }

    const game = createGame(host, {
        width: CELLS_X * CELL,
        height: CELLS_Y * CELL,
        background: '#0a0a12',
        renderer
    });

    // Declare Scenes
    game({
        Game: Life(renderer, brush)
    });
};

side('WEBGPU', 'compute');
side('WEBGL2', 'fragment shader');
```

`backends/webgl2.ts`:

```ts
import type { TWebGl2PassContext, TWebGl2Pass } from 'nacatamalon/extend/gpu';
import type { TLifeState } from '../gpu_life';
import { FULL_SCREEN, STEP_GLSL, COLOUR_PASS_GLSL } from '../shaders';

export const createLifeWebgl2 = (context: TWebGl2PassContext, state: TLifeState): TWebGl2Pass => {
    const { gl, outputs } = context;
    const { width, height, brush } = state;

    const compile = (fragment: string) => {
        const program = gl.createProgram()!;

        for (const [type, source] of [[gl.VERTEX_SHADER, FULL_SCREEN], [gl.FRAGMENT_SHADER, fragment]] as const) {
            const shader = gl.createShader(type)!;

            gl.shaderSource(shader, source);
            gl.compileShader(shader);

            if (!gl.getShaderParameter(shader, gl.COMPILE_STATUS)) {
                throw new Error(gl.getShaderInfoLog(shader) ?? 'shader');
            }

            gl.attachShader(program, shader);
            gl.deleteShader(shader);
        }

        gl.linkProgram(program);

        if (!gl.getProgramParameter(program, gl.LINK_STATUS)) {
            throw new Error(gl.getProgramInfoLog(program) ?? 'program');
        }

        return program;
    };

    const step = compile(STEP_GLSL);
    const paint = compile(COLOUR_PASS_GLSL);
    const where = (program: WebGLProgram, name: string) => gl.getUniformLocation(program, name);

    const at = {
        before: where(step, 'before'),
        size: where(step, 'size'),
        brush: where(step, 'brush'),
        painting: where(step, 'painting'),
        seed: where(step, 'seed'),
        sow: where(step, 'sow'),
        board: where(paint, 'board'),
    };

    // Two boards of its own, each a picture with its framebuffer, and one more framebuffer
    // for the pass's own picture.
    const framebufferOf = (texture: WebGLTexture) => {
        const framebuffer = gl.createFramebuffer()!;

        gl.bindFramebuffer(gl.FRAMEBUFFER, framebuffer);
        gl.framebufferTexture2D(gl.FRAMEBUFFER, gl.COLOR_ATTACHMENT0, gl.TEXTURE_2D, texture, 0);

        return framebuffer;
    };

    const boards = [0, 1].map(() => {
        const texture = gl.createTexture()!;

        gl.bindTexture(gl.TEXTURE_2D, texture);
        gl.texImage2D(gl.TEXTURE_2D, 0, gl.RGBA8, width, height, 0, gl.RGBA, gl.UNSIGNED_BYTE, null);
        gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_MIN_FILTER, gl.NEAREST);
        gl.texParameteri(gl.TEXTURE_2D, gl.TEXTURE_MAG_FILTER, gl.NEAREST);

        return {
            texture,
            framebuffer: framebufferOf(texture)
        };
    });

    const shown = framebufferOf(outputs[0]);
    // drawArrays needs a vertex array bound, even with no attributes: this one is its own.
    const vertexArray = gl.createVertexArray()!;
    let turn = 0;

    return {
        render: () => {
            // Everything this draws with is set here: the engine puts its own back afterwards.
            gl.bindVertexArray(vertexArray);
            gl.disable(gl.BLEND);
            gl.disable(gl.DEPTH_TEST);
            gl.disable(gl.STENCIL_TEST);
            gl.disable(gl.SCISSOR_TEST);
            gl.disable(gl.CULL_FACE);
            gl.colorMask(true, true, true, true);
            gl.viewport(0, 0, width, height);
            gl.activeTexture(gl.TEXTURE0);
            gl.bindSampler(0, null);

            const from = boards[turn];
            const into = boards[1 - turn];

            gl.bindFramebuffer(gl.FRAMEBUFFER, into.framebuffer);
            gl.useProgram(step);
            gl.bindTexture(gl.TEXTURE_2D, from.texture);
            gl.uniform1i(at.before, 0);
            gl.uniform2i(at.size, width, height);
            gl.uniform2i(at.brush, brush.x, brush.y);
            gl.uniform1i(at.painting, brush.down ? 1 : 0);
            gl.uniform1ui(at.seed, state.seed);
            gl.uniform1i(at.sow, state.sowing ? 1 : 0);
            gl.drawArrays(gl.TRIANGLES, 0, 3);
            state.sowing = false;

            gl.bindFramebuffer(gl.FRAMEBUFFER, shown);
            gl.useProgram(paint);
            gl.bindTexture(gl.TEXTURE_2D, into.texture);
            gl.uniform1i(at.board, 0);
            gl.drawArrays(gl.TRIANGLES, 0, 3);
            turn = 1 - turn;
        },
        destroy: () => {
            for (const board of boards) {
                gl.deleteFramebuffer(board.framebuffer);
                gl.deleteTexture(board.texture);
            }

            gl.deleteFramebuffer(shown);
            gl.deleteProgram(step);
            gl.deleteProgram(paint);
            gl.deleteVertexArray(vertexArray);
        },
    };
};
```

`backends/webgpu.ts`:

```ts
import type { TWebGpuPassContext, TWebGpuPass } from 'nacatamalon/extend/gpu';
import type { TLifeState } from '../gpu_life';
import { STEP_WGSL } from '../shaders';

export const createLifeWebgpu = (context: TWebGpuPassContext, state: TLifeState): TWebGpuPass => {
    const { device, outputs } = context;
    const { width, height, brush } = state;

    const cells = () => device.createBuffer({
        size: width * height * 4,
        usage: GPUBufferUsage.STORAGE
    });

    const boards = [cells(), cells()];

    const params = device.createBuffer({
        size: 32,
        usage: GPUBufferUsage.UNIFORM | GPUBufferUsage.COPY_DST
    });

    const numbers = new Int32Array(8);

    const pipeline = device.createComputePipeline({
        layout: 'auto',
        compute: {
            module: device.createShaderModule({
                code: STEP_WGSL
            }),
            entryPoint: 'main'
        },
    });

    const picture = outputs[0].createView();

    // From the first board into the second, and back.
    const turns = [0, 1].map((from) => device.createBindGroup({
        layout: pipeline.getBindGroupLayout(0),
        entries: [
            {
                binding: 0,
                resource: {
                    buffer: params
                }
            },
            {
                binding: 1,
                resource: {
                    buffer: boards[from]
                }
            },
            {
                binding: 2,
                resource: {
                    buffer: boards[1 - from]
                }
            },
            {
                binding: 3,
                resource: picture
            },
        ],
    }));

    let turn = 0;

    return {
        render: ({ encoder }) => {
            numbers.set([width, height, brush.x, brush.y, brush.down ? 1 : 0, state.seed, state.sowing ? 1 : 0, 0]);
            device.queue.writeBuffer(params, 0, numbers);
            state.sowing = false;

            const compute = encoder.beginComputePass();

            compute.setPipeline(pipeline);
            compute.setBindGroup(0, turns[turn]);
            compute.dispatchWorkgroups(Math.ceil(width / 8), Math.ceil(height / 8));
            compute.end();
            turn = 1 - turn;
        },
        destroy: () => {
            for (const board of boards) {
                board.destroy();
            }

            params.destroy();
        },
    };
};
```

`components/life_board.ts`:

```ts
import { createSprite, useKeyboard, usePointer, useUpdate } from 'nacatamalon';
import { useGpuLife } from '../gpu_life';
import { CELLS_X, CELLS_Y, CELL } from '../settings';
import type { TLifeState } from '../gpu_life';

export type TSharedBrush = TLifeState['brush'] & {
    over: string
};

export const LifeBoard = (side: string, brush: TSharedBrush) => {
    const life = useGpuLife(CELLS_X, CELLS_Y);

    createSprite({
        texture: life.picture,
        width: CELLS_X * CELL,
        height: CELLS_Y * CELL,
        anchor: {
            x: 0,
            y: 0
        },
    });

    const pointer = usePointer();
    const keys = useKeyboard();

    useUpdate(() => {
        const at = pointer.position();

        if (at !== null) {
            brush.over = side;
            brush.x = Math.floor(at.worldX / CELL);
            brush.y = Math.floor(at.worldY / CELL);
            brush.down = pointer.isDown();
        } else if (brush.over === side) {
            brush.down = false;
        }

        life.brush.x = brush.x;
        life.brush.y = brush.y;
        life.brush.down = brush.down;

        if (keys.justPressed(' ')) {
            life.pass.enabled = !life.pass.enabled;
        }

        if (keys.justPressed('r')) {
            life.sow();
        }
    });
};
```

`gpu_life.ts`:

```ts
import { useGpuPass } from 'nacatamalon/extend/gpu';
import { createLifeWebgpu } from './backends/webgpu';
import { createLifeWebgl2 } from './backends/webgl2';

export type TLifeState = {
    width: number;
    height: number;
    brush: {
        x: number;
        y: number;
        down: boolean
    };
    seed: number;
    sowing: boolean;
};

// The scene receives an ordinary texture and controls. Only the backend factories touch the GPU.
export const useGpuLife = (width: number, height: number) => {
    const state: TLifeState = {
        width,
        height,
        brush: {
            x: -100,
            y: -100,
            down: false
        },
        seed: 1,
        sowing: true,
    };

    const pass = useGpuPass({
        name: 'game of life',
        outputs: [
            {
                width,
                height
            }
        ],
        webgpu: (context) => createLifeWebgpu(context, state),
        webgl2: (context) => createLifeWebgl2(context, state),
    });

    return {
        picture: pass.outputs[0],
        pass,
        brush: state.brush,
        sow: () => {
            state.seed++;
            state.sowing = true;
        },
    };
};
```

`scenes/life.ts`:

```ts
import { createScene, useSpawn } from 'nacatamalon';
import { LifeBoard } from '../components/life_board';
import type { TSharedBrush } from '../components/life_board';

export const Life = (side: string, brush: TSharedBrush) => () => {
    useSpawn(LifeBoard)(side, brush);

    return createScene();
};
```

`settings.ts`:

```ts
export const CELLS_X = 100;
export const CELLS_Y = 76;
export const CELL = 3;
```

`shaders.ts`:

```ts
const COOLING = 24;

// The same hash in both languages, on whole numbers, so both backends sow the very same board.
const HASH_WGSL = `
fn hash(x: u32, y: u32, seed: u32) -> u32 {
    var h = x * 374761393u + y * 668265263u + seed * 2246822519u;
    h = (h ^ (h >> 13u)) * 1274126177u;
    return h ^ (h >> 16u);
}`;

const HASH_GLSL = `
uint hash(uint x, uint y, uint seed) {
    uint h = x * 374761393u + y * 668265263u + seed * 2246822519u;
    h = (h ^ (h >> 13u)) * 1274126177u;
    return h ^ (h >> 16u);
}`;

// The colour of a heat, the same in both: dark when cold, a warm trail as it cools, pale when alive.
const COLOUR_WGSL = `
fn colour(heat: u32) -> vec4<f32> {
    if (heat == 255u) {
        return vec4<f32>(1.0, 0.93, 0.62, 1.0);
    }
    let t = f32(heat) / 255.0;
    return vec4<f32>(mix(vec3<f32>(0.04, 0.04, 0.07), vec3<f32>(0.85, 0.25, 0.45), t), 1.0);
}`;

const COLOUR_GLSL = `
vec4 colour(uint heat) {
    if (heat == 255u) {
        return vec4(1.0, 0.93, 0.62, 1.0);
    }
    float t = float(heat) / 255.0;
    return vec4(mix(vec3(0.04, 0.04, 0.07), vec3(0.85, 0.25, 0.45), t), 1.0);
}`;

export const STEP_WGSL = `
struct Params { size: vec2<u32>, brush: vec2<i32>, painting: u32, seed: u32, sow: u32, unused: u32 };
@group(0) @binding(0) var<uniform> params: Params;
@group(0) @binding(1) var<storage, read> before: array<u32>;
@group(0) @binding(2) var<storage, read_write> after: array<u32>;
@group(0) @binding(3) var picture: texture_storage_2d<rgba8unorm, write>;
` + HASH_WGSL + COLOUR_WGSL + `
fn alive(x: i32, y: i32) -> u32 {
    let w = i32(params.size.x);
    let h = i32(params.size.y);
    let at = ((y + h) % h) * w + (x + w) % w;
    return select(0u, 1u, before[u32(at)] == 255u);
}

@compute @workgroup_size(8, 8)
fn main(@builtin(global_invocation_id) id: vec3<u32>) {
    if (id.x >= params.size.x || id.y >= params.size.y) {
        return;
    }
    let x = i32(id.x);
    let y = i32(id.y);
    var heat = before[id.y * params.size.x + id.x];
    if (params.sow == 1u) {
        heat = select(0u, 255u, hash(id.x, id.y, params.seed) % 4u == 0u);
    } else {
        var around = 0u;
        for (var dy = -1; dy <= 1; dy++) {
            for (var dx = -1; dx <= 1; dx++) {
                if (dx != 0 || dy != 0) {
                    around += alive(x + dx, y + dy);
                }
            }
        }
        let was = heat == 255u;
        if ((was && (around == 2u || around == 3u)) || (!was && around == 3u)) {
            heat = 255u;
        } else {
            heat = heat - min(heat, ` + COOLING + `u);
        }
    }
    let reach = vec2<i32>(x, y) - params.brush;
    if (params.painting == 1u && dot(reach, reach) <= 4) {
        heat = 255u;
    }
    after[id.y * params.size.x + id.x] = heat;
    textureStore(picture, vec2<i32>(id.xy), colour(heat));
}`;

export const FULL_SCREEN = `#version 300 es
// One triangle that covers the whole picture, made from its corner numbers: no buffer needed.
void main() {
    vec2 corner = vec2(float((gl_VertexID << 1) & 2), float(gl_VertexID & 2));
    gl_Position = vec4(corner * 2.0 - 1.0, 0.0, 1.0);
}`;

// gl_FragCoord.y counts the rows as they are stored, and the engine reads the first stored row as
// the top of the picture. So working row by row like this, the WebGL2 board comes out the same way
// up as the WebGPU one without turning anything over. Something drawn with shapes (an arrow
// pointing up, in clip space) would come out upside down, and that pass would turn it over itself.
export const STEP_GLSL = `#version 300 es
precision highp float;
precision highp int;
uniform sampler2D before;
uniform ivec2 size;
uniform ivec2 brush;
uniform int painting;
uniform uint seed;
uniform int sow;
out vec4 state;
` + HASH_GLSL + `
uint heatAt(ivec2 at) {
    return uint(round(texelFetch(before, (at + size) % size, 0).r * 255.0));
}
void main() {
    ivec2 at = ivec2(gl_FragCoord.xy);
    uint heat = heatAt(at);
    if (sow == 1) {
        heat = hash(uint(at.x), uint(at.y), seed) % 4u == 0u ? 255u : 0u;
    } else {
        uint around = 0u;
        for (int dy = -1; dy <= 1; dy++) {
            for (int dx = -1; dx <= 1; dx++) {
                if (dx != 0 || dy != 0) {
                    around += heatAt(at + ivec2(dx, dy)) == 255u ? 1u : 0u;
                }
            }
        }
        bool was = heat == 255u;
        if ((was && (around == 2u || around == 3u)) || (!was && around == 3u)) {
            heat = 255u;
        } else {
            heat = heat - min(heat, ` + COOLING + `u);
        }
    }
    ivec2 reach = at - brush;
    if (painting == 1 && reach.x * reach.x + reach.y * reach.y <= 4) {
        heat = 255u;
    }
    state = vec4(float(heat) / 255.0, 0.0, 0.0, 1.0);
}`;

export const COLOUR_PASS_GLSL = `#version 300 es
precision highp float;
precision highp int;
uniform sampler2D board;
out vec4 shown;
` + COLOUR_GLSL + `
void main() {
    shown = colour(uint(round(texelFetch(board, ivec2(gl_FragCoord.xy), 0).r * 255.0)));
}`;
```