日別アーカイブ: 2007年9月18日

Direct3D ShaderModel4.0 Shaderで迷路作成

2D 迷路を作成する Shader を作ってみました。
これは実際に見た方が早いと思うので、環境がある方はぜひ走らせて、
動いているところをご覧ください。

64×64 で作成中
maze 64x64

512×512 で作成中の一部
maze 512x512

前のフレームの画像をもとに Shader で発展させていくだけで迷路が
出来上がります。

同時に移動した場合の成長点同士の衝突判定を行う都合上、壁が 1dot
成長するために 2フレームかかります。
その代わり平行していくつでも成長点を設けることができ、
同時に複数の壁を伸ばすことができます。
画像1枚をレンダリングしているだけなので、成長点がいくつあっても
処理速度はほぼ一定です。

アーカイブ内の initdata.png が初期画像です。任意のサイズを与える
ことができます。また白黒2値の絵を描いておくとそれをもとに発展
させます。最外周には必ず白枠が必要です。

生成処理は PixelShader 1つで完結しています。
最適化は全くしておらず、命令数は 625 slot もあります。
ほとんど if 文の塊で、調べたら動的分岐が 9段もネストしていました。
temp register を 27個も使っているので並列度も低いです。
ループを unroll しているのは最適化のためではなく、ループを中断
終了するためです。

sampler を使わずに Buffer から読み込んで整数処理すれば、条件判断
も簡略化できるためずっと小さくなるでしょう。

乱数テーブルのみ CPU で生成しています。本当はこれもシェーダーで
やるべきところなのですが今回は見送りました。

成長点はランダムで壁が変質して出来ます。各ピクセルの意味は R で
判断しており、次の 4つの状態があります。

R = 状態
	0.0  = 空白 (黒)
	1.0  = 固定壁 (白)
	0.5  = 成長点 (壁相当)
	0.25 = 成長予約席 (空白相当)

成長点のみ G B A も意味を持ちます。

R = 0.5 (成長点)
G = 向き (0.0~0.25=上, 0.25~0.50=下, 0.50~0.75=左, 0.75~1.00=右)
B = 直進制限長
A = 回転タイムアウト

最後になかなか埋まらない隙間が出来るのは壁から成長点を作る判定が
単なる乱数だからです。全く発展できない場所にもどんどん成長点を
作ってしまい、それがちらついてノイズに見えてしまいます。
必要な場所に生成して、不要な場所には成長点を作らないようにすれば
隙間も埋まるしちらつきも減ると思います。
成長点の生成ノイズが縞々に見えるのは、乱数の質が悪い証拠です。

実行ファイルとソースのアーカイブはこちら。シェーダーも入ってます。
wheelhandle_ss03t.zip

動作には Vista + DirectX10 (August2007 Runtime) が必要です。