吉本集の個人ブログ
Web制作の技術について書いています。たまに日記も書きます。

セル・オートマトンとは

2014年5月10日 / category : lab, processing

ある参考書に「セル・オートマトン」について書かれていたので、調べてみた。
wiki : セル・オートマトン
簡単に言うと、
規則的に並んだセルの集合体で、隣接しているセルによって影響し合い、あるパターンによりモデル化される現象・・・な感じです。
と、言ってもよくわからないと思うので、次にDEMOを作ったので、見てみてください。

DEMO : ルール90による1次元セル・オートマトン

確かに、規則的にセルが配置されているように見えますよね。
これが、セル・オートマトンの例です。
で、これがどんな仕組みで作られているか、というのが今回ブログの記事としてメモしておきたかったことです。
まず、セルを次の2種類とします。

【セルの種類】
1 → 状態 : 1 / 色 : 黒 / サイズ : 2px × 2px
2 → 状態 : 0 / 色 : 白 / サイズ : 2px × 2px

次に、先ほどの簡単な説明の中に、「隣接しているセルによって影響し合い」とありました。隣接しているセル同士が影響し合い変化していきます。その影響する変化にルールを決めます。
まず、隣接しているセルのパターンは次の8パターンとなります。

□□□ / □□■ / □■□ / □■■ / ■□□ / ■□■ / ■■□ / ■■■

上のパターンから、真ん中のセルが、両隣のセルがどういう状態の時、どう変化するかのルールを決めます。
例えば、次のようなルールにするとします。

□□□ → □(両隣のセルが白(0)の場合、真ん中のセルは、白(0)となる。)
□□■ → ■
□■□ → ■
□■■ → ■
■□□ → ■
■□■ → □
■■□ → □
■■■ → □

上のルールには、実は有名なルールのようで、「ルール30」と名前がつけられています。
このルールによって作られるセル・オートマトンは、次のようになります。

DEMO : ルール30による1次元セル・オートマトン

他にも、「ルール110」と呼ばれているルールがあります。

□□□ → □
□□■ → ■
□■□ → ■
□■■ → ■
■□□ → □
■□■ → ■
■■□ → ■
■■■ → □

このルールによって作られるセル・オートマトンは、次のようになります。

DEMO : ルール110による1次元セル・オートマトン

次に、プログラムの考え方ですが、
まず、隣接しているセルのパターンを数値に置き換えます。

【色】
□□□ / □□■ / □■□ / □■■ / ■□□ / ■□■ / ■■□ / ■■■

【数値】
000 / 001 / 010 / 011 / 100 / 101 / 110 / 111

このパターンを数値化したものを2進法と考え、10進法に変更してみます。

2進法 → 10進法
000 → 0*4 + 0*2 + 0*1 = 0
001 → 0*4 + 0*2 + 1*1 = 1
010 → 0*4 + 1*2 + 0*1 = 2
011 → 0*4 + 1*2 + 1*1 = 3
100 → 1*4 + 0*2 + 0*1 = 4
101 → 1*4 + 0*2 + 1*1 = 5
110 → 1*4 + 1*2 + 0*1 = 6
111 → 1*4 + 1*2 + 1*1 = 7

【数値(10進法)】
0 / 1 / 2 / 3 / 4 / 5 / 6 / 7

この数値を配列のインデックスとして使用することで、ルールと紐づけることができます。
「ルール30」を例にすると、次のような配列を作ることができます。

var rule = [0,1,1,1,1,0,0,0]

ここまでできれば、プログラムにできそうですね。
例えば、ステージサイズが14pxだとして、セルのサイズが2pxだとすると、横一列に、7個のセルが並ぶことになります。

□□□■□□□

このセルを配列に置き換えると、次のようになります。

var cells = [0,0,0,1,0,0,0]

隣接しているセル同士が影響し合った変化を2列目に描画することにします。
また、「隣接しているセルによって影響し合い」というルールなので、最初のセルの左側にも、セルがなければいけませんので、この場合は、配列の最後のセルを参照することにします。
逆に、最後のセルも、右側のセルがないので、配列の最初のセルを参照することにします。
隣接しているセル同士の参照は次のようになります。

cells[0] → cells[6] cells[0] cells[1]
cells[1] → cells[0] cells[1] cells[2]
.
.
.
cells[6] → cells[5] cells[6] cells[0]

上の配列で参照しているものを配列に格納されている数値に置き換えると、次のようになります。

cells[0] → 000
cells[1] → 000
cells[2] → 001
cells[3] → 010
cells[4] → 100
cells[5] → 000
cells[6] → 000

上の数値を2進法と考え、10進法に変更してみます。

cells[0] → 0
cells[1] → 0
cells[2] → 1
cells[3] → 2
cells[4] → 4
cells[5] → 0
cells[6] → 0

この数値を「ルール30」のインデックスとして置き換えてみます。

cells[0] → rule[0] → 0
cells[1] → rule[0] → 0
cells[2] → rule[1] → 1
cells[3] → rule[2] → 1
cells[4] → rule[4] → 1
cells[5] → rule[0] → 0
cells[6] → rule[0] → 0

結果は次のようになります。

cells = [0,0,1,1,1,0,0]

この結果を、色に置き換えます。

□□■■■□□

そして、この変化の結果を、2列目に描画すると、次のようになります。

□□□■□□□
□□■■■□□

この描画を繰り返していくと、「規則的に並んだセルの集合体で、隣接しているセルによって影響し合い、あるパターンによりモデル化される現象」となり、これをセル・オートマトンと呼びます。