在RPG中碰撞处理过程，就是防止主角人物或者其他NPC向崂山道士学习的过程。在我的想象中的RPG地图都是被分割成N×M的矩阵，每个(n,m)矩阵单元的值可以简化成0和1，0就是可以走路；1就是墙。这样处理就可以很容易的抓出那些没有向崂山道士学艺的人了。但这样看来老张的问题似乎很好解决了，我们只要不停的更新这个矩阵似乎就可以了。如果老张开的是网上一度流行的“液晶版极品飞车”这样似乎就可以了。我们不断更新的是一个矩阵，而且这个矩阵一直在做一个卷轴的动作，如果老张觉得每次要吧[n-1]行的东西搬到[n]行很消耗CPU的话，她甚至可以用两根指针解决这个卷轴。老张是多么希望自己是“液晶版”啊……
但，如果老张是“非液晶版”的《极品飞车》呢？那就麻烦了。最简单的是建立一个XYZ的坐标系，把老张的车子和撞他的车子，分别用八个点确定下来。问题简化为：这俩八点围成的空间在什么时候相交的时候，就是碰撞发生的时候。这样在往下讨论就是空间解析几何的问题了。我在写文章之前，也帮老张推算过一下。不过我发现我的空间解析有点退步看着满纸的(x0,y1,z2)的坐标头脑发昏两眼发黑……
我们把问题的难度降低一些再讨论。如果是在一个二维的空间里面呢？这时老张已经从去医院缝针我们可以不管他了。飞行模拟类游戏FLY（Fly Game）——《雷电III》和射击类游戏STG（Shooting Game）——《魂斗罗》。他们的核心技术就是碰撞处理——胜负的关键不是别人或者他的子弹碰到你，就是你或者你的子弹碰到别人。
把刚才“非液晶版”老张的思路拿过来在进一步抽象一下把所有的物体抽象成用C[(x,y),r]这个二元组表示的圆。碰撞的发生条件就是，在一个XOY坐标中，圆C1和圆C2相切——擦肩而过；相交——老张No.2。根据这个模型，我们可以把问题再简化成一个数学问题。就是当(x1,y1)到(x2,y2)的距离小于r1+r2的时候就是碰撞。似乎很完美，而且很容易实现。但这个模型只能用在UFO躲避陨石的游戏中。因为我们常见的打飞机的游戏中，没有浑圆的飞机。他们的形状经过抽象一般都是三角的或者是其他什么几何图形。这样抽象出来的图形如果做一个外切园的话，就会发现空白了很多。为了让这个空白达到一个折中的情况，这个外切圆就不能完全包围我们的飞机，就会出现机翼没有完全包围的情况。经过如上所述的抽象，如果套用上面提到的那个算法，就会出现两条足可以让你这个游戏被玩家从INSTALL到UNINSTALL不到半小时的理由：
——机枪手扫射，给我把那些敌人打回去！
——是的长官！
——为什么？为什么？我们打不下一架敌人的飞机，我们明明打中了他的右弦
——长官，这是因为那部分右弦是在外切圆之外的。
——这是谁开发的-_-!
——报告长官，在我正前方发现敌人的飞机，他们向我们全速撞击过来。
——右偏舵。
——是长官。
——好像他从我们左翼边上擦过，我们脱险了！
——是的长官，但他们还是装撞上了我们的外切圆，所以，我们爆炸了
——等待补丁吧……
……BOOM……
看来我们需要一个更精确的碰撞判断的方法。
在考虑新的方法的时候，我们在想想我们敬爱的老张同志。老张是怎么撞的？无非就是他开着车子他这次的外壳碰上了别人车子的外壳这样就撞了。由此可见“外壳”就是在碰撞处理中的一个关键点，我们把“外壳”变化一个名词叫他“边框”——这个边框其实是游戏实体没有的，用户也是看不见的。有个边框概念之后，检查碰撞其实就是检查不同的边框之间是否发生干扰。但边框怎么确定呢？如果边框就是沿着游戏实体的外围走这么一圈，还要添加这个概念干什么呢？既然我们加了一个新的概念自然要有一层的“抽象”。当然，你可以用物体的准确几何形状作边界框，但出于效率的考虑，我不赞成这样做，因为游戏中的物体一般都很复杂，用复杂的边界框将增加大量的计算，尤其是浮点计算，而这正是我们想尽量避免的。但边界框也不能与准确几何形状有太大的出入，否则就象用半径法一样出现奇怪的现象。
在打飞机的游戏中——就是《雷电III》那样的游戏啊！别多想啊！——飞机一般都是三角形的。因此我们可以用三角形作近似的边界框。在我下面的分析中我假设飞机是正三角型——其实也可以是等腰三角型，但如果谁要觉的飞机可以是一个不规则的一般三角型的话……老大，你好强——我的飞机是正着的、向上飞的三角形，敌人的飞机是倒着的、向下飞的三角形，且飞机不会旋转（大部分游戏中都是这样的）。我们可以这样定义飞机：中心点O(Xo,Yo),三个顶点P0(X0,Y0)、P1(X1,Y1)、P2(X2,Y2)。中心点为正三角形的中心点，即中心点到三个顶点的距离相等（如图1）。哈哈，两个飞机已经开始忽悠忽悠的在天上飞了，接下来的问题是怎样确定两个三角形互相干扰了呢？也就是说，怎么来判断两个飞机怎么样才相撞呢？
相信平面解析几何大家都是没问题的，现在您一定已经想出很多办法来解决这个问题了。我最先想到的一个办法是：判断一个三角形的各个顶点是否在另一个三角形里面。看起来是个不错的方法，我手工演示了一下，我却发现在里面是有一个小问题的。一个三角形的顶点没有在另一个三角形的里面，却可能发生了碰撞，因为另一个三角形的顶点在这个三角形的里面，所以要判断两次，这很麻烦。
XOY坐标有点想不下去了，我就把三角形放到极坐标平面中，中心点为原点，水平线即X轴为零度角。我们发现三角形成了这个样子：在每个角度我们都可以找到一个距离，用以描述三角形的边。既然我们找到了边到中心点的距离，那就可以用这个距离来检测碰撞。如图一，两个三角形中心点坐标分别为（Xo,Yo）和(Xo1,Yo1),由这两个点的坐标求出两点的距离及两点连线和X轴的夹角θ，再由θ求出中心点连线与三角形边的交点到中心点的距离，用这个距离与两中心点距离比较，从而判断两三角形是否碰撞。
因为三角形左右对称，所以θ取-90～90度区间就可以了。嘻嘻……现在问题有趣多了，-90～90度区间正是正切函数的定义域，求出θ之后再找对应的边到中心点的距离就容易多了，利用几何知识，如图二，将三角形的边分为三部分,即图2中红(0<=θ<=π/2)、绿(θ2<=θ<0)、蓝(-π/2<=θ<θ2)三部分，根据θ在那一部分而分别对待。用正弦定理求出边到中心点的距离，即图2中黄色线段的长度。但是，如果飞机每次移动都这样判断一次，效率仍然很低。我们可以结合半径法来解决，先用半径法判断是否可能发生碰撞，如果可能发生碰撞，再用上面的方法精确判断是不是真的发生了碰撞，这样基本就可以了。如果飞机旋转了怎么办呢，例如，如图三所示飞机旋转了一个角度α，仔细观察图3会发现，用（θ-α）就可以求出边到中心点的距离，这时你要注意边界情况，即（θ-α）可能大于90度或小于-90度。
罗嗦了这么多，其实就是上面一段最关键，最关键这一段我还觉得自己没有表达清楚。我最后给出一个简单的函数来演示我刚才说的问题：
#define NUM_VERTICES 3
#define Ang_30 -0.5236
#define Ang60 1.0472
#define Ang120 2.0944
Struct Object
{
float xo,
yo;
float radio;
float x_vel,
y_vel;
float vertices[NUM_VERTICES][2];
}
/*根据角度求距离*/
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;
}
碰撞中还有很多问题，比如能量损耗；在“非液晶版”的老张中还有就是不同的撞击点，造成的不同的效果等等……
