1

2 次元の世界に動的なオブジェクトがたくさんあるとしましょう。たとえば、キャラクター、投射物、パワーアップなど、ゲームでよく見られるものです。それらのすべてが動いています。それらの間の衝突を検出したいと考えています。それを行う良い方法は何ですか？

四分木を見てきましたが、動的に移動するオブジェクト間の衝突を検出するようです。フレームごとに四分木を再作成する必要があります (オブジェクトはフレームごとに位置が変わるため)。これはコストのかかる操作のように見えます。

四分木以外に、この問題に対する他のアプローチはありますか? 四分木アプローチを改善する方法はありますか? 結局のところ、すべてのフレームでツリーを再作成することはそれほどコストがかからないのでしょうか?

4

1 に答える 1

1

通常、（古いものを捨てて新しいものを構築するのではなく）四分木を更新しますが、これは思ったほど高価ではありません。通常、オブジェクトは各フレームでわずかな距離しか移動しないため、大部分は同じままです。四分木のノードであり、いくつかの変更があります。すべてのアイテムが主要な境界を越えて移動し、削除して再挿入する必要がある最悪の場合でも、コストはO（n log n）のみです。しかし、多かれ少なかれ、すべてのアイテムのループはこれだけの費用がかかるので、もう1つのループはそれほど大したことではありません。

于 2012-09-13T16:23:20.427 に答える