若い大人のための衝突検出ゲームのチュートリアルを設計していますので、説明を簡単にするためにできるだけシンプルにしたいと思います。良い、簡単な、2D矩形のみの衝突検出アルゴリズムとは何ですか？
要件は非常に簡単です。世界は2Dであり、（任意のサイズの）矩形のみを含みます。 BSPでもクアッドトツトさえも、過度な（シンプルさに重点が置かれている）ようですが、すべてのn（n-1）/ 2の可能な衝突をブルートフォースよりも効率的にしたいと思います。
2D、長方形のみ、単純です。
誰でもアルゴリズムを指し示すことができますか？ quadtreeアルゴリズムは私が探しているものですか？
編集：また、四角形は決して回転しません（私はそれを簡単に保ちます）。私がどのような規模で作業しているのかを知るために、PygameでPythonで実装された典型的なユーザーのラップトップ/デスクトップ（5歳未満）で動作する数百の四角形があります。
私の経験では、すべての広帯域衝突検出アルゴリズムは比較的微妙で理解しづらいものです。安価な矩形衝突テストがどのようなものかを考えると、n^2アルゴリズムを使用してレッスンを構造化し、次にボーナスという素材を使用して、空間インデックスの考え方を導入するかもしれません。何百もの長方形がありますが、私は愚かな方法では十分に速いと確信しています。
クォドツリーはあなたの目的には問題ありませんが、ノンポイントを扱うときは、交差する象限のすべてを含むノードに矩形を置く必要があります。次に、低ノードにあるものをテストするときには、そのノードとそのすべての祖先のすべての矩形に対してテストする必要があります。
既にソートとスイープのアルゴリズムを検討しているかもしれません。なぜなら、既に得られているのは、軸に合わせたバウンディングボックスだからです。
拡張オブジェクトの場合、境界ボリューム階層が4分木よりも優れた選択肢です。 –
アプリケーションによって異なります。彼は1秒間に何万回もの長方形を扱うことができます。その時点で、最適化について考えることが理にかなっています。または、8ビット、1 MHzプロセッサなどの埋め込みアプリです。 –
私はquadtreeが理解するのが最も簡単だと思います。あなたは交差問題を抱えていますが、それはひどいことではありません。実際には、学生は自分自身でそれを見ることができます。グラフィカルに説明するのも非常に簡単で、教材としても役立ちます。 –
シンプルな2Dのゲームでの初期の試みで検出をスピードアップ一つの簡単な戦略は、長いdimension.The衝突相順にソートされたリストを維持するために、このようなもので構成されました：
for i in 0..n
j = i+1
while rect[j].left < rect[i].right
check for collision in y
j=j+1
endwhile
endfor
はここに簡単ですアルゴリズムは、物事を少し速くし、軸に沿った長方形で動作します。
軸の1つを「ソートされた軸」として選択します。この説明では、X軸がソートされているとします。各矩形をソートされた軸上の2つのノード、「入力」ノード、および「終了」ノードとして指定します。入力ノードは、出口ノードより常に軸上の値が小さくなければなりません。
すべての入力ポイントと終了ポイントのソートされたリストを作成します。
ソートされたリストを参照してください。各「入力」ノードを押すと、入力した矩形のリストにそのノードを追加してから、「入力済み」リストの他のすべてのノードに対してブルートフォースの衝突検出を行います。それぞれの「終了」ノードを押すと、「入力済み」リストからノードを削除します。
「入力済み」リスト自体がY軸上でソートされ、Y軸上の「入力」および「終了」ポイントで並べ替えることができます。
はい。それは私が「並べ替えと掃除」を意味するものです。 –
"the"軸に整列した四角形だけを見ているとしますか？ – erickson
はい、長方形が常に軸と整列していると仮定できます。長方形は決して回転しません。 –