Simulating Life with the Web: Conway's Life Game WebGL

The Chinese Valentine’s Day festival is a good time to discuss the topic of creating life. You may not get a chance to make a multi-billion dollar deal, but with JavaScript, you can conquer a few million pixels on the web — and that’s the subject of our talk, conway’s Game of Life.

The Conway Game of Life is a cellular automaton (remember this concept?) invented by British mathematician John Horton Conway. It can be used to prove the Turing-completeness of CSS. The rules of the game (i.e., the code implementation) are extremely simple, but the “evolutionary” effect can be quite impressive. Thanks to the simplicity of its rules, this article is more of a WebGL tutorial — with a big simplification, of course, based on our own WebGL base library, Beam.

background

The game of life is really just a set of rules for computing on a two-dimensional grid. Suppose there is one cell in each grid, whose survival at the next moment depends on the number of living cells in the eight adjacent grids:

If there are too many living cells around, the cell will die due to lack of resources (vol.
If there are too few living cells around, it will also die because it is too lonely (too few people).
With the right number of living cells around, the grid of dead cells can be transformed into a living state (reproduction).

The implementation of this set of rules is free to play, and Conway’s version is the most classic, but it’s also simple:

If the current cell is alive and the number of living cells around it is 2 or 3, keep it as it is.
If the current cell is alive and the number of surrounding living cells is less than 2, the cell dies.
If the current cell is alive and there are more than three living cells around, the cell dies.
If the current cell dies and there are three living cells around, the cell becomes viable.

With these rules in mind, it is easy to interpret the following periodic states:

More complex is sustainable reproduction. Like this:

But that’s obviously not the most spectacular sight. The effect in this illustration is much more complex than these simple patterns, and we’ll see how to code it later.

So, where do we start? Before you dive into WebGL, it’s a good idea to get your hands dirty with a naive implementation.

Simple implementation

Given only the above rules of the game of life, without limiting the implementation and performance, I believe that many of the authors should be able to write them easily — just use the number[][] two-dimensional array containing 0 or 1 to store the state, and then update it frame by frame:

function update (oldCells) {
  const newCells = []
  for (let i = 0; i < oldCells.length; i++) {
    const row = []
    for (let j = 0; j < oldCells[i].length; j++) {
      const oldCell = get(oldCells, i, j)
      const total = (
        get(oldCells, i - 1, j - 1) +
        get(oldCells, i - 1, j) +
        get(oldCells, i - 1, j + 1) +
        get(oldCells, i, j - 1) +
        get(oldCells, i, j + 1) +
        get(oldCells, i + 1, j - 1) +
        get(oldCells, i + 1, j) +
        get(oldCells, i + 1, j + 1))let newCell = 0
      if (oldCell === 0) {
        if (total === 3) newCell = 1
      }
      else if (total === 2 || total === 3) newCell = 1
      row.push(newCell)
    }
    newCells.push(row)
  }
  return newCells
}
Copy the code

The code above is nothing more than a two-layer for loop, as long as you are careful to avoid possible subscript overruns in the get function. With the new data calculated, it’s easy to render it to the DOM or Canvas, so I won’t go into detail here.

However, this plain implementation is clearly not fit for purpose. As long as 1000×1000 this order of magnitude cell, it means to carry out millions of array access and comparison frame by frame, no matter how to do JS layer “extreme optimization” is difficult to break through the bottleneck. So what do we need? Speed it up, of course! Speed it up!

Accelerate the principle

While WebGL has a lot of complex concepts, most of them come from the specific application scenario of 3D graphics. Aside from these concepts, you can also think of the GPU as an accelerator for a for loop. As long as the tasks in the for loop do not have sequential dependencies (parallelizable), it is easy to drop such tasks onto the GPU to complete the computation.

From this perspective, we can get a straightforward understanding of WebGL:

How do I provide the data that the for loop will iterate over? By providing Textures that are accessible in XY coordinates.
How to determine the range of for loop traversal? By vertex coordinates array (Buffers).
How do you write the specific computational logic in a for loop? Shaders written in GLSL.

Therefore, the thinking model of the rendering process of the life game implemented by WebGL can be understood as follows:

Provide a rectangle (two triangles) that fills the screen as the render range.
Provides a bitmap texture with its initial state as the grid data.
In a shader written in GLSL, each point on the rectangle (called a slice) is sampled for eight surrounding points.
Based on the sampling results, the shader uses simple if-else logic to make a judgment and output the color.

But that’s an oversimplification. There’s one last key problem with WebGL’s render pipeline: If pixels are rendered directly onto the screen, it’s hard to read back to calculate the state of the next frame (gl.readPixels are slow, to be specific). To do this we need to borrow the classic concept of double buffers and render interleaved:

Create two textures of the same size as the render target.
When initialized, thecanvas 或 imgIs uploaded to the first texture.
After entering the main loop, the previous texture is interleaved as input and the shader’s calculation is output to the other texture.

But with this off-screen rendering, the results are invisible to us. Finally, another simple shader is needed to render the updated texture state to the screen frame by frame.

Does that sound interesting? Let’s take a look at how to write this process semantically using Beam.

Beam-based implementation

In “How to Design a WebGL Base Library,” we’ve given a good introduction to the Beam API and corresponding WebGL concepts. In simple terms, the concept model for WebGL rendering using Beam is to call draw with Shader and Resources. Like this:

const beam = new Beam(canvas)
const shader = beam.shader(MyShader)
const resources = [
  // buffers, textures, uniforms...] beam.draw(shader, ... resources)Copy the code

In this case, the Resources passed in for beam.draw include the previously mentioned Buffers and Textures. As an example, let’s start with the simplest requirement: If an IMG tag contains the initial state of the game of Life, how can it be rendered in WebGL? In the Beam Basic Image example, a fairly simple implementation is given:

// The shader used to render the base image
const shader = beam.shader(BasicImage)

// Construct a unit rectangular buffer with width and height of [-1, 1]
const rect = createRect()
const rectBuffers = [
  beam.resource(VertexBuffers, rect.vertex),
  beam.resource(IndexBuffer, rect.index)
]

loadImage(url).then(image= > {
  // Construct and upload the texture
  const textures = beam.resource(Textures)
  // 'img' corresponds to the variable name in the shader
  textures.set('img', { image, flip: true })
  // Execute draw after clearbeam.clear().draw(shader, ... rectBuffers, textures) })Copy the code

The main new concepts in the above code should be VertexBuffers and IndexBuffers. This is also one of the obstacles for beginners, but it simply goes like this: the rectangle has four vertices, and if you split it into two triangles for WebGL, you have six vertices. To avoid data redundancy, we use the VertexBuffer to carry the coordinates of the four vertices, and the IndexBuffer contains a subindex describing “which of the four points corresponds to all six triangle vertices”.

It’s a little convoluted, right? So just log and look at the structure of rect, that should make sense.

With a vertex Buffer, the slice shader executes once for each pixel it covers. In the default BasicImage shader, we sample the img texture at the corresponding position. In this way, the corresponding position of the image is filled with pixels. Since WebGL’s screen coordinate system is also [-1, 1], the effect of the above code is to automatically stretch and display the image, covering the entire Canvas region of WebGL. As for BasicImage, it is a simple shader configuration:

const vertexShader = ` attribute vec4 position; attribute vec2 texCoord; varying highp vec2 vTexCoord; void main() { gl_Position = position; vTexCoord = texCoord; } `

const fragmentShader = ` precision highp float; uniform sampler2D img; varying highp vec2 vTexCoord; void main() { vec4 texColor = texture2D(img, vTexCoord); gl_FragColor = texColor; } `

export const BasicImage = {
  vs: vertexShader,
  fs: fragmentShader,
  buffers: {
    position: { type: vec4, n: 3 },
    texCoord: { type: vec2 }
  },
  textures: {
    img: { type: tex2D }
  }
}
Copy the code

The difference between vertex shaders and chip shaders is explained in the Beam introduction article. All we need to care about here is the slice shader, which is GLSL code like this:

void main() {
  vec4 texColor = texture2D(img, vTexCoord);
  gl_FragColor = texColor;
}
Copy the code

It can be roughly understood as a for loop executed in JS:

function main (img, x, y) {
  PIXEL_COLOR = getColor(img, x, y)
}

for (let texCoordX = 0; texCoordX < width; texCoordX++) {
  for (let texCoordY = 0; texCoordY < height: texCoordY++) {
    main(img, texCoordX, texCoordY)
  }
}
Copy the code

Shader execution on the GPU is completely parallel. By assigning a value to gl_FragColor, you can output the pixels to the screen.

So, once you understand this “for loop to Shader” mapping, it’s easy to implement the simple CPU version of the game of Life in Shader:

uniform sampler2D state;
varying vec2 vTexCoord;
const float size = 1.0 / 2048.0; // Pixel size conversion

void main() {
  float total = 0.0;
  total += texture2D(state, vTexCoord + vec2(1.0.1.0) * size).x > 0.5 ? 1.0 : 0.0;
  total += texture2D(state, vTexCoord + vec2(0.0.1.0) * size).x > 0.5 ? 1.0 : 0.0;
  total += texture2D(state, vTexCoord + vec2(1.0.1.0) * size).x > 0.5 ? 1.0 : 0.0;
  total += texture2D(state, vTexCoord + vec2(1.0.0.0) * size).x > 0.5 ? 1.0 : 0.0;
  total += texture2D(state, vTexCoord + vec2(1.0.0.0) * size).x > 0.5 ? 1.0 : 0.0;
  total += texture2D(state, vTexCoord + vec2(1.0.1.0) * size).x > 0.5 ? 1.0 : 0.0;
  total += texture2D(state, vTexCoord + vec2(0.0.1.0) * size).x > 0.5 ? 1.0 : 0.0;
  total += texture2D(state, vTexCoord + vec2(1.0.1.0) * size).x > 0.5 ? 1.0 : 0.0;

  vec3 old = texture2D(state, vTexCoord).xyz;
  gl_FragColor = vec4(0.0);

  if (old.x == 0.0) {
    if (total == 3.0) {
      gl_FragColor = vec4(1.0); }}else if (total == 2.0 || total == 3.0) {
    gl_FragColor = vec4(1.0); }}Copy the code

Just replace the Beam image rendering example above with this shader and we’ve taken a key step: the first life evolution!

After the first time, how do you achieve a sustainable double happiness? Of course, two pieces of joy (cross out, two buffer zones) overlapped with each other. In native WebGL, this involves a series of operations on the FramebufferObject/RenderbufferObject/ColorAttachment/DepthComponent/Viewport. But Beam greatly simplifies the semantics of this process. In the offscreen2D method that comes with the example, the “render target” can be abstracted from the scope of the function. For example, logic like this:

// Render to screenbeam .clear() .draw(shaderA, ... resourcesA) .draw(shaderB, ... resourcesB) .draw(shaderC, ... resourcesC)Copy the code

You can seamlessly change to off-screen rendering like this:

// Initialize the target for off-screen rendering
const target = beam.resource(OffscreenTarget)

// Connect the target to the texture
const textures = beam.resource(Textures)
textures.set('img', target)

// Render to the texture, the existing rendering logic is completely unchanged
beam.clear()
beam.offscreen2D(target, () = >{ beam .draw(shaderA, ... resourcesA) .draw(shaderB, ... resourcesB) .draw(shaderB, ... resourcesC) })// In other shaders, you can now use the texture named 'img' under Textures
Copy the code

Note that we can’t “directly” render to a texture, but we need a target (actually a Framebuffer Object), connect it to a texture, and then select to render to that target.

Offscreen2D is actually a Command that can be customized. You can also design more render pipelines that “need to be cleaned up” and encapsulate them as commands to express more complex combinations with deeply nested functions, which is another strength of Beam.

With this off-screen rendering API understood, we can easily get interlaced renderings using the power of offscreen2D:

const targetA = beam.resource(OffscreenTarget)
const targetB = beam.resource(OffscreenTarget)
let i = 0

const render = () = > {
  // Interleave the two targets
  const targetFrom = i % 2= = =0 ? targetA : targetB
  const targetTo = i % 2= = =0 ? targetB : targetA

  beam.clear()
  beam.offscreen2D(targetTo, () = > {
    conwayTexture.set('state', targetFrom) beam.draw(conwayShader, ... rectBuffers, conwayTexture) })// Output the result of the interleaved rendering to the screen by another simple shader
  screenTexture.set('img', targetTo) beam.draw(imageShader, ... rectBuffers, screenTexture) i++ }Copy the code

Just prepare the initial state and call the render function frame by frame using the requestAnimationFrame. By generating a series of random points on the Canvas, you can get this test effect:

This indicates that the critical parallel acceleration process has been completed. Finally, by making a few changes to the element shader, you can add a 50 cent “shadow” effect:

float decay = 0.95; // The attenuation parameter

/ / gl_FragColor = vec4 (0.0); // No longer empty directly
gl_FragColor = vec4(0.0, old.yz * decay, 1.0);

// The following if-else...
Copy the code

That’s the whole point! Now we can experience the Rendered Conway Life game on the GPU. It has some preset classical input states, such as life in the form of this “oscillator” :

You can also assemble huge structures that continuously “produce life” :

And then there’s this little seed maniac:

But my personal favorite is this: “A seemingly uniform group that collapses when it reaches its borders” :

At this point, your WebGL widget is complete. With the help of WebGL, it’s easy to calculate more than 4 million pixels per frame on a 2048×2048 mesh size. You can access a Demo of it here. Finally, some relevant articles are worth referring to:

A GPU Approach to Conway’s Game of Life
Conway in WebGL

conclusion

In fact, like Conway life game such a simple demo, is obviously a professional graphics developers “disdain” to explain the trivial skills. But there is clearly a big gap: a general lack of understanding and use of WebGL concepts by the average front-end developer. At this point, maybe we need more examples of fun and simplicity to say, “So that’s it.”

In particular, the beam-based entire Conway Life Gaming application is only 5.6KB in size, which is more than 90% smaller than the LightGL Demo used in the community implementation. But Beam isn’t a toy, it’s a generic WebGL base library. You can also use it to learn WebGL image processing, and we used it to render PBR-supported 3D text in the Web editor. Its extremely lightweight size makes it very easy to embed into other front-end frames. In this respect, there are many ideas worth exploring have not yet been realized, we hope that more star support!

Beam – Expressive WebGL

After all, “rendering” is not just some sort of virtual DOM diff that you toss around in your interview answers. It’s also a calculation, with infinite possibilities. As a technology that has not been fully developed in the front-end industry, the use of WebGL does not necessarily require 3D expertise and can be used as a powerful accelerator for specific computing tasks (parallelizable for loops). Want to learn how to be a WebGL accelerator? Welcome to Beam and experience Expressive WebGL in 10KB

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Simulating Life with the Web: Conway’s Life Game WebGL

background

Simple implementation

Accelerate the principle

Beam-based implementation

conclusion

Simulating Life with the Web: Conway’s Life Game WebGL

background

Simple implementation

Accelerate the principle

Beam-based implementation

conclusion

Related Posts

Make an AI robot and answer my messages!

Part THREE: WinDBG time travel debugging

Node series – 001-Node