广相碰撞检测方法？

Question

我正在构建2D物理引擎，我想添加广相碰撞检测，尽管我只知道2种或3种类型：

• 检查其他所有内容（O（n ^ 2）复杂度）
• 扫描和修剪（排序和扫描）
• 关于二进制空间分区的一些知识（不确定如何执行此操作）

但是肯定还有更多选择吧？这些是什么？并可以提供每一个的基本描述或描述的链接吗？

我已经看到了这一点，但是我想索取可用的算法列表，而不是满足我需要的最佳算法。

在这种情况下，“宽相碰撞检测”是物理引擎用来确定其模拟中的哪些物体足够接近以值得进一步研究并可能解决碰撞的方法。

Answer 1

最佳方法取决于特定用途，但最重要的是要细分您的世界空间，以便（a）每个实体都精确地在一个细分中，（b）每个细分都足够大，以至于某个细分中的一个实体只能与同一细分或相邻细分中的实体发生碰撞，并且（c）特定细分中的实体的数量应尽可能小。

您如何执行此操作取决于您拥有多少个车身，它们如何运动，对性能的要求是什么以及要在引擎上花费多少时间。如果您正在谈论物体在一个很大的开放空间中移动，最简单的方法是将世界划分为一个网格，其中每个单元格都比最大对象大，并跟踪每个单元格中的对象列表。如果您要在经典街机游戏的规模上构建某种东西，那么此解决方案可能就足够了。

如果您要处理在更大的开放世界中移动的物体，则简单的网格将很快变得不堪重负，并且您可能想要某种基于树的结构，例如四叉树，正如Arriu所建议的那样。

如果您要谈论的是在有界空间而不是开放空间中移动物体，那么您可以考虑使用BSP树；树木将世界划分为“您可以进入的空间”和“墙壁”，然后将尸体修剪到树木中确定其是否处于合法位置。根据世界的几何形状，您还可以使用BSP对世界上的物体之间的碰撞进行广义检测。

在有限空间内移动的物体的另一种选择是门户引擎。如果您的世界可以由凸多边形区域组成，其中多边形的每一边都是实心墙或通往另一个凹空间的“门户”，则可以通过多边形点检验轻松地确定物体是否在区域内，并且仅查看同一区域或连接区域中的物体，即可简化碰撞检测。