トップ言語処理 > 一次元セル・オートマトン

演習6.一次元セル・オートマトン

この演習では、オートマトンの例として、 人工生命の分野では有名な一次元セル・オートマトン(cellular automaton)を取り上げる。 セルは細胞、小さな箱を表す。

1.セル・オートマトン

有限の状態を持つセルによって、セル・オートマトンは構成され、離散的な時間で変化する。 その変化は、ある時刻 t においてのそのセル自身の状態、および近傍のセルの状態によって、 次の時刻 t + 1 、すなわち新たな世代(generation)での各セルの状態が決定される。

2.一次元セル・オートマトン

一次元セル・オートマトンはひも状のものであり、 セル・オートマトンの中で一番単純なものである。 あるセルに隣接するセルは左右の二つである。自分自身と左右の現在の状態から、次の世代の状態が決まる。

ルール30,90,110と呼ばれる2状態の一次元セル・オートマトンがよく知られている。 ルール30の規則は次のように表される。

ルール30
  時刻tでの内部状態(左、中央、右)     111 110 101 100 011 010 001 000
  時刻t+1での中央のセルの内部状態      0   0   0   1   1   1   1   0

次の状態の 2進数(0001 1110)は10進数では30となることからルール30と呼ばれる。

状態 0 を□、状態 1 を■で表す。時刻0での状態を
□□□□□□□□□□■□□□□□□□□□□ とすると、時刻1では
□□□□□□□□□■■■□□□□□□□□□となる。
すなわち、時間の経過によって状態が次のように変化する。

時刻0□□□□□□□□□□■□□□□□□□□□□
時刻1□□□□□□□□□■■■□□□□□□□□□
時刻2□□□□□□□□■■□□■□□□□□□□□
時刻3□□□□□□□■■□■■■■□□□□□□□
時刻4□□□□□□■■□□■□□□■□□□□□□

さらに、長時間これを繰り返した結果を下図に示す。この模様は右図の貝殻(イモ貝)に似ている。

 

参考文献 セル・オートマトン

3.一次元セル・オートマトンのプログラム

矩形領域の塗りつぶしではFillRect関数を用いたが、 画素単位の微細な描画では SetPixel関数を使う方が高速であり、プログラムも簡単になる。 色の指定方法は CreateBrush関数のときと同じである。

COLORREF SetPixel(
  HDC hdc,           // デバイスコンテキストのハンドル
  int X,             // ピクセルの x 座標
  int Y,             // ピクセルの y 座標
  COLORREF crColor   // ピクセルの色
);

描画関数paint自体は極めて簡単であり、次のようになる。

一方、init関数は予め画素データcell[IMAX][JMAX]を作っておくものである。 このような初期化は WindowProc関数で WM_CREATEメッセージを受けて、 ここからコールすることが多い。ウィンドウが生成されたとき一度だけ実行することとなる。

cellデータはウィンドウには一切依存していないため、 WinMain関数の先頭で呼び出し、実行しておいても問題はない。

ここで、末尾(右端)のセルcell[IMAX-1][n]の右隣は、 先頭(左端)のセルcell[0][n] と考える。同様に先頭(左端)の左は末尾(右端)と考える。

このような考え方は、プログラムの世界ではよくある話である。 if 文を使うのではなく、次のような剰余を求める方法を使う。

    int l = (j + length - 1) % length;  // left
    int r = (j + 1) % length;           // right
#define IMAX  200       // 行方向(Y軸)
#define JMAX  200       // 列方向(X軸)
int cell[IMAX][JMAX];
int rule[] = { 0, 0, 0, 1, 1, 1, 1, 0 }; // 上位ビットから

void paint(HWND hwnd){
    PAINTSTRUCT ps;
    HDC hdc = BeginPaint(hwnd, &ps);
    int i, j;
    for (i = 0; i < IMAX; i++){
        for (j = 0; j < JMAX; j++){
            if (cell[i][j] == 1) {
                 SetPixel(hdc, j, i, 0); // 最後の引数は色(この場合、黒)
            } // 座標(i,j) を左端として縦横1,1 の四角を描く
        }
    }
    EndPaint(hwnd, &ps);
}

void init() {
    int i, j;
    // 初期化
    cell[0][JMAX/2] = 1; // 第0行の中央のみ 1        
 
    // 計算
    for (i = 1; i < IMAX; i++){         // 第1行〜第(IMAX-1)行
        for (j = 0; j < JMAX; j++){     // 第0列〜第(JMAX-1)列
            int length = JMAX;
            int before = i - 1; // 一つ前の行

            // 両隣を決定
            int l = (j + length - 1) % length;  // left
            int c = j;                          // center
            int r = (j + 1) % length;           // right

            // コードを計算 code = 0 〜 7
            int code = cell[before][l] * 4
                     + cell[before][c] * 2
                     + cell[before][r] * 1;
            // セルの状態をセット
            cell[i][j] = rule[7-code];
        }
    }
}

即時描画

上の描画プログラムでは、ウィンドウサイズは考慮せず、描画領域を 200×200 画素に固定している。 描画領域をGetClientRect関数で求めた矩形領域にする方が気の利いたプログラムと言える。 その場合には、少なくともサイズが変わるごとに、cell配列のデータを計算しなおす必要がある。

予め、描画データを求めておくのではなく、paint関数で、計算しながら、描画してもよい。 cell[2][JMAX] を宣言しておき、時刻0では cell[0] に現在の状態をセット、 時刻1では cell[0] が前の状態、cell[1]が現在の状態、 時刻2では cell[1] が前の状態、cell[0]が現在の状態、という風に2面の配列を交互に使うことになる。

JMAXの値はパソコンのディスプレィの横幅のドット数にしておく。

この場合、画面サイズが変わるごとに、再描画するために、WM_SIZEメッセージを受けて、 InvalidateRect(hwnd, NULL, TRUE); を実行する必要があります。 これにより、クライアントウィンドウ全体の再描画が行われます。 これがないと、ウィンドウの横幅を変えたとき、崩れた図形となります。

ルール90、ルール110

ルール90、ルール110 を下に示す。rule配列を変更するだけでよい。
ルール90
  時刻tでの内部状態(左、中央、右)     111 110 101 100 011 010 001 000
  時刻t+1での中央のセルの内部状態      0   1   0   1   1   0   1   0
ルール110
  時刻tでの内部状態(左、中央、右)     111 110 101 100 011 010 001 000
  時刻t+1での中央のセルの内部状態      0   1   1   0   1   1   1   0


【課題6】

演習5のプログラムを参考にして、上で述べたルール30のプログラムを完成してください。

【発展課題】余裕があれば、paint関数で画面(クライアントウィンドウ)のサイズを得て、 直接、描画するプログラムを考えてみてください。

プログラムのソースコードと実行画面のコピーを提出してください。 ソースコードはルール30に対するものだけ、画面はルール30,90,110の三つの結果を載せてください。 直接、描画するプログラムについても完成した場合は、そのプログラムも載せてください。