5

作成中のゲームでクワッドツリーを衝突検出に使用しようとしていますが、異なるクワッド間を移動している可能性のあるオブジェクトを処理する方法がわかりません。

私が考えることができる唯一の方法は、フレームごとにツリー全体をクリアしてから、そこにすべてを追加することですが、それはCPUを集中的に使用し、あまり効率的ではないようです. フレームごとに各オブジェクトをチェックして、現在のクワッドの境界の外に移動したかどうかを確認し、移動した場合は削除して再読み込みしますか? フレームごとにすべての移動オブジェクトに対して衝突チェックを実行することになるため、これもかなり非効率的なように思えます。

また、四分木についてですが、その中で動き回るオブジェクトとは関係ありませんが、同じクワッド内の複数のオブジェクトをどのように処理しますか? それらについて私が読んだほとんどのサイトでは、クワッド内のオブジェクトは 1 つ、場合によっては 2 つだけにする必要があり、それ以上のオブジェクトを取得した場合はツリーに押し下げると書かれています。こんな状況だったら？3 つの円があり、それらはすべてその下のレベルの端にあるため、それ以上下に行くことはできませんが、同じレベルに 3 つすべてがあり、人々はあなたが持つべきではないと言っています。

4

2 に答える 2

1

あなたの提案を実装するのが特に非効率的だとは思いません。オブジェクトが四分木の外側に移動したかどうかを確認し、移動した場合は削除して再度追加します。あるフレームから次のフレームに移動するオブジェクトには、衝突検出を実行する必要がありますよね? また、四分木操作は四分木を移動する場合にのみ実行され、そこで費やされる CPU 時間は、より正確な「オブジェクト A はオブジェクト B に接触しますか?」を行う CPU 時間によっておそらく影が薄くなります。計算。だから、あなたがもっとうまくやれるかどうかはわかりません。

2番目の質問について:他の人が四分木をどのように実装するかはわかりませんが、図で指定した理由(オブジェクトが境界にまたがる場合)のために、オブジェクトが複数の四分木を占めることを許可します。そのため、オブジェクトには「現在のクワッド」ではなく「現在のクワッドのリスト」があります。

于 2011-10-29T00:39:31.770 に答える
0

削除/再追加は、アイテムをツリーから完全に削除してから再度追加するのではなく、クアッド ツリーを上に移動することで最適化できます。つまり、「親」クワッドに移動し、「親」に追加させます。 「親」に収まらない、「祖父母」に行くなど。

2番目の懸念については、ある程度の柔軟性が必要です-3つすべてがエッジにある場合、それらを下げることはできません-しかし、それは（しゃれを許して）エッジケースである必要があります.

于 2014-06-02T20:17:40.840 に答える