实现康威的生命游戏
设计
在我们深入之前，我们有一些设计选择需要考虑。
无限的宇宙
生命游戏是在无限的宇宙中进行的，但我们没有无限的内存和计算能力。 解决这个相当恼人的限制，通常有以下三种风格:
1。 跟踪宇宙的哪个子集发生了有趣的事情，并根据需要，扩展此区域。 在最坏的情况下，这种扩展是无限制的，实现将变得越来越慢，最终耗尽内存。
2。 创建固定大小的 Universe，边缘上的单元格具有较少的邻居 比中间的单元格。 这种方法的缺点是无限 像滑翔机一样到达宇宙尽头的模式被扼杀了。
3。 创建一个固定大小的周期性 Universe，其中边缘上的单元格具有环绕到 Universe 另一侧的邻居。 因为邻居环绕宇宙的边缘，滑翔机可以永远运行。
我们将实现第三种选择。
连接 Rust 和 JavaScript
⚡ 这是从本教程中，你要理解和获取的最重要的概念之一!
JavaScript 的垃圾收集堆 - Object，Array和 DOM 节点 是被分配的 - 不同于 WebAssembly 的线性内存空间，我们的 Rust 值 存在于其中。 WebAssembly 目前无法直接访问垃圾收集堆 (截至 2018 年 4 月，预计会随“主机绑定 host-bindings”提案而改变) 。 另一方面，JavaScript 可以读取和写入 WebAssembly 线性存储空间，但仅作为一个ArrayBuffer标量值 (u8，i32，f64等等...) WebAssembly 函数也接受，并返回标量值. 这些是构成 WebAssembly 和 JavaScript 通信 的所有构建块。
wasm_bindgen定义了，如何与跨边界复合结构一起工作的共识。 它涉及封装 Rust 结构，将指针包装在 JavaScript 类 中以实现可用性，或者 从 Rust 索引到 一个 JavaScript 对象表格。 wasm_bindgen非常方便，但它不需要考虑我们的数据表示，以及跨越这个边界传递什么值和结构.。相反，将其视为实现您选择的接口设计的工具。
在设计 WebAssembly 和 JavaScript 之间的接口时，我们希望针对以下属性进行优化:
-
**最小化 WebAssembly 线性存储器的 进/出复制 。**不必要的副本会产生不必要的开销。
-
**最小化序列化和反序列化。**与复制类似，序列化和反序列化也会产生开销，并且通常也会进行复制。 如果我们可以将不透明的控制，传递给数据结构 - 而不是在一边序列化后，将其复制到 WebAssembly 线性存储器中的某个已知位置，并在另一边进行反序列化 - 我们通常可以减少大量开销。
wasm_bindgen帮助我们 定义和使用 JavaScript 的Object或 已封装的 Rust 结构的不透明控制。
作为一般的经验法则，一个好的 JavaScript↔WebAssembly 接口设计，通常是将大型，长寿命的数据结构实现，为生活在 WebAssembly 线性内存 中的 Rust 类型，并作为不透明控制暴露给 JavaScript. JavaScript 调用，这些持有不透明控制的导出了的 WebAssembly 函数，转换数据，执行繁重的计算，查询数据，最终返回一个小的可复制结果。 通过仅返回计算的小结果，我们避免在 JavaScript 垃圾收集堆和 WebAssembly 线性存储器 之间，来回复制和序列化所有内容。
在我们的生命游戏中连接 Rust 和 JavaScript
让我们首先列举一些要避免的危险。 我们不希望在每次tick，都将整个 Universe 复制到 WebAssembly 线性内存。 我们不希望为宇宙中的每个单元分配对象，也不想强加一个跨边界调用来读写每个单元。
这给我们留下了什么? 我们可以将 Universe 表示为，位于 WebAssembly 线性内存中的平面数组，并且每个单元格都有一个字节。 0是一个死单元格，1是一个活单元格。
以下是 4 x 4 宇宙在内存中的样子:
要在 Universe 的给定行和列中，查找单元格的数组索引，我们可以使用以下公式:
index(row, column, universe) = row * width(universe) + column
我们有几种方法可以将 Universe 的单元格暴露给 JavaScript。 首先，我们为Universe添加std::fmt::Display实现，可以用来产生 一个单元格的 RustString ，渲染为文本字符。 然后将此 Rust String 从 WebAssembly 线性内存 复制到 JavaScript 的垃圾回收堆中 的 JavaScript String 中，然后通过设置HTML的textContent显示。 在本章的后面，我们将推演这个实现，以避免在堆之间复制 Universe 的单元格，和渲染到<canvas>。
另一个可行的设计替代方案是， Rust 返回每次 tick 后，更改状态的每个单元格的列表，而不是将整个 Universe 暴露给 JavaScript。 好处在于，JavaScript 在渲染时不需要遍历整个 Universe ，只需要相关的子集。 问题权衡，在于这种 基于 delta 的设计实现起来，稍微困难一些。
Rust 实现
在上一章中，我们克隆了一个初始项目模板. 我们现在将修改该项目模板.
让我们开始删除 wasm-game-of-life/src/lib.rs的 alert导入 和greet 函数，并用单元格的类型定义替换它们:
# #![allow(unused_variables)] #fn main() { #[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的单元格向量。
# #![allow(unused_variables)] #fn main() { #[wasm_bindgen] pub struct Universe { width: u32, height: u32, cells: Vec<Cell>, } #}
要访问 给定行和列 的单元格，我们将 行和列 转换为 单元格向量 的索引，如前所述:
# #![allow(unused_variables)] #fn main() { impl Universe { fn get_index(&self, row: u32, column: u32) -> usize { (row * self.width + column) as usize } // ... } #}
为了计算单元格的下一个状态，我们需要计算 其邻居有多少 是活着的。 我们来写一个live_neighbor_count方法，做到这一点!
# #![allow(unused_variables)] #fn main() { 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方法使用 deltas 和 modulo 来避免宇宙的边缘情况。 当应用-1的增量时，我们添加
self.height - 1，然后让 modulo 做它的事，而不是试图减去1。 row和column可以为0，如果我们试图减去1， 从他们来看，会有一个 无符号整数 下溢。
现在我们拥有了当前计算下一代所需的一切! 每个游戏的规则遵循 转换条件用match直接表达。 另外，因为我们希望 JavaScript 控制 tick 时间，我们将把这个方法放在一个#[wasm_bindgen]注释下，以便它暴露给 JavaScript。
# #![allow(unused_variables)] #fn main() { /// 公有方法, 暴露给 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; } // ... } #}
到目前为止，宇宙的状态被表示为 单元格 的载体。 为了使这个可读，让我们实现一个基本的文本渲染器。 我们的想法是逐行将 Universe 写成文本，对于每个活着的单元格，打印 Unicode 字符◼️ (”黑色方格”) 。 对于死单元格，我们将打印◻️ (”白色方格”) 。
通过实现来自 Rust 标准库 的Displaytrait ，我们可以添加一种面向用户, 格式化结构的方法。 这也会自动给我们一个to_string方法.
# #![allow(unused_variables)] #fn main() { 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(()) } } #}
最后，我们定义一个构造函数，用一个有趣的 活单元格和死单元格 模式来初始化宇宙，以及render方法:
# #![allow(unused_variables)] #fn main() { /// Public methods, exported to JavaScript. #[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() } } #}
有了这个，我们的生命游戏 Rust 实现的一半就完成了!
在wasm-game-of-life 目录内，通过运行wasm-pack build重新编译为 WebAssembly。
使用 JavaScript 渲染
首先，让我们添加一个用于渲染宇宙的<pre>元素到wasm-game-of-life/www/index.html，就放在 <script> 上好了:
<body>
<pre id="game-of-life-canvas"></pre>
<script src="./bootstrap.js"></script>
</body>
另外，我们想要这个<pre>，以网页中间为中心. 我们可以使用 CSS flex 来完成这项任务。 添加以下内容<style>，到index.html的<head>里面:
<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循环][requestanimationframe]。 在每次迭代中，它将当前的 Universe 绘制到<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 中生成 (和分配) 一个String， 然后有wasm-bindgen将其转换为有效的 JavaScript 字符串 ，来会生成 Universe 单元格 的不必要副本。 其实在 JavaScript 代码 知道 Universe 的宽度和高度，并且可以直接从 JavaScript 中读取 WebAssembly 线性内存 中的单元格字节， 我们就可以修改render方法，用来返回 单元数组的开头指针。
还有，我们将切换到使用Canvas API。 而不是渲染 unicode 文本。 我们将在本教程的其余部分中使用此设计。
首先，让我们把pre，换成了一个<canvas> (它也应该在<body>， <script>加载我们的 JavaScript 之前) :
wasm-game-of-life/www/index.html内，让我们把之前添加的<pre>换成准备渲染的一个<canvas>(它也应该在<body>， 在<script>加载我们的 JavaScript 之前):
<body>
<canvas id="game-of-life-canvas"></canvas>
<script src="./bootstrap.js"></script>
</body>
为了从 Rust 实现 中获取必要的信息，我们需要为 Universe 的宽度，高度和指向 其单元数组 的指针 添加更多的一些 getter函数。 所有这些都暴露在 JavaScript 中。添加这些内容wasm-game-of-life/src/lib.rs:
# #![allow(unused_variables)] #fn main() { /// Public methods， exported to JavaScript. #[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，我们也从wasm-game-of-life导入Cell，和让我们定义 JavaScript 在渲染 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';
现在，让我们重写当前的 JS 代码 (导入除外) ，不再写入<pre>的textContent，而是专注在<canvas>:
// 构造 the universe， and get its width and height.
const universe = Universe.new();
const width = universe.width();
const height = universe.height();
// Give the canvas room for all of our cells and a 1px border
// around each of them.
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.lineWidth = 1 / window.devicePixelRatio;
ctx.strokeStyle = GRID_COLOR;
// Vertical lines.
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);
}
// Horizontal lines.
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 的 线性内存， 而这个memory由原生 wasm 模块wasm_game_of_life_bg提供。为了绘制 单元格，我们拿到 universe's cells 的指针 ，构造一个覆盖单元格缓存的Uint8Array，迭代每个单元格，并分别根据 单元格是死还是活，绘制白色或黑色矩形。 通过使用 指针 和 覆盖，我们避免在每次tick上跨边界复制单元格。
// 文件顶部，导入 WebAssembly memory
import {memory} from './wasm_game_of_life_bg';
// ...
const getIndex = (row, column) => {
return row * width + column;
};
const drawCells = () => {
const cellsPtr = universe.cells(); // < universe's 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] === DEAD ? DEAD_COLOR : ALIVE_COLOR;
ctx.fillRect(
col * (CELL_SIZE + 1) + 1,
row * (CELL_SIZE + 1) + 1,
CELL_SIZE,
CELL_SIZE
);
}
}
ctx.stroke();
};
要开始渲染过程，我们将使用与 上部分相同的代码 ，来开始渲染循环的第一次迭代:
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/，你应该受到令人兴奋的展示!
您可以 checkout chapter-one 分支 找到完整代码.
还有一个非常巧妙的算法，来实现生命游戏，叫做hashlife。 它使用积极的内存，实际上计算后代的时间越长，获得的指数级更快! 鉴于此，您可能想知道为什么我们在本教程中没有实现hashlife。 因为它超出了本文的范围，我们专注于 Rust 和 WebAssembly 集成，但我们强烈建议您自己去了解hashlife!
练习
-
使用单个太空飞船，初始化宇宙.
-
不是硬编码最初的宇宙，而是生成一个随机的，有五十五个单元格活着或死亡的机会.
提示:使用
js-sys箱导入Math.randomJavaScript 函数.答案
首先，在wasm-game-of-life/Cargo.toml添加依赖:# ... [dependencies] js-sys = "0.3" # ...然后，使用
js_sys::Math::random翻转硬币的函数:# #![allow(unused_variables)] #fn main() { extern crate js_sys; // ... if js_sys::Math::random() < 0.5 { // Alive... } else { // Dead... } #} -
用 一个字节 表示 每个单元格 可以很容易地迭代单元格，但这是以浪费内存为代价的. 每个字节是 8 位，但我们只需要 一个位 来表示每个单元 是活还是死. 重构数据表示，以便每个单元，仅使用一个空格位.
答案
在 Rust 中，您可以使用fixedbitset箱子和它的FixedBitSet类型，来表示单元格，代替Vec<Cell>:
# #![allow(unused_variables)] #fn main() { // 确保你添加此依赖到了 Cargo.toml! extern crate fixedbitset; use fixedbitset::FixedBitSet; // ... #[wasm_bindgen] pub struct Universe { width: u32, height: u32, cells: FixedBitSet, } #}
可以通过以下方式调整 Universe 构造函数:
# #![allow(unused_variables)] #fn main() { 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方法:
# #![allow(unused_variables)] #fn main() { 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，您可以转换FixedBitSet到切片，然后将切片转换为指针:
# #![allow(unused_variables)] #fn main() { #[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 位):
const cells = new Uint8Array(memory.buffer, cellsPtr, (width * height) / 8);
给出一个索引和Uint8Array，你可以确定是否使用以下函数设置 nth 位:
const bitIsSet = (n, arr) => {
let byte = Math.floor(n / 8);
let mask = 1 << n % 8;
return (arr[byte] & mask) === mask;
};
鉴于此，新版本drawCells看起来像这样:
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);
// This is updated!
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();
};