使用 WebAssembly 制作康威生命游戏

图片来源

Ray Smith

康威的生命游戏是一种流行的编程练习，用于创建元胞自动机，这是一个由无限网格单元组成的系统。您不是以传统意义上的方式玩游戏；事实上，它有时被称为零玩家游戏。

一旦您启动生命游戏，游戏就会自行运行以繁殖和维持“生命”。在游戏中，代表生命形式的数字单元可以按照一组规则更改状态。当规则通过多次迭代应用于单元时，它们会表现出复杂的行为和有趣的模式。

生命游戏模拟非常适合 WebAssembly 实现，因为它可能在计算上非常密集；必须为每次迭代计算整个网格中每个单元的状态。WebAssembly 在计算密集型任务方面表现出色，这归功于其预定义的执行环境和内存粒度以及许多其他特性。

编译为 WebAssembly

虽然可以手动编写 WebAssembly，但随着复杂性的增加，它会变得非常不直观且容易出错。最重要的是，它并非旨在以这种方式编写。这相当于手动编写汇编语言指令。

这是一个简单的 WebAssembly 函数，用于添加两个数字

(func $Add (param $0 i32) (param $1 i32) (result i32)
    local.get $0
    local.get $1
    i32.add
)

可以使用许多现有语言（包括 C、C++、Rust、Go，甚至 Lua 和 Python 等解释型语言）编译 WebAssembly 模块。这个列表还在不断增长。

使用现有语言的问题之一是 WebAssembly 没有太多运行时。它不知道释放指针或闭包是什么意思。所有这些特定于语言的运行时都必须包含在生成的 WebAssembly 二进制文件中。运行时大小因语言而异，但它会影响模块大小和执行时间。

AssemblyScript

AssemblyScript 是一种尝试通过不同方法克服其中一些挑战的语言。AssemblyScript 专为 WebAssembly 设计，专注于提供低级控制、生成更小的二进制文件并减少运行时开销。

AssemblyScript 使用 TypeScript 的严格类型变体，TypeScript 是 JavaScript 的超集。熟悉 TypeScript 的开发人员不必费力学习一种全新的语言。

入门

可以通过 Node.js 轻松安装 AssemblyScript 编译器。首先在空目录中初始化一个新项目

npm init
npm install --save-dev assemblyscript

如果您没有在本地安装 Node，您可以使用简洁的 WebAssembly Studio 应用程序在浏览器中试用 AssemblyScript。

AssemblyScript 附带 asinit，它应该在您运行上面的安装命令时安装。它是一个有用的实用程序，可以快速设置具有推荐目录结构和配置文件的 AssemblyScript 项目

npx asinit .

新创建的 assembly 目录将包含所有 AssemblyScript 代码，assembly/index.ts 中的一个简单示例函数，以及 package.json 内的 asbuild 命令。asbuild 将代码编译为 WebAssembly 二进制文件。

当您运行 npm run asbuild 来编译代码时，它会在 build 内部创建文件。.wasm 文件是生成的 WebAssembly 模块。.wat 文件是文本格式的模块，通常用于调试和检查。

您需要做一些工作才能使二进制文件在浏览器上运行。

首先，创建一个简单的 HTML 文件，index.html

<html>
    <head>
        <meta charset=utf-8>
        <title>Game of life</title>
    </head>
    
    <body>
        <script src='./index.js'></script>
    </body>
</html>

接下来，将 index.js 的内容替换为下面的代码片段，以加载 WebAssembly 模块

const runWasm = async () => {
  const module = await WebAssembly.instantiateStreaming(fetch('./build/optimized.wasm'));
  const exports = module.instance.exports;

  console.log('Sum = ', exports.add(20, 22));
};

runWasm();

此代码 fetches 二进制文件并将其传递给 WebAssembly.instantiateStreaming，这是将模块编译为可立即使用的实例的浏览器 API。这是一个异步操作，因此它在异步函数内部运行，以便可以使用 await 等待其完成编译。

module.instance.exports 对象包含 AssemblyScript 导出的所有函数。使用 assembly/index.ts 中的示例函数并记录结果。

您将需要一个简单的开发服务器来托管这些文件。此 gist 中列出了很多选项。我使用了 node-static

npm install -g node-static
static

您可以通过将浏览器指向 localhost:8080 并打开控制台来查看结果。

图片来源

^{（Mohammed Saud，CC BY-SA 4.0）}

