Tweet

Pocket

なんか真っ赤で怖いですがタイトルの通りです。

こちらは単なるサンプルですが、今作っているアプリで衝突判定に時間がかかるようになっちゃったので、効率化をはかるために4分木空間分割での衝突判定モジュールを作成しました。
ついでなのでGitHubでそのモジュールを公開しちゃいます。

4分木空間分割衝突判定モジュール(cocos2d-x v3用)

GitHubにて公開しています。
使い方もREADME.mdに載せました。使いたい方はお好きに使用／改造してください。
4分木空間分割衝突判定モジュール For cocos2d-x v3

4分木空間分割というのは、衝突判定を効率的に行うためのアルゴリズムみたいです。
以下にとても詳しくのっています。
その８ 4分木空間分割を最適化する！（理屈編)

作ったモジュールは、cocos2d-x 2.xで4分木空間分割を行うものを作成した方のをかなり参考にしました。
その方のブログは以下になります。v2用のライブラリも公開されてます。
cocos2d-xでSTGを作るために(当たり判定編)

はい、今回の記事はこれで全てです。
下はおまけですが、大したこと書いてないので暇すぎて5分後死んでそうって方だけどうぞ。
ただ読んでも内容が暇で死ぬかもしれません。その場合はなんかごめんなさい。

衝突判定について

ぐぐったらとてもたくさん出てくるので別に特記するものもないのですが、
シューティングゲームやアクションゲームみたいに何かに当たることでイベントが起きるゲームの
開発において、衝突判定は非常に重要なロジックになります。
全ての弾幕を無条件神回避する味方ユニットと敵ユニットしか出てこないSTGを作ろうという場合は必要ないかもしれませんが、そうでない場合は必ず実装するものです。

ただ、この処理って結構重いんですよね…
理由は1フレームごとに全てのオブジェクトの判定を行う必要があるからです。

60FPSの設定にしている場合、1フレームは16ミリ秒です。その中で、画面の更新から他のイベント処理など全てを行えないと、FPSは下がります。
10〜20回くらいの判定なら一瞬でしょうが、全てのNodeでやみくもに衝突判定を行う場合、計算量は常にO(n^2)となります。
こういう処理ですね。

// 総当り衝突判定
// 処理数: (n^2-n)
for(auto node1 : nodeList){
    for(auto node2 : nodeList) {
        if(node1 != node2 && node1->isCollision(node2)) {
            // 衝突した
        }
    }
}

上記は一番効率の悪いやり方です。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]とかって同じことやってますよね。

そこでもう少し効率化を図ります。とりあえず組み合わせ判定とでも言っておきますね。

// 組み合わせ衝突判定
// 処理数：n(n-1) / 2
for(int i = 0; i < nodeList.size(); i++) {
    auto node1 = nodeList.at(i);
    for(int j = i + 1; j < nodeList.size(); j++) { auto node2 = nodeList.at(j); if(node1->isCollision(node2)) {
            // 衝突した
        }
    }
}

この場合、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ミリ秒かかる計算ですので、もう少し効率化を図らないとダメそうです。
(200個もオブジェクトの衝突判定をさせる機会なんて弾幕ゲーくらいしかないかもですが)

そこで、4分木空間分割衝突判定ですよ

上でも書いたように、以下にとても詳しく載っています。

その８ 4分木空間分割を最適化する！（理屈編)
その９ 4分木空間分割を最適化する！（実装編）

にわかのぼくが書くよりかははるかにわかりやすいと思いますので、興味ある方は上の記事を読むのをおすすめします。

こちらもオブジェクトが密集した場合の計算量は最大でO(n^2)となります。
ただ、うまく空間内にオブジェクトが分散され、最適化された場合はO(n)の計算量で済みます。
そしてそんなめちゃくちゃ密集することってあまりないはずなので、平均してO(n)の計算で行えることになるわけです。そりゃ早いですね。

ベンチマーク

そんなわけで、性能がどんな風になったかを計測してみました。
やったのは上で紹介した「総当り」「組み合わせ」「4分木空間分割」での衝突判定です。
オブジェクトの対象数を100、200、300、400、500でそれぞれ計測し、また空間内にオブジェクトが密集〜分散するように、フィールドの大きさを1倍、2倍、3倍でそれぞれ計測しました。
(iOSシミュレータを使って、iPhone6Plusで計測)

総当りの場合

※単位：秒

やっぱり、フィールドに関係なくn^2に比例してあがっています。
少しだけフィールド2倍、3倍の方が効率がよくなるのは、オブジェクトが分散されることで衝突判定時のロジックで早めにぬけ出すものが増えるからでしょう。

組み合わせの場合

※単位：秒

総当りとほとんど同じです。
計算量が少し減る分総当りよりはマシになってますが、それでも分散に関係なくオブジェクトの数に比例して増えています。

ちなみに、これらの計算結果から1つあたりの衝突判定にかかる時間は0.7マイクロ秒っぽいです。
(ただCPUによって当然処理速度は違うし、回転も考慮した矩形の衝突判定という結構重い処理でやったので、簡単なやつならもっと早いと思います)

4分木衝突判定の場合

※単位：秒

だいぶ効率化が図れていることがわかります。
総当りと比較して、処理にかかる時間が最大10分の1にまで減りました。
密集している場合はやはり時間がかかるものの、それでも上の二つとくらべて2分の1〜4分の1にまで減ってますね。

無駄な動画

アップした後でかなり無駄な動画だと思いましたがアップしちゃったんで一応載せておきます。
4分木空間分割を使う／使わないでかなり速さが違うことがわかるかも。

GitHubにあげてます。

興味ある方はこちらにアップしてるんでビルドしたりして遊んでみてください。
4分木空間分割衝突判定モジュール For cocos2d-x v3