たそがれブランチたそがれブランチcocos2d-xを使ったアプリ開発などやってます。@br_branchTweetPocketなんか真っ赤で怖いですがタイトルの通りです。こちらは単なるサンプルですが、今作っているアプリで衝突判定に時間がかかるようになっちゃったので、効率化をはかるために4分木空間分割での衝突判定モジュールを作成しました。ついでなのでGitHubでそのモジュールを公開しちゃいます。v3用)GitHubにて公開しています。使い方もREADME.mdに載せました。使いたい方はお好きに使用/改造してください。v34分木空間分割というのは、衝突判定を効率的に行うためのアルゴリズムみたいです。以下にとても詳しくのっています。2.xで4分木空間分割を行うものを作成した方のをかなり参考にしました。その方のブログは以下になります。v2用のライブラリも公開されてます。cocos2d-xでSTGを作るために(当たり判定編)はい、今回の記事はこれで全てです。下はおまけですが、大したこと書いてないので暇すぎて5分後死んでそうって方だけどうぞ。読んでも内容が暇で死ぬかもしれません。その場合はなんかごめんなさい。衝突判定についてぐぐったらとてもたくさん出てくるので別に特記するものもないのですが、シューティングゲームやアクションゲームみたいに何かに当たることでイベントが起きるゲームの開発において、衝突判定は非常に重要なロジックになります。全ての弾幕を無条件神回避する味方ユニットと敵ユニットしか出てこないSTGを作ろうという場合は必要ないかもしれませんが、そうでない場合は必ず実装するものです。この処理って結構重いんですよね...理由は1フレームごとに全てのオブジェクトの判定を行う必要があるからです。60FPSの設定にしている場合、1フレームは16ミリ秒です。その中で、画面の更新から他のイベント処理など全てを行えないと、FPSは下がります。10〜20回くらいの判定なら一瞬でしょうが、全てのNodeでやみくもに衝突判定を行う場合、計算量は常にO(n^2)となります。}}上記は一番効率の悪いやり方です。A、B、C、Dというオブジェクトがある場合[A,B],[A,C],[A,D],[B,A],[B,C],[B,D],[C,A],[C,B],[C,D]と衝突判定を行うわけですが、[A,B]と[B,A]とかって同じことやってますよね。そこでもう少し効率化を図ります。組み合わせ判定とでも言っておきますね。}}この場合、A、B、C、Dというオブジェクトの衝突判定は[A,B],[A,C],[A,D],[B,C],[B,D],[C,D]だけで済みます。上記でも結局のところ常にO(n^2)の計算量となります。100個のNodeがある場合は4950回の衝突判定が行われます。200個だと19900回です。ひとつの処理に平均1マイクロ秒かかるとしたら200個の処理判定に19ミリ秒かかる計算ですので、もう少し効率化を図らないとダメそうです。上でも書いたように、以下にとても詳しく載っています。4分木空間分割を最適化する!(実装編)にわかのぼくが書くよりかははるかにわかりやすいと思いますので、興味ある方は上の記事を読むのをおすすめします。こちらもオブジェクトが密集した場合の計算量は最大でO(n^2)となります。うまく空間内にオブジェクトが分散され、最適化された場合はO(n)の計算量で済みます。そんなめちゃくちゃ密集することってあまりないはずなので、平均してO(n)の計算で行えることになるわけです。ベンチマークそんなわけで、性能がどんな風になったかを計測してみました。やったのは上で紹介した「総当り」「組み合わせ」「4分木空間分割」での衝突判定です。オブジェクトの対象数を100、200、300、400、500でそれぞれ計測し、また空間内にオブジェクトが密集〜分散するように、フィールドの大きさを1倍、2倍、3倍でそれぞれ計測しました。0.145※単位:秒やっぱり、フィールドに関係なくn^2に比例してあがっています。フィールド2倍、3倍の方が効率がよくなるのは、オブジェクトが分散されることで衝突判定時のロジックで早めにぬけ出すものが増えるからでしょう。総当りとほとんど同じです。計算量が少し減る分総当りよりはマシになってますが、それでも分散に関係なくオブジェクトの数に比例して増えています。ちなみに、これらの計算結果から1つあたりの衝突判定にかかる時間は0.7マイクロ秒っぽいです。0.014※単位:秒だいぶ効率化が図れていることがわかります。総当りと比較して、処理にかかる時間が最大10分の1にまで減りました。密集している場合はやはり時間がかかるものの、それでも上の二つとくらべて2分の1〜4分の1にまで減ってますね。無駄な動画アップした後でかなり無駄な動画だと思いましたがアップしちゃったんで一応載せておきます。4分木空間分割を使う/使わないでかなり速さが違うことがわかるかも。GitHubにあげてます。興味ある方はこちらにアップしてるんでビルドしたりして遊んでみてください。コメントをキャンセルメールアドレスが公開されることはありません。