15

最初から、衝突検出は O(n^2) の問題のように感じます。

多数のオブジェクトがあり、各オブジェクトが他のオブジェクトと衝突しているかどうかを確認する必要があります。ただし、各オブジェクトを他のすべてのオブジェクトに対してチェックするのは非常に非効率的であることを私は知っています。2 つのボールが互いに近くにさえないのに、なぜ比較的コストのかかる 2 つのボール間の衝突チェックを行うのでしょうか?

私が取り組んでいる簡単なプログラムの例を次に示します。

代替テキスト

1000 個のボールがある場合、単純な衝突検出を使用すると、1000^2 (100 万) のコレクション チェックが発生します。この衝突チェックは、すぐに私のアプリケーションのボトルネックになりました。大まかなフェーズの剪定を実装する必要があります。

2D の円形オブジェクトで作業する場合、衝突チェックを削除するにはどのようなテクニックを使用する必要がありますか? QuadTrees、BSP、空間ハッシュなどについて読んだことがありますが、このユースケースに最も適した方法を整理するのは困難です。

何が最も効果的かについて誰か知っている人はいますか?

4

3 に答える 3

7

空間ハッシュ。これについては、Hugo Elias のページを参照してください。

于 2009-01-05T21:31:09.820 に答える
7

ボールがツリー間を移動するたびにツリーのバランスを取り、再調整する必要があるため、QuadTrees などの複雑なものは使用しません。グリッドを持っているだけでおそらくより効率的です.ボールを動かすたびに、それがどのグリッドセルにあるかを計算し、変更された場合はそこに投げることができます. また、衝突チェックを行う必要があるたびに、中心がグリッド内にあるか、エッジに十分近い場合は隣接するボールをチェックするだけで済みます。

グリッド サイズを試して、最適なサイズを見つけることができます。持っているボールの数によって異なります。

以下のコメントでこれを述べましたが、それは答えの一部になるに値すると思います:何かが動くときにのみ衝突検出を行うので、移動するものをグリッドの正方形内のもの(および上記の隣接するもの)に対してチェックするだけで済みます）。そうすれば、動いていないものの山が下にある場合、すぐにそれらのオブジェクトの衝突がチェックされなくなります。これは、グリッド内で何も動いておらず、グリッドに出入りするものも何もないためです。

于 2009-01-05T21:32:18.023 に答える
2

2番目にGridメソッドです。ボールの2Dシミュレーションは、QuadTrees（キャラクターや建物などの複雑なジオメトリがある場合に一般的に使用されます）やBSP（高濃度など、オブジェクトの分散/濃度が非常に不均一な場合に選択する必要があります）の恩恵を受けません。マルチプレイヤーまたは戦略ゲームのエリアと低集中エリア）

于 2009-01-06T06:52:00.843 に答える