コンウェイのライフゲーム

本館用に Javascript Canvas APIライフゲームを書いてみました。128×128 のマス目で、枠で閉じた系にしています。

https://tociyuki.sakura.ne.jp/lifegame.html
https://tociyuki.sakura.ne.jp/lifegame.js

コンストラクタでは、パラメータ他をすべて設定します。

  var Lifegame = function(id) {
    var canvas;
    this.dotsize = 4;
    this.width = 128;
    this.height = 128;
    this.deadfill = '#EEEEEE';
    this.livefill = '#000000';
    this.shuffle_probability = 0.3;
    this.interval = 250;
    this.running = 2; // 0: pause, 1: evolve & update, 2: shuffle & draw
    this.init_grid();
    canvas = $(id);
    canvas.height = this.dotsize * this.height;
    canvas.width = this.dotsize * this.width;
    this.ctx = canvas.getContext('2d');
  };

セルを格納しているグリッドは2次元の配列にしており、現世代のグリッド、次世代計算用のグリッドの 2 つを割り当てています。隣接生存セル数の計算を容易にするため、グリッド枠外にセルを番兵として配置しています。さらに、生存セルのリスト、次世代の生存セルのリスト、再描画対象もそれぞれ1次元の配列に割り当てています。一つ一つの配列の要素数は 16900 個で、それらをガベージコレクションによる寸断防止のため、あらかじめ 5 つ割り当てておく贅沢な書き方をしています。

  Lifegame.prototype.init_grid = function() {
    var i, j, k, m, n;
    this.grida = new Array(this.height + 2); // 現世代のグリッド
    this.gridb = new Array(this.height + 2); // 次世代算出用のグリッド
    for (j = 0, n = this.height + 2; j < n; ++j) {
      this.grida[j] = new Array(this.width + 2);
      this.gridb[j] = new Array(this.width + 2);
      for (i = 0, m = this.width + 2; i < m; ++i) {
        this.grida[j][i] = 0;
        this.gridb[j][i] = 0
      }
    }
    this.livea_size = 0;
    this.liveb_size = 0;
    this.inval_size = 0;
    this.livea = new Array(this.height * this.width); // 現世代の生存セルの座標
    this.liveb = new Array(this.height * this.width); // 次世代の生存セルの座標
    this.inval = new Array(this.height * this.width); // 変更されたセルの座標
    for (k = 0, n = this.livea.length; k < n; ++k) {
      this.livea[k] = [0, 0];
      this.liveb[k] = [0, 0];
      this.inval[k] = [0, 0];
    }
  };

次の世代のグリッドを求めるにあたって、変化するのは生存セルとそれに隣接しているセルだけなので、生存セルをリストアップしておきます。変化対象セル一つずつにつき、その都度、隣接生存セル数を数えて次の世代の状態を決定しています。さらに、再描画用にセルの状態が変化した座標をリストアップし、それだけを再描画しています。

なお、セルの座標は 1 から始まります。ゼロは枠線の番兵の座標で、隣接生存セルの計算のときに使うだけです。

  Lifegame.prototype.evolve_mark = function() {
    var h, w, livea, gridb,
        i0, j0, di, dj, i, j, k, n;
    h = this.height; w = this.width;
    livea = this.livea; gridb = this.gridb;
    for (k = 0, n = this.livea_size; k < n; ++k) {
      j0 = livea[k][0]; i0 = livea[k][1];
      for (dj = -1; dj < 2; ++dj) {
        j = j0 + dj;
        if (j < 1 || j > h)
          continue;
        for (di = -1; di < 2; ++di) {
          i = i0 + di;
          if (i < 1 || i > w)
            continue;
          gridb[j][i] = 128; // 未計算マークをつける
        }
      }
    }
  };

  Lifegame.prototype.evolve = function() {
    var h, w, inval, livea, liveb, grida, gridb,
        i0, j0, di, dj, i, j, ka, kb, kc, n, row0, row1, row2;
    this.evolve_mark();
    h = this.height; w = this.width;
    livea = this.livea; liveb = this.liveb; inval = this.inval;
    grida = this.grida; gridb = this.gridb;
    // 生存セルとその隣接セルを対象に、次世代のセルを計算する
    kb = kc = 0;
    for (ka = 0, n = this.livea_size; ka < n; ++ka) {
      j0 = livea[ka][0]; i0 = livea[ka][1];
      for (dj = -1; dj < 2; ++dj) {
        j = j0 + dj;
        for (di = -1; di < 2; ++di) {
          i = i0 + di;
          if (gridb[j][i] < 2) // 計算済み
            continue;
          // 8 個の隣接セル中の生存セルの数を求める
          row0 = grida[j - 1]; row1 = grida[j]; row2 = grida[j + 1];
          c = row0[i - 1] + row0[i] + row0[i + 1]
            + row1[i - 1]           + row1[i + 1]
            + row2[i - 1] + row2[i] + row2[i + 1];
          // セル grida[j][i] から状態遷移し、gridb[j][i] に書き込む
          //   c: 0 1 2 3 4 5 6 7 8
          // 0 -> 0 0 0 1 0 0 0 0 0
          // 1 -> 0 0 1 1 0 0 0 0 0
          if (c == 3 || (row1[i] && c == 2)) {
            gridb[j][i] = 1;
            liveb[kb][0] = j; liveb[kb][1] = i;
            ++kb;
          }
          else {
            gridb[j][i] = 0;
          }
          // セルの状態が変化したら inval に座標を記録する
          if (grida[j][i] != gridb[j][i]) {
            inval[kc][0] = j; inval[kc][1] = i;
            ++kc;
          }
        }
      }
    }
    // 変化したセルを書き直す
    for (ka = 0; ka < kc; ++ka) {
      j = inval[ka][0]; i = inval[ka][1];
      grida[j][i] = gridb[j][i];
    }
    this.livea = liveb; this.liveb = livea;
    this.livea_size = kb; this.liveb_size = 0; this.inval_size = kc;
    return this;
  };

変化したセルの座標のリストにしたがって Canvas を再描画します。なお、Firefox 28.0 では、四角形のストロークの描画が遅いので、1 ピクセル分小さな正方形で塗りつぶします。

  Lifegame.prototype.update = function() {
    var i, j, k, n, ds, ds1, grid, inval, live, dead;
    grid = this.grida; inval = this.inval;
    ds = this.dotsize; ds1 = ds - 1;
    live = this.livefill; dead = this.deadfill;
    for (k = 0, n = this.inval_size; k < n; ++k) {
      j = inval[k][0]; i = inval[k][1];
      this.ctx.fillStyle = grid[j][i] ? live : dead;
      this.ctx.fillRect(ds * (i - 1), ds * (j - 1), ds1, ds1);
    }
    return this;
  };