3.1 长方形物体间的碰撞检测 【矩形、德摩根定律】 游戏开发中一个必不可少的要素当属碰撞检测。本小节将介绍长方形（矩形）物体间的碰撞检测的实现。 本章开始介绍游戏开发中必不可少的碰撞检测的实现，而本小节将首先介绍2D游戏中最基本的长方形（矩形）物体之间的碰撞检测。示例程序CheckHit_1_1.cpp 实现了长方形物体间的碰撞检测。运行这个程序会显示“A”与“B”两个长方形，“A”长方形可以通过方向键移动，当其与“B”长方形重叠（即碰撞）时，颜色会变成红色。这个程序中执行碰撞检测的部分如代码清单3-1-1 所示，会运行CheckHit函数。 代码清单3-1-1 对于长方形物体间进行碰撞检测的CheckHit 函数（CheckHit_1_1.cpp 片段） 037 int CheckHit( F_RECT *prcRect1, F_RECT *prcRect2 ) // 碰撞检测 038 { 039 int nResult = false; 040 041 if ( ( prcRect1->fRight > prcRect2->fLeft ) && 042 ( prcRect1->fLeft < prcRect2->fRight ) ) 043 { 044 if ( ( prcRect1->fBottom > prcRect2->fTop ) && 045 ( prcRect1->fTop < prcRect2->fBottom ) ) 046 { 047 nResult = true; 048 } 049 } 050 051 return nResult; 052 } CheckHit函数以两个矩形（长方形）作为入口参数。代表矩形的F_RECT结构体的定义如下所示。 代码清单3-1-2 F_RECT结构体的定义（CheckHit_1_1.cpp 片段） 017 struct F_RECT { 018 float fLeft, fTop; // 左、上 019 float fRight, fBottom; // 右、下 020 }; 结构体通过一个矩形左上角的坐标与右下角的坐标来描述一个矩形（参考图3-1-2）。 CheckHit 函数会对上述形式的两个矩形物体进行碰撞检测。检测过程中首先会通过下面两行代码，对水平方向上矩形重叠的可能性进行判定。 041 if ( ( prcRect1->fRight > prcRect2->fLeft ) && 042 ( prcRect1->fLeft < prcRect2->fRight ) ) 为了便于理解，我们先不要考虑什么情况下物体是可能重叠的，而是换个角度，想一想什么情况下两个物体是不可能重叠的。比如有矩形1、矩形2 两个矩形，以矩形2 为基准（示例程 序中是矩形B），如果矩形1 的右端比矩形2 的左端还靠左，那么就可以认为两个矩形不可能重叠（参考图3-1-3 左）。同理，如果矩形1的左端比矩形2 的右端还靠右，也可以认为两个矩形不可能重叠（参考图3-1-3 右）。 简而言之就是，当矩形1 的右端比矩形2 的左端靠左，或矩形1 的左端比矩形2 的右端靠右时，两个矩形是不可能重叠的。因此，在与上述结论相反的情况下，两个矩形就可能重叠，即矩形1 的右端比矩形2 的左端靠右，并且矩形1 的左端比矩形2 的右端靠左时，两个矩形是可能重叠的。上述理论，只要认真思考一下应该不难理解，在数学上称为德摩根定律。所谓德摩根定律，用程序员习惯的方式来书写的话，就是当有bCond1与bCond2两个条件时， if ( !( bCond1 || bCond2 ) ) 这一条件与 if ( !bCond1 && !bCond2 ) 这一条件在任何情况下都是等价的。同时， if ( !( bCond1 && bCond2 ) ) 这一条件与 if ( !bCond1 || !bCond2 ) 这一条件在任何情况下也是等价的。用文字表述就是，对全体条件的否定，可以分解为对每个子条件的否定。只是这时逻辑运算AND要反转为OR，OR要反转为AND。如果不熟记德摩根定律，虽然也可以通过逻辑推导得出同样的结论，但推导过程难免要占用时间，所以还是背下来比较有效率。 我们已经考虑了水平方向上重叠的情况，接下来对垂直方向也套用同样的方法，就可以得到结论：当矩形1 的下端比矩形2 的上端靠下，并且矩形1 的上端比矩形2 的下端靠上时，垂直方向上矩形1 与矩形2 是可能重叠的。执行这个检测的代码如下所示。 044 if ( ( prcRect1->fBottom > prcRect2->fTop ) && 045 ( prcRect1->fTop < prcRect2->fBottom ) ) 当然，上述检测运行的前提条件，是在水平方向的检测中已经判断得出两个矩形是可能重叠的（如果没有这个前提，上面的if 语句也不会执行）。因此当垂直方向的条件也满足时，矩形 1 与矩形2 就是重叠的。此时， 047 nResult = true; 变量nResult被置为true，并作为CheckHit函数的返回值返回。而如果水平方向和垂直方向的条件都不满足，矩形则是没有重叠的，变量nResult的定义部分 039 int nResult = false; 中，变量nResult的初始值被设置为false，并且直接作为返回值返回。 在上面的讨论中，并没有考虑两个矩形正好在边界碰撞（或者说接触）的情况。比如上文中我们将与“矩形1 的右端比矩形2 的左端靠左”相反的情况视为“矩形1 的右端比矩形2 的左 端靠左”，而这两者都漏掉了一种情况，即“矩形1 的右端与矩形2 的左端正好在同一位置”，因此当满足这个边界条件时应当如何处理，就需要好好考虑一下。 而在上文的示例程序CheckHit_1_1.cpp 中，CheckHit函数并没有处理两端正好位于同一位置的情况。这是由于考虑到矩形是基于左上角及右下角的坐标绘制的，而在现代的3D硬件中，这样的矩形的右端及下端的最后1 像素正好会被省略。在现代的3D硬件中，比如要绘制左上角为（10，10）、右下角为（20，20）的矩形时，最左端的第10 像素会被绘制，而最右端的第20 像素一般则不会被绘制出来。垂直方向也一样，上端的第10 像素会被绘制，而最下端的第20 像素一般则不会被绘制。至于为什么有这样的设定，我也没有详细了解过，但按照这样的设定，并且考虑到让碰撞检测的可视化效果更加真实，当端与端位于同一位置时，我们人为设定其为没有碰撞。读者可以将CheckHit_1_1.cpp中矩形A的移动速度调慢（比如1 帧1 像素），并仔细观察就会发现，当两个矩形重叠时会判定为碰撞，如果只是边缘接触则会判定为没有碰撞。另外读者也可以修改CheckHit函数中的if 语句，全部加入等号，即 041 if ( ( prcRect1->fRight >= prcRect2->fLeft ) && 041 ( prcRect1->fLeft <= prcRect2->fRight ) ) 043 { 044 if ( ( prcRect1->fBottom >= prcRect2->fTop ) && 045 ( prcRect1->fTop <= prcRect2->fBottom ) ) 这样就可以让端与端位于同一位置时也判定为碰撞，那么当两个矩形仅仅边缘接触时，也满足碰撞检测的条件。示例程序CheckHit_1_1.cpp 中是没有等号的，所以端与端在同一位置时就 会判定为没有碰撞。 不过上面的处理方式还不能作为开发类似程序的统一标准，因为在众多绘图硬件及程序库中，也许存在特例会将图形的右端及下端也进行绘制。因此端与端在同一位置的碰撞检测，还 是需要根据具体情况来决定如何处理。