残忍的比对
碰撞检测能够使用很多的方法来完成。最简单和直接的方法就是测试每个对象和其他的对象的冲突。因为每个对象需要同一个对象列表进行测试，测试一个对象和他的自身的是没有意义的。就是众所周知的残忍的比对。
for (i = 0; i < n; i++)
{
a = obj[i];
for (j = i + 1; j < n; j++)
{
b = obj[j];
collide(a, b)
}
}
|
这种两次的循环嵌套耗费了很大的时间（n是需要检查的对象的数量）：
它立即就被发现这样做会遇到一个很大的问题：指数增长。一个很棒的文章（Dave Robers）中描述这个问题在更多的细节中也包含了几个可供选择的方法来检测碰撞。
空间的划分运算法则在这里使用了空间的划分，这就意味着它划分屏幕为更小的区域。每个区域都包含较少的对象。碰撞的监测是在区域中的所有的实体（任何的什么东西）对他们进行逐个的比较---在一个小的区域中对象的较少，这是非常的有效的。
两个普通的空间分割的方法是Binary Space Partition(BSP)和Quadtree/Octree Partitioning.他们的共同之处在于他们都递归空间划分为更小的空间。RDC,但是，不要创建一个树形的数据结构和重新计算每个框架。BSP和Quad trees在另一个方面的最好的用处就是当进行预先运算的时候，虽然他们不容易修改。
所以，首先，我通过使用空间分割来限制了进行碰撞检测的数量。第二，我在一定的范围内限制了对象来快速的排除了没有碰撞的对象。
RDC具有一个一般的复杂度：
当测试的数量使用外部的压力单独激发的时候，RDC的方法提高了线性的近似值。
运算法则RDC是由Steve Rabin所提出的，在Game Programming GemsII提出："Recursive Dimensional Clustering,一个快速的碰撞检测的运算法则"。不用研究的更深，我尝试去重新梳理一些基础的原理，你可以下载自己试一下。
RDC运算法则包括以下的步骤：
一、反复的遍历所有的对象，在一个列表中存储一个给定的轴的时间间隔。对于X轴，我保存了对象边界的最小值（open）和最大值（close）的X位置，一个实现的简单方法就是使用displayObjectInstance.getBounds()。对Y轴和Z轴也作相同的处理。每条边界必须记住他属于什么实体和是否他是一个open或者close的类型：
class Boundary
{
public var type:String;
public var position:Number;
public var object:Object;
}
|
二、挑选那些列表中的分界线对象，并根据位置从低到高进行排序：
var boundaries:Array = getIntervals(objects, axis)
boundaries.sortOn("position", Array.NUMERIC);
|
三、重新遍历已经挑选的分界线列表，存储那些重叠时间间隔的对象到一个groups中：
var group:Array = [];
var groupCollection:Array;
var count:int = 0;
for (var i:int = 0; i < boundaries.length; i++)
{
var object:Boundary = boundaries[i];
if (object.type == "open")
{
count++;
group.push(object);
}
else
{
count--;
if (count == 0)
{
groupCollection.push(group);
}
}
}
|
如果你只是处理一个纬度（那将是一个奇怪的游戏）你已经完成了。
如果你需要处理一个更高的纬度，你必须再分解group到其他的轴（2d是y，3d是z），然后重新分解groups到其他的轴，对于2d，你可以这样：
1、分解出X轴
2、分解出Y轴
3、在此分解出X轴
这些步骤反复的被执行直到递归到一定的深度。
所有的对象都高兴的分离着，没有groups产生。
对象a和b的open/close边界线重叠后被放到了一个group中。
尽管对象a和b的间隔的x轴是重叠的，但是他们的y轴是分离的。
沿着X轴划分为一个group[A,B,C].第二个通过Y轴划分group为
,[A,C]。对[A,C]沿着X轴再次进行划分，最终得到了[A],[B],[C]。
[b]交互演示这将会让你对什么是RDC有一个更好地了解。在输入区所定义的值是在一个group中有多少个对象的时候才会停止递归。数值越低，你实际上是在提高递归的层级（计算更慢）。所以你告诉了运算："试着通过进一步的划分来创建更小的group"。如果你设置了值为1。每个group只允许有一个对象。如果你设置的值太高（计算更快）你会得到更大的groups。这可以被看作一个在遍历和RDC之间的一个混合因子，以便一个group中包含有5-10个对象的话会效率更高。
-------
下载源文件