Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
[go: Go Back, main page]

The Black Mind of Cellra Automata
7/12 セル・オートマトンの黒い野望





デモで多用されるセル・オートマトン。その実態

 Final Realityが、現在Direct3Dを使ったベンチマークというかTech.Demoというかそのようなジャンルの中でもっともカッコよくて有名なものだと仮定すれば、僕の目標はそれにおいつき追い越すことです。

 このページでFinalRealityが最初に出てきた時にも言いましたが、あるものを否定するにはせめて自分のなかでそれ以上のものだと納得できる程度のものを作り上げなくては本当の批判にはなり得ないでしょう。

 そんなわけで、デモで使われているエフェクトについて、たいていはみればなにをやっているか想像はつくのだけれど、本当にそうなのかどうかは実際に試してみるまでわからないので、いろいろと試行錯誤をしているところなわけです。プリンの味は、食べた人にしかわかりません。

 前回、メガデモの話を書いたとき、とあるデモな人からメールをいただきました。詳しい内容については割愛しますが、ひとつびっくりしたことがありました。実はメールをくださった方はデモを作ってらっしゃるにも関わらず、セル・オートマトンについてご存知なかったのです。

 私の中では、デモで用いられているほぼ半分近いエフェクトはセル・オートマトンとしか見えなかったのですが、それ以外の捉えかたがあるというのは意外でした。そこで、それをきっかけにしてこのページで古くて新しいこの話題について触れてみようと思ったわけです。


 さて、そもそもセル・オートマトンというのはセル(細胞)ということばと、オートマトン(自動機械)ということばの合成です。ふたつをあわせると細胞自動機械と呼ぶことができます。

 セル・オートマトンのもともとの考え方を作り上げたのが誰かという議論になりますと私も生まれるより前のことを覚えているわけではないので正確には言えませんけれども、少なくとも電子計算機の発明時点には既にあったと考えられます(もっとも、当時は電子計算機でセル・オートマトンの計算が十分にできたとは考えにくいのですが)。

 さて、セル・オートマトンというのはなんなのかというと、きわめて一般的にいえば、まず第一に無数のセル・オートマトンが共同して動作し、第二にセル・オートマトンは複数の状態を取りうる一種の状態マシンである。そして第三には、まわりのセル状態を引数として次世代の状態を新規に決定する状態遷移関数を内部に持つものである・・・・と、定義されます。

 といってもなんのことだか解っていただけないかもしれないので具体例を出して説明することにしましょう。
 偉大な数学者パスカルの考えた、パスカルの三角形というものがあります。これは一次元セル・オートマトンの代表選手としてあまりにも有名です。

 パスカルの三角形とは右図のような三角形を言います。

 一見しておわかりのように、より下にある数字はより上にある数字の両辺を足した結果になっています。

 中学か高校で、このような三角形を目にした方も多いのではないでしょうか。実は組み合わせの数を求めるときにこの三角形がよく説明のため使われるのです。他にもn元方程式の次数を調べるときにも使えます。

 さて、これがどうしてセル・オートマトンなのでしょうか。

 パスカルの三角形をセル・オートマトン的にあらわすと次のようになります。



 ひとつひとつのセルはなんらかの状態(この場合は数値)をとり、その状態が時間とともに遷移していきます。セルには状態遷移関数を定義しなくてはなりませんが、パスカルの三角形の場合は状態遷移関数が「両隣の数値(状態)を足したものを自分の次の状態とする」というものなわけです。ふつう、状態遷移関数を単にルールと呼びます。

 このルールにしたがった一次元セル・オートマトンが、実際にパスカルの三角形となることを示すのが右の図です。

 ひとつひとつの桝目がセルで、空白の部分には数字のゼロが入っていると思ってください。

 あるセルの次の行(ひとつひとつの行を世代と呼びます)では、直前の世代で両隣にあったセルを足したものになっていることに注目してください。

 最初の世代(第一世代)で1のあったセルは、次の世代では両隣のゼロを加えた結果、ゼロ状態になっています。そのかわり、その両隣のセルはそれぞれ1の値をとっているわけです。

 さらに次の世代は・・・と見ていくと、実に巧妙にパスカルの三角形が再現されることがおわかりいただけると思います。


 これが、セル・オートマトンなのです。

 デモな方や、もしくはかの有名な「ファイア・エフェクト」をご存知の方はここで「おや?」と思われたことでしょう。そう。実は炎が燃え上がっているように見えるファイア・エフェクトというのは、このパスカルの三角形をさかさまにして、ルールを「両隣の状態を加算して二で割る」と少し変えただけのものなのです。

 あとはパレットを炎が燃えているような感じのものにすればいともたやすくファイア・エフェクトの完成です。

 私が、デモのほとんどのエフェクトはセル・オートマトンであると言った理由がおわかりいただけると思うのですが如何でしょうか。

 実は、セル・オートマトンというのはパスカルの三角形に限らず、遥か以前から莫大な事例について事細かに研究され続けてきたコンピュータ科学の一大分野のひとつでもあるのです。たとえば数学者コンウェイがScientific American誌で紹介したことから一躍有名になった「ライフ・ゲーム」(聞いたことありますよね)や、画像エフェクトで使われるボカシ効果、等々、とにかく敷き詰められた個々の要素について同じルールを適用して要素の状態自身を変化させるものすべてをひっくるめて「セル・オートマトン」と言うのです。

 さらに、セル・オートマトンのルールの研究は遥か昔から続けられており、その黎明期の成果のひとつにファイア・エフェクトと同様の発見があったことは見ての通りです。




