我正在构建一个 2D 物理引擎，我想添加宽相碰撞检测，尽管我只知道 2 或 3 种类型：
但肯定有更多的选择，对吧？这些是什么？是否可以提供每个的基本描述或描述的链接？
我已经看到了这一点，但我要求提供可用算法的列表，而不是最适合我需要的算法。
在这种情况下，“宽相碰撞检测”是物理引擎用来确定其模拟中哪些物体足够接近以保证进一步调查和可能的碰撞解决的方法。
最好的方法取决于具体的用途，但底线是你想要细分你的世界空间，这样（a）每个身体都在一个细分中，（b）每个细分都足够大，以至于一个身体在一个特定的细分中只能与同一细分或相邻细分中的物体发生碰撞，并且（c）特定细分中的物体数量尽可能少。
你如何做到这一点取决于你有多少身体，它们是如何移动的，你的性能要求是什么，以及你想花多少时间在你的引擎上。如果您谈论的是在一个很大的开放空间中移动的物体，最简单的技术是将世界划分为一个网格，其中每个单元格都大于您最大的对象，并跟踪每个单元格中的对象列表。如果您要在经典街机游戏的规模上构建一些东西，那么这个解决方案可能就足够了。
如果您正在处理在更大的开放世界中移动的物体，那么简单的网格将很快变得难以应付，并且您可能需要某种基于树的结构，例如四叉树，正如 Arriu 所建议的那样。
如果您正在谈论在有界空间而不是开放空间内移动物体，那么您可以考虑使用BSP 树；树将世界划分为“您可以走进的空间”和“墙壁”，将身体剪入树中确定它是否处于合法位置。根据世界几何形状，您还可以使用 BSP 对世界中物体之间的碰撞进行宽相位检测。
在有界空间中移动的物体的另一个选择是门户引擎。如果您的世界可以由凸多边形区域组成，其中多边形的每一边都是实心墙或通往另一个凹空间的“门户”，您可以通过多边形点测试轻松确定物体是否在区域内通过仅查看同一区域或连接区域中的物体来简化碰撞检测。
QuadTrees 或 BSPTrees 的替代方案是SphereTrees（2D 中的 CircleTrees，实现或多或少相同）。SphereTrees 的优点是它们可以很好地处理大量动态对象。如果您的对象不断移动，那么 BSPTrees 和 QuadTrees 的更新速度要比 Sphere/Circle Tree 慢得多。
如果您有静态和动态对象的良好组合，一个相当好的解决方案是使用 QuadTree/BSPTree 作为静态对象，使用 Sphere/Cicle Tree 作为动态对象。请记住，对于任何给定的对象，您都需要对照两棵树检查它。
所有加速算法都依赖于使用廉价的测试来快速排除对象（或对象组），从而减少您必须进行的昂贵测试的数量。我按类别查看算法，每个类别都有很多变化。
空间划分。瓜分空间，廉价地排除不同地区的候选人。例如，BSP、网格、八叉树等。
对象分区。与 #1 类似，但聚类更关注对象本身而不是它们所在的空间。例如，边界体层次结构。
排序和扫描方法。将对象在空间上按顺序排列，并排除不相邻对象之间的碰撞。
1 和 2 通常是分层的，根据需要递归到每个分区。使用 3，您可以选择沿不同维度进行迭代。
权衡很大程度上取决于场景几何。对象是聚集在一起还是均匀分布或稀疏分布？它们的大小都差不多还是大小有很大差异？场景是动态的吗？你能负担得起大量的预处理时间吗？
“便宜”的测试实际上是从非常便宜到有点贵的范围内。选择最佳算法意味着最小化廉价测试的成本与减少昂贵测试数量的比率。除了算法问题之外，您还需要进行调优，例如担心缓存位置。
另一种方法是普通网格，例如 20x20 或 100x100（取决于您的世界和内存大小）。该实现比递归结构更简单，例如四叉树/bsp 树（或球树）。
在这种情况下，跨越单元格边界的对象稍微简单一些，并且不会像 bsp/quad/oct-tree 的简单实现那样退化。
使用该（或其他技术），您应该能够快速剔除许多对并获得一组需要进一步调查的潜在碰撞。
我刚刚提出了一个不依赖于网格大小的解决方案，并且可能是 O(nlogn) （这是没有碰撞时的最佳值），但在 O(n n logn) 时最差（当一切都发生碰撞时）。
我也实现并测试了它，这里是源代码的链接。但我没有将它与蛮力解决方案进行比较。
它是如何工作的描述：（我正在寻找矩形的碰撞）
在 x 轴上，我根据矩形的右边缘（ O(nlogn) ）对矩形进行排序
对于排序列表中的每个矩形，我取左边缘并进行二进制搜索，直到在左边缘的左侧找到最右边的边缘，并将这些矩形插入到可能的_Collision_On_X_Axis 集合中的这些索引之间（这些是 n 个矩形，登录二进制搜索，n 在 O(log n) 每次插入时插入 int 集合）
在y轴上我做同样的事情
在每个集合中，我现在在 x（在一个集合中）和 y（另一个集合）上可能发生碰撞，我与这些集合相交，现在我在 x 轴和 y 轴上都有碰撞（这意味着我采取共同元素）（O（n））
抱歉描述不佳，希望您从源头上更好地理解，这里也是一个示例：图片
你可能想看看 Scott 在Chipmunk中使用空间散列做了什么。源是免费的。我认为他使用了与Box-2D类似的技术，如果不是为了碰撞，肯定是为了接触持久性。
我在一个较大的项目中使用了四叉树，这对于移动不大的游戏对象（较少的移除和重新插入）很有用。同样的原则也适用于八叉树。
基本思想是，您创建一个递归树结构，其中存储 4 个（对于四边形）或 8 个（八角形）与树根相同类型的子对象。树中的每个节点代表笛卡尔空间的一部分，例如，每个适用轴上的 -100 -> +100。每个孩子代表相同的空间，但被细分为一半（示例的直接孩子将表示，例如，X 轴上的 -100->0 和 Y 轴上的 -100->0）。
想象一个具有给定尺寸的正方形或平面。现在在每个轴的中心画一条线，将该平面分成 4 个较小的平面。现在取其中一个，一次又一次地做，直到你到达一个平面段的大小大致是游戏对象大小的点。现在你有了你的树。只有占据同一平面的物体才有可能发生碰撞。当您确定哪些对象可以碰撞时，您会从它们生成可能的碰撞对。在这个阶段，broadphase 已经完成，您可以进入窄相碰撞检测，这是您进行更精确和昂贵计算的地方。
Broadphase 的目的是使用廉价的计算来生成可能的碰撞，并剔除不可能发生的接触，从而减少窄相算法必须执行的工作，进而使您的整个碰撞检测算法更加高效。
因此，在您继续尝试实现这样的算法之前，就像您自己一样：
我的游戏中有多少个对象？如果有很多，我可能需要一个广泛的阶段。如果不是，那么 Nnarrowphase 就足够了。另外，我是否在处理许多移动物体？
树结构通常会因移动物体而减慢速度，因为它们可以随着时间的推移改变它们在树中的位置，只需移动即可。这要求在每一帧（可能）中移除并重新插入对象，这比理想的要少。
如果是这种情况，最好使用 Sweep 和 Prune，它可以保持世界中形状范围的最小/最大堆。对象不需要重新插入，但堆需要在每一帧都重新使用，认为这通常比树宽、删除和重新插入遍历要快。
根据您的编码经验，一种编码可能比另一种更复杂。就我个人而言，我发现树对代码来说更直观，但效率较低，而且更容易出错，因为它们会引发其他问题，例如如果您有一个直接位于轴或中心顶部的对象该怎么办的根节点。这可以通过使用具有一些空间重叠的松散树来解决，这样当这种情况发生时，一个子节点总是优先于其他子节点。
如果您的对象在其中移动的空间是有界的，那么您可以使用网格来细分您的对象。将每个对象放入对象覆盖（完全或部分）的每个网格单元中。要检查对象 A 是否与任何其他对象发生碰撞，请确定对象 A 覆盖的网格单元格，然后获取这些单元格中唯一对象的列表，最后针对每个唯一对象测试对象 A。如果大多数对象通常包含在单个网格单元中，这种方法效果最好。
如果您的空间没有界限，那么您将需要实现某种动态网格，该网格可以在四个方向（二维）中的每一个方向上按需增长。
这种方法相对于更具自适应性的算法（即 BSP、Quadtree、Circletree）的优势在于可以在 O(1) 时间（即恒定时间）而不是 O(log N) 时间（即对数时间）内访问单元。然而，后一种算法能够使自己适应物体密度的巨大变化。当对象密度在整个空间中相当恒定时，网格方法效果最佳。
我想推荐 Ian Millington 的游戏物理介绍性参考，游戏物理引擎开发。它有一个关于广泛相位碰撞检测和示例代码的重要部分。
