游戏算法整理 算法五：飞行射击游戏中的碰撞检测

在游戏中物体的碰撞是经常发生的，怎样检测物体的碰撞是一个很关键的技术问题。在RPG游戏中，一般都将场景分为许多矩形的单元，碰撞的问题被大大的简化了，只要判断精灵所在的单元是不是有其它的东西就可以了。而在飞行射击游戏（包括象荒野大镖客这样的射击游戏）中，碰撞却是最关键的技术，如果不能很好的解决，会影响玩游戏者的兴趣。因为飞行射击游戏说白了就是碰撞的游戏——躲避敌人的子弹或飞机，同时用自己的子弹去碰撞敌人。

　　碰撞，这很简单嘛，只要两个物体的中心点距离小于它们的半径之和就可以了。确实，而且我也看到很多人是这样做的，但是，这只适合圆形的物体——圆形的半径处处相等。如果我们要碰撞的物体是两艘威力巨大的太空飞船，它是三角形或矩形或其他的什么形状，就会出现让人尴尬的情景：两艘飞船眼看就要擦肩而过，却出人意料的发生了爆炸；或者敌人的子弹穿透了你的飞船的右弦，你却安然无恙，这不是我们希望发生的。于是，我们需要一种精确的检测方法。

　　那么，怎样才能达到我们的要求呢？其实我们的前辈们已经总结了许多这方面的经验，如上所述的半径检测法，三维中的标准平台方程法，边界框法等等。大多数游戏程序员都喜欢用边界框法，这也是我采用的方法。边界框是在编程中加进去的不可见的边界。边界框法，顾名思义，就是用边界框来检测物体是否发生了碰撞，如果两个物体的边界框相互干扰，则发生了碰撞。用什么样的边界框要视不同情况而定，用最近似的几何形状。当然，你可以用物体的准确几何形状作边界框，但出于效率的考虑，我不赞成这样做，因为游戏中的物体一般都很复杂，用复杂的边界框将增加大量的计算，尤其是浮点计算，而这正是我们想尽量避免的。但边界框也不能与准确几何形状有太大的出入，否则就象用半径法一样出现奇怪的现象。

　　在飞行射击游戏中，我们的飞机大多都是三角形的，我们可以用三角形作近似的边界框。现在我们假设飞机是一个正三角形（或等要三角形，我想如果谁把飞机设计成左右不对称的怪物，那他的审美观一定有问题），我的飞机是正着的、向上飞的三角形，敌人的飞机是倒着的、向下飞的三角形，且飞机不会旋转（大部分游戏中都是这样的）。我们可以这样定义飞机：中心点O(Xo,Yo),三个顶点P0(X0,Y0)、P1(X1,Y1)、P2(X2,Y2)。中心点为正三角形的中心点，即中心点到三个顶点的距离相等。接下来的问题是怎样确定两个三角形互相干扰了呢？嗯，现在我们接触到问题的实质了。如果你学过平面解析几何，我相信你可以想出许多方法解决这个问题。判断一个三角形的各个顶点是否在另一个三角形里面，看起来是个不错的方法，你可以这样做，但我却发现一个小问题：一个三角形的顶点没有在另一个三角形的里面，却可能发生了碰撞，因为另一个三角形的顶点在这个三角形的里面，所以要判断两次，这很麻烦。有没有一次判断就可以的方法？我们把三角形放到极坐标平面中，中心点为原点，水平线即X轴为零度角。我们发现三角形成了这个样子：在每个角度我们都可以找到一个距离，用以描述三角形的边。既然我们找到了边到中心点的距离，那就可以用这个距离来检测碰撞。如图一，两个三角形中心点坐标分别为（Xo,Yo）和(Xo1,Yo1),由这两个点的坐标求出两点的距离及两点连线和X轴的夹角θ，再由θ求出中心点连线与三角形边的交点到中心点的距离，用这个距离与两中心点距离比较，从而判断两三角形是否碰撞。因为三角形左右对称，所以θ取-90～90度区间就可以了。哈，现在问题有趣多了，-90～90度区间正是正切函数的定义域，求出θ之后再找对应的边到中心点的距离就容易多了，利用几何知识，如图二，将三角形的边分为三部分,即图2中红绿蓝三部分，根据θ在那一部分而分别对待。用正弦定理求出边到中心点的距离，即图2中浅绿色线段的长度。但是，如果飞机每次移动都这样判断一次，效率仍然很低。我们可以结合半径法来解决，先用半径法判断是否可能发生碰撞，如果可能发生碰撞，再用上面的方法精确判断是不是真的发生了碰撞，这样基本就可以了。如果飞机旋转了怎么办呢，例如，如图三所示飞机旋转了一个角度α，仔细观察图三会发现，用（θ-α）就可以求出边到中心点的距离，这时你要注意边界情况，即（θ-α）可能大于90度或小于-90度。啰罗嗦嗦说了这么多，不知道大家明白了没有。我编写了一个简单的例程，用于说明我的意图。在例子中假设所有飞机的大小都一样，并且没有旋转。 

 

 

 

/////////////////////////////////////////////////////////////////////
//example.cpp
//碰撞检测演示
//作者 李韬
/////////////////////////////////////////////////////////////////////
//限于篇幅，这里只给出了碰撞检测的函数
//define/////////////////////////////////////////////////////////////
#define NUM_VERTICES 3
#define ang_30 -0.5236
#define ang60   1.0472
#define ang120 2.0944
//deftype////////////////////////////////////////////////////////////

struct object
{
     float xo, yo;
     float radio;
     float x_vel, y_vel;
     float vertices[NUM_VERTICES][2];
}

//faction/////////////////////////////////////////////////////////////
//根据角度求距离
float AngToDis(struct object obj, float angle)
{
     float dis, R;
     R = obj.radius;
     if (angle <= ang_30)
         dis = R / (2 * sin(-angle));
     else if (angle >= 0)
         dis = R / (2 * sin(angle + ang60));
     else dis = R / (2 * sin(ang120 - angle));
     return dis;
}

//碰撞检测
int CheckHit(struct object obj1, struct object obj2)
{
     float deltaX, deltaY, angle, distance, bumpdis;
     deltaX = abs(obj1.xo - obj2.xo);
     deltaY = obj1.yo - obj2.yo;
     distance = sqrt(deltaX * deltaX + deltaY * deltaY);
     if (distance <= obj.radio)
     {
         angle = atan2(deltaY, deltaX);
         bumpdis1 = AngToDis(obj1, angle);
         return (distance <= 2 * bumpdis);
     }
     ruturn 0;
}
//End//////////////////////////////////////////////////////////////

 

 　上面程序只是用于演示，并不适合放在游戏中，但你应该明白它的意思，以便写出适合你自己的碰撞检测。游戏中的情况是多种多样的，没有哪种方法能适应所有情况，你一定能根据自己的情况找到最适合自己的方法。