「ずれたセルオートマトン・パスカルの三角形・フラクタル」

はじめに

ブログの背景(PC版)をライフゲームにしているにも関わらずそっち系の記事がまだなかったので、今日は「セルオートマトン」なるものの新しい例を提案したり、フラクタル図形との関連について書いてみます。

この記事では、「パスカルの三角形」と呼ばれるものを塗り分けることで「フラクタル」な形状が表れるというよく知られた事実を最初に紹介します。その形状と似てるけれど少し違うものが「セルオートマトン」によってできることも紹介し、それでは不満なのでその形状を忠実に再現する「ちょっとずれたセルオートマトン」を提案してみます*1。

パスカルの三角形やセルオートマトンをご存知なら「ちょっとずれたセルオートマトン」の章から読めば十分かと思います。

パスカルの三角形

パスカルの三角形とは、二項係数を以下のように三角に並べたものです。

↑ Wikipedia(パスカルの三角形 - Wikipedia)より。

二項係数の計算方法を知らなくても、以下の単純な方法によってつくることができます。

最上段に1を配置する。それより下の行はその位置の右上の数と左上の数の和を配置する。
パスカルの三角形 - Wikipedia

この説明を図にすると以下のようになります。

ここで興味深いのは、パスカルの三角形に登場する奇数と偶数を黒と白で塗り分けると以下のようなパターンが表れるということです。

三角形を大きくしていくと、以下のようになります。

これはシェルピンスキーのギャスケットと呼ばれ、自分自身がその一部と相似形をなす自己相似的な図形（フラクタル図形）となっています。おもしろいですね。

シェルピンスキーのギャスケット - Wikipedia

ふつうのセルオートマトン

先ほどの「シェルピンスキーのギャスケット」のような形は、1次元セルオートマトンと呼ばれるものによっても描くことができます。

まず、直線上にマス目（セルと呼びます）が並んでいて、それぞれのセルは1か0の状態を持つとします。

そして、次の時間にそれぞれのセルは自分自身の状態と左右の状態に応じて状態を更新します。時刻t+1の状態は、時刻tの状態の下段に描いてゆきます。

そのような更新ルールは、以下の8通りの周囲環境において下図の「?」で示した所に0と1のどちらをいれるかということで指定できます。

ルールは256通り考えられますが、そのうちのルール90と呼ばれるルールを採用し、真ん中に「1」が一つだけポツンと存在する初期状態からスタートすると以下のようになります。

（↑：http://www.wolframalpha.com/input/?i=rule+90より。）

これはシェルピンスキーのギャスケットですね！

ちょっとずれたセルオートマトン

動機

ここまでで、パスカルの三角形からでもセルオートマトンからでもシェルピンスキーのギャスケットが描けることが分かりました。
でも、よく見てみるとそれらは微妙に異なります。下図をみてください。

どちらもシェルピンスキーのギャスケットと呼べるものですが、細かく見るとその構造が微妙に異なりますよね？

その理由は、マス目の並びかたが以下のように異なるところにあります。左側がパスカルの三角形に用いたマス目・右側がセルオートマトンに用いたマス目です。左側は半分ずつずれていますね。

そこで、左側のようなずれたマス目上でもセルオートマトンができないか？と考えました。さらに、それによってパスカルの三角形で得られたのとまったく同じシェルピンスキーのギャスケットを描くことをめざします。

ルール

既に紹介したように、通常のセルオートマトンではそれぞれのセルが自分自身の状態と左右の状態に応じて状態を更新するのでした。その模式図は下図の左側です。
しかし、「ずれたマス目」を用いる場合には事情が異なります。ここでは、下図の右側のように斜め上2つの状態に応じて次の状態を決めることにしましょう。

状態更新方法については2^(2^2)=16通りが考えられるのですが、ここでは以下のようにします。これは、斜め上2つのセルの「排他的論理和(XOR)」に相当します。

どうしてこうするかというと、パスカルの三角形の偶数・奇数に関する以下のパターンを模すためです。

これにより、パスカルの三角形の偶奇を考えることは、上記ルールの「ずれたセルオートマトン」を考えることに帰着されます。わお！

結果

