我正在构建一个游戏引擎，我想知道：有没有时间复杂度为 O(N^log N) 的碰撞检测算法？
我还没有编写任何编码，但我只能想到一个 O(N^2) 算法（即：2 个 for 循环遍历对象列表以查看是否存在冲突）。
任何建议和帮助将不胜感激。
谢谢
问问题
1717 次
4 回答
3
空间分区可以创建 O(n log(n)) 解决方案。根据对象的确切结构和性质，您将需要不同的空间分区算法，但最常见的是八叉树和 BSP。
基本上，空间分区的想法是按对象占据的空间对对象进行分组。节点 Y 中的对象永远不会与节点 X 中的对象发生碰撞（除非 X 是 Y 的子节点，反之亦然）。然后，您将对象划分为进入哪些节点。我自己实现了一个八叉树。
于 2012-05-10T16:35:14.373 回答
2
您可以通过将对象分类到空间区域来最小化检查次数。（检查 0,0 附近的对象和 1000,1000 附近的对象之间的碰撞是没有意义的）
显而易见的解决方案是将您的空间连续分成两半并使用树（BSP）结构。尽管这对稀疏的物体云最有效，否则您会一直检查边界附近的物体是否碰到边界另一侧的物体
于 2012-05-10T16:27:45.670 回答
2
我假设你有一个有限的交互长度，即当两个对象有一定的距离时，没有更多的交互。如果是这样，您通常会将您的空间划分为适当大小的域（例如，每个方向的交互长度）。现在，要将相互作用应用于粒子，您需要做的就是通过它自己的域和最近的相邻域，因为所有其他粒子都保证比相互作用长度更远。当然，您必须在粒子更新时检查是否跨越了任何域边界，并相应地调整域成员。考虑到由于交互对数的减少而带来的巨大性能改进，这种额外的簿记是没有问题的。对于更多技巧，我建议一本关于数值 N-Body-Simulation 的科学书籍。
当然，每个域都有自己的位于该域中的粒子列表。在模拟中拥有粒子的中央列表并遍历所有条目以检查每个条目是否在当前域或相邻域中是没有用的。
于 2012-05-10T16:29:54.123 回答
1
我将八叉树用于 3D 中的位置，这可能是非常不均匀分布的。树（重新）构建通常非常快，bot O(N log(N))。然后可以在 O(K) 中找到给定粒子的所有碰撞，其中 K 是每个粒子的碰撞次数，特别是没有因子 log(N)。因此，要在树构建之后找到所有碰撞，则需要 O(K*N)。
于 2012-05-10T17:04:13.557 回答