問題タブ [collision-detection]

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

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

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

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

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

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

重力のあるゲームは、プレイヤー、モンスター、オブジェクトなどの動くものと床との関係をどのように処理しますか? プレーヤーは常に床に「落ち」、跳ね返されていますか?

私が見つけた衝突に反応する2つの方法は、プレイヤーを衝突前の以前の場所に戻すことと、移動する前に新しい位置をテストして衝突が発生するかどうかを確認することですが、これらのいずれかがどのように機能するかわかりません上向きに上昇し、プレーヤーを持ち上げることができる必要があるプラットフォームに対処できます。これは 2D ゲーム デザインの観点から見ていますが、3D ゲーム デザインでも同じ問題が発生するのではないかと想像します。ヒントはありますか？チェックアウトする必要がある参照はありますか？ありがとう。

衝突検出に関する文献はたくさんありますが、ほとんどの手法にかなり精通しているので、少なくともそのかなりの部分を読んだことがあります。ただし、しばらくの間、私にはわかりにくいことがあります。StackOverflowを使用すると、多数の優秀な頭脳に一度にアクセスできるため、本棚を掘り下げる前に、まずここで質問したいと思います。

この時代では、CPUではなくGPUに委任される作業が増えており、多くの場合、これは良いことです。たとえば、新しいジオメトリを作成するためのジオメトリシェーダー、または（少し新しいですが、それでも非常に魅力的な）頂点シェーダーがあり、そこに多数の頂点を通過でき、そこからエレガントなものが生まれます。これらのプリミティブはグラフィックハードウェアにのみ存在するため、私が検討していたことは、これらのプリミティブとの信頼性の高い衝突検出をどのように実行するのでしょうか。ある種の非常に単純化されたメッシュが頂点シェーダーで置き換えられていると仮定しましょう（具体的な問題はありません。アイデアをもっと試していますが、ジオメトリシェーダーについてはまだ深く理解していません）。

これまで私が考えてきたのは、適切な角度からパスを分離し、シェーディングを多かれ少なかれオフにし、おそらく低解像度のメッシュで、2番目のプリミティブの内側（面を内側に反転）をレンダリングしたいメッシュと一緒にレンダリングすることです。メッシュに対してテストし、オクルージョンクエリを実行します。メッシュが完全に隠れている場合、交差はありません。もちろん、これには2番目のプリミティブが凸である必要があります。

どういうわけか、この種のテストは、プリミティブの数が増えるにつれて（大部分を直接カリングできる場合でも）非常に高価になると感じています。他の誰かが別のアイデアやテクニックを持っていますか？私はdirectxよりもopenglとcgに精通していますが、directxにいくつかの例があれば、openglの対応物を理解できると思います。

すべてのアイデアに感謝しますので、ブレインストーミングしてください。:)

画面上でボールを跳ね返せる単純な物理モデラーを作成しました。クリック アンド ドラッグしてボールを発射したり、一度に数百個のボールを生成して相互に作用する様子を観察したりできます。

[拡大版へのリンク]

取り組むのは楽しい小さなプログラムでした。できればさらに進めたいと思っています。時期尚早の最適化がすべての悪の根源であると彼らが言うことは知っていますが、実際のパフォーマンスの障壁にぶつかり始めています。ゲーム/シミュレーター開発の経験がある人が助けてくれるかどうか知りたいです.

問題：

現時点では、ボールを追加しすぎるとプログラムが停止します (私のマシンでは 800 個を超えるボールを処理できないようです)。実行すると、シミュレーションが現実的ではなくなり、すべてのボールが下部で重なり合ってしまいます。

問題は衝突検出にあります。最も素朴なケースでは、衝突検出は O(N^2) 問題です。各ボールは、他のすべてのボールをチェックします。これにより、すぐにパフォーマンスが低下します (100 個のボールの後でも、ループ サイクルごとに 10,000 の衝突チェックを行うことになります)。

ここを見ると、数百個のボールを追加したスクリーンショットを見ることができます。シミュレーターが追いつかなくなり、お互いに重なり始めます。

[拡大版へのリンク]

現在、重なっているボールを探すことで衝突を検出しています。重なっている 2 つのボールを見つけた場合は、それらを最小移動距離 (MTD) で離すか、押し離します。次に、単純な物理方程式を使用してインパルス ベクトルを調整し、衝突後に異なる方向に進みます。

ボールが多すぎる場合に最小移動距離が顕著になることを除いて、これはうまく機能します。それらは大量に重なり始め、常に底で互いに押し合います。「重力」を増やせば増やすほど悪くなる。それらへの圧力が増加し、それらが互いに圧縮/重なり合う量が増加します。

繰り返しますが、かなりの N 個のボールを打つまで問題はありません。

