殘忍的比對
碰撞檢測能夠使用很多的方法來完成。最簡單和直接的方法就是測試每個對象和其他的對象的沖突。因為每個對象需要同一個對象列表進行測試，測試一個對象和他的自身的是沒有意義的。就是眾所周知的殘忍的比對。
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個對象的話會效率更高。
-------
下載源文件