绘制到画布

您将把所有单元绘制到 <canvas> 元素上

<body>
    <canvas id=canvas></canvas>

    ...
</body>

添加一些 CSS

<head>
    ...

    <style type=text/css>
    body {
      background: #ccc;
    }
    canvas {
      display: block;
      padding: 0;
      margin: auto;
      width: 40%;

      image-rendering: pixelated;
      image-rendering: crisp-edges;
    }
    </style>
</head>

image-rendering 样式用于防止画布平滑和模糊像素化图像。

您需要在 index.js 中使用画布绘图上下文

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

Canvas API 中有很多函数可以用于绘图，但您需要使用 WebAssembly 而不是 JavaScript 进行绘图。

请记住，WebAssembly 无权访问 JavaScript 拥有的浏览器 API，并且任何需要进行的调用都应通过 JavaScript 进行接口。这也意味着，如果与 JavaScript 的通信尽可能少，您的 WebAssembly 模块将运行得最快。

一种方法是创建 ImageData（画布底层像素数据的数据类型），用 WebAssembly 模块的内存填充它，并在画布上绘制它。这样，如果内存缓冲区在 WebAssembly 内部更新，它将立即对 ImageData 可用。

定义画布的像素计数并创建一个 ImageData 对象

const WIDTH = 10, HEIGHT = 10;