現在の最適化方法:

衝突検出 -
スイープとプルーニング- (別名、ソートとスイープ)

x軸に沿ってループサイクルごとにボールに挿入ソートを使用します。挿入ソートの性質により、シミュレーターの一時的な一貫性を活用できます。フレームごとに、ボールの位置がわずかに変化するだけなので、並べ替える作業はそれほど多くありません。これにより、線形ソートの償却された実行時間が O(N^2) の平均実行時間ではなく、O(N) または線形になります。

ボールがソートされているので、衝突をチェックする前に、2 番目のループでいくつかの事前チェックを行います。これで、互いに近くにあるボールをチェックするだけで済み (x 軸に沿ってソートされているため)、xmin が現在のボールの xmax より大きい別のボールに対してボールをチェックするたびに、2 番目のループから抜け出します。 . したがって、何千ものチェックをスキップします。

これを実装したところ、速度が大幅に向上しました。それでも600～800球以上は扱えるようにしたいです。10,000 個のオブジェクト間の衝突検出を同時に簡単に処理できる物理エンジンについて読んだことがあります。

プロファイラーを実行したところ、衝突検出に約 55% の時間が費やされ、レンダリングに約 45% の時間が費やされていることがわかりました。したがって、これらは私の 2 つの最も高価なコストです。

質問：

シミュレーターがより多くのボールを処理できるようにするための、より優れたアルゴリズムまたは手法を思いつきますか?

関連コード:

プロジェクト全体:

svn チェックアウトhttp://simucal-projects.googlecode.com/svn/ballbounce/trunk/

または、ここをクリックして、ブラウザでファイルを手動で参照します。

関心のあるセクション:

• Pastebin: checkCollisions() - w/ Sweep と Prune
• Pastebin: resolveCollision() - Sweep と Prune によってまだ削除されていない場合、高価な真の衝突チェックと解決。
• Pastebin: render() - レンダリングだけで約 45% の時間が費やされます。

このプログラミングゲームを参考に、現在制作中です。

この投稿の回答のおかげで、長方形のすべての点の xy 座標を見つけることができるようになり (回転した場合でも)、壁による衝突検出はほぼ完全に機能するようになりました。

ここで、ボット自体との衝突検出を実装する必要があります (明らかに、アリーナには複数のボットが存在するためです)。

この場合、Square-Square Collision Detection (Non-rotated) は有効ではありません。これは、ボットが角度を付けて回転するためです (ここで説明したように)。

では、この形式の回転四角形の衝突検出を WPF で実装する最良の方法は何でしょうか?

数学が関係しているに違いないと思いますが、通常、WPFにはこれらの数学を「計算」する関数があることがわかります（この場合のように）

さて、140 度に回転した 30x100 の長方形内の点が 200 度に回転した別の 30x100 の長方形の中にあるかどうかを教えてくれるプログラムを書こうとしています。

正直なところ、どこから始めればよいかさえわかりません。通常の計算を行う前にそれらを再回転することを考えましたが、それでも一致しません。

これどうやってするの？

本当に楽しいだけのプロジェクトに取り組んでいるときに、いくつかの問題に遭遇しました。

丸いボール、先のとがった三角形、細い線 (その他の野生動物も) で構成された 2D の世界があります。それらはすべて WorldCreatures のサブクラスです。彼らはこの世界の中を移動することができます。それらが互いに出会うと、衝突が発生します。

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

• 私にとって、Ball-Ball は簡単​​です。位置からの距離を計算し、それを「サイズ」の合計と比較するだけです。
• ボールと世界の端の間の衝突も単純です - 私はそこからの距離をチェックするだけで、デカルト座標では単純です。
• より一般的な問題は - ライン (あるポイントで開始および終了する) またはそこにある可能性のある他のオブジェクト間の衝突を検出する方法は? 線と点の間の距離も簡単に計算できますが、私が欲しいのは

AObject が Objectと衝突するかどうかを示すある種の一般的な方法B。現在のコードは次のようになります。

ここで、衝突検出メカニズムは、どのオブジェクトが衝突できるかに依存する必要があります。効果もそうでしょう。

メモリ内のすべてのオブジェクトのリストを保持し、すべてのステップでそれらすべてをループする必要がありますか? または、このタスクのパフォーマンスを向上させるためのより良い方法はありますか?

2 つの円が重なっているかどうかを計算するメソッドを作成しようとしています。私は次のことを思いつきましたが、さらに最適化できる方法があるかどうか知りたいだけです。

私はボールを動かし、外側の境界と動くパドルとの衝突を検出しなければならないピンポンゲームをやっています。三角法ではなくベクトルを使用して実装したい。

私は数学がとても苦手なので、親切に教えてください。