为什么我应该使用带有碰撞检测的四叉树

Why I should use QuadTree with Collision Detection

本文关键字：碰撞检测 四叉树 我应该 为什么      更新时间：2023-09-26

我正在阅读一些关于QuadTrees以及如何使用它们进行更好的碰撞检测的信息。但我不明白为什么QuadTrees能给我带来更多的性能。我正在 2D 游戏中尝试这个。

如果我使用的是四叉树，我

必须在四叉树的每一帧上清除并插入我的所有对象，然后我循环访问它以获得所有可能的碰撞对象。然后循环通过它来获得我需要的碰撞对象。为什么这比遍历我的所有对象更好？对于四叉树，如果我正确的话，我需要 O（n logn）。但是通过我所有对象的循环是 O（n）

格莱兹

将每个对象与所有其他对象进行比较是 O（n^2），因为您需要遍历所有对象 （O（n）），对于每个对象，您需要检查（几乎）所有其他对象，所以这是另一个 O（n），结果为 O（n^2）。

这比 O（n log n） 更糟糕。

如果您只有 5 个左右的对象，将每个对象与其他对象进行比较可能仍然更便宜，因为您可以避免创建四叉树的开销。

此外，如果不是所有对象都更改其位置，则可以重用四叉树。

相关文章：