爲什麼我應該使用QuadTree與碰撞檢測

我正在閱讀一些關於QuadTrees以及如何使用它們來實現更好的碰撞檢測。但我不明白爲什麼QuadTrees會帶給我更多的性能。我正在嘗試2D遊戲。爲什麼我應該使用QuadTree與碰撞檢測

如果我使用QuadTree，我必須清除QuadTree的每一幀，然後插入所有對象，然後通過循環來獲取所有可能的碰撞對象。然後通過這個循環來獲得我需要的碰撞對象。爲什麼這會更好，然後循環遍歷所有對象？對於QuadTree，我需要O（n logn）if im right。但通過我的所有對象的循環是O（n）

格爾茨

來源

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），導致O（n^2）。

這比O（n log n）更差。

如果您只有5個對象，比較每個對象與其他對象可能仍然更便宜，因爲您避免了創建四叉樹的開銷。

另外，如果不是所有的對象都改變它們的位置，你也許可以重用四叉樹。

來源

2016-04-26 08:42:56 TilmannZ

因此，如果我只需要檢查我的播放器到所有對象，沒有四叉樹的工作應該更好？謝謝你 – R3Tech

如果只有一個對象移動，它甚至不需要在四叉樹中。四叉樹是否更好取決於對象的數量。最好嘗試一下。 – TilmannZ

爲什麼我應該使用QuadTree與碰撞檢測

回答

相關問題