c++ - 用于碰撞检测的 O(n^log n) 算法

Question

我正在构建一个游戏引擎，我想知道:是否有任何时间复杂度为 O(N^log N) 的碰撞检测算法？

我还没有编写任何代码，但我只能想到 O(N^2) 算法(即:2 个 for 循环遍历对象列表以查看是否存在碰撞)。

我们将不胜感激任何建议和帮助。

谢谢

Answer 1

空间分区可以创建 O(n log(n)) 的解决方案。根据对象的确切结构和性质，您需要不同的空间分区算法，但最常见的是八叉树和 BSP。

基本上，空间分区的想法是根据对象占据的空间对它们进行分组。节点 Y 中的对象永远不会与节点 X 中的对象发生碰撞(除非 X 是 Y 的子节点，反之亦然)。然后，您将对象划分为进入哪些节点。我自己实现了一个八叉树。