我正在阅读有关QuadTree的一些知识，以及如何使用它们进行更好的碰撞检测。但是我不明白为什么QuadTrees给我带来了更高的性能。
我正在2D游戏上尝试。
如果我使用的是QuadTree，则必须在每一帧上清除QuadTree并插入所有对象，然后循环遍历以获取所有可能的碰撞对象。然后循环遍历以获得我需要的碰撞对象。
为什么这样做更好，然后遍历我的所有对象呢？
对于四叉树，如果正确，我需要O（n logn）。但是我所有对象的循环是O（n）
格蕾兹
最佳答案
将每个对象与所有其他对象进行比较的结果是O（n ^ 2），因为您需要遍历所有对象（O（n）），并且对于每个对象，您都需要检查（几乎）所有其他对象，因此又是另一个O（n） ，得出O（n ^ 2）。
这比O（n log n）还差。
如果只有5个左右的对象，则将每个对象进行比较可能会更便宜，因为这样可以避免创建四叉树的开销。
此外，如果并非所有对象都改变其位置，则可以重用四叉树。