algorithm - 2D での衝突検出に使用される技術のリソースは?

Question

2D 環境での衝突検出に使用するアルゴリズムまたは技術を説明している最良のリソース (書籍または Web ページ) は何だと思いますか?

より洗練された効率的なゲームを作成するためのさまざまなテクニックを学びたいと思っています。

Answer 1

衝突検出は、多くの場合、2 フェーズのプロセスです。2 つのオブジェクトが重なり合う可能性があるかどうかを判断するためのある種の「大まかなフェーズ」アルゴリズム (n^2 の比較を回避するため) に続いて、アプリケーションのジオメトリ要件に基づく「狭いフェーズ」の衝突検出アルゴリズムが続きます。 .

Sweep and Pruneは、比較的物理的な動きを受けるオブジェクト (非常に高速に移動するもの、またはサイズと境界領域が大きく異なるものは、これを不適切にする可能性がある) に対して、十分に確立された効率的な広範なフェーズ アルゴリズムです (アプリケーションに適しているかどうかに関係なく、いくつかのバリエーションがあります)。 ）。Bulletライブラリには、参照用の3D 実装があります。

狭位相衝突は、多くの場合、「CircleIntersectCircle」のように単純です。ここでも、Bullet ライブラリには優れた参照実装があります。任意のオブジェクトに対してより正確な検出が必要な 3d ランドでは、GJKは現在の作物のクリームの 1 つです。私の知る限り、2d に適応することを妨げるものは何もありません (ただし、すべてのエッジを力ずくで強制するよりも遅くなる可能性があります。 )

最後に、衝突検出を行った後、何らかの衝突応答が必要になることがよくあります。 ボックス 2dは、身体的反応の解決策の出発点として適しています。

Answer 2

Metanet Software は、いくつかの関連するチュートリアルを公開しています。Metanet は、 N (Flash ベース、Windows、Mac、Linux 用) およびN+ (X360、DS、および PSP 用) を開発しています。

Answer 3

個人的にはポール・バークの作品が好きです。

また、Paul Nettle はこのトピックについて書いていました。彼は完全な 3D 衝突検出ライブラリを持っていますが、そのようなライブラリ (2D に非常に適用可能) の背後にあるアイデアにもっと興味があるかもしれません。これについては、楕円体を使用したゲームの一般的な衝突検出を参照してください。

Answer 4

Christer Ericsonによる本「Real-TimeCollisionDetection」（ISBN：1-55860-732-3）は、最近（2005）に広く賞賛された本であり、いくつかの良い答えが得られるはずです。

それはあなたが知る必要があるいくつかの数学の基本的な入門書から始まり、次に衝突検出で一般的に使用されるさまざまなタイプのバウンディングボリューム（球、軸に整列したバウンディングボックス、方向付けられたバウンディングボックス）に入ります。

次に説明するのは、線、三角形、球、ポリゴン、平面、バウンディングボリュームなど、プリミティブのさまざまな組み合わせ間の衝突を検出するための多数のアルゴリズムです。

また、オブジェクトの空間分割と編成の主要な方法（ボリューム階層、BSPツリー、八分木など）のいくつかをカバーすることも重要です。これにより、オブジェクトを細分化できるため、衝突検出が本質的に高速化され、オブジェクト間の不要な比較を回避できます（たとえば、データ構造から、オブジェクトAがオブジェクトBに到達するには遠すぎることがわかっているので、実行しません。距離チェック）。

また、移動するオブジェクト間の衝突（間隔など）を実際にチェックする方法についても説明しますが、これはかなり重い本であり、資料を十分にカバーしていますが、解決や応答ではなく、衝突検出用であることに注意してください。したがって、2つのオブジェクトが衝突したかどうかを判断するのに役立ちますが、実際には何をすべきか、つまりどのように解決するかはわかりません。交差テストは通常​​、そのような決定を行うために必要なデータを提供しますが、衝突検出ルーチンを使用して衝突を検出し、それらをどうするかを決定するソルバーを作成するという一般的な問題に関しては、この本では取り上げません。その深さ。

Answer 5

オブジェクトが2D空間のポイントとして表されている場合は、線の交点を使用して、2つのオブジェクトが衝突したかどうかを判断できます。同様のロジックを使用して、オブジェクトが別のオブジェクトの内部にあるかどうかを確認できます（したがって、現在交差していない線でも衝突しています）。これを行うための数学は非常に単純であり、基本的な幾何学に関する教科書でカバーされている必要があります。ただし、オブジェクトがオブジェクトを完全に通過したかどうかを検出するのは少し難しいかもしれません。