2D碰撞检测技术的资源是什么？

Question

在您看来，在2D环境中用于碰撞检测的最佳资源（书籍或网页）是什么算法或技术？

我渴望学习不同的技术，以制作更复杂和高效的游戏。

- borrego

Answer 1

碰撞检测通常是一个两阶段的过程。首先需要使用某种“广义相交算法”来确定两个物体是否可能重叠(以尝试避免n^2比较)，然后再使用基于应用程序几何要求的“窄带相交碰撞检测算法”。

扫描和剪枝是一种经过充分验证的高效广义相交算法（具有多种变体，可以适用于您的应用程序），适用于正在运动的物体（快速移动或具有非常不同的大小和边界区域的物体可能不适合） 。 Bullet 库有一个三维实现可供参考。

窄带相交碰撞通常可以简单地使用“CircleIntersectCircle”来实现。同样，Bullet库提供了良好的参考实现。当需要针对任意对象进行更精确的检测时，GJK是当前最佳选择之一——在我的知识范围内，没有什么能够阻止它被改编为二维（但它可能会比直接暴力搜索所有边缘更慢;)。

最后，在进行碰撞检测之后，通常需要某种形式的碰撞响应。 Box 2d是物理响应解决方案的良好起点。

- Jeff

Answer 2

个人而言，我喜欢Paul Bourke的工作。

此外，Paul Nettle曾经就这个话题撰写过文章。他有一个完整的3D碰撞检测库，但您可能更感兴趣的是这些库背后的思想（这对于2D非常适用）。请参见使用椭球体的游戏通用碰撞检测。

- Frank Krueger

---

Paul Bourke的作品似乎已经下线。可在Wayback机器上找到的最新版本为2012年7月22日。 - Domenico De Felice

Answer 3

Metanet Software已发布一些相关教程。Metanet开发N（基于Flash，适用于Windows、Mac和Linux）和N+（适用于X360、DS和PSP）。

- Nikhil Chelliah

Answer 4

Christer Ericson的《实时碰撞检测》（ISBN：1-55860-732-3）是一本近期（2005年）广受好评的书籍，可以为您提供一些很好的答案。

它从您需要了解的一些数学基础开始，并进入常用于碰撞检测的各种边界体类型（球体、轴对齐边界框、定向边界框）。

接下来讨论的是许多算法，用于检测各种基元之间的碰撞，例如线段、三角形、球体、多边形、平面、边界体等。

还有一个重要的内容是涵盖了一些主要的空间划分和组织对象的方法（体积层次结构、BSP树、八叉树等）。这实际上加速了碰撞检测，因为它允许您将对象进行细分，以避免不必要的对象比较（例如，我从我的数据结构中知道对象A距离对象B太远，所以我甚至不会进行距离检查）。

书中还包含如何检测移动物体之间的碰撞（区间等）的一些内容，但需要注意的是，尽管这本书相当厚重且涵盖了材料，它只讨论了碰撞检测，而不是解决或响应。因此，它可以帮助您确定两个对象是否发生了碰撞，但并没有说明如何处理碰撞，也就是说，如何解决它。相交测试通常会给您提供所需的数据来做出这样的决策，但就编写使用碰撞检测例程检测碰撞然后决定如何处理它们的求解器这一普遍问题而言，本书并未深入探讨。

- Slacker

Answer 5

如果您的对象在2D空间中表示为点，则可以使用线段交叉来确定两个对象是否发生了碰撞。您可以使用类似的逻辑来检查一个对象是否在另一个对象内部（因此，即使它们的任何一条线段当前没有相交，它们也已经发生了碰撞）。这个数学问题非常简单，应该被任何基础几何学教科书所涵盖。不过，检测一个对象是否完全穿过另一个对象可能会有些棘手。

- Anders Sandvig