というわけで、上記のように新しく定義した「ずれたセルオートマトン」を実行してみます。初期状態は中心に「1」が1つだけ存在する状態としました。
これまでの記事と同様にHTML5 Canvasを用いましたが、動かしてもたいしておもしろくないので画像を以下に示します。プログラムは記事末尾にあるので自由にご利用ください。

このように、パスカルの三角形を偶奇で塗り分けたときのシェルピンスキーのギャスケットが完全に再現されました！

おわりに

この記事では「ずれたセルオートマトン」を新しく定義しました。
排他的論理和に相当するルールを採用することでシェルピンスキーのギャスケットが描けましたが、他にも様々なルールが考えられるので、今後試してみるかもしれません。

↓ ずれたマス目上のセルオートマトンを可視化するプログラム。自由にご利用ください。

<canvas id="a_canvas" width="400" height="400"></canvas>
<script type="text/javascript">
var canvas = document.getElementById("a_canvas");
var ctx = canvas.getContext("2d");
canvas.width = 400;
canvas.height = 400;
// variables
var cell_size = 10;
var board = new Array();
var step = 0;

// 実行
init();
ctx.strokeStyle = "rgb(100, 100, 100)";// gray
draw_grid();
draw_cell();
for (var t=0; t<40; t++){
    update();
}
//------------- 関数 -------------------//
// init board
function init(){
    var i, j;
    for (i=0; i<(canvas.height/cell_size); i++){
        board[i] = new Array();
        for (j=0; j<(canvas.width/cell_size); j++){
            board[i][j] = 0;
        }
    }
    board[0][(canvas.width/cell_size)/2] = 1;
}
// (x1, y1)から(x2, y2)に太さwの線を引く関数
function draw_line(x1, y1, x2, y2, w){
    ctx.lineWidth = w;
    ctx.beginPath();
    ctx.moveTo(x1, y1);
    ctx.lineTo(x2, y2);
    ctx.closePath();
    ctx.stroke();
}
function draw_cell(){
    var i, j;
    for (i=0; i<(canvas.height/cell_size); i++){
        for (j=0; j<(canvas.width/cell_size); j++){
            if (board[i][j] === 1){
                // 黒に塗る
                ctx.fillStyle = "rgb(20, 20, 20)";
                // ずれを考慮
                if (i%2 === 0){
                    ctx.fillRect(cell_size*j, cell_size*i,
                                 cell_size, cell_size);
                }else{
                    ctx.fillRect(cell_size*(j+0.5), cell_size*i, 
                                 cell_size, cell_size);
                }
            }
        }
    }    
}
// 枠線を描画する関数
function draw_grid(){
    var i, j;
    for (i=0; i<(canvas.height/cell_size); i++){
        // 横線
        draw_line(0, i*cell_size, canvas.width, i*cell_size, 0.5);
        // 縦線
        if (i%2 === 0){
            for (j=0; j<(canvas.width/cell_size)+1; j++){
                draw_line(j*cell_size, i*cell_size, 
                          j*cell_size, (i+1)*cell_size, 0.5);
            }
        }else{
            for (j=0; j<(canvas.width/cell_size); j++){
                draw_line((j+0.5)*cell_size, i*cell_size, 
                          (j+0.5)*cell_size, (i+1)*cell_size, 0.5);
            }
        }
    }
}
// board[step][*]をもとにboard[step+1][*]をつくる関数
function update(){
    var i;
    if (step%2 === 0){
        for (i=0; i<canvas.width/cell_size-1; i++){
            if ((board[step][i]===0 && board[step][i+1] == 1) || 
                (board[step][i]==1 && board[step][i+1] === 0)){
                board[step+1][i] = 1;
            }else{
                board[step+1][i] = 0;
            }
        }
    }else{
        for (i=1; i<canvas.width/cell_size-1; i++){
            if ((board[step][i]===0 && board[step][i-1] == 1) || 
                (board[step][i]==1 && board[step][i-1] === 0)){
                board[step+1][i] = 1;
            }else{
                board[step+1][i] = 0;
            }
        }        
    }
    step++;
    draw_cell();
}
</script>

*1:素人ですし、調査したわけでもないので、もしかしたら全然新しくないかもしれないです。