实现康威生命游戏
设计
在我们编码之前,我们有一些设计上的选择要考虑。
无限宇宙
生命的游戏是在无限的宇宙中进行的,但我们没有无限的记忆和计算能力。解决这个相当烦人的限制通常有三种方式:
- 跟踪宇宙的哪个子集发生了有趣的事情,并根据需要扩展这个区域。在最坏的情况下,这种扩展是无限的,实现会越来越慢,最终耗尽内存。
- 创建一个固定大小的宇宙,边缘的细胞比中间的细胞有更少的邻居。这种方法的缺点是,到达宇宙尽头的无限模式,如滑翔机,被扼杀了。
- 创造一个固定大小、周期性的宇宙,其中边缘的细胞有环绕宇宙另一边的邻居。因为邻居环绕着宇宙的边缘,所以滑翔机可以永远不停地飞行。
我们将实施第三种选择。
设计 Rust 和 JavaScript 的接口
⚡ 这是本教程中最重要的概念之一!
JavaScript 的垃圾收集堆(在这里分配Object
、Array
和 DOM
)不同于 WebAssembly 的线性内存空间,在这里我们的 trust 值存在。WebAssembly 目前无法直接访问垃圾收集堆(截至2018年4月,这一点预计将随“接口类型”建议而改变)。
另一方面,JavaScript 可以读写 WebAssembly 线性内存空间,但只能作为标量值(u8
、i32
、f64
等)的ArrayBuffer
。WebAssembly 函数还获取并返回标量值。这些是构成所有 WebAssembly 和 JavaScript 通信的构建块。
wasm_bindgen
定义了如何跨此边界处理复合结构的共同理解。
它包括封装的 Rust structures,将指针封装到 JavaScript 类中以获得可用性,或者从 Rust 索引到 JavaScript 对象表中。
wasm_bindgen
非常方便,但是它不需要考虑我们的数据表示,以及通过这个边界传递什么值和结构。相反,可以将它看作是实现所选接口设计的工具。
在设计 WebAssembly 和 JavaScript 之间的接口时,我们希望优化以下属性:
- 最小化对WebAssembly线性内存的复制。 不必要的拷贝会带来不必要的开销。
- 最小化序列化和反序列化。 类似于副本,序列化和反序列化也会带来开销,而且还经常要求复制。如果我们能把不透明的操作传递数据结构 —— 与其在一边序列化,不如将其复制到 WebAssembly 线性内存中的某个已知位置,在另一边反序列化 —— 我们可以减少很多开销。
wasm_bindgen
帮助我们定义和使用 JavaScript 对象或封装的 Rust structures,将指针封装到的不透明操作。
一般来说,一个好的 JavaScript↔WebAssembly 接口设计通常是将大型、长寿命的数据结构实现为驻留在 WebAssembly 线性内存中的 Rust 类型,并将其作为不透明操作开放给JavaScript。 JavaScript 调用导出的 WebAssembly 函数,这些函数接受这些不透明的操作,转换它们的数据,执行繁重的计算,查询数据,最终返回一个小的、可复制的结果。通过只返回较小的计算结果,我们可以避免在 JavaScript 垃圾收集堆和 WebAssembly 线性内存之间来回复制和/或序列化所有内容。
在游戏中连接 Rust 和 JavaScript
让我们先列举一些要避免的危险。我们不想把整个宇宙都复制到 WebAssembly 的线性内存中。我们不想为宇宙中的每个单元分配对象,也不想对每个单元进行读写的跨边界调用。
这给我们留下了什么? 我们可以将 Universe 表示为,位于 WebAssembly 线性内存中的平面数组,并且每个单元格都有一个字节。 0是一个死单元格,1是一个活单元格。
在内存中,4x4的宇宙是这样的:
要在 Universe 的给定行和列中,查找单元格的数组索引,我们可以使用以下公式:
index(row, column, universe) = row * width(universe) + column
我们有几种方法可以将 Universe 的单元格暴露给 JavaScript。 首先,我们为Universe
添加 std::fmt::Display
实现,可以用来产生 一个单元格的 Rust String
,渲染为文本字符。 然后将此 Rust String
从 WebAssembly 线性内存复制到 JavaScript 的垃圾收集堆中 的 JavaScript String
中,然后通过设置HTML的 textContent 显示。 在本章的后面,我们将推演这个实现,以避免在堆之间复制 Universe 的单元格,和渲染到 <canvas>
。
Rust 实现
在上一章中,我们克隆了一个初始项目模板. 我们现在将修改该项目模板.
让我们开始删除 wasm-game-of-life/src/lib.rs
的 alert
导入 和 greet
函数,并用单元格的类型定义替换它们:
#[wasm_bindgen]
#[repr(u8)]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Cell {
Dead = 0,
Alive = 1,
}
重要的是我们拥有 #[repr(u8)]
,以便每个单元格表示为单个字节。 同样重要的是 Dead
代表 0
,那个 Alive
是 1
,这样我们就可以轻松地计算一个单元格的活邻居。
接下来,让我们定义宇宙(Universe)。 宇宙具有宽度和高度,以及长度为 width * height
的单元格向量。
#[wasm_bindgen]
pub struct Universe {
width: u32,
height: u32,
cells: Vec<Cell>,
}
要访问给定行和列的单元格,我们将行和列转换为单元格向量的索引,如前所述:
#![allow(unused_variables)]
impl Universe {
fn get_index(&self, row: u32, column: u32) -> usize {
(row * self.width + column) as usize
}
// ...
}
为了计算一个细胞的下一个状态,我们需要计算它的邻居中有多少人还活着。 我们需要写一个实时计数邻居的函数。
#![allow(unused_variables)]
impl Universe {
// ...
fn live_neighbor_count(&self, row: u32, column: u32) -> u8 {
let mut count = 0;
for delta_row in [self.height - 1, 0, 1].iter().cloned() {
for delta_col in [self.width - 1, 0, 1].iter().cloned() {
if delta_row == 0 && delta_col == 0 {
continue;
}
let neighbor_row = (row + delta_row) % self.height;
let neighbor_col = (column + delta_col) % self.width;
let idx = self.get_index(neighbor_row, neighbor_col);
count += self.cells[idx] as u8;
}
}
count
}
}
live_neighbor_count
方法使用增量和取模来避免宇宙的边缘情况。
当应用 -1 的增量时,我们添加 self.height - 1
,然后让取模做它的事,而不是尝试减去1。
row 和 column 可以为0,如果尝试从中减去1,则会出现无符号整数下溢。
现在我们有了从现在的计算下一代所需的一切!游戏的每一条规则都遵循一个简单的转换为 match
表达式上的条件。
另外,因为我们希望 JavaScript 控制触发 tick
,所以我们将把这个方法放在 #[wasm#u bindgen]
块中,这样它就可以开放给JavaScript。
/// 公共方法,开放给 JavaScript。
#[wasm_bindgen]
impl Universe {
pub fn tick(&mut self) {
let mut next = self.cells.clone();
for row in 0..self.height {
for col in 0..self.width {
let idx = self.get_index(row, col);
let cell = self.cells[idx];
let live_neighbors = self.live_neighbor_count(row, col);
let next_cell = match (cell, live_neighbors) {
// 规则 1: 任何少于两个邻居的活细胞死亡,就好像是由于人口不足造成的一样。.
(Cell::Alive, x) if x < 2 => Cell::Dead,
// 规则 2: 任何一个有两个或三个邻居的活体细胞都能传到下一代。.
(Cell::Alive, 2) | (Cell::Alive, 3) => Cell::Alive,
// 规则 3: 任何居住着三个以上邻居的活细胞都会死亡,就好像是由于人口过剩。.
(Cell::Alive, x) if x > 3 => Cell::Dead,
// 规则 4:任何一个只有三个相邻的活细胞的死细胞都会变成活细胞,就像通过繁殖一样。.
(Cell::Dead, 3) => Cell::Alive,
// 所有其他单元格保持相同状态。
(otherwise, _) => otherwise,
};
next[idx] = next_cell;
}
}
self.cells = next;
}
// ...
}
到目前为止,宇宙的状态被表示为一个细胞向量。为了使其具有可读性,让我们实现一个基本的文本呈现器。这个想法是把宇宙一行一行地写成文本,对于每个活着的细胞,打印Unicode字符◼ (“黑色中方形“)。对于死细胞,我们会打印出来◻ (“白色中等正方形”)。
通过实现Rust标准库中的 Display
特性,我们可以添加一种以面向用户的方式格式化结构的方法。这也将自动为我们提供一个 to_string
方法。
use std::fmt;
impl fmt::Display for Universe {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
for line in self.cells.as_slice().chunks(self.width as usize) {
for &cell in line {
let symbol = if cell == Cell::Dead { '◻' } else { '◼' };
write!(f, "{}", symbol)?;
}
write!(f, "\n")?;
}
Ok(())
}
}
最后,我们定义了一个构造函数,它用一个有趣的活细胞和死细胞模式以及一个呈现方法来初始化宇宙:
#[wasm_bindgen]
impl Universe {
// ...
pub fn new() -> Universe {
let width = 64;
let height = 64;
let cells = (0..width * height)
.map(|i| {
if i % 2 == 0 || i % 7 == 0 {
Cell::Alive
} else {
Cell::Dead
}
})
.collect();
Universe {
width,
height,
cells,
}
}
pub fn render(&self) -> String {
self.to_string()
}
}
有了它,我们游戏的一半实现就完成了!
在 wasm-game-of-life
目录下运行 wasm-pack build
,将其重新编译到 WebAssembly。
使用 JavaScript 进行渲染
首先,让我们在 wasm-game-of-life/www/index.html
中添加一个 <pre>
元素,将宇宙渲染到 <script>
标记的正上方:
<body>
<pre id="game-of-life-canvas"></pre>
<script src="./bootstrap.js"></script>
</body>
另外,我们希望 <pre>
集中在网页的中间。我们可以使用 CSS flex-box 来实现。
在 wasm-game-of-life/www/index.html
的 <head>
中添加以下 <style>
标记:
<style>
body {
position: absolute;
top: 0;
left: 0;
width: 100%;
height: 100%;
display: flex;
flex-direction: column;
align-items: center;
justify-content: center;
}
</style>
在 wasm-game-of-life/www/index.js
的前几行,我们导入 Universe
将原来的 greet
函数替换:
import { Universe } from "wasm-game-of-life";
接着,我们将获取刚刚添加的 <pre>
元素,并实例化一个新的 Universe
:
const pre = document.getElementById("game-of-life-canvas");
const universe = Universe.new();
JavaScript 运行在 requestAnimationFrame循环 。
在每次迭代中,它都会将当前宇宙绘制到 <pre>
,然后调用 Universe::tick
。
const renderLoop = () => {
pre.textContent = universe.render();
universe.tick();
requestAnimationFrame(renderLoop);
};
要开始渲染过程,我们只需对渲染循环的第一次迭代进行初始调用:
requestAnimationFrame(renderLoop);
运行开发服务器(在 wasm-game-of-life/www
里面运行 npm run start
)。
并且打开浏览器进入 http://localhost:8080/
从内存渲染到 Canvas
在 Rust 中生成(并分配)一个字符串,然后让 wasm-bindgen
将其转换为一个有效的 JavaScript 字符串,这样就产生了不必要的宇宙单元副本。
由于 JavaScript 代码已经知道宇宙的宽度和高度,并且可以直接读取构成单元的 WebAssembly 的线性内存,因此我们将修改 render 方法以返回指向单元数组开头的指针。
另外,我们将切换到使用 Canvas API,而不是呈现 Unicode 文本。我们将在本教程的其余部分使用此设计。
在 wasm-game-of-life/www/index.html
里面,我们将 <pre>
替换成为 <canvas>
,它将依然在 <body>
里面:
<body>
<canvas id="game-of-life-canvas"></canvas>
<script src='./bootstrap.js'></script>
</body>
从 Rust 实现中获取必要的信息,我们需要为宇宙的宽度、高度和指向其单元格数组的指针添加更多的 getter 函数。
所有这些都开放在 JavaScript 中。
将这些添加到 wasm-game-of-life/src/lib.rs
:
#[wasm_bindgen]
impl Universe {
// ...
pub fn width(&self) -> u32 {
self.width
}
pub fn height(&self) -> u32 {
self.height
}
pub fn cells(&self) -> *const Cell {
self.cells.as_ptr()
}
}
然后,在 wasm-game-of-life/www/index.js
,我们将 Cell
引入,然后定义一些 canvas 所需要到常量。
import { Universe, Cell } from "wasm-game-of-life";
const CELL_SIZE = 5; // px
const GRID_COLOR = "#CCCCCC";
const DEAD_COLOR = "#FFFFFF";
const ALIVE_COLOR = "#000000";
现在,让我们重写此 JavaScript 代码的其余部分,使其不再写入 <pre>
的 textContent
,而是绘制到 <canvas>
:
// 构造 universe,得到它的宽度和高度。
const universe = Universe.new();
const width = universe.width();
const height = universe.height();
// 我们为 canvas 定义大小,以及添加 1px 的边框。
const canvas = document.getElementById("game-of-life-canvas");
canvas.height = (CELL_SIZE + 1) * height + 1;
canvas.width = (CELL_SIZE + 1) * width + 1;
const ctx = canvas.getContext('2d');
const renderLoop = () => {
universe.tick();
drawGrid();
drawCells();
requestAnimationFrame(renderLoop);
};
为了在单元格之间绘制网格,我们绘制了一组等距水平线和一组等距垂直线。这些线纵横交错形成网格。
const drawGrid = () => {
ctx.beginPath();
ctx.strokeStyle = GRID_COLOR;
// 垂直线
for (let i = 0; i <= width; i++) {
ctx.moveTo(i * (CELL_SIZE + 1) + 1, 0);
ctx.lineTo(i * (CELL_SIZE + 1) + 1, (CELL_SIZE + 1) * height + 1);
}
// 水平线
for (let j = 0; j <= height; j++) {
ctx.moveTo(0, j * (CELL_SIZE + 1) + 1);
ctx.lineTo((CELL_SIZE + 1) * width + 1, j * (CELL_SIZE + 1) + 1);
}
ctx.stroke();
};
我们可以通过 memory
直接访问 WebAssembly 的线性内存,内存是在原始 wasm 模块 wasm_game_of_life_bg
中定义的。
为了绘制单元格,我们得到一个指向宇宙单元格的指针,构造一个覆盖单元格缓冲区的 Uint8Array
,遍历每个单元格,并根据单元格是死的还是活的分别绘制一个白色或黑色的矩形。
通过使用指针和覆盖,我们可以避免在每个记号上跨边界复制单元格。
// 在文件前几行导入的WebAssembly memory。
import { memory } from "wasm-game-of-life/wasm_game_of_life_bg";
// ...
const getIndex = (row, column) => {
return row * width + column;
};
const drawCells = () => {
const cellsPtr = universe.cells();
const cells = new Uint8Array(memory.buffer, cellsPtr, width * height);
ctx.beginPath();
for (let row = 0; row < height; row++) {
for (let col = 0; col < width; col++) {
const idx = getIndex(row, col);
ctx.fillStyle = cells[idx] === Cell.Dead
? DEAD_COLOR
: ALIVE_COLOR;
ctx.fillRect(
col * (CELL_SIZE + 1) + 1,
row * (CELL_SIZE + 1) + 1,
CELL_SIZE,
CELL_SIZE
);
}
}
ctx.stroke();
};
要开始渲染过程,我们将使用与上面相同的代码开始渲染循环的第一次迭代:
drawGrid();
drawCells();
requestAnimationFrame(renderLoop);
注意,在调用 requestAnimationFrame()
之前,我们在这里调用 drawGrid()
和 drawCells()
。
我们这样做的原因是,宇宙的初始状态是在我们做出修改之前绘制出来的。
如果我们简单地调用 requestAnimationFrame(renderLoop)
,我们最终会遇到这样的情况:绘制的第一个帧实际上是在第一次调用 universe.tick()
之后,这是这些细胞生命周期中的第二个“tick”。
运行
通过在 wasm-game-of-life
目录中运行以下命令,重建 WebAssembly 和绑定胶水层:
wasm-pack build
将开发服务器运行。如果不行,请从 wasm-game-of-life/www
目录中重新启动:
npm run start
如果你刷新 http://localhost:8080/,你应该得到一个令人兴奋的游戏展示!
顺便说一句,还有一个实现生命游戏的非常简洁的算法叫做 hashlife(暂无中文) 。 它使用积极的内存,实际上可以得到指数更快的计算后代运行时间越长! 有鉴于此,你可能想知道为什么我们没有在本教程中实现 hashlife。 这超出了本文的范围,我们将重点讨论Rust和WebAssembly集成,但我们强烈建议你自己去学习 hashlife!
练习
- 用一艘宇宙飞船初始化宇宙。
不要硬编码初始宇宙,而是生成一个随机的宇宙,其中每个细胞有50%的机会活或死。
提示:使用
js-sys
crate 导入 Math.random JavaScript 函数。答案
首先,在 wasm-game-of-life/Cargo.toml添加依赖:toml # ... [dependencies] js-sys = "0.3" # ...
然后,使用js_sys::Math::random
计算 二分之一 的函数rust extern crate js_sys; // ... if js_sys::Math::random() < 0.5 { // Alive... } else { // Dead... }
用 一个字节 表示 每个单元格 可以很容易地迭代单元格,但这是以浪费内存为代价的. 每个字节是 8 位,但我们只需要 一个位 来表示每个单元 是活还是死重构数据表示,以便每个单元,仅使用一个空格位.
答案
在 Rust 中,你可以使用fixedbitset crate
和它的FixedBitSet
类型 ,来表示单元格,代替Vec: | rust // 确保你添加此依赖到了 Cargo.toml! extern crate fixedbitset; use fixedbitset::FixedBitSet; // ... #[wasm_bindgen] pub struct Universe { width: u32, height: u32, cells: FixedBitSet, }
可以通过以下方式调整 Universe 构造函数:rust pub fn new() -> Universe { let width = 64; let height = 64; let size = (width * height) as usize; let mut cells = FixedBitSet::with_capacity(size); for i in 0..size { cells.set(i, i % 2 == 0 || i % 7 == 0); } Universe { width, height, cells, } }
要更新宇宙的下一个 tick 中的单元格,我们使用FixedBitSet
的set
方法:rust next.set(idx, match (cell, live_neighbors) { (true, x) if x < 2 => false, (true, 2) | (true, 3) => true, (true, x) if x > 3 => false, (false, 3) => true, (otherwise, _) => otherwise });
要将指向开头位的指针传递给 JavaScript,你可以转换 FixedBitSe t到切片,然后将切片转换为指针:rust #[wasm_bindgen] impl Universe { // ... pub fn cells(&self) -> *const u32 { self.cells.as_slice().as_ptr() } }
在 JavaScript 中,构建 Wasm 的内存成一个 Uint8Array,与之前相同,只是数组的长度不再是width * height
,而是width * height / 8
,因为我们一个位有一个单元,而不是字节(8 位):javascript const cells = new Uint8Array(memory.buffer, cellsPtr, (width * height) / 8);
给出一个索引和 Uint8Array ,你可以确定是否使用以下函数设置 n^th 位:javascript const bitIsSet = (n, arr) => { let byte = Math.floor(n / 8); let mask = 1 << n % 8; return (arr[byte] & mask) === mask; };
然后,新版本drawCells
是这样的:javascript const drawCells = () => { const cellsPtr = universe.cells(); // 在这更新 const cells = new Uint8Array(memory.buffer, cellsPtr, (width * height) / 8); ctx.beginPath(); for (let row = 0; row < height; row++) { for (let col = 0; col < width; col++) { const idx = getIndex(row, col); // 更新 ctx.fillStyle = bitIsSet(idx, cells) ? ALIVE_COLOR : DEAD_COLOR; ctx.fillRect( col * (CELL_SIZE + 1) + 1, row * (CELL_SIZE + 1) + 1, CELL_SIZE, CELL_SIZE ); } } ctx.stroke(); };