使用四叉樹時，如何處理四邊形之間移動的物體？

Question

我正在嘗試在遊戲中使用四叉樹進行碰撞檢測，但我不確定如何處理可能在不同四邊形之間移動的對象？

我能想到的唯一方法是每幀清除整棵樹，然後再把所有東西都加回去，但看起來像這樣可能會導致CPU密集並且效率不高。你是否每幀都檢查每個對象，看看它是否已經移動到當前四邊形的邊界之外，如果是，則將其移除並讀取它？這又似乎可能是非常低效的，因爲你會在每一幀對每個移動物體進行碰撞檢查。

此外，關於四叉樹，但與在其中移動的對象無關，您如何處理同一四邊形中的多個對象？我讀過的大多數網站都說，你應該只有一個，也許是兩個對象，如果你得到的不僅僅是這些，而是​​把它們推到樹上。如果您遇到類似this的情況，該怎麼辦？你有三個圈子，他們都在他們下面的關卡邊緣，所以他們不能再往下走，但同一層有三個圈子，人們說你不應該擁有這三個圈子。

Answer 1

我不認爲這是實施你的建議特別低效：檢查一個對象是否已經移出它的四叉樹，如果是，然後刪除並重新添加它。任何從一幀移動到下一幀的物體都需要進行一些碰撞檢測，當然？而四叉樹操作只在移動四叉樹時纔會執行，並且CPU時間可能會被CPU時間所掩蓋，從而執行更精確的「確定對象是否觸摸對象B？」計算。所以我不知道你可以做得更好。在你的第二個問題上：我不知道其他人是如何實現四叉樹的，但是我允許物體佔據多個四叉樹，正是由於你在圖中給出的原因（當一個物體跨越邊界時） 。所以一個物體有一個「當前四邊形列表」而不是「當前四邊形」。

Answer 2

刪除/重新添加可以通過向上移動四叉樹來完成，而不是完全從樹中移除項目，然後重新添加，即移動到「父」四邊形，然後添加「父」它 - 如果它不適合在「父母」，去「祖父母」等

至於你的第二個問題，你將需要一些靈活性 - 如果所有3個邊緣，那麼你可以不會降低他們 - 但這應該是（赦免雙關語）邊緣案例。