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

Direct3D 10 ShaderModel4.0 迷路の自動探索Shader

前回迷路を作成するシェーダーを作りました。
Direct3D ShaderModel4.0 Shaderで迷路作成

でも作成した迷路が本当に端から端までつながっているのか、
壁がどっかでつながっていたりしないか確認するのが大変なので、
今度は自分で探索させてみました。

ss04 maze 128x128

まず迷路を作り、その後色のついたピクセルが勝手に歩き回ります。

キャプチャだけだと良くわからないので、これも実際に走らせて
ぜひ動いているところをご覧ください。
動いているところだったら、何をやっているのか一目瞭然だと思います。

今回は動きがわかりやすいように 128×128 の初期データが入ってます。
ss03(前回)の initdata.png を使うと 512×512 の迷路になります。
拡大しないとわからないですが暇な時にじっくり見るのにお勧めです。

基本的にすべての探索点は同じアルゴリズムで動いています。
どれも右側の壁伝いに歩いてすべての通路を歩きつくそうとします。
ただしお互いにも衝突するので、狭い路地から出られなくなったり
ショートカットして違う分岐に進んだりと結構ランダムに散ら
ばってくれるようです。

壁伝いに動くため、壁を見失うとその場でくるくる回ってしまい
ます。誰かが助けに来てくれるまでそのままです。

探索点はランダムに左上 (1,1) の点から生み出されます。

シェーダーは下記の 2つです。
 ・maze.fx (迷路生成、前回のものと互換性あり)
 ・walk.fx (迷路探索)

cpp 側のソースを見るとわかりますが、シェーダーを適用して
Draw( 4, 0 ) で四角形を1つ描いているだけになっています。

処理は全部 PixelShader です。迷路のデータを元画像として
レンダリングすると次のシーンが出来上がるわけです。
使っている画像フォーマットも通常の 32bit (R8G8B8A8_UNORM) です。

walk.fx での内部的なピクセルの意味は次の通り。

R= 0.00 路地
   0.25 衝突判定用予約点
   0.50 探索点
   1.00 壁
G= 向き (探索点と予約点のみ) 0.25単位で 上下左右
B= 向き確定フラグ (探索点のみ)
A= 探索点の色

フレームバッファに転送する際に内部ワーク状態を消すようにした
ので、ちらつきも無く見やすくなっています。その代わり判定
している様子など内部状態は見えなくなりました。

walk.fx で使っている乱数は1つだけ。探索点の生成と探索点自身
の色決定です。移動時の判定順は次の通り。

(1) 未確定で右側が空白なら優先して向きを変える(確定)
(2) 前が空白ならそのまま確定
(3) 右も前も埋まっているなら左に向きを変える(未確定)

単なる画像処理なので探索点はいくつでも構わないし、何千個
あっても、数万個あっても処理速度はほぼ一定です。
動的分岐とリソースアクセス遅延によるばらつきが出る可能性が
ありますが、ほぼ完全に面積だけで速度が決定します。

複数同時に動く可能性があるので、衝突判定はかなり厳密です。
Shader が入力可能なのは 1つ前のシーンだけなので、同じ空白を
複数のピクセルが同時に移動可能と判断してしまう可能性が
あるからです。

この同期サイクルのせいで、1pixel 歩くまでに 3フレームも
費やしています。迷路生成よりも判定が長いのは、確定判定が
追加されたからです。まず maze と違い足跡を正確に消す必要が
あります。さらに右を向いた瞬間もと来た場所が空きになるので、
さらに右手に回れると判断してしまう(戻ってしまう)ことも防いでいます。

これらの判定のおかげでピクセルが同時にいっぺんに移動しても
問題なく処理可能となりました。すり抜けも起こらないでしょう。

迷路の生成 maze.fx は ss03 と同じものですが、乱数計算に
偏りのバグがあったので一部修正しました。これはそのまま
ss03 で使うことも出来ます。

ダウンロードはこちらです。
wheelhandle_ss04t.zip
ソースだけでなく実行ファイルも入っています。