サンプルコード

 そんなわけでまずはファイア・エフェクト相当のプログラムを組んでみましたが、予想通りアッサリと組めました。しかしあまりにも味気なかったので乱数で揺らめきを出して、とりあえずは満足することにしました。

 ボカシ(ブラー)を使うエフェクトは基本的には周りのセルの状態を平均したものを自分の次の状態にすればよいので、ファイアエフェクトをちょっと変えるだけでボカシになります(というか下方向のピクセルしかボカさないのがファイア・エフェクトなのですが)。

 もうひとつ、セル・オートマトンならではのルールとして、生成と消滅を伴うエフェクトを作ってみました。なんだか蝕まれていくような気持ちの悪い効果が出るのでセル・オートマトンの例としては適切でしょう。

 ソースコード付きで掲載します。右のボタンをクリックしてください。

 操作は、B〜Nまでのキーにいろいろな機能をわりあてていますので、適当に押して遊んで見てください。PDSです。ライセンスフリーとします。


 ファイア・エフェクトについては、そのままだとあまりにもつまらないので、乱数でゆらぎを与えるようにしてあります。rand()関数を使っているのでボトルネックが発生していますが、今回はサンプルということで無視してあります。

 また、普通ファイア・エフェクトというと256モードで作りますが、それでは芸がないし応用性に乏しいので敢えて16bitモードで作りました。そのおかげで、図のようにセピア調の写真とファイアを同居させることができます。

 全体的にスピードが遅いのですが、それは画面からフィードバックしているせいだと思います。メモリ転送に余分なオーバーヘッドがかかっています。本気でやるならもとネタの画像はあらかじめどこかのバッファに転送しておくべきでしょうが、面倒なのでふつうにフィードバックしています。

 



