私は単純なタイルベースの2Dゲームを開発しています。レベルがあり、タイルや相互にやりとりできるオブジェクトが配置されています。タイルマップとの衝突をチェックすることはかなり簡単であり、複雑な線形のすべてのオブジェクトに対して行うことができます。しかし今、私はオブジェクト間の衝突を検出しなければなりません。そして、私はすべてのオブジェクトを他のすべてのオブジェクトと照合しなければなりません。衝突検出にO（n^2）の複雑さを避ける
私は正方形の複雑さを避けたいと思います。オブジェクト間の衝突検出呼び出しを減らすための既知の方法はありますか？ BSPツリーのようなデータ構造がありますが、これは簡単に維持でき、一度に多くの衝突を拒否することができます。
例えば、レベル内のオブジェクトの総数は、500の周りで約50それらのは、一度に画面に表示されている...
ありがとう！
タイルに、どのオブジェクトがそれらを占有しているかに関する情報を格納させるのはなぜですか。オブジェクトが新しいタイルに移動されるたびに、そのタイルに既に別のオブジェクトが含まれているかどうかを確認することで、衝突を検出できます。
これは事実上何も必要ありません。
+1これはクワッドツリーを使うよりはるかに簡単な解決策です。 –
と非常に高速です。 – Peladao
これは悪くない、あなたはまた、そのような地図上でA *を実行することができます。しかし、バグやその他の制限につながる可能性があることに注意してください。 1つのタイルなどに複数のオブジェクトが必要な場合また、すべてのオブジェクトがタイルに収まらなければならないという制限につながります。そうでなければ、2x1タイルオブジェクトを処理するのが複雑になります。など。 – InsertNickHere
クワッドツリーを使用してスペースを分割し、衝突をチェックする必要があるオブジェクトの数を減らすことができます。 （それはツリーを維持するために、CPUパワーの多くがかかっていることが、それはまた、大幅にチェックの数を減らす - 一見 -
See this article - Quadtree demonstration.
And perhaps this - Collision Detection in Two Dimensions.
Or this - Quadtree (source included)
見えるかもしれません最初のリンクのデモンストレーションを参照してください）。
実際の実行時オーバーヘッドは、多くのオブジェクトに到達するまではかなり小さいことにも注意してください。実際の問題は、コードの複雑さが増えてしまうことです。オブジェクトがタイルのサイズに近いサイズであれば、Peladaoのソリューションはこのケースではうまくいく可能性があります。 –
あなたのゲームはすでにゲームプレイ関連のタイルマップという概念を持っています。このタイルマップを衝突検出に使用するか、スプライト追跡と衝突検出用に特別に使用される競技場に二次グリッドを重ねることができます。
グリッド内では、各スプライトは1つ以上のタイルを占有します。スプライトはどのタイルを占有しているかを知っており、タイルはどのスプライトがそれを占めているかを知っています。スプライトが動くと、スプライトが占めるタイル内の衝突をチェックするだけです。これは、スプライトが同じタイルを占有するのに十分近い場合を除いて、衝突検出が全く必要でないことを意味し、それでも一緒に近いスプライト間の衝突をチェックする必要があります。
ゲームプレイでスプライトが頻繁に絡み合うような場合は、グリッドを四分木として実装して、各タイルを細分することができ、スプライトが同じグリッドタイルを占有しないようにすることができます。
また、実装によっては、衝突を判断するのに使用するよりもタイル占有率を判断するために、少し大きめのバウンディングボックスを使用する必要があります。そうすれば、スプライトが重なるようになり、衝突境界が接する前に同じタイルを占めることが保証されます。
すべてのオブジェクトまたは表示オブジェクトの衝突検出を行いますか？ –
hm。まだ分からない。私は、画面外のオブジェクトとの衝突を無視することができると思います – SadSido
その場合、可視オブジェクトのみを収集し、衝突検出を行うことができます。まだO（n^2）時間の複雑さ。 –