精华游戏算法之五

碰撞，这很简单嘛，只要两个物体的中心点距离小于它们的半径之和就可以了。确实，而且我也看到很多人是这样做的，但是，这只适合圆形的物体——圆形的半径处处相等。如果我们要碰撞的物体是两艘威力巨大的太空飞船，它是三角形或矩形或其他的什么形状，就会出现让人尴尬的情景：两艘飞船眼看就要擦肩而过，却出人意料的发生了爆炸；或者敌人的子弹穿透了你的飞船的右弦，你却安然无恙，这不是我们希望发生的。于是，我们需要一种精确的检测方法。　　那么，怎样才能达到我们的要求呢？其实我们的前辈们已经总结了许多这方面的经验，如上所述的半径检测法，三维中的标准平台方程法，边界框法等等。大多数游戏程序员都喜欢用边界框法，这也是我采用的方法。边界框是在编程中加进去的不可见的边界。边界框法，顾名思义，就是用边界框来检测物体是否发生了碰撞，如果两个物体的边界框相互干扰，则发生了碰撞。用什么样的边界框要视不同情况而定，用最近似的几何形状。当然，你可以用物体的准确几何形状作边界框，但出于效率的考虑，我不赞成这样做，因为游戏中的物体一般都很复杂，用复杂的边界框将增加大量的计算，尤其是浮点计算，而这正是我们想尽量避免的。但边界框也不能与准确几何形状有太大的出入，否则就象用半径法一样出现奇怪的现象。　　在飞行射击游戏中，我们的飞机大多都是三角形的，我们可以用三角形作近似的边界框。现在我们假设飞机是一个正三角形（或等要三角形，我想如果谁把飞机设计成左右不对称的怪物，那他的审美观一定有问题），我的飞机是正着的、向上飞的三角形，敌人的飞机是倒着的、向下飞的三角形，且飞机不会旋转（大部分游戏中都是这样的）。我们可以这样定义飞机：中心点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度。啰罗嗦嗦说了这么多，不知道大家明白了没有。我编写了一个简单的例程，用于说明我的意图。在例子中假设所有飞机的大小都一样，并且没有旋转。 IMG upload/forum/200562134623.gif[/IMG] IMG upload/forum/200562134627.gif[/IMG] IMG upload/forum/200562134632.gif[/IMG] ///////////////////////////////////////////////////////////////////// //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////////////////////////////////////////////////////////////// 　　上面程序只是用于演示，并不适合放在游戏中，但你应该明白它的意思，以便写出适合你自己的碰撞检测。游戏中的情况是多种多样的，没有哪种方法能适应所有情况，你一定能根据自己的情况找到最适合自己的方法。 ----------------------------------------------------------------------------- 高级碰撞检测技术 高级碰撞检测技术　第一部分 Advanced Collision Detection Techniques 这文章原载于Gamasutra，共有三部分。我想将它翻译，请大家指教。 http://www.gamasutra.com/features/20000330/bobic_01.htm http://www.gamasutra.com/features/20000330/bobic_02.htm http://www.gamasutra.com/features/20000330/bobic_03.htm / 1 …………………………………………………………………………………………………. 自从电脑游戏降临以来，程序员们不断地设计各种方法去模拟现实的世界。例如Pong（著名的碰球游戏），展示了一个动人的场面（一个球及两根摆绳）。当玩家将拽住摆绳移动到一定高度的，然后放开球，球就会离开玩家向对手冲去。以今天的标准，这样的基础操作也许就是原始碰撞检测的起源。现在的电脑游戏比以前的Pong复杂多了，而且更多是基于3D的。这也使3D碰撞检测的困难要远远高于一个简单的2D Pong。一些较早的飞行模拟游戏说明了糟糕的碰撞检测技术是怎样破坏一个游戏。如：当你的飞机撞到一座山峰的时候，你居然还可以安全的幸存下来，这在现实中是不可能发生的。甚至最近刚出的一些游戏也存在此类问题。许多玩家对他们喜爱的英雄或是女英雄部分身体居然可以穿过墙而感到失望。甚至更坏的是玩家被一颗没有和他发生碰撞关系的火箭击中。因为今天的玩家要求增加唯实论的要求越来越高，我们游戏开发者们将尽可能在我们的游戏世界做一些改进以便接近真实的世界。　　Since the advent of computer games, programmers have continually devised ways to simulate the world more precisely. Pong, for instance, featured a moving square (a ball) and two paddles. Players had to move the paddles to an appropriate position at an appropriate time, thus rebounding the ball toward the opponent and away from the player. The root of this basic operation is primitive(by today’s standards) collision detection. Today’s games are much more advanced than Pong, and most are based in 3D. Collision detection in 3D is many magnitudes more difficult to implement than a simple 2D Pong game. The experience of playing some of the early flight simulators illustrated how bad collision detection can ruin a game. Flying through a mountain peak and surviving isn’t very realistic. Even some recent games have exhibited collision problems. Many game players have been disappointed by the sight of their favorite heroes or heroines with parts of their bodies inside rigid walls. Even worse, many players have had the experience of being hit by a rocket or bullet that was “not even close” to them. Because today’s players demand increasing levels of realism, we developers will have to do some hard thinking in order to approximate the real world in our game worlds as closely as possible. / 2 ………………………………………………………………………………………………… 这篇碰撞检测的论文会使用一些基础的几何学及数学知识。在文章的结束，我也会提供一些参考文献给你。我假定你已经读过Jeff Lander写的图形教程中的碰撞检测部分(“Crashing into the New Year,” ; “When Two Hearts Collide,”; and “Collision Response: Bouncy, Trouncy, Fun,” )。我将给你一些图片让你能快速的联系起核心例程。我们将要讨论的碰撞检测是基于portal-based 及BSP-based 两种类型的引擎。因为每个引擎都有自己组织结构，这使得虚拟世界物体的碰撞检测技术也不尽相同。面向对象的碰撞检测是使用得比较多的，但这取决于你的现实可实性，就想将引擎分成两部分一样。稍后，我们会概述多边形碰撞检测，也会研究如何扩展我们的弯曲物体。 This article will assume a basic understanding of the geometry and math involved in collision detection. At the end of the article, I’ll provide some references in case you feel a bit rusty in this area. I’ll also assume that you’ve read Jeff Lander’s Graphic Content columns on collision detection (“Crashing into the New Year,” ; “When Two Hearts Collide,”; and “Collision Response: Bouncy, Trouncy, Fun,” ). I’ll take a top-down approach to collision detection by first looking at the whole picture and then quickly inspecting the core routines. I’ll discuss collision detection for two types of graphics engines: portal-based and BSP-based engines. Because the geometry in each engine is organized very differently from the other, the techniques for world-object collision detection are very different. The object-object collision detection, for the most part, will be the same for both types of engines, depending upon your current implementation. After we cover polygonal collision detection, we’ll examine how to extend what we’ve learned to curved objects. / 3