使用 Rust 和 WebAssembly 實作「康威生命遊戲」應用程式

WebAssembly
, , , , ,

前言

本文為「Rust and WebAssembly」教學指南的學習筆記。

介紹

康威生命遊戲（Conway’s Game of Life），又稱康威生命棋，是英國數學家康威在 1970 年發明的細胞自動機。

  • 規則一：任何活細胞周圍有低於兩個活細胞時，將因人口稀少而死亡。
  • 規則二：任何活細胞周圍有兩至三個活細胞時，將存活至下個世代。
  • 規則二：任何活細胞周圍有高於三個活細胞時，將因人口過剩而死亡。
  • 規則四：任何死細胞周圍有剛好三個活細胞時，將因繁衍而成為活細胞。

例如，以下方世界（universe）為例：

1
2
3
4
5
6
🟦🟦🟦🟦🟦
🟦🟦🟧🟦🟦
🟦🟦🟧🟦🟦
🟦🟦🟧🟦🟦
🟦🟦🟦🟦🟦
 1 2 3 4 5

座標 3-2 和 3-4 的活細胞，將因規則一死去；座標 3-3 的活細胞，將因規則二繼續存活；座標 2-3 和 4-3 的活細胞，將因規則四成為活細胞。

到了下個世代，細胞將形成以下狀態。

1
2
3
4
5
6
🟦🟦🟦🟦🟦
🟦🟦🟦🟦🟦
🟦🟧🟧🟧🟦
🟦🟦🟦🟦🟦
🟦🟦🟦🟦🟦
 1 2 3 4 5

建立專案

建立專案。

1
cargo generate --git https://github.com/rustwasm/wasm-pack-template --name wasm-game-of-life

進入專案。

1
cd wasm-game-of-life

建立前端專案。

1
npm init wasm-app www

進入前端專案。

1
cd www

修改 package.json 檔。

1
2
3
4
5
6
7
{
  // ...
  "dependencies": {
    "wasm-game-of-life": "file:../pkg"
  },
  // ...
}

安裝依賴套件。

1
npm install

啟動前端專案。

1
npm run start

架構設計

在程式中盡量最佳化以下兩件事情：

  • 最小化從 WebAssembly 線性記憶體當中資料的存取。
  • 最小化資料的序列化與反序列化。

因此，避免在每個世代把整個世界（universe）的物件複製進或複製出 WebAssembly 線性記憶體，而是使用扁平的陣列來表達當前世界的狀態，並使用 0 來表示死細胞，使用 1 來表示活細胞。

以下是一個高度為 4 且寬度為 4 的世界存在於記憶體中的樣子。

1
2
3
0           4           8           12
🔲 🔲 🔲 🔲 🔲 🔲 🔲 🔲 🔲 🔲 🔲 🔲 🔲 🔲 🔲 🔲
    row1   |    row2   |    row3   |    row4

為了找出指定行列的細胞陣列索引，可以使用以下公式：

1
index(row, column, universe) = row * width(universe) + column

實作後端

首先，修改 src/lib.rs 檔，定義一個 Cell 枚舉。這裡使用 #[repr(u8)] 屬性，用來表示每一個細胞都是一個位元組，並使用 0 來表示死細胞，使用 1 來表示活細胞，如此一來就可以使用加法來計算一個細胞的周圍存在多少活細胞。

1
2
3
4
5
6
7
8
9
use wasm_bindgen::prelude::*;

#[wasm_bindgen]
#[repr(u8)]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Cell {
    Dead = 0,
    Alive = 1,
}

再來，定義一個 Universe 結構體，包含了其寬度、高度，和一組細胞陣列。

1
2
3
4
5
6
#[wasm_bindgen]
pub struct Universe {
    width: u32,
    height: u32,
    cells: Vec<Cell>,
}

接著為 Universe 結構體建立一個 get_index 方法，用來取得指定行列的細胞陣列索引。