ラジアルブラーの黒い謎


 さて、デモといえばなんだか派手っちいエフェクト。オマケにこの僕は当代きってのブラーマニア(ぼかし狂)ときており、PhotoshopのBlur機能はもう隅から隅まで使いまくりというありさまで、ここまできたらもうちょい派手なエフェクトもぜひとも欲しい。そんな気持ちで作ったのが右の画面のような放射ブラー(Radial Blur)なのです。

 こういうのをエフェクトとして使ってるデモはけっこうみますが、半分は単なるフェイクのようですね。掲示板で^Cさんが教えてくださった、Javaデモ、forwardのオープニングもフェイクのようです(添付されていたGIFファイルをみてわかりました)。しかしここまで見事にやられるとフェイクとは全然気づかず、関心してしまいました。

 でもフェイクを多用しすぎるとテクニックのデモというよりは単なる紙芝居になってしまうし、そもそも意味がないのでFinalRealityのタイトルロゴのようリアルタイムで計算する方法をなぞってみることにしました。敵を制するには敵を知れ、ということですね。

 さて、この放射ブラーはそもそもどういうものなのかというと、この画面写真のように中央から周囲にむかって光の尾を引くような効果をさします。

 このような効果は放射状にぼかしをかけることで実現できます。それゆえ「放射ブラー」とよばれているわけです。

 これはカメラのシャッタースピードを遅くして、シャッターがあいている時間にズームレンズを操作する、スローシャッター効果とほぼ同じです。この技法はスピード感と立体感を演出できるので時々使われているのをみますが、立体感をうまく出すには単に放射状にぼかしをかけるだけでは不十分です。

 そこで、画面の中心に近いほど多くサンプリング点をとり、平均したものを自分の色とします。

 このやりかたはOh!Xの1992年2月号の中野修一氏の記事を参考にしました(バックナンバーを貸してくれた平松クンthanx)。それによると、サンプリングするピクセルの座標を求めている式は次のようになります。

    x = 127+i-(sgn(i)*(k*k)/l)*abs(i)/49
    y = 127+j-(sgn(j)*(k*k)/l)*abs(j)/49

 このとき、xとyはサンプリング点の座標で、これは図のオレンジの点にあたります。iとjは色を求めたいピクセルの座標で、これは図の赤い点にあたります。sgnというのはX-BASICの関数で、これはsgn(a)のとき、aの内容が正なら1、負なら-1を返す関数のようです。kは図で言うとオレンジ色の点の何番めに位置するかの数です。これは好きなだけ増やしたりできますが、増やしすぎてもわけがわからくなるだけです。absはご存知絶対値を求める関数です。lは適当な定数です。

 この式を使うと、画面の中心付近(kが小さいとき)は細かく、画面から離れる(kが大きいとき)にしたがっておおざっぱにサンプリングすることになり、これを平均すると、必然的に画面中心方向が細かくなり、強調されることになります。

 127というのはマジックナンバーで、おそらくこれはX68000の256x256という画面モードを使っているのでしょう。つまり画面の中心座標は(127,127)なわけです。

 さて、当然ですがこれを素直に実装するとさすがの最新鋭CPUであるPentiumIIでも、画面がでてくるまでに数秒かかる場合があり、とても実用に耐えません。そこである疑念が生まれました。「果たして放射ブラーというのはここまで実直に計算しているのだろうか」と。

 というのも、実直に計算すればするほど墓穴を掘るだけで、とても駄目です。さらにFinalRealityなどでは中心を左右にゆらしていかにも後ろから光があたっているような効果を出しています。

 左右にゆらすということは、静的な計算もフェイクも事実上使えないわけで、これにはどう対処すべきだろうか真剣に考えてみました。

 すると、おかしなことに気づいたのです。

 FinalRealityのタイトル部分はいきなりブラーがかかるのではなく、少しじわっと出てきます。つまり厳密な計算でいえば放射ブラーとは違うわけです。

 そこで考えたのが、毎回まじめに計算するのをやめて、セル・オートマトンのように前回の結果(状態)を利用する方法です。

 まず、先の式を分解してテーブルを作りました。といっても、640x480のテーブルを作ったら爆発的なことになってしまいますしあまりにも頭が悪いので式の性質に着目し、X用のテーブルとY用のテーブルをわけてつくることにしました。



	for(x=0;x < 1024;x++){
		int sx,ax;
		sx = sgn(x-cx);
		ax = abs(x-cx);
		for(i=0;i < 32;i++){
			int mx,my;
			mx =  - (sx*i*i/8)*ax/49;
			x_table[x][i] = mx;
				
		}
	}

 右はテーブルをつくっている部分の抜粋です。

 X軸用のテーブルとY軸用のテーブルを別に用意していますが、これは中心とする座標がxとyで違うためです。完全な正方形画面ならば同じテーブルが使えます。

 これらのテーブルはサンプリング点の座標を求めるものです。これで余分な計算はなくなり、ただのぼかしと同じことになります。ここでは念のためにひとつの点について32個もサンプリング点を計算していますが、実際につかっているのは最大で4つの点です。まぁ試行錯誤の跡ということです。

 0から1024まで変化させて計算しているのは、あとで中心を左右に振るためです。また、2の累乗にしておくと二次元配列のアドレス計算が簡略化できて高速になるためでもあります。

 中央を左右にふり、アニメーションさせるにはテーブルをつくりなおすのではなく、それぞれの点について適用するテーブルのインデックスにゲタをはかせます。

 実際の計算ルーチンではこのテーブルから適当な点を選んで加算し、平均をとっているだけです。他の部分ではフィードバック処理などをしていますがDirectDrawの機能を使っているだけなので省略します。

 また、ごらんのように計算を中央部からやるかそれとも外周部からやるかによって計算結果が著しくかわります(フィードバックするからです)。これは本来、二つの計算バッファを用意して毎回切り替えるのですが、今回はそれを嫌って中央部から外苑部にむけて計算を行うように二つのループを作っています。

 詳しくはソースコードをごらんください。

 いやぁ、なかなか奥が深かったですね。仕事の合間につくっていたのですが、作り上げるのに半日も費やしてしまいました。他にやることがあるだろーに(^^;