1.4.1  限定框算法

限定框算法是最常见的冲突检测算法之一，它的思想是：在对象的周围建立一些框，依据这些对象，在一个可以接受的精度范围内检测其上的最小冲突。在图1-7中，我们可以看到一些希望进行冲突检测的对象以及它们的限定框。

图1-7  射手对象和怪物对象的限定框

在游戏代码中，我们必须检查用于冲突检测的限定框之间是否有重叠，但不是检查图像的每个像素。例如，在图1-7中，如果围绕箭头的限定框触及到围绕怪物的限定框的话，那么这将是一个击中(hit)操作。

使用图1-7中展示的限定框可能会获得好的效果，然而通常情况下如果使用针对游戏者(图1-7中的射手)的较小限定框，检测冲突效果会更好一些。如果仅仅是因为子弹(或箭)仅有一个像素的误差而偏离目标，但结果是怪物被摧毁了，则游戏者将不会抱怨什么。但是，如果情况正好相反，游戏者就会感到自己被游戏本身欺骗了。为了给游戏者一点快感，为射手创建一个较小的限定框是一种较好的选择。

现在可以重新定义限定框，如图1-8所示。

图1-8  修订后的射手限定框和怪物限定框

一般而言，我们即将介绍的冲突检测技术将会涉及到“按轴线排列限定框问题(Axis Aligned Bounding Boxes，AABB)”。即：限定框将依据屏幕上的x轴和y轴进行某种特定的排列，这使得所有的计算都非常简单。此处描述的关于二维图形的冲突检测技术通常可以应用于三维图形的冲突检测，但是对于算法而言，三维图形要比二维图形复杂得多。无论如何，二维图形冲突检测并不具备真正数学意义上的复杂性。一种实现AABB检测的简便方法是把该问题分解为两个独立的检测问题。

第一个检测称为“宽阔性”(broad phase)检测，它仅仅检测两个限定框是否有机会重叠。假设您正在玩一种赛车游戏并且希望查看一下两辆汽车是否会发生碰撞。如果一辆汽车在西雅图，而另一辆汽车在纽约，那么这两辆汽车将不会有发生碰撞的机会。“宽阔性”检测将对可能发生问题的两个限定框进行稳定可靠的检查。如果两个限定框中心之间距离的绝对值小于两框的半宽(每个限定框的宽或高的一半)之和，则这两个限定框在该轴上将存在发生重叠的机会。如果这两个限定框发生抵触的话，则“宽阔性”检测对X轴和Y轴均为真。这种方法也称作“邻近性检测”(proximity test)，在本章的后续内容里，我们将对其进行详细讨论。现在，让我们通过图示和代码来了解它。

可以看到，在图1-9中，两个长方形在x轴上重叠但在y轴上不重叠。尽管x轴检测值为真，但y轴检测值却不为真。执行检测的代码如下：

Dim Dx As Single = Math.Abs(R2.X - R1.X)

Dim Dy As Single = Math.Abs(R2.Y - R1.Y)

if (Dx > (R1.ExtentX+R2.ExtentX) And (Dy > (R1.ExtentY+R2.ExtentY)) Then

' The boxes do not overlap.

Else

' The boxes overlap.

End If

图1-9  两个不发生重叠的框

依照示例代码，两个限定框当且仅当长方形2的x坐标值和y坐标值均在长方形1的范围之内时才发生重叠。观察示意图可知，x轴上两个框之间的距离小于它们的宽度之和，因此这两个框存在发生重叠的机会。这也意味着这两个框可能会发生重叠。但是，在y轴上两框之间的距离大于它们之间的高度之和，这意味着此二框不存在发生重叠的可能。

图1-10中的两框发生了重叠，因为它们之间的距离(包括两个轴上的距离)小于它们的宽度或高度之和。

如果“宽阔性”检测断定两个长方形存在邻近关系，则可以开始更进一步的冲突检测。这可以通过很多方式进行，不过您现在可能仍然会坚持使用“邻近性检测”方法。但是当处理成百上千个此类检测时，将会很容易地发现某些地方的处理复杂度越来越大。如果想要使情况更加复杂的话，可以想像这些限定框均在实时地移动。由此不难发现，当我们把类似于冲突检测这样的挑战性问题考虑进去时，游戏就会变得非常复杂，而复杂的游戏则需要速度更快的计算机和图形显示卡。

图1-10  发生重叠的两个框

创建自定义的长方形对象

我们可以对算法进行一个简单的改进是：创建一个自定义的长方形对象用以存储限定框的两个点，即框的左上角和右下角，然后就可以直接对这些变量进行检测而不必执行算法全部的检测操作。

这种方法很容易扩展到外形不是长方形的对象中去，只需要为每个对象创建一组长方形而非单个长方形即可。例如，对于飞机而言，可以使用两个重叠的框(如图1-12)而不是使用单个框(如图1-11)来近似它，从而获得了较高的精度。

图1-11  使用单个框来近似飞机的外形        图1-12  使用两个框来近似飞机的外形

这种方法的缺点是：如果使用了太多的框，则计算起来将非常耗时。因此，对于每个游戏或对象而言，我们总是需要在精度和速度之间寻找一个平衡点。在许多三维图形应用程序中，我们常用“邻近性检测”把检测区域分解得越来越小，直到检测区域为我们所关心区域的最小集为止。利用前面的示例，可以把飞机机舱的限定框分解为几个针对飞机起落架的附加限定框，然后就可以执行冲突检测来查看飞机轮子是否触及到跑道。通过连续地对越来越小的限定框进行冲突检测，我们可以获得越来越高的准确度。

准确度(accuracy)和精度(precision)的区别

绝大多数程序员对有关“准确度”和“精度”的问题感到困惑，但它们是根本不同的两回事。我们来看一下两个例子，假设您和您的朋友在玩箭术，您的朋友射中目标的外围环，那么她的射箭是准确的，但不是精确的。如果您拉弓并射中公牛的眼睛(在与您朋友的射击目标完全一致的情况下)，那么您的射箭可以用“精确”而不是“准确”来形容。另一个例子是π值，3可以代表π值，但它不是精确的。然而3与2.14159相比，3是一个较好的选择。2.14159是精确的但不是准确的。

计算机对于像1、2、3这样的可数的整数值而言是精确且准确的，但是对于实数而言，在这方面却面临着挑战。这种挑战基于现代计算机技术的两个基础性问题。第一，实数必须以二进制格式存储，这一点看起来好像是微不足道的事情，但是实际上它是一个非常大的挑战性问题。例如，简单数1/10不能始终如一地使用一种计算机浮点格式来表示，因为数值是基于二进制存储的(基于二进制情况下，1/10将产生一串重复的数字)。第二个挑战来自于可以用多少位(bit)来表示一个实数这个问题，它限制了数的准确度。这导致了聚束效应(bunching)，即当数值接近零或者非常大时准确度非常高，而介于两者之间的数却没有那么高的准确度。如果想要进一步了解有关该问题的前沿技术文档，请参见附录A中的“What Every Computer Scientist Should Know About Floating-Point Arithmetic”。