ホーム < ゲームつくろー！< 衝突判定編

その９ 4分木空間分割を最適化する！（実装編）：サンプルプログラム

　衝突判定編2D衝突編その９「4分木空間分割を最適化する！（実装編）」で説明した内容を踏まえたサンプルプログラムです。実行すると、非常に沢山の円が出現し画面内で衝突しながら飛び散ります。

サンプルスクリーンショット。これだけの円が衝突判定しながら60FPSで動いてます！
（ただしリリースモード＋フルスクリーンモードの時のみです）

○ コンパイル方法

　必要なファイルはこちらからダウンロードできます(COLSmp_2D_No9_v104)(2009. 2. 7更新)。DirectX9が必要です。ファイルをダウンロードして解凍したら、main.cpp、CollisionAPI.h、SmartPtr.hそしてColTrees.hを空のWin32アプリケーションに追加し、2枚の絵（Circle.pngとCircle(Col).png）をプロジェクトフォルダ下にコピーすれば、コンパイルして実行できます。また実行形式も含めておりますので、動作確認だけしたい方はそちらをどうぞ。

　実行すると上のような円の衝突がリアルタイムの実行されます。ただし、デバッグモードではメモリ管理とSTLが死ぬほど遅いので参考にはなりません。リリースモードでお楽しみ下さい。終了はESCキーです。それでも環境によってはデフォルトの円の数で余裕がある方もいれば、まともに動かないほどカクカクする人もいるかと思います。余裕がある人はプログラムを変更して円を増やし、ない人は減らして下さい（増減はグローバル変数g_CircleNumを変更します）。

○ プログラムのポイント

　このプログラムのポイントは衝突･･･ではなくて線形4分木による衝突数の最適化にあります。それは画面左上の「Optimaization」でパーセンテージとして表示されています。上のスクリーンショットの場合、counter=101の時点で4.13%となっています。これは総当り法を100%とした時の最適化衝突回数の割合を表しています。1500個の円を総当り法で判定すると約112万回必要になりますが、上の時点ではこれを46,500回くらいに減らしています。もの凄い減り方ですが、円が画面内にランダムにある状態だと1%台になることもあります。線形4分木恐るべしです。

　線形4分木関連はすべてColTrees.h内にまとめてあります。このヘッダー内にはOBJECT_FOR_TREEクラス、CCell空間クラスそしてCLiner4TreeManager管理クラスが含まれています。すべてテンプレートクラスです。細かな使用方法は衝突判定編2D衝突編その９「4分木空間分割を最適化する！（実装編）」にもありますが、まずCLiner4TreeManager::Initメソッドで4分木空間の範囲と分割レベルを決めます。分割レベルはきっと8ぐらいがいいところです。一応それ以上は設定できない仕様にはしています。以下に分割レベルと占有メモリのサイズを示します：

Level	空間数	メモリサイズ(kB)
0	1	0.02
1	5	0.10
2	21	0.41
3	85	1.66
4	341	6.66
5	1365	26.66
6	5461	106.66
7	21845	426.66
8	87381	1706.66

CCellクラスのサイズは16バイトですが、線形4分木配列はポインタなので+4で20バイト×空間数です。

空間範囲を作成したらCLiner4TreeManager::RegistメソッドでOBJECT_FOR_TREEクラスを登録します。これで空間にオブジェクトが高速配置されます。全部配置したらCLiner4TreeManager::GetAllCollisionListメソッドを呼び出すと衝突対応リストを出力してくれます。後はそれを見て衝突判定をチェックしていけば1回の衝突プロセスが終了します。2回目以降はOBJECT_FOR_TREE::Removeメソッドを呼び出して一度空間からオブジェクトをはずし、位置を変更後に再度登録しなおせば、新しい衝突リストを得る事ができます。

　初期化、再登録、リスト出力という流れをつかめば、テンプレート化されているため色々な局面に使いまわせるクラスだと思いますので、お試し下さい。

○ プログラムで遊ぶポイント

　4分木空間分割レベル（g_PartitionLevel）を増減させると最適化の度合いが変わるのがわかると思います。あまり分割し過ぎてもメモリを食うだけで大した最適化効率にならない事もわかります。

　このサンプルプログラムは衝突判定もさせていますので、これで大いに遊べます。私は楽し過ぎて夜なか中パラメータをいじって遊びました（笑）。簡単に触れるパラメータはmain.cppの最初にグローバル変数としてまとめました。円の大きさや初期位置などはメイン関数内の「円オブジェクトの初期位置・速度の設定」というコメント下で触れます。殆ど変更しても問題ありませんが、.scaleだけは触らない方が良いです（画像との兼ね合いのため）。

　衝突している円はオレンジ色に変わります。オレンジになりっぱなしになっているのが沢山ありますが、これは「2回目の衝突」を無視しているためです。つまり1回目に衝突して位置を変えた後は衝突判定をしていないために重なりが起きてしまいます。これをちゃんとすればボリュームにめり込まない衝突にもなるのですが、かなり面倒な実装になり、ここでの主点にならないため省略致します。

　衝突がすっぽ抜ける時があります。愛嬌愛嬌です(^-^;;てへへ

○ バージョン情報

v1.00 -> v1.01
　・ モートン空間の決定の計算をマイナスで行っていたのを排他的論理和に訂正

v1.01 -> 1.02
　・ パーティクル同士の衝突関数を新しい物に変更
　・ 平面とパーティクルの衝突関数を新しい物に変更

v1.02 -> 1.03
　・ 取得モートン空間番号が親番号になっていたバグを修正（親空間に所属していた物通しで衝突判定をしていた事になります）

v1.03 -> v1.04 (2009. 2. 7)
　・ スマートポインタによる管理をやめた（循環参照問題のため）
　・ リストから逸脱する時のPre-Next接続のバグを修正