私は 2D 物理エンジンを構築しており、ブロード フェーズの衝突検出を追加したいと考えていますが、2 つまたは 3 つのタイプしか知りません。
でも確かにもっとオプションがありますよね？彼らは何ですか？また、それぞれの基本的な説明または説明へのリンクを提供できますか?
私はこれを見てきましたが、私のニーズに最適なものではなく、利用可能なアルゴリズムのリストを求めています.
この場合、「ブロード フェーズ コリジョン検出」は、シミュレーション内のどのボディが十分に接近しているかを判断するために物理エンジンによって使用される方法であり、さらなる調査と、場合によってはコリジョンの解決を保証します。
最善のアプローチは特定の用途によって異なりますが、最終的には、（a）すべてのボディが正確に1つのサブディビジョンに含まれるように、（b）すべてのサブディビジョンが特定のサブディビジョンのボディに十分な大きさになるように、ワールドスペースを細分化する必要があります。同じサブディビジョンまたは隣接するサブディビジョン内のボディとのみ衝突でき、（c）特定のサブディビジョン内のボディの数は可能な限り少なくなります。
それをどのように行うかは、ボディの数、ボディの移動方法、パフォーマンス要件、およびエンジンに費やしたい時間によって異なります。広い空間で体が動き回るという話をしている場合、最も簡単な方法は、世界をグリッドに分割し、各セルが最大のオブジェクトよりも大きい場合、各セルのオブジェクトのリストを追跡することです。古典的なアーケードゲームの規模で何かを構築している場合は、このソリューションで十分かもしれません。
より大きなオープンワールドで動く体を扱っている場合、単純なグリッドはすぐに圧倒されます。Arriuが示唆しているように、おそらく四分木のようなツリーベースの構造が必要になるでしょう。
オープンスペースではなく、境界のあるスペース内でボディを移動することについて話している場合は、BSPツリーを検討することができます。ツリーは、世界を「歩けるスペース」と「壁」に分割し、ボディをツリーにクリップすることで、それが合法的な位置にあるかどうかを判断します。ワールドジオメトリによっては、BSPを使用して、ワールド内のボディ間の衝突を広相で検出することもできます。
境界のある空間を移動する物体のもう1つのオプションは、ポータルエンジンです。ポリゴンの各辺がソリッドウォールまたは別の凹型スペースへの「ポータル」である凸型ポリゴン領域で世界を構成できる場合は、ポイントインポリゴンテストを使用して、ボディが領域内にあるかどうかを簡単に判断できます。同じ領域または接続された領域内のボディのみを確認することにより、衝突検出を簡素化します。
四分木分割をお勧めします。とてもシンプルで、とてもうまく機能します。ブルート フォース衝突検出とクアッドツリー衝突検出の Flashデモを次に示します。(四分木構造を表示するように指示できます。) そのデモでは、四分木衝突検出が力ずくのわずか 3% であることに気付きましたか?
また、エンジンに真剣に取り組んでいる場合は、リアルタイムの衝突検出を選択することを強くお勧めします。お金もかからないし、知りたいことはすべて網羅されている素晴らしい本です。(GPU ベースの衝突検出を含む。)
すべての高速化アルゴリズムは、安価なテストを使用してオブジェクト (またはオブジェクトのグループ) をすばやく除外し、実行する必要がある高価なテストの数を削減することに依存しています。アルゴリズムはカテゴリ別に表示され、それぞれに多くのバリエーションがあります。
空間分割。スペースを分割し、異なる地域にいる候補者を低コストで除外します。たとえば、BSP、グリッド、オクツリーなどです。
オブジェクトの分割。#1 と同様ですが、クラスタリングはオブジェクトが存在する空間よりもオブジェクト自体に重点を置いています。たとえば、ボリューム階層の境界などです。
ソートおよびスイープ メソッド。オブジェクトを空間的に整理し、隣接していないオブジェクト間の衝突を除外します。
1 と 2 は階層的であることが多く、必要に応じて各パーティションに再帰します。3 を使用すると、必要に応じてさまざまな次元に沿って反復できます。
トレードオフは、シーン ジオメトリに大きく依存します。オブジェクトはクラスタ化されていますか、それとも均等またはまばらに分散されていますか? それらはすべてほぼ同じサイズですか、それともサイズに大きな違いがありますか? シーンはダイナミックですか？多くの前処理時間を確保できますか?
「安価な」テストは、実際には非常に安価なものから高価なものまでさまざまです。最適なアルゴリズムを選択するということは、高価なテストの数の削減に対する安価なテストのコストの比率を最小限に抑えることを意味します。アルゴリズムの問題を超えて、キャッシュの局所性について心配するなど、チューニングに取り掛かります。
別の方法は、20x20または100x100などのプレーングリッドです（ワールドとメモリサイズによって異なります）。実装は、quad / bsp-trees（または球体ツリー）などの再帰構造よりも単純です。
この場合、セルの境界を越えるオブジェクトは少し単純であり、bsp / quad/oct-treeの単純な実装ほど縮退しません。
それ（または他の手法）を使用すると、多くのペアをすばやくカリングして、さらに調査が必要な一連の潜在的な衝突を取得できるはずです。
私は大規模なプロジェクトで四分木を使用しました。これは、あまり動かない (削除と再挿入が少ない) ゲーム オブジェクトに適しています。オクトリーにも同じ原則が適用されます。
基本的なアイデアは、再帰的なツリー構造を作成し、ツリーのルートと同じタイプの 4 (quad) または 8 (oct) の子オブジェクトを格納することです。ツリーの各ノードはデカルト空間のセクションを表します。たとえば、該当する各軸で -100 -> +100 です。各子は同じスペースを表しますが、半分に分割されます (例の直接の子は、たとえば、X 軸で -100->0、Y 軸で -100->0 を表します)。
与えられた一連の寸法を持つ正方形または平面を想像してみてください。次に、各軸の中心を通る線を引き、その平面を 4 つの小さな平面に分割します。そのうちの 1 つを取得して、平面セグメントのサイズがゲーム オブジェクトのサイズとほぼ同じになるポイントに到達するまで、何度も繰り返します。これでツリーができました。同じ平面を占めるオブジェクトのみが衝突する可能性があります。どのオブジェクトが衝突できるかを決定したら、それらから可能な衝突のペアを生成します。この段階で、ブロード フェーズが完了し、ナロー フェーズの衝突検出に進むことができます。これは、より正確で高価な計算を行う場所です。
Broadphase の目的は、安価な計算を使用して衝突の可能性を生成し、発生しない接触を除外することです。これにより、狭いフェーズ アルゴリズムが実行する必要のある作業が削減され、衝突検出アルゴリズム全体がより効率的になります。
したがって、先に進んでそのようなアルゴリズムを実装しようとする前に、次のことを行います。
ゲーム内のオブジェクトの数は? たくさんある場合は、おそらくブロードフェーズが必要です。そうでない場合は、Nnarrowphase で十分です。また、多くの移動オブジェクトを扱っていますか?
ツリー構造は、移動するだけでツリー内の位置が時間の経過とともに変化する可能性があるため、オブジェクトを移動すると一般に速度が低下します。これには、フレームごとにオブジェクトを削除して再挿入する必要があり (場合によっては)、これは理想的ではありません。
この場合、ワールド内の形状の範囲の最小/最大ヒープを維持する Sweep と Prune を使用する方がよいでしょう。オブジェクトを再挿入する必要はありませんが、フレームごとにヒープを再ソートする必要があります。これは、削除と再挿入を伴うツリー全体のトラバーサルよりも一般的に高速であると考えられます。
コーディングの経験によっては、コーディングがより複雑になる場合があります。個人的には、ツリーはコーディングがより直感的であることがわかりましたが、効率が低く、エラーが発生しやすいことがわかりました。これは、オブジェクトが軸の真上または中心にある場合にどうするかなど、他の問題を引き起こすためです。ルートノードの。これは、空間的なオーバーラップがあるルーズ ツリーを使用することで解決できます。これにより、このような場合に、1 つの子ノードが常に他のノードよりも優先されるようになります。
グリッドサイズに依存せず、おそらく O(nlogn) (衝突がない場合は最適) ですが、O(n n logn) (すべてが衝突する場合) で最悪のソリューションを思いつきました。
私もそれを実装してテストしました。ソースへのリンクは次のとおりです。しかし、私はそれをブルートフォースソリューションと比較していません。
仕組みの説明: (四角形の衝突を探しています)
x 軸で、右端 ( O(nlogn) ) に従って四角形を並べ替えます。
並べ替えられたリストのすべての四角形に対して、左端を取り、左端の左にある右端が見つかるまでバイナリ検索を実行し、これらの四角形を possible_Collision_On_X_Axis セットのこれらのインデックスの間に挿入します (これらは n 個の四角形で、二分探索、挿入ごとに O(log n) でセットに n 回挿入)
y軸で私は同じことをします
各セットで、x (一方のセット) と y (int) で衝突が発生する可能性があります。これらのセットと交差し、x 軸と y 軸の両方で衝突が発生します (つまり、共通要素) (O(n))
説明が不十分で申し訳ありません。ソースから理解を深めていただければ幸いです。また、ここに例を示します。
Game Physics Engine Developmentの Ian Millington によるゲーム物理の入門リファレンスをお勧めします。サンプルコードを使用した広範なフェーズ衝突検出に関する優れたセクションがあります。
オブジェクトが移動する空間が制限されている場合は、グリッドを使用してオブジェクトを分割できます。オブジェクトが (完全または部分的に) カバーするすべてのグリッド セルに各オブジェクトを配置します。オブジェクト A が他のオブジェクトと衝突するかどうかを確認するには、オブジェクト A がカバーするグリッド セルを特定し、それらのセル内の一意のオブジェクトのリストを取得し、最後にオブジェクト A を一意の各オブジェクトに対してテストします。この方法は、ほとんどのオブジェクトが通常 1 つのグリッド セルに含まれている場合に最適です。
スペースが制限されていない場合は、必要に応じて 4 つの方向 (2D) のそれぞれに拡張できる何らかの動的グリッドを実装する必要があります。
より適応性の高いアルゴリズム (つまり、BSP、Quadtree、Circletree) に対するこのアプローチの利点は、O(log N) 時間 (つまり、対数時間) ではなく、O(1) 時間 (つまり、一定時間) でセルにアクセスできることです。ただし、これらの後者のアルゴリズムは、オブジェクトの密度の大きな変動に適応できます。グリッド アプローチは、オブジェクト密度が空間全体でかなり一定である場合に最適に機能します。
