我正在开发一个2D物理引擎，希望添加广义相撞检测，但我只知道2或3种方法：
- 对每个物体都进行相互检测 (O(n^2) 复杂度)
- 扫描和修剪（排序和扫描）
- 关于二进制空间分割的某些内容（不确定如何实现）
但是肯定还有更多选项，对吗？它们是什么？每个算法可以提供基本描述或指向其描述的链接吗？
我看过这个，但我想要的是可用算法列表，而不是最适合我的需求的算法。
在这种情况下，“广义相撞检测”是物理引擎用来确定模拟中哪些物体足够接近以需要进一步调查和可能进行碰撞解决的方法。
广义相撞检测方法？
29
- RCIX
2
1如果您用更一般的术语来表达问题，可能会得到更好的回应。我对碰撞检测、复杂性和其他一些东西有一点了解，但“广义相撞检测”似乎是领域特定的术语；我敢打赌它是一个简单概念的代码，但我不想花时间去研究它。 - Beta
1感谢大家提供的所有答案，它们都很好，但是它们只涵盖了一种类型的碰撞检测。如果有人能够列出这里列出的所有类型的清单，我将非常感激，否则我将不得不自己制作... - RCIX
10个回答
28
最佳方法取决于具体的用途，但底线是要将世界空间细分，以便(a)每个物体都在一个子区域中，(b)每个子区域足够大，以便特定子区域中的物体只能与该子区域或相邻子区域中的物体发生碰撞，(c)特定子区域中的物体数量尽可能少。
如何做取决于您有多少个物体、它们如何移动、您的性能要求以及您想在引擎上花费多少时间。如果您谈论的是在一个较大的开放空间中移动的物体，最简单的技术就是将世界划分为网格，其中每个单元格都比您的最大对象大，并跟踪每个单元格中的对象列表。如果您正在构建类似于经典街机游戏的规模，这种解决方案可能足够。
如果您处理的是在较大的开放世界中移动的物体，简单的网格很快就会变得不堪重负，您可能需要一些基于树的结构，例如四叉树，正如Arriu所建议的那样。
如果您谈论的是在有界空间内移动物体而不是开放空间内，则可以考虑使用BSP tree；树将世界分成“可行走的空间”和“墙壁”，并将物体剪切到树中确定它是否处于合法位置。根据世界几何形状，您还可以在世界中使用BSP来进行碰撞的广域检测。
另一种有界空间内物体移动的选择是门户引擎；如果您的世界可以由凸多边形区域组成，其中每个多边形的每条边都是实心墙壁或通往另一个凹空间的“门户”，则可以通过点-多边形测试轻松确定物体是否在区域内，并通过仅查看相同区域或连接区域中的物体简化碰撞检测。
如何做取决于您有多少个物体、它们如何移动、您的性能要求以及您想在引擎上花费多少时间。如果您谈论的是在一个较大的开放空间中移动的物体，最简单的技术就是将世界划分为网格，其中每个单元格都比您的最大对象大，并跟踪每个单元格中的对象列表。如果您正在构建类似于经典街机游戏的规模，这种解决方案可能足够。
如果您处理的是在较大的开放世界中移动的物体，简单的网格很快就会变得不堪重负，您可能需要一些基于树的结构，例如四叉树，正如Arriu所建议的那样。
如果您谈论的是在有界空间内移动物体而不是开放空间内，则可以考虑使用BSP tree；树将世界分成“可行走的空间”和“墙壁”，并将物体剪切到树中确定它是否处于合法位置。根据世界几何形状，您还可以在世界中使用BSP来进行碰撞的广域检测。
另一种有界空间内物体移动的选择是门户引擎；如果您的世界可以由凸多边形区域组成，其中每个多边形的每条边都是实心墙壁或通往另一个凹空间的“门户”，则可以通过点-多边形测试轻松确定物体是否在区域内，并通过仅查看相同区域或连接区域中的物体简化碰撞检测。
- Skirwan
11
SphereTrees（在2D中为CircleTrees，实现方式或多或少相同）是四叉树或二叉空间划分树的替代方案。SphereTrees的优点是它们能够很好地处理大量动态对象的负载。如果您的对象经常移动，则BSPTrees和QuadTrees在更新时比Sphere/Circle Tree要慢得多。
如果您有良好的静态和动态对象混合，一个相当好的解决方案是使用QuadTree/BSPTree来处理静态对象，使用Sphere/Circle Tree来处理动态对象。只需记住，对于任何给定的对象，您都需要检查它是否与两棵树相交。
- Russell Newquist
6
所有加速算法都依赖于使用廉价测试来快速排除对象（或对象组），从而减少需要执行的昂贵测试数量。我将算法分为不同类别，每个类别有许多变种。
1. 空间划分。将空间分割并廉价地排除位于不同区域的候选对象。例如，BSP、网格、八叉树等。
2. 对象划分。类似于第一种方法，但聚类更集中在对象本身而不是它们所在的空间上。例如，边界体层次结构。
3. 排序和扫描方法。将对象按空间顺序排列，并排除那些不相邻的对象之间的碰撞。
其中1和2通常是分层的，按需要递归到每个分区。对于3，您可以选择沿不同维度迭代。
权衡取决于场景几何。对象是否聚集在一起还是均匀或稀疏分布？它们大小是否大致相同或存在巨大的尺寸差异？场景是否动态？你能否接受大量预处理时间？
“廉价”的测试实际上覆盖了从非常廉价到有点昂贵的范围。选择最佳算法意味着将廉价测试成本与减少昂贵测试数量的比率最小化。除了算法方面的考虑外，您还需要进行调整，例如担心缓存局部性等。
1. 空间划分。将空间分割并廉价地排除位于不同区域的候选对象。例如，BSP、网格、八叉树等。
2. 对象划分。类似于第一种方法，但聚类更集中在对象本身而不是它们所在的空间上。例如，边界体层次结构。
3. 排序和扫描方法。将对象按空间顺序排列，并排除那些不相邻的对象之间的碰撞。
其中1和2通常是分层的，按需要递归到每个分区。对于3，您可以选择沿不同维度迭代。
权衡取决于场景几何。对象是否聚集在一起还是均匀或稀疏分布？它们大小是否大致相同或存在巨大的尺寸差异？场景是否动态？你能否接受大量预处理时间？
“廉价”的测试实际上覆盖了从非常廉价到有点昂贵的范围。选择最佳算法意味着将廉价测试成本与减少昂贵测试数量的比率最小化。除了算法方面的考虑外，您还需要进行调整，例如担心缓存局部性等。
- Adrian McCarthy
2
一种替代方案是使用简单的网格，比如20x20或100x100（取决于您的世界和内存大小）。这种实现比递归结构（如四叉/bsp树，或球形树）要简单。
在这种情况下，穿过单元格边界的物体会更加简单，并且不像bsp / quad / oct-tree的naive实现那样退化。
使用这种（或其他）技术，您应该能够快速剔除许多对并获得需要进一步研究的潜在碰撞集。
- Macke
1
我刚想出了一个解决方案，它不依赖于网格大小，可能是O(nlogn)（当没有碰撞时是最优的），但最坏情况下为O(nnlogn)（当所有东西都发生碰撞时）。
我还实现并测试了它，这里是源代码的链接。但我还没有将其与暴力解决方案进行比较。
它的工作原理描述如下： （我正在寻找矩形之间的碰撞）
在x轴上，我根据矩形的右边缘进行排序（O(nlogn)）
对于排序后列表中的每个矩形，我取左边缘并进行二分查找，直到找到左边缘左侧最右边的边缘，并将这些矩形插入到可能发生碰撞的X轴集合的这些索引之间（这些是n个矩形，二分查找需要logn，每次插入集合需要O(log n)）
在y轴上，我也是同样的操作
现在，在每个集合中，我都有可能在x轴上发生碰撞（在一个集合中）和在y轴上发生碰撞（在另一个集合中），我相交这些集合，现在我有了x轴和y轴上的碰撞（也就是我取公共元素）（O(n)）
很抱歉描述不太清楚，希望您能从源代码中更好地理解，这里还有一个示例：image
- csiz
3
1我非常理解，实际上我也有类似的东西（Sweep And Prune是官方名称）。不过有一个提示; 你正在使用插入排序吗？对于几乎排序的列表（就像你那里的列表），这是最好的算法，并且可以在http://www.sorting-algorithms.com/insertion-sort找到很好的解释/可视化。 - RCIX
谢谢你提供这个名称，我以为在我的语言中有一个类似的算法。由于矩形会随着时间移动而改变位置（因此变得随机），所以列表并不一定是几乎排序的，因此我使用std::sort。 - csiz
但是想法是每次更新时只调用一次，这样你就可以依赖于列表几乎被排序，并使用插入排序以获得最大性能。 - RCIX
1
我在一个大型项目中使用了四叉树，适用于那些很少移动的游戏对象（减少删除和重新插入操作）。八叉树也是同样的原理。
基本思想是创建一个递归树结构，存储与树根相同类型的4个（四叉）或8个（八叉）子对象。树中的每个节点表示笛卡尔空间的一个部分，例如，在每个适用轴上为 -100 -> +100。每个子项表示同一空间，但由半个进行细分（例如，示例的直接子项将表示 X 轴上的 -100->0 和 Y 轴上的 -100->0）。
假设有一个给定尺寸的正方形或平面。现在在每个轴上通过中心画一条线，将该平面分成4个较小的平面。现在再取其中一个平面再进行同样的操作，直到平面段的大小大约与游戏对象的大小相同。现在你有了树形结构。只有占据同一平面的对象才可能发生碰撞。当您确定哪些对象可能发生碰撞时，从中生成可能碰撞的对象对。在此阶段，广义碰撞检测完成，您可以进入窄带碰撞检测阶段，这是您更精确和昂贵的计算所在的地方。
广义碰撞检测的目的是使用廉价的计算来生成可能的碰撞，并剔除不能发生的接触，从而减少窄带算法必须执行的工作，反过来使整个碰撞检测算法更加有效。
因此，在尝试实施此类算法之前，请自问：
我的游戏中有多少个对象？ 如果有很多对象，则我可能需要广义碰撞检测。如果没有，则窄带应该足够。 另外，我是否处理许多移动对象？
树结构通常会因为移动对象而变慢，因为它们可以随时改变在树中的位置。这要求每帧都需要删除和重新插入对象（可能），这不是最理想的方法。
如果是这种情况，最好使用Sweep and Prune算法，它维护了世界中形状范围的最小/最大堆。对象不需要重新插入，但是每帧需要重新排序堆，尽管这通常比遍历整个树并进行删除和重新插入要快得多。
根据您的编程经验，其中一种可能比另一种更复杂。个人而言，我发现树更直观易懂，但效率较低，容易出错，因为它们引起其他问题，例如如果您有一个物体直接位于轴或根节点中心上方，该怎么办。这可以通过使用松散树来解决，它们具有一些空间重叠，因此当出现这种情况时，始终优先考虑一个子节点而不是其他节点。
基本思想是创建一个递归树结构，存储与树根相同类型的4个（四叉）或8个（八叉）子对象。树中的每个节点表示笛卡尔空间的一个部分，例如，在每个适用轴上为 -100 -> +100。每个子项表示同一空间，但由半个进行细分（例如，示例的直接子项将表示 X 轴上的 -100->0 和 Y 轴上的 -100->0）。
假设有一个给定尺寸的正方形或平面。现在在每个轴上通过中心画一条线，将该平面分成4个较小的平面。现在再取其中一个平面再进行同样的操作，直到平面段的大小大约与游戏对象的大小相同。现在你有了树形结构。只有占据同一平面的对象才可能发生碰撞。当您确定哪些对象可能发生碰撞时，从中生成可能碰撞的对象对。在此阶段，广义碰撞检测完成，您可以进入窄带碰撞检测阶段，这是您更精确和昂贵的计算所在的地方。
广义碰撞检测的目的是使用廉价的计算来生成可能的碰撞，并剔除不能发生的接触，从而减少窄带算法必须执行的工作，反过来使整个碰撞检测算法更加有效。
因此，在尝试实施此类算法之前，请自问：
我的游戏中有多少个对象？ 如果有很多对象，则我可能需要广义碰撞检测。如果没有，则窄带应该足够。 另外，我是否处理许多移动对象？
树结构通常会因为移动对象而变慢，因为它们可以随时改变在树中的位置。这要求每帧都需要删除和重新插入对象（可能），这不是最理想的方法。
如果是这种情况，最好使用Sweep and Prune算法，它维护了世界中形状范围的最小/最大堆。对象不需要重新插入，但是每帧需要重新排序堆，尽管这通常比遍历整个树并进行删除和重新插入要快得多。
根据您的编程经验，其中一种可能比另一种更复杂。个人而言，我发现树更直观易懂，但效率较低，容易出错，因为它们引起其他问题，例如如果您有一个物体直接位于轴或根节点中心上方，该怎么办。这可以通过使用松散树来解决，它们具有一些空间重叠，因此当出现这种情况时，始终优先考虑一个子节点而不是其他节点。
- Ian Young
0
如果你的物体在一个有边界的空间内移动，那么你可以使用网格来将物体分割。将每个物体放入物体完全或部分占据的每个网格单元中。要检查A对象是否与其他对象发生碰撞，请确定A对象覆盖的网格单元格，然后获取这些单元格中唯一对象的列表，并最终测试A对象与每个唯一对象。如果大多数对象通常包含在单个网格单元格中，则此方法效果最佳。
如果你的空间没有边界，则需要实现某种动态网格，在2D中可以根据需要向四个方向扩展。
与更适应性算法（即BSP、Quadtree、Circletree）相比，这种方法的优点是单元格可以在O(1)时间（即常量时间）内访问，而不是O(log N)时间（即对数时间）。但是后者能够自适应于对象密度的大变化。当物体密度在整个空间中相当恒定时，网格方法效果最佳。
- voidstar69
2
我不确定"hashtable"是否确切地算作一个特别相关的碰撞检测算法。 - Paul McMillan
这不是哈希表方法。任何碰撞检测算法都会将空间细分以减少所需的物体对物体比较次数（如问题中所述）。该问题的其他答案提到了空间的自适应分区。我的答案涉及常规的、非自适应的空间分区。这显然存在效率与适应空间内非均匀分布对象之间的平衡取舍。 - voidstar69
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接