從一開始，碰撞檢測就像是一個O（n^2）問題。應該使用什麼技術來修剪2d碰撞檢查？
你有一堆對象，你需要檢查每個對象是否與任何其他對象發生碰撞。但是，我知道，檢查每個對象與所有其他對象是非常無效的。爲什麼兩個球之間相對昂貴的碰撞檢查，如果他們甚至不接近彼此？
這裏是我的簡單程序的例子我的工作：
如果你有1000個球，然後，如果你與天真的碰撞檢測去你將有1000^2集檢查（一百萬）！這種碰撞檢查很快就成爲我應用程序的瓶頸。 I 需要來實施一些寬泛的修剪。
在使用2D - 圓形對象時，應使用哪些技術來修剪碰撞檢查？我讀過關於QuadTrees，BSP，空間散列等的內容，但很難理清哪種方法最適合這種用例。
有沒有人有什麼可能最適合工作的知識？
我不會使用QuadTrees或其他任何複雜的東西，因爲當樹球在它們之間移動時，您會不斷平衡和重新平衡樹木。只有擁有一個網格可能會更有效率 - 每次移動一個球時，只需計算它所在的網格單元格，並在發生變化時將其放入該網格單元中。每次您需要進行碰撞檢查時，您都可以檢查中心位於網格中的球，或者在距離邊緣足夠近的情況下檢查相鄰的球。
您可以嘗試使用網格大小來查找最佳值。你可能會發現它取決於你有多少球。
我在下面的評論中說過這一點，但我認爲它應該成爲答案的一部分： 只有在某物移動時才進行collsion檢測，因此您只需檢查移動的東西是否與其網格方格中的東西相對如上所述的相鄰的）。這樣，如果你在底部得到一堆沒有移動的東西，那麼很快就不會檢查這些對象是否發生了碰撞，因爲沒有任何東西在網格中移動，也沒有任何東西移動到網格中或者移出網格。
我第二個網格方法。 QuadTrees（通常用於角色和建築物等複雜幾何體時使用）或BSP（如果物體的分散度/濃度非常不均勻，如高濃度時應該選擇）在多人遊戲或戰略遊戲中）
將相關問題添加到我的答案中，並從答案中刪除了問題，因爲它令人分心。 – mmcdole 2009-01-05 21:46:26
很好，@Simucal。 – 2009-01-06 17:23:34