なぜ私は衝突検出でQuadTreeを使うべきですか

私はQuadTreeについていくつか読んでおり、より良い衝突検出のためにそれらをどのように使用することができます。しかし、QuadTreesがなぜ私にもっとパフォーマンスをもたらすのか分かりません。私はこれを2Dゲームで試しています。なぜ私は衝突検出でQuadTreeを使うべきですか

私がQuadTreeを使用している場合は、すべてのフレームでQuadTreeをクリアしてすべてのオブジェクトを挿入し、次にこれをループしてすべての衝突オブジェクトを取得する必要があります。そして、私が必要とする衝突オブジェクトを得るためにこれをループします。なぜこれは、代わりに、すべてのオブジェクトをループするより良いですか？ QuadTreeの場合は、右の場合はO（n logn）が必要です。あなたはすべてのオブジェクト（O（n））を通過する必要がありますので、しかし、私のすべてのオブジェクトをループはO（n）は

Greetz

出典

2016-04-25 R3Tech

これは非常にクールで魅力的な質問ですが、私はそれがStackOverflowのトピックではないと思います。あなたはhttp://gamedev.stackexchange.com/にもっと幸運を祈るかもしれません.QuadTreesは簡単な答えとして、衝突の検出をチェックする必要があるオブジェクトの数を制限し、パフォーマンスを向上させます。衝突検出は、シーン内のすべての単一のオブジェクトに対してチェックする必要がある場合には高価です。 http://www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/ –

は、他のすべてとそれぞれのオブジェクトを比較するには、O（N^2）ですオブジェクトごとに（ほとんど）すべての他のオブジェクトをチェックする必要があります。つまり、別のO（n）がO（n^2）になります。

これはO（n log n）より悪いです。

オブジェクトが5つしかない場合は、すべてのオブジェクトを他のオブジェクトと比較すると、クォードツリーを作成するオーバーヘッドを避けることができます。

また、すべてのオブジェクトがその位置を変更していない場合は、クアッドツリーを再利用することができます。

出典

2016-04-26 08:42:56 TilmannZ

私はすべてのオブジェクトに自分のプレーヤーをチェックする必要があるので、quadtreeなしで動作する方が良いはずですか？ありがとう – R3Tech

オブジェクトが1つしか移動しない場合は、四分木にする必要もありません。クアッドツリーがより良いかどうかは、オブジェクトの数に依存します。ベストそれを試してみてください。 – TilmannZ

なぜ私は衝突検出でQuadTreeを使うべきですか

答えて

関連する問題