游戏中的碰撞检测,并不只限于矩形物体。根据实际需求,有时候也需要对圆形物体进行碰撞检测。 本小节就让我们一起来学习圆形与圆形、圆形与长方形物体的碰撞检测。 本小节将介绍圆形与圆形、圆形与长方形物体间进行碰撞检测的方法。 2D游戏中经常会用到3.1 节介绍的矩形物体间的碰撞检测。这主要是由于矩形物体间的碰撞检测通过一些简单的计算就可以实现,在一些低端机器上也能流畅地运行。而如今PC及游戏机都已经迈入高性能时代,即便碰撞检测中包含一些稍复杂的运算,大部分情况下也不会有什么问题。特别是圆形物体间的碰撞检测,由于计算方法相对简单,在2D游戏中也会经常用到。 那么接下来就让我们来看一下圆形物体间的碰撞检测。实际执行的程序为示例程序CheckHit_2_1.cpp。程序中重要的部分是CheckHit函数的内容,如代码清单3-2-1 所示。 代码清单3-2-1 对圆形物体进行碰撞检测的CheckHit 函数(CheckHit_2_1.cpp 片段) 034 int CheckHit( F_CIRCLE *pcrCircle1, F_CIRCLE *pcrCircle2 ) // 碰撞检测 035 { 036 int nResult = false; 037 float dx, dy; // 位置坐标之差 038 float ar; // 两圆半径之和 039 float fDistSqr; 040 041 dx = pcrCircle1->x - pcrCircle2->x; // ⊿ x 042 dy = pcrCircle1->y - pcrCircle2->y; // ⊿ y 043 fDistSqr = dx * dx + dy * dy; // 距离的平方 044 ar = pcrCircle1->r + pcrCircle2->r; 045 if ( fDistSqr < ar * ar ) { // 直接使用平方进行比较 046 nResult = true; 047 } 048 049 return nResult; 050 } 其中被作为CheckHit函数的参数所传递的F_CIRCLE结构体如下所示。 代码清单3-2-2 F_CIRCLE结构体的定义(CheckHit_2_1.cpp 片段) 014 struct F_CIRCLE { 015 float x, y; // 圆心 016 float r; // 半径 017 }; 像这样,程序会通过两个圆的圆心及半径,来检测两个圆是否有碰撞。 至于具体要如何计算,可能数学好的朋友会想到:检测两个圆是否有交点,可以联立两圆的方程式,然后根据判别式求解。其实大可不必如此麻烦。判断两圆是否有碰撞,只要将两圆圆心之间的距离与两圆的半径之和相比较即可(参考图3-2-2)。 如此一来,就无需再考虑一个圆是否完全包含另一个圆或者两圆间是否有交点等情况,只需要一个条件就可以进行圆形物体间的碰撞检测。 那么就让我们来实际比较一下两圆圆心间的距离与两圆半径之和吧。假设圆1 的圆心为(x1,y1),圆1 的半径为r1,圆2 的圆心为(x2, y2),圆2 的半径为r2,两圆圆心间的距离为l,根据勾股定理有下列等式成立(参考图3-2-3)。 l x x l x x y y y y 2 1 2 1 2 2 1 2 2 2 1 2 ` 2 = - = - + + - - ] ] ] ] g g g g 然后再将l 与两圆的半径之和r1+r2比较,如果小于则可判定为碰撞。 在示例程序CheckHit_2_1.cpp 的CheckHit函数中,为了节省计算时间,并没有完全按照上面的等式书写语句,而是使用了略有不同的判定方法。可以看到在示例程序的CheckHit函数中,并没有计算平方根的sqrtf 函数。这是因为该程序并没有直接使用圆心间的距离l,而是通过比较距离的平方来进行的碰撞判定。这使用了数学中的当a1H0、a2H0时,如果a1 a 2 2 1 2,则必 有a11a2这一原理(可参考小节末的POINT部分)。因为参与比较的对象为距离,都为非负数,所以距离之间的比较,与距离的平方之间的比较,所得到的结果是一样的。这个结论在游戏的碰撞检测中有时会用到,请读者最好能记下来。 由于距离不可能为负数,所以距离之间的比较,与距离的平方之间的比较,其结果是一样的,直接比较平方还能节省计算时间。 将平方之间的比较写成语句,首先当 l1r1+r2 时,两圆碰撞。由于lH0 且r1+r2H0,因此分别对两边平方,得到 l2 r r 1 2 1] + g2 由勾股定理可知l2 x x y y 1 2 2 1 2 =] - g +] - g2,将其代入上式,得到 x1 x2 y y r r 2 1 2 2 1 2 ] - g +] - g 1] + g2 即得到了CheckHit函数中的条件语句。通过这种方式来回避平方根运算是非常有意义的,因为通过对平方进行比较,可以将平方根运算替换为乘法运算。而平方根运算的速度依赖于CPU的浮点数运算能力,与乘法运算所花费的时间有巨大差别。根据硬件结构的不同,两者的差距有时可达10 倍以上,因此凡是能回避平方根运算的地方,都应该尽可能地在程序中使用上述方法。 ●圆形与长方形的碰撞检测 接下来就让我们来学习圆形与长方形的碰撞检测。由于圆形与长方形的形状存在差异,这类碰撞检测会稍微复杂一些。最终实现的程序请参考示例程序CheckHit_2_2.cpp。这个程序中重要的部分是CheckHit 函数的内容,由于程序比较长,这里就不直接引用代码了。本小节仅从理论层面讲解一下实现的思路,具体代码请读者自行查阅示例程序(源代码下载地址请参考文前的“关于本书”)。 在CheckHit_2_2.cpp的CheckHit函数中,主要可以分为以下两个阶段进行碰撞检测。 1. 将需要检测的长方形,在上下左右4个方向均向外扩张,扩张的长度为圆半径r,如果扩张后得到新的长方形内包含了圆心坐标,则认为两物体具备碰撞的可能(反之则无碰撞的可能)。 2. 在满足条件1 的情况下,如果圆心坐标在原长方形以外、扩张后的长方形的左上、左下、右上、右下四个角处,且圆内没有包含长方形最近的顶点,则认为两物体没有碰撞。 步骤1、2 的判定请参考图3-2-4。之所以通过这种方式检测,是因为按照一般的思维方式,仅仅考虑长方形的各边是否与圆形相交,是不够全面的,还必须考虑到圆形完全包含长方形, 或长方形完全包含圆形等情况。因此在CheckHit_2_2.cpp 中,并没有去检查长方形的各边与圆周是否相交,而是针对长方形包含圆形这一特殊情况,先进行了条件1 的检测,然后又针对圆形包含长方形的情况,进行了条件2 的检测。 具体来说,首先条件1 的检测是以长方形为中心来考虑的。之所以将各边向各方向扩张半径r 形成新的长方形,是因为圆的半径为r,当圆心在原长方形之外,且与长方形的距离为r 时,圆与长方形也有可能发生碰撞。但是扩张后的长方形的四个角,即边长为r 的正方形区域则需要特殊判断(参考图3-2-4)。因为在这个区域中包含圆心的情况下,仍然存在圆的上下左右端都与原长方形不相交的可能性,这时就需要根据条件2 进行判断。条件2 的检测是以圆形为中心的,从这个角度出发来考虑圆形不包含长方形的情况应该更加容易理解。判断圆形不包含长方形,或者以圆形为中心检测时判断二者没有发生碰撞的最简单的条件是:长方形的4 个顶点中,离圆心最近的顶点没有在圆内。即当满足条件1 而不满足条件2 时,就可以认为两物体没有碰撞。之所以按这样的顺序进行两个阶段的判定,是为了尽可能地减少计算量。首先进行简单的判定,将明显不是碰撞的情况排除,并判断是否有必要进行有距离(确切来说是距离的平方)计算的条件2 的判定,而只有在必要时,才会进行最终的计算处理。 图3-2-4 将长方形向外扩张圆半径r来进行碰撞检测 扩张 扩张 r r r r 当a1H0 且a2H0 时,如果a1 2<a2 2 则a1<a2 的证明 a1 a 2 2 1 2 将 a2 2 移项到左边得到 a1 a 0 2 2 ] - 2g1 将左边因数分解得到 ]a1+a2g]a1-a2g10 由于a1H0 且a2H0 时,a1+a2H0,这样一个正值乘以(a1-a2) 为负值,所以(a1-a2) 为负值,即 ]a1-a2g10 将a2 移项到右边得到 a11a2 即得到证明。另外,根据y=x2 这个函数在xH0 的范围内是单调递增函数,也可以证明当a1H0 且a2H0 时,如果a1 2<a2 2,则a1<a2。