1
2
3
4
5
6
7
impl Universe {
    fn get_index(&self, row: u32, column: u32) -> usize {
        (row * self.width + column) as usize
    }

    // ...
}

再建立一個 live_neighbor_count 方法，用來取得一個細胞的周圍有多少活細胞。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
    }
}

建立一個帶有 #[wasm_bindgen] 屬性的 Universe 實作，將方法暴露給前端。

1
2
3
4
#[wasm_bindgen]
impl Universe {
  // ...
}

建立一個公開的 tick 方法，用來記算在下一個世代的細胞狀態。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#[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) {
                    // Rule 1: Any live cell with fewer than two live neighbours
                    // dies, as if caused by underpopulation.
                    (Cell::Alive, x) if x < 2 => Cell::Dead,
                    // Rule 2: Any live cell with two or three live neighbours
                    // lives on to the next generation.
                    (Cell::Alive, 2) | (Cell::Alive, 3) => Cell::Alive,
                    // Rule 3: Any live cell with more than three live
                    // neighbours dies, as if by overpopulation.
                    (Cell::Alive, x) if x > 3 => Cell::Dead,
                    // Rule 4: Any dead cell with exactly three live neighbours
                    // becomes a live cell, as if by reproduction.
                    (Cell::Dead, 3) => Cell::Alive,
                    // All other cells remain in the same state.
                    (otherwise, _) => otherwise,
                };

                next[idx] = next_cell;
            }
        }

        self.cells = next;
    }

    // ...
}

為 Universe 結構體實作一個 fmt 方法，用來渲染出人類可讀的方塊圖形，並且可以使用 to_string 方法呼叫。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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(())
    }
}

再為 Universe 結構體建立一個公開的 new 方法當作建構子，用來初始化一個新的世界。並建立一個 render 方法，用來渲染方塊圖形。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#[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()
    }
}

執行編譯。

1
wasm-pack build

實作前端

修改 www/index.html 檔。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Hello wasm-pack!</title>
    <style>
      body {
        position: absolute;
        top: 0;
        left: 0;
        width: 100%;
        height: 100%;
        display: flex;
        flex-direction: column;
        align-items: center;
        justify-content: center;
      }
    </style>
  </head>
  <body>
    <pre id="game-of-life-canvas"></pre>
    <script src="./bootstrap.js"></script>
  </body>
</html>

修改 www/index.js 檔。

1
2
3
4
5
6
7
8
9
10
11
12
13
import { Universe } from "wasm-game-of-life";

const pre = document.getElementById("game-of-life-canvas");
const universe = Universe.new();

const renderLoop = () => {
  pre.textContent = universe.render();
  universe.tick();

  requestAnimationFrame(renderLoop);
};

requestAnimationFrame(renderLoop);

啟動服務。

1
npm run start

前往 http://localhost:8080 瀏覽。

重構

修改後端的 src/lib.rs 檔，建立以下公開方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#[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()
    }
}

修改 www/index.html 檔，將渲染的節點改為畫布。

1
2
3
4
<body>
  <canvas id="game-of-life-canvas"></canvas>
  <script src="./bootstrap.js"></script>
</body>

修改 www/index.js 檔，引入 wasm_game_of_life_bg 檔的 memory 模組，直接存取指向細胞的指針，並寫入 Uint8Array 陣列使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import { Universe, Cell } from "wasm-game-of-life";
import { memory } from "wasm-game-of-life/wasm_game_of_life_bg";

const CELL_SIZE = 5;
const GRID_COLOR = "#CCCCCC";
const DEAD_COLOR = "#FFFFFF";
const ALIVE_COLOR = "#000000";

const universe = Universe.new();
const width = universe.width();
const height = universe.height();

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;

  // 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();
};

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);

重新執行編譯。

1
wasm-pack build

重新啟動服務。

1
npm run start

前往 http://localhost:8080 瀏覽。

程式碼

參考資料