const runWasm = async () => {
...

canvas.width = WIDTH;
canvas.height = HEIGHT;

const ctx = canvas.getContext('2d');
const memoryBuffer = exports.memory.buffer;
const memoryArray = new Uint8ClampedArray(memoryBuffer)

const imageData = ctx.createImageData(WIDTH, HEIGHT);
imageData.data.set(memoryArray.slice(0, WIDTH * HEIGHT * 4));
ctx.putImageData(imageData, 0, 0);

WebAssembly 模块的内存在 exports.memory.buffer 中作为 ArrayBuffer 提供。您需要将其用作 8 位无符号整数数组或 Uint8ClampedArray。现在您可以向模块的内存填充一些像素。在 assembly/index.ts 中，您首先需要增加可用内存

memory.grow(1);

WebAssembly 默认情况下无权访问内存，需要使用 memory.grow 函数从浏览器请求内存。内存以 64Kb 的块增长，并且可以在调用它时指定所需的块数。现在您不需要超过一个块。

请记住，可以根据需要多次请求内存，并且一旦获取，内存就无法释放或返回给浏览器。

写入内存

store<u32>(0, 0xff101010);

一个像素由 32 位表示，RGBA 值各占 8 位。这里，RGBA 以相反的顺序定义 - ABGR - 因为 WebAssembly 是小端序。

store 函数在索引 0 处存储值 0xff101010，占用 32 位。alpha 值为 0xff，因此像素完全不透明。

图片来源

^{（Mohammed Saud，CC BY-SA 4.0）}

使用 npm run asbuild 再次构建模块，然后刷新页面以在画布的左上角看到您的第一个像素。

实现规则

让我们回顾一下规则。生命游戏维基百科页面对它们进行了很好的总结

任何活细胞的活邻居少于两个时，都会因人口不足而死亡。
任何活细胞的活邻居为两个或三个时，都会存活到下一代。
任何活细胞的活邻居多于三个时，都会因人口过剩而死亡。
任何死细胞的活邻居正好为三个时，都会变成活细胞，就像通过繁殖一样。

您需要遍历所有行，在每个单元上实现这些规则。您不知道网格的宽度和高度，因此编写一个小函数来使用此信息初始化 WebAssembly 模块

let universe_width: u32;
let universe_height: u32;
let alive_color: u32;
let dead_color: u32;
let chunk_offset: u32;

export function init(width: u32, height: u32): void {
  universe_width = width;
  universe_height = height;
  chunk_offset = width * height * 4;

  alive_color = 0xff101010;
  dead_color = 0xffefefef;
}

现在您可以在 index.js 中使用此函数向模块提供数据

exports.init(WIDTH, HEIGHT);

接下来，编写一个 update 函数来迭代所有单元，计算每个单元的活动邻居数，并相应地设置当前单元的状态

export function update(): void {
  for (let x: u32 = 0; x < universe_width; x++) {
    for (let y: u32 = 0; y < universe_height; y++) {

      const neighbours = countNeighbours(x, y);

      if (neighbours < 2) {
        // less than 2 neighbours, cell is no longer alive
        setCell(x, y, dead_color);
      } else if (neighbours == 3) {
        // cell will be alive
        setCell(x, y, alive_color);
      } else if (neighbours > 3) {
        // cell dies due to overpopulation
        setCell(x, y, dead_color);
      }
    }
  }

  copyToPrimary();
}

您有两个单元数组副本，一个代表当前状态，另一个用于计算和临时存储下一个状态。计算完成后，第二个数组被复制到第一个数组以进行渲染。

这些规则相当简单，但 countNeighbours() 函数看起来很有趣。仔细看看

function countNeighbours(x: u32, y: u32): u32 {
  let neighbours = 0;

  const max_x = universe_width - 1;
  const max_y = universe_height - 1;

  const y_above = y == 0 ? max_y : y - 1;
  const y_below = y == max_y ? 0 : y + 1;
  const x_left = x == 0 ? max_x : x - 1;
  const x_right = x == max_x ? 0 : x + 1;

  // top left
  if(getCell(x_left, y_above) == alive_color) {
    neighbours++;
  }

  // top
  if(getCell(x, y_above) == alive_color) {
    neighbours++;
  }

  // top right
  if(getCell(x_right, y_above) == alive_color) {
    neighbours++;
  }

  ...

  return neighbours;
}

图片来源

^{（Mohammed Saud，CC BY-SA 4.0）}

每个单元有八个邻居，您可以检查每个邻居是否处于 alive_color 状态。此处处理的重要情况是单元正好位于网格边缘。元胞自动机通常被假定位于无限空间中，但由于尚未发明无限大的显示器，因此坚持在边缘处扭曲。这意味着当一个单元超出顶部时，它会在底部返回其对应的位置。这通常被称为环面空间。

getCell 和 setCell 函数是 store 和 load 函数的包装器，以便更轻松地使用 2D 坐标与内存交互

@inline
function getCell(x: u32, y: u32): u32 {
  return load<u32>((x + y * universe_width) << 2);
}

@inline
function setCell(x: u32, y: u32, val: u32): void {
  store<u32>(((x + y * universe_width) << 2) + chunk_offset, val);
}

function copyToPrimary(): void {
  memory.copy(0, chunk_offset, chunk_offset);
}

@inline 是一个注解，它请求编译器使用函数定义本身转换对函数的调用。

从 index.js 在每次迭代时调用 update 函数，并从模块内存渲染图像数据

const FPS = 5;

const runWasm = async () => {
  ...

  const step = () => {
    exports.update();
 
    imageData.data.set(memoryArray.slice(0, WIDTH * HEIGHT * 4));
    ctx.putImageData(imageData, 0, 0);
 
    setTimeout(step, 1000 / FPS);
  };
  step();

此时，如果您编译模块并加载页面，它将不显示任何内容。代码运行良好，但由于您最初没有任何活细胞，因此没有新细胞出现。

创建一个新函数以在初始化期间随机添加单元

function fillUniverse(): void {
  for (let x: u32 = 0; x < universe_width; x++) {
    for (let y: u32 = 0; y < universe_height; y++) {
      setCell(x, y, Math.random() > 0.5 ? alive_color : dead_color);
    }
  }

  copyToPrimary();
}

export function init(width: u32, height: u32): void {
  ...

  fillUniverse();

由于 Math.random 用于确定单元的初始状态，因此 WebAssembly 模块需要一个种子函数来从中派生随机数。

AssemblyScript 提供了一个方便的模块加载器，它可以执行此操作以及更多操作，例如包装用于模块加载的浏览器 API 以及为更精细的内存控制提供函数。您不会在此处使用它，因为它抽象出了许多细节，否则这些细节将有助于学习 WebAssembly 的内部工作原理，因此请改为传入种子函数

  const importObject = {
    env: {
      seed: Date.now,
      abort: () => console.log('aborting!')
    }
  };
  const module = await WebAssembly.instantiateStreaming(fetch('./build/optimized.wasm'), importObject);

可以使用可选的第二个参数（一个将 JavaScript 函数公开给 WebAssembly 模块的对象）调用 instantiateStreaming。在这里，使用 Date.now 作为种子来生成随机数。

现在应该可以运行 fillUniverse 函数并最终在您的网格上拥有生命！

您还可以试用不同的 WIDTH、HEIGHT 和 FPS 值，并使用不同的单元颜色。