Ark's Blog

参加記や備忘録などを書いていきます

ようこそ

D言語くんとGopherの多数決オートマトン

この記事はD言語くん Advent Calendar 2017の13日目の記事です。

D言語くんとGopherの多数決オートマトン」を作りました!

>こちら<

以上です。

由緒あるD言語くんアドベントカレンダーは、2015, 2016と、毎年全部埋まってるので今年も埋まってほしいですね!
まだ空いてる日があるのでなにかネタがある人は書いていきましょう!!!!















以降、D言語くんに関係ない話です。

これはなに

元ネタは「Vichniac vote」というセル・オートマトンの一種です。

単純に「majority rule」と呼ばれることもあるらしくて、多数決の様子をセル・オートマトンでシミュレーションしたものになります。

色々と試してみると分かるように、周りのセルを見て多数派のキャラクター(D言語くん or Gopher)に変化していく傾向にあります。

Vichniac voteの生成規則は

  • セルの状態は「生」と「死」の2状態
  • 自身を含めた周囲9個の「生」のセルの合計を数える(これを\text{sum}とおく)
  • 次のセルの状態は
    • \text{sum} \geq 5ならば「生」
    • \text{sum} \leq 4ならば「死」
    • ただし、 \text{sum} = 4, 5ならば「生」と「死」を逆にする。

表に書くと

\text{sum} 次のセルの状態
0
1
2
3
4
5
6
7
8
9

実は \text{sum} = 4, 5で反転してるところがミソで、これがないと一瞬でセルの様子が収束してしまいます。(リンク先のNoizeのチェックボックスがこの反転の有無に対応しています)

ソースコード

JavaScriptでライブラリにp5.jsを使ってます。

"use strict";

const p5 = require("p5");

const sketch = (p) => {

    const CANVAS_WIDTH  = Math.min(window.innerWidth, window.innerHeight, 600);
    const CANVAS_HEIGHT = Math.min(window.innerWidth, window.innerHeight, 600);

    const CELL_NUM_X    = 50;
    const CELL_NUM_Y    = 50;
    const CELL_WIDTH    = CANVAS_WIDTH/CELL_NUM_X;
    const CELL_HEIGHT   = CANVAS_HEIGHT/CELL_NUM_Y;
    const DMAN_SIZE     = CELL_WIDTH * 1.5;
    const GOPHER_SIZE   = CELL_WIDTH * 1.1;

    let dmanImage;
    let gopherImage;

    const fpsSlider     = document.querySelector("#fpsSlider");
    const fpsText       = document.querySelector("#fpsText");
    const randomButton  = document.querySelector("#randomButton");
    const noizeCheckBox = document.querySelector("#noizeCheckBox");

    function iota(n) {
        return Array.from({length: n}, (_, i) => i);
    }

    function updateFpsText() {
        fpsText.innerHTML = fpsSlider.value;
    }

    class Cell {
        constructor(indexX, indexY, isAlive) {
            this.indexX = indexX;
            this.indexY = indexY;
            this.isAlive = isAlive;
            this.throttleFrame = this.throttleDuration = 20;
        }
        step() {
            if (p.mouseIsPressed && this.throttleFrame >= this.throttleDuration) {
                let ok = true;
                let x = this.indexX * CELL_WIDTH;
                let y = this.indexY * CELL_HEIGHT;
                ok &= x <= p.mouseX && p.mouseX < x + CELL_WIDTH;
                ok &= y <= p.mouseY && p.mouseY < y + CELL_HEIGHT;
                if (ok) {
                    this.isAlive = !this.isAlive;
                    this.throttleFrame = 0;
                }
            }
            this.throttleFrame++;
        }
        draw() {
            let centerX = (this.indexX + 0.5) * CELL_WIDTH;
            let centerY = (this.indexY + 0.5) * CELL_HEIGHT;
            let img = this.isAlive ? dmanImage : gopherImage;
            p.image(img, centerX, centerY);
        }
    }

    function getRandomCells() {
        return Array.from(
            {length: CELL_NUM_X},
            (_, x) => Array.from(
                {length: CELL_NUM_Y},
                (_, y) => new Cell(x, y, Math.random() < 0.5)
            )
        );
    }

    function hasNoize() {
        return noizeCheckBox.checked;
    }

    function next(grid) {
        return grid.map(
            cells => cells.map(
                cell => nextCell(cell, grid)
            )
        );
    }

    function nextCell(cell, grid) {
        const dx = [-1, -1, -1,  0,  0,  0,  1,  1,  1];
        const dy = [-1,  0,  1, -1,  0,  1, -1,  0,  1];
        const getX = i => (cell.indexX + dx[i] + CELL_NUM_X) % CELL_NUM_X;
        const getY = i => (cell.indexY + dy[i] + CELL_NUM_Y) % CELL_NUM_Y;
        const cnt = iota(9).map(
            i => grid[getX(i)][getY(i)]
        ).filter(
            c => c.isAlive
        ).length;
        let isAlive = cnt > 4;
        if (hasNoize() && (cnt == 4 || cnt == 5)) {
            isAlive = !isAlive;
        }
        return new Cell(cell.indexX, cell.indexY, isAlive);
    }

    function drawBackground() {
        p.noStroke();
        p.fill(40, 170, 110, 5);
        p.rect(0, 0, p.width, p.height);
    }

    let timeBySlider = 0.0;
    function shouldNext() {
        let ok = fpsSlider.value > fpsSlider.min && timeBySlider>=1.0;
        if (ok) timeBySlider -= 1.0;
        timeBySlider += 1.0/(fpsSlider.max - fpsSlider.min)*(fpsSlider.value);
        return ok;
    }

    let grid;

    function randomize() {
        grid = getRandomCells();
    }

    p.preload = () => {
        dmanImage = p.loadImage("img/dman.gif");
        gopherImage = p.loadImage("img/gopher.gif");
    };

    p.setup = () => {
        p.imageMode(p.CENTER);
        p.createCanvas(CANVAS_WIDTH, CANVAS_HEIGHT);
        p.background(40, 170, 110);
        dmanImage.resize(DMAN_SIZE, DMAN_SIZE);
        gopherImage.resize(GOPHER_SIZE, GOPHER_SIZE);
        randomize();
    };

    p.draw = () => {
        updateFpsText();
        drawBackground();
        if (shouldNext()) {
            grid = next(grid);
        }
        grid.forEach(cells => cells.forEach(cell => cell.step()));
        grid.forEach(cells => cells.forEach(cell => cell.draw()));
    };

    randomButton.onclick = () => randomize();
};

const app = new p5(sketch, document.querySelector("#sketch"));

参考

この本、いい本なのでもっと広まってほしい。