こんにちは。
今回は「セル･オートマトン」について書いてみます。
セル･オートマトンとは
セル･オートマトンは、格子状の「セル」を並べ、近接したセル間で「規則」を適用することでできるモデルで、簡単な割にいろいろなことをシミュレートできて有用だそうです。
言葉で言われても分かりづらいので例を見ていきましょう。
今回は、いろいろなセル･オートマトンをつくって遊んでみたいと思います。
一次元
ウルフラムコード
まずは「ウルフラムコード」です。
（「ウルフラムコード」は規則の呼び名ですが、モデル自体は「一次元のセル･オートマトンのひとつ」といった感じで分かりにくいので、そうと呼ぶことにしました。）
規則
ウルフラムコードでは、あるセルの両隣の状態によって次のステップでのそのセルの状態を決めます。
例えば、「ルール30」と呼ばれるものでは、
あるセルが「1」のとき、
両隣が「1」ならば、次のステップでは「0」
左隣が「1」、右隣が「0」ならば、次のステップでは「0」
左隣が「0」、右隣が「1」ならば、次のステップでは「1」
両隣が「0」ならば、次のステップでは「1」
あるセルが「0」のとき、
両隣が「1」ならば、次のステップでは「0」
左隣が「1」、右隣が「0」ならば、次のステップでは「1」
左隣が「0」、右隣が「1」ならば、次のステップでは「1」
両隣が「0」ならば、次のステップでは「0」
というように決めていきます。
具体的に言えば、初めに
0001000
という状態であったとすると、ステップを経るに従って、
0001000 ↓ 0011100 ↓ 0110010 ↓ 1101111 ↓ …
というように変化していくことになります。
（両端の状態は常に「0」としています。）
そして、「1」を黒いセル、「0」を白いセルと対応させて、より長い文字列で考えると以下の図のようになります。
（一番上の行が最初の文字列で、そこから下に行くに従ってステップが増えていっています。）
ちなみに、もっと長い文字列で描画すると、「イモガイ」という貝の模様に似たような図になります。
さて、「あるセルが「1」のとき、両隣が「1」ならば、次のステップでは「0」」という規則は、「111」が「0」に対応することと等しいと言えます。
他の条件も同様に考えて表にまとめると、
現在の状態 : 111 110 101 100 011 010 001 000 次のステップ : 0 0 0 1 1 1 1 0
ここで、下の数列「00011110」を二進数と考えると、十進数では「30」と表され、これがウルフラムコードの中で「ルール30」と呼ばれている理由です。
なので、ウルフラムコードでの「規則」は$2^{8} = 256$種類あることになります。
ちなみに、「ルール90」は「シェルピンスキーのギャスケット」というフラクタルと同じような形になります。
コード
int len; int col, row; int[][] c; int j = 0; int[] rule = new int[8]; void setup(){ size(1000, 500); len = 5; //1セルの大きさ col = width/len; //セルの列数 row = height/len; //セルの行数 c = new int[col][row]; //最初の文字列の指定 c[col/2][0] = 1; //真ん中のみに「1」 /* for(int i = 0; i < col; i ++){ c[i][0] = floor(random(2)); //ランダム } */ int ruleNumber = 30; //規則の指定（0~255） //数字から規則へ変換 String b = binary(ruleNumber); //二進数に変換 String[] r = b.split("", b.length()); //1文字ずつに分ける for(int i = 0; i < 8; i ++){ rule[i] = int(r[i+24]); //最後の8文字だけ取り出す } // } void draw(){ background(255); //セルの描画 for(int i = 0; i < col; i ++){ for(int j = 0; j < row; j ++){ stroke(255); fill((1-c[i][j])*255); rect(i*len, j*len, len, len); } } // //次のステップでの文字列を計算 int[][] next = new int[col][row]; //次のステップでの文字列を格納 for(int i = 1; i < col-1; i ++){ if(c[i][j] == 0){ //ある文字列が「0」のとき if(c[i-1][j] == 0 && c[i+1][j] == 0){ //両端が0ならば next[i][j] = rule[7]; //規則の配列の8番目を取り出す } //以下同様 else if(c[i-1][j] == 0 && c[i+1][j] == 1){ next[i][j] = rule[6]; } else if(c[i-1][j] == 1 && c[i+1][j] == 0){ next[i][j] = rule[3]; } else if(c[i-1][j] == 1 && c[i+1][j] == 1){ next[i][j] = rule[2]; } } else if(c[i][j] == 1){ if(c[i-1][j] == 0 && c[i+1][j] == 0){ next[i][j] = rule[5]; } else if(c[i-1][j] == 0 && c[i+1][j] == 1){ next[i][j] = rule[4]; } else if(c[i-1][j] == 1 && c[i+1][j] == 0){ next[i][j] = rule[1]; } else if(c[i-1][j] == 1 && c[i+1][j] == 1){ next[i][j] = rule[0]; } } c[i][j+1] = next[i][j]; //計算した文字列を適用する } // j ++; //ステップを進める if(j == row-1){ //一番下まで来たら noLoop(); //止める } }
まずは、ウルフラムコードのどれを適用するかをruleNumberで指定します。
現在の状態 : 111 110 101 100 011 010 001 000 次のステップ : 0 0 0 1 1 1 1 0
から、適用すべきルールとruleNumberとの関係が分かっているので、先程やったのと逆の手順で「次のステップ」部分の数列をつくり、rule[]に格納します。
そして、それをrule[0]~rule[7]で適当なところで呼び出して、ルールを適用するようにしています。
実行すると、
二次元
ライフゲーム
セル･オートマトンの中で一番有名なものがこれでしょう。
規則
ウルフラムコードではあるセルの両隣で考えましたが、ライフゲームではあるセルの周囲8マスで考えます。
規則としては、
そのセルが死んでいるとき、
周囲8マスに生きているセルが3つあれば、次の世代が誕生する
（他の場合はそのまま）
そのセルが生きているとき、
周囲8マスに生きているセルが2つか3つあれば、そのまま生きている
（他の場合は死ぬ）
wikipediaには「過疎」と「過密」の規則もありますが、今回のやり方では必要ないので省きました。
コード
int len; int col, row; int[][] c; boolean pause = false; int n = 0; void setup(){ size(750, 750); len = 10; col = width/len; row = height/len; c = new int[col][row]; //最初の配置 for(int i = 0; i < col; i ++){ for(int j = 0; j < row; j ++){ //c[i][j] = 0; //生命無し c[i][j] = floor(random(2)); //ランダム } } } void draw(){ background(255); //セルの描画 for(int i = 0; i < col; i ++){ for(int j = 0; j < row; j ++){ stroke(230); fill((1-c[i][j])*255); rect(i*len, j*len, len, len); } } // //生命を置く位置のプレビュー if(pause == true){ //描画が止まっているとき int[][] pre = new int[col][row]; //プレビュー用の盤面 for(int i = 0; i < col; i ++){ for(int j = 0; j < row; j ++){ pre[i][j] = 0; //初期化 if(i*len <= mouseX && mouseX < (i+1)*len && j*len <= mouseY && mouseY < (j+1)*len){ //マウスのある位置(i,j)に pre[i][j] = 1; //生命を置く } if(pre[i][j] == 1){ //位置(i,j)に生命があれば fill(255, 0, 0); //赤色に noStroke(); //線なし ellipse(len/2+i*len, len/2+j*len, len, len); //円を描く } } } } // //生命を置いたり消したりする「ペン」 if(pause == true){ for(int i = 0; i < col; i ++){ for(int j = 0; j < row; j ++){ if(i*len <= mouseX && mouseX < (i+1)*len && j*len <= mouseY && mouseY < (j+1)*len){ if(mousePressed == true){ if(mouseButton == LEFT){ //左クリックで c[i][j] = 1; //生命を置く } if(mouseButton == RIGHT){ //右クリックで c[i][j] = 0; //生命を消す } } } } } } // //次のステップでの生命の配置を計算 if(pause == false){ //描画が動いているとき int[][] next = new int[col][row]; for(int i = 1; i < col-1; i ++){ for(int j = 1; j < row-1; j ++){ //周囲8マスの生きているセルの数を計算 int neighbors = c[i-1][j-1] + c[i][j-1] + c[i+1][j-1] + c[i-1][j] + c[i+1][j] + c[i-1][j+1] + c[i][j+1] + c[i+1][j+1]; if(c[i][j] == 0){ //あるセルが生きているとき if(neighbors == 3){ //周囲の生きたセル3つなら next[i][j] = 1; //生命の誕生 } } //以下同様 else if(c[i][j] == 1){ if(neighbors == 2 || neighbors == 3){ //生存 next[i][j] = 1; } /* //以下は必要ないが、一応 else if(neighbors <= 1){ //過疎 next[i][j] = 0; } else if(neighbors >= 4){ //過密 next[i][j] = 0; } */ } } } c = next; //次のステップの配置を適用 } } void keyPressed(){ //「s」キーでポーズする if(key == 's') pause = true; //「c」キーで画面の初期化 if(key == 'c'){ for(int i = 0; i < col; i ++){ for(int j = 0; j < row; j ++){ c[i][j] = 0; } } } } void keyReleased(){ //「s」キーが離されたらポーズを解除 if(key == 's') pause = false; }
やっていることはウルフラムコードと似ています。
初期値の設定、画面の描画、次ステップの計算･適用、という流れです。
「過疎」と「過密」が必要ないといったのは、nextの計算が全て「0」の盤面をつくっていおいて「1」になる部分がどこかを計算する、という方法で行っているためです。
「s」キーを押しながら画面上をドラッグすることで生命を置くことができ、「s」キーを離せばライフゲームが始まります。
実行すると、
このコードではいちばん外側の1セル分は常に"死んだ"状態になっていまが、境界条件によってはループさせることもできます。
ラングトンのアリ
「粉遊び」というブラウザゲームをご存じでしょうか。
その中にある「ANT」が（全く同じではないと思いますが）これと似たような動きをします。
規則
ラングトンのアリでは、アリのいる位置の状態のみを考えます。
アリのいるセルが「0」の場合、そのマスを「1」にし、90°右を向き、1マス進む アリのいるセルが「1」の場合、そのマスを「0」にし、90°左を向き、1マス進む
これだけ単純でありながら、描く図はなかなか複雑になります。
コード
int len; int col, row; int[][] c; int ai, aj; int angle; void setup(){ size(600, 600); frameRate(10000); len = 5; col = width/len; row = height/len; //盤面の設定 c = new int[col][row]; for(int i = 0; i < col; i ++){ for(int j = 0; j < row; j ++){ c[i][j] = 0; //全て「0」 } } //アリの位置と向きの指定 ai = col/2; aj = row/2; angle = 0; } void draw(){ background(255); //セルの描画 for(int i = 0; i < col; i ++){ for(int j = 0; j < row; j ++){ stroke(230); fill((1-c[i][j])*255); rect(i*len, j*len, len, len); } } // //アリの描画 noStroke(); fill(255, 0, 0); ellipse(len/2+ai*len, len/2+aj*len, len, len); // //次のステップでの位置と向きを計算 if(angle % 4 == 0){ //右を向いているとき if(c[ai][aj] == 0){ //アリの位置が「0」なら c[ai][aj] = 1; //「1」に変える angle ++; //90°右を向く aj ++; //1マス進む } else if(c[ai][aj] == 1){ //アリの位置が「1」なら c[ai][aj] = 0; //「0」に変える angle --; //90°左を向く aj --; //1マス進む } } //以下同様 else if(angle % 4 == 1){ //下を向いているとき if(c[ai][aj] == 0){ c[ai][aj] = 1; angle ++; ai --; } else if(c[ai][aj] == 1){ c[ai][aj] = 0; angle --; ai ++; } } else if(angle % 4 == 2){ //左を向いているとき if(c[ai][aj] == 0){ c[ai][aj] = 1; angle ++; aj --; } else if(c[ai][aj] == 1){ c[ai][aj] = 0; angle --; aj ++; } } else if(angle % 4 == 3){ //上を向いているとき if(c[ai][aj] == 0){ c[ai][aj] = 1; angle ++; ai ++; } else if(c[ai][aj] == 1){ c[ai][aj] = 0; angle --; ai --; } } // //境界条件 if(ai > col-1){ ai = 0; } if(aj > row-1){ aj = 0; } if(ai < 0){ ai = col-1; } if(aj < 0){ aj = row-1; } // }
次のステップでの状態を計算する部分では、面倒な感じになっています。
angleを4で割った余りによって場合分けをしており、0、1、2、3それぞれを右、下、左、上に対応させています。
そしてそれぞれの向きのときに、右･左に対応する方向にaiやajを動かして曲がった判定にするようにしました。
もっとスマートなやり方があるでしょうが、それは思いついたときにでも追記しておくことにします。
実行すると、
描画するステップ数とファイルサイズとの兼ね合いでえらい速いですが、アリが上記の規則に従って動き、蟻の巣のような雲のような図を描いていきます。
ちなみに、アリの描画の部分で、
ellipse(len/2+ai*len, len/2+aj*len, len, len);
を
float r = len/3; pushMatrix(); translate(ai*len+len/2, aj*len+len/2); rotate(angle*radians(90)); beginShape(); vertex(-r, -r); vertex(-r, +r); vertex(2*r, 0); endShape(); popMatrix();
などと、angleに応じて向きが変わるような図形で描画するようにすれば、angleの変化を可視化させることができます。
森林火災
先程紹介した「粉遊び」で「VINE」を燃やしたときに似たような挙動をとります。
規則
森林火災では、これまでと似てはいますが、確率が関わってきます。
あるセルが空き地のとき、確率pで新たな木が生える
あるセルが木のとき、
確率qで発火する
周囲8マスに火が1つでもあれば、確率rで燃え移る
あるセルが燃えているとき、燃えつきて空き地になる
以下では、0、1、2をそれぞれ空き地、木、火に対応させています。
コード
int len; int col, row; int[][] c; void setup(){ size(750, 750); frameRate(10); len = 10; col = width/len; row = height/len; //初期値の設定 c = new int[col][row]; for(int i = 0; i < col; i ++){ for(int j = 0; j < row; j ++){ c[i][j] = 1; //全て木 } } } void draw(){ background(255); //セルの描画 for(int i = 0; i < col; i ++){ for(int j = 0; j < row; j ++){ stroke(230); if(c[i][j] == 0){ //空き地 fill(255); } else if(c[i][j] == 1){ //木 fill(0, 255, 0); } else if(c[i][j] == 2){ //火 fill(255, 0, 0); } rect(i*len, j*len, len, len); } } // //次のステップでの状態を計算 int[][] next = new int[col][row]; for(int i = 1; i < col-1; i ++){ for(int j = 1; j < row-1; j ++){ if(c[i][j] == 0){ //空き地のとき float p = random(1); if(p <= 0.001){ //0.1%の確率で next[i][j] = 1; //木が生える } } else if(c[i][j] == 1){ //木のとき float q = random(1); if(q <= 0.00001){ //0.001%の確率で next[i][j] = 2; //出火する } else{ //99.999%の確率で next[i][j] = 1; //そのまま } //周囲8マスの1つでも燃えているとき if(c[i-1][j-1] == 2 || c[i][j-1] == 2 || c[i+1][j-1] == 2 || c[i-1][j] == 2 || c[i+1][j] == 2 || c[i-1][j+1] == 2 || c[i][j+1] == 2 || c[i+1][j+1] == 2){ float r = random(1); if(r <= 0.3){ //30%の確率で next[i][j] = 2; //延焼する } else{ //70%の確率で next[i][j] = 1; //そのまま } } } /* else if(c[i][j] == 2){ //火のとき next[i][j] = 0; //消える } */ } } c = next; 次のステップの状態を適用 // }
確率は適当に設定しました。
また、火が消える条件は、ライフゲームのときの「過疎」「過密」のときと同じ理由で省略可能です。
実行すると、
森の中に突然火が出て延焼していく様子が見えます。
そして燃えたところは空き地になって、またポツポツ木が生えてきています。
確率p、q、rを変えればまた違った様子になります。
チューリングパターン
周りの状態に影響されてあるセルでの状態が決まるという点では、以前つくった「チューリングパターン」もセル･オートマトンと言えます。
詳しくは以下の記事を参照してください。
まとめ
以上で、いろいろなセル･オートマトンをつくることができました。
いくつもあって難しいと思うかもしれませんが、基本は「初期値の設定→画面の描画→次ステップの計算･適用」という流れです。 「次のステップの計算」の部分が規則にあたり、そこを変えることでいろいろなセル･オートマトンを実装することができます。
自分なりに規則をつくってみたり、初期条件を変えてみたりしてセル･オートマトンを実行するとまた面白いかと思います。
