1次元セル・オートマトンって？
まず、セル・オートマトンとは格子状のセルの状態を、ルールに従って変化させることによる様々なことに応用可能なモデルです。例えば、コンウェイのライフゲームもその一例ですが、ライフゲームは2次元です。
例えばライフゲームでは各セルが隣接する8セル+自己の合計9セルの状態に応じて次のセルの状態を決定します。
同様に、1次元セル・オートマトンでは各セルが隣接する2セル+自己の合計3セルの状態に応じて次のセルの状態を決定します。
ルール90を例にとって解説します。
| 現在の状態 | 中央のセルの次の状態 |
|---|---|
| off,off,off | off |
| off,off,on | on |
| off,on,off | off |
| off,on,on | on |
| on,off,off | on |
| on,off,on | off |
| on,on,off | on |
| on,on,on | off |
以上がルール90です。
例えば、第一世代が以下のような状態であったとしましょう。
第1世代 : off,off,off,off,off,on,off,off,off,off,off
先程のルールに従うと以下のように世代が進んでいくとよいです。
第1世代 : off,off,off,off,off,on,off,off,off,off,off
第2世代 : off,off,off,off,on,off,on,off,off,off,off
第3世代 : off,off,off,on,off,off,off,on,off,off,off
第4世代 : off,off,on,off,on,off,on,off,on,off,off
第5世代 : off,on,off,off,off,off,off,off,off,on,off
これを、横幅を40セル、20世代で行って、onを黒、offを白として画像にするとこうなります。
もっと大きなサイズ、沢山の世代数でやってみるとこうなります。
実際に作る
言語選び
言語は、JavaScriptにしました。理由は、ライブラリ無しでも描画周りが直感的にいじれるからです。
こんなかんじにファイルを置いておきます。
CA/
┣ca.html
┗script.js
HTML
HTMLの方はは以下のように、canvasを置いておきます。
<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="UTF-8">
<title>1次元セル・オートマトン</title>
<script src="script.js"></script>
</head>
<body>
<canvas id="cvs"></canvas>
</body>
</html>
どう実装するか
以下のような真偽値をセルの状態に見立てます。以下のような配列を作ります。
[false,false,false,false,false,true,false,false,false,false,false,]
さて、各セルの周囲2マス+自己の計3セルとルールをどう照らし合わせるか考えていましたが、3セルの状態を2進数の桁に見立てたら、0~7の数値で表せます。逆に、0~7の整数は2進数にすると、3セルの状態のすべての状態を表すことができます。
| 10進数 | 2進数 |
|---|---|
| 0 | 000 |
| 1 | 001 |
| 2 | 010 |
| 3 | 011 |
| 4 | 100 |
| 5 | 101 |
| 6 | 110 |
| 7 | 111 |
これを、利用すると、以下のような関数を作ることができます。
const compareAroundCells = function(cells, rules, x) {
let count = 0;
for (let i = -1; i < 2; i++) {
if (cells[i + x]) {
count += 2 ** (1 - i);
}
}
return rules[count];
}
//テスト
let rules = [false, true, false, true, true, false, true, false]
//ルールを配列で表している。左から順に2進数で表したときの3セルの状態(0b000~0b111)と対応している。↑
let cells = [false, false, false, false, false, true, false, false, false, false, false, ]
console.log(compareAroundCells(cells, rules, 6));
//結果:true
これを各セルに実行して、次の世代に移行すれば、よいわけです。
const compareAroundCells = function(cells, rules, x) {/*省略*/}
let getNextCells = function(cells, rules) {
let nextCells = new Array(cells.length);
for (let x = 0; x < cells.length; x++) {
nextCells[x] = compareAroundCells(cells, rules, x);
}
return nextCells;
}
//テストしてみる
let rules = [false, true, false, true, true, false, true, false]
let cells = [false, false, false, false, false, true, false, false, false, false, false]
console.log(getNextCells(cells, rules));
//結果:[false, false, false, false, true, false, true, false, false, false, false]
いい感じですね。これをつかって繰り返し世代を更新。描画を繰り返していけばさっきのような画像になります。どうせならもっとでかいサイズでやりたいので、セルの数を101、世代数を50とします。
完成！
const compareAroundCells = function(cells, rules, x) {
let count = 0;
for (let i = -1; i < 2; i++) {
if (cells[i + x]) {
count += 2 ** (1 - i);
}
}
return rules[count];
}
//
let getNextCells = function(cells, rules) {
let nextCells = new Array(cells.length);
for (let x = 0; x < cells.length; x++) {
nextCells[x] = compareAroundCells(cells, rules, x);
}
return nextCells;
}
const RULES = [false, true, false, true, true, false, true, false];
const GENERATIONS = 50; //世代数
const NUM_OF_CELLS = 101; //セルの数
let cells = new Array(NUM_OF_CELLS)
for (let x = 0; x < NUM_OF_CELLS; x++) {
cells[x] = x == Math.floor(NUM_OF_CELLS / 2);
}
const CELL_SIZE = 4; //描画時のセルの大きさ
window.onload = function() {
const cvs = document.getElementById("cvs");
const ctx = cvs.getContext("2d");
cvs.width = NUM_OF_CELLS * CELL_SIZE;
cvs.height = GENERATIONS * CELL_SIZE;
const drawCell = function(x, y, cellSize, color) {
ctx.fillStyle = color;
ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
}
for (let t = 0; t < GENERATIONS; t++) { //世代を更新しながら描画する
for (let x = 0; x < cells.length; x++) { drawCell(x, t, CELL_SIZE, (cells[x]) ? "black" : "white") };
let nextCells = getNextCells(cells, RULES);
for (let x = 0; x < cells.length; x++) { cells[x] = nextCells[x]; };
}
}
以下のような結果が得られます。
やってみた感想
各セルを周囲のセルと照らし合わせる処理の実装にはだいぶ困りました。
各セルを周囲のセルと照らし合わせるのに、周囲のセルの状態を2進数の桁に見立てるアイデアは、学校で休み時間にひらめいて「これだ！！」と思いました。
それ以外はさくっと実装できました。