14

若年成人向けの衝突判定ゲームのチュートリアルをデザインしているので、わかりやすくするためにできるだけシンプルにしたいと思います。

要件は非常に単純です。世界は2Dであり、（任意のサイズの）長方形のみが含まれています。BSPや四分木でさえ、やり過ぎのように見えますが（ここでも、単純さに重点が置かれています）、n（n-1）/2の可能なすべての衝突をブルートフォースするよりも効率的なものが必要です。

2D、長方形のみ、およびシンプル。

誰かが私が調べることができるアルゴリズムを指すことができますか？四分木アルゴリズムは私が探しているものですか？

編集：また、長方形は決して回転しません（私はそれを単純に保ちます）。そして、私が取り組んでいるスケールのアイデアを与えるために、Pygameを使用してPythonで実装された典型的なユーザーのラップトップ/デスクトップ（5歳未満）で実行されている数百の長方形のオーダーがあります。

4

3 に答える 3

8

私の経験では、すべてのブロードフェーズ衝突検出アルゴリズムは比較的巧妙で理解しにくいものです。四角形の衝突テストがいかに安価かを考えると、n^2 アルゴリズムを使用してレッスンを構成し、ボーナスマテリアルとして、空間インデックスのアイデアを紹介します。四角形の数が数百に満たないので、ばかげた方法で十分高速であるに違いありません。

四分木は目的には問題ありませんが、ポイント以外を扱う場合は、交差するすべての四分円を含むノードに四角形を配置する必要があることに注意してください。次に、下位ノードにあるものをテストするときは、そのノードとそのすべての祖先のすべての四角形に対してテストする必要があります!

既に取得しているのは軸に沿ったバウンディング ボックスであるため、並べ替えとスイープのアルゴリズムを検討することもできます。

于 2009-11-24T21:18:56.227 に答える
7

単純な 2D ゲームでの初期の試みで検出を高速化した単純な戦略の 1 つは、長い次元で並べ替えられたリストを維持することでした。衝突フェーズは、次のようなもので構成されていました。

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
于 2009-11-24T21:43:14.047 に答える
3

これは、物事を少し高速化し、軸に沿った長方形で機能する単純なアルゴリズムです。

軸の 1 つを「並べ替えられた軸」として選択します。この説明では、X 軸がソートされているとします。各四角形を、並べ替えられた軸上の "enter" ノードと "exit" ノードの 2 つのノードとして指定します。開始ノードは、常に、終了ノードよりも軸上の値が小さい必要があります。

すべての開始点と終了点のソート済みリストを作成します。

ソートされたリストをたどります。各「入力」ノードをヒットすると、それを「入力」長方形のリストに追加し、「入力」リスト内の他のすべてのノードに対してブルートフォース衝突検出を実行します。各「終了」ノードにヒットしたら、「入力済み」リストから削除します。

次に、「入力」リスト自体が Y 軸上でソートされ、Y 軸の「入力」ポイントと「終了」ポイントが配置される演習を読者に説明することができます。

于 2009-11-24T21:44:16.030 に答える