关于算法:用于2D碰撞检测的技术资源?

关于算法:用于2D碰撞检测的技术资源?

Resources of techniques use for collision detection in 2D?

您认为哪些最佳资源(书籍或网页)描述了在2D环境中用于碰撞检测的算法或技术?

我只是渴望学习不同的技术来制作更复杂,更高效的游戏。
----------------------------------------


冲突检测通常是一个两个阶段的过程。某种"宽相位"算法,用于确定两个对象是否甚至有重叠的机会(试图避免进行n ^ 2比较),其后是"窄相位"碰撞检测算法,该算法基于您的应用程序的几何要求。

Sweep and Prune是一种行之有效的高效广相算法(具有一些可能适合您或可能不适合您的应用的变体),用于对象进行相对物理运动(快速移动的物体或大小和边界区域可能相差很大的物体)使它不合适)。 Bullet库具有3d实现供参考。

窄相碰撞通常可以像" CircleIntersectCircle"那样简单。同样,Bullet库具有良好的参考实现。在3d土地上,需要对任意物体进行更精确的检测时,GJK属于当前的农作物-据我所知,没有什么可以阻止GJK适应2d的(但最终结果可能比蛮力逼迫您的所有边缘还要慢; )

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


Metanet软件已发布了一些相关的教程。 Metanet开发了N(针对Windows,Mac,Linux,基于Flash)和N(针对X360,DS和PSP)。


我个人很喜欢保罗·伯克(Paul Bourke)的作品。

此外,保罗·内特尔(Paul Nettle)曾经写过这个话题。他拥有完整的3D碰撞检测库,但是您可能会对此类库(非常适用于2D)背后的想法感兴趣。为此,请参阅使用椭球的游戏的常规碰撞检测。


克里斯特·埃里克森(Christer Ericson)的著作《实时碰撞检测》(Real-Time Collision Detection)(ISBN:1-55860-732-3)是一本新书(2005年),该书广受赞誉,应该会给您一些很好的答案。

它从您需要了解的一些数学基础入门开始,然后介绍了碰撞检测中常用的各种类型的边界体积(球体,轴对齐的边界框,定向的边界框)。 >

接下来要讨论的是用于检测图元的各种组合(例如直线,三角形,球体,多边形,平面,边界体积等)之间的碰撞的众多算法。

同样重要的是覆盖一些主要的空间划分方法和对象组织方式(体积层次结构,BSP树,八叉树等)。这从本质上加快了碰撞检测的速度,因为它允许您细分对象,从而避免了对象之间不必要的比较(例如,我从我的数据结构中知道对象A离对象B太远了,所以我什至不做距离检查)。

它还涵盖了一些有关如何实际检查运动对象(间隔等)之间的碰撞的内容,但请注意,即使这本相当笨重的书并涵盖了相当多的内容,它也用于碰撞检测,而不是解决方法或回复。因此,它将帮助您确定两个对象是否已发生碰撞,但并不是真正要解决该问题,即如何解决它。相交测试通常会为您提供做出此类决策所需的数据,但是就编写求解器的一般问题而言,该求解器使用冲突检测例程来检测冲突,然后决定如何处理冲突,因此本书不涉及深度。


如果将对象表示为2D空间中的点,则可以使用线相交来确定两个对象是否发生碰撞。您可以使用类似的逻辑来检查一个对象是否在另一个对象内(因此,即使它们的任何一条线当前都不相交,它们也已发生碰撞)。做到这一点的数学很简单,任何有关基本几何的教科书都应涵盖。但是,检测对象是否已完全通过对象可能会有些棘手。


推荐阅读