異なるオブジェクト間の衝突を検出するアルゴリズムをどのように提示しますか？

Question

本当に唯一の楽しいプロジェクトに取り組んでいたのですが、何か問題が発生しました。

Round Balls、Pointy Triangles、Skinny Lines（その他の野生動物も多分）の2D世界があります。それらはすべてWorldCreaturesのサブクラスです。彼らはこの世界の中で動くことができます。彼らがお互いに会うと、衝突が起こります。

私がしたいことは、それらの間の衝突を検出する方法を作ることです。ここに私が今立っていることがあります：

• ボールボールは簡単ですが、私は自分の位置からの距離を計算し、それらの「サイズ」の合計と比較します。
• 世界のボールとエッジの衝突も簡単です - デカルト座標での距離は簡単ですが、それは単純です。
• もっと一般的な問題は、Line（いくつかの点で開始点と終了点）や他のオブジェクトとの衝突を検出する方法です。ラインとポイントの間の距離があまりにも簡単に計算しますが、どのような私が好きなことは、オブジェクトAは、オブジェクトBと衝突した場合に言うこと

一般的な方法のいくつかの種類を持っていることができます。それが今であるように、コードはいくらかのようになります。

class WorldCreature: 
    def detectCollision(self, otherObject): 
     # do something 
     if collision: 
      self.onCollision(otherObject) 
      otherObject.onCollision(self) 
class Ball(WorldCreature): 
    # someing here 
class Line(WorldCreature): 
    # someing here 

今、衝突検出mechanizmは、オブジェクトが衝突することができるかに依存する必要があります。効果もそうです。

メモリ内のすべてのオブジェクトのリストを保持して、すべてをの各ステップで繰り返す必要がありますか？ステップですか？または、このタスクのパフォーマンスを改善するためのより良い方法がありますか？

Answer 1

quadtreeを使用してください。彼らはあなたが衝突半径の外にあると知っている広い領域を排除するために使用されていますし、最も近い点をすばやく検索することができます。

実際の衝突検出が行われる限り、凸オブジェクトのみを使用しているため、the separating axis theoremのMetanet Software's tutorialをご覧ください。彼らの主力ゲームでは、実際にグリッドを使ってすべてのオブジェクトを見つけて衝突をチェックしますが、代わりにクォッドツリーを使用するのは難しくありません。

（私はあなたが半径内のポイントを見つけることができる方法を説明するために、グリッドに円を使用四分木上の記事を読んで覚えている。私もそれを見つけるように見えることはできません。）

Answer 2

これに対する答えは異なりいくつのオブジェクトがあるか、いくつのオブジェクトが存在しているのか、どのオブジェクトがどれくらい多く動いているのか、どのくらい動いていないのか、どのくらい速く動いているのかなど、さまざまな要素について考えることができます。コリジョンチェックなどをプルーニングするために行う最適化を無視しています。

コアコードが正しい場合は、実験の実行を開始して何がうまくいくかを確認できます。私はkd木のような何らかの空間的細分法をお勧めします（2dでは、あなたは4分木を使うこともできます）。

基本的には、ゲームをコーディングして試してみることができるものを除いて、基本的に正解はありません。

Answer 3

私はHough Transformがどうにか役立つはずだと思います。

Answer 4

Python。私のために変だらけの獣8）

私はゲームを作成する経験があるので、私はこの観点から話します。

まず、広い位相の衝突検出が必要なオブジェクトの数が少ない場合は、これをスキップできます。すでに説明したquadtreeは、実装の可能性が1つだけです。 衝突する可能性のあるオブジェクトのペアを見つけるには、広域位相が必要です。

次に、ペアがチェックされると狭い段階になります。

私は（注意 - これは心の中でプリミティブで作成された、あなたは多面体の衝突が必要な場合 - ちょうどGJKと球、プラス線を使用し、セグメント）以下のスキームを使用：衝突を必要と

すべてがCollisionObjectを持っていますこれCollisionPrimitive（ボックス、球体など）を変換して保存処理し

各CollisionPrimitiveはTYPE_IDました - あなたはA_B_CheckIntersectionを書くとき - 最初のオブジェクトを常にあなたが幅広いから取得し、リスト内の各ペアの下TYPE_ID

を持っていますフェーズ - 必要に応じてオブジェクトを交換し、アルファを索引付けする特定の衝突関数へのポインタが格納されているy。 確かに - そのためにあなたがそれらが同一のインターフェース（C++）を持っている必要がありますが、それは8簡単です）

特定の衝突ルーチン用として：それは四分木のため