殘忍的比對
碰撞檢測能夠使用很多的方法來完成。最簡單和直接的方法就是測試每個對象和其他的對象的沖突。因為每個對象需要同一個對象列表進行測試，測試一個對象和他的自身的是沒有意義的。就是眾所周知的殘忍的比對。
for (i = 0; i < n; i++)
{
a = obj[i];
for (j = i + 1; j < n; j++)
{
b = obj[j];
collide(a, b)
}
}
|
這種兩次的循環(huán)嵌套耗費了很大的時間（n是需要檢查的對象的數(shù)量）：
它立即就被發(fā)現(xiàn)這樣做會遇到一個很大的問題：指數(shù)增長。一個很棒的文章（Dave Robers）中描述這個問題在更多的細節(jié)中也包含了幾個可供選擇的方法來檢測碰撞。
空間的劃分運算法則在這里使用了空間的劃分，這就意味著它劃分屏幕為更小的區(qū)域。每個區(qū)域都包含較少的對象。碰撞的監(jiān)測是在區(qū)域中的所有的實體（任何的什么東西）對他們進行逐個的比較---在一個小的區(qū)域中對象的較少，這是非常的有效的。
兩個普通的空間分割的方法是Binary Space Partition(BSP)和Quadtree/Octree Partitioning.他們的共同之處在于他們都遞歸空間劃分為更小的空間。RDC,但是，不要創(chuàng)建一個樹形的數(shù)據(jù)結(jié)構和重新計算每個框架。BSP和Quad trees在另一個方面的最好的用處就是當進行預先運算的時候，雖然他們不容易修改。
所以，首先，我通過使用空間分割來限制了進行碰撞檢測的數(shù)量。第二，我在一定的范圍內(nèi)限制了對象來快速的排除了沒有碰撞的對象。
RDC具有一個一般的復雜度：
當測試的數(shù)量使用外部的壓力單獨激發(fā)的時候，RDC的方法提高了線性的近似值。
運算法則RDC是由Steve Rabin所提出的，在Game Programming GemsII提出："Recursive Dimensional Clustering,一個快速的碰撞檢測的運算法則"。不用研究的更深，我嘗試去重新梳理一些基礎的原理，你可以下載自己試一下。
RDC運算法則包括以下的步驟：
一、反復的遍歷所有的對象，在一個列表中存儲一個給定的軸的時間間隔。對于X軸，我保存了對象邊界的最小值（open）和最大值（close）的X位置，一個實現(xiàn)的簡單方法就是使用displayObjectInstance.getBounds()。對Y軸和Z軸也作相同的處理。每條邊界必須記住他屬于什么實體和是否他是一個open或者close的類型：
class Boundary
{
public var type:String;
public var position:Number;
public var object:Object;
}
|
二、挑選那些列表中的分界線對象，并根據(jù)位置從低到高進行排序：
var boundaries:Array = getIntervals(objects, axis)
boundaries.sortOn("position", Array.NUMERIC);
|
三、重新遍歷已經(jīng)挑選的分界線列表，存儲那些重疊時間間隔的對象到一個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);
}
}
}
|
如果你只是處理一個緯度（那將是一個奇怪的游戲）你已經(jīng)完成了。
如果你需要處理一個更高的緯度，你必須再分解group到其他的軸（2d是y，3d是z），然后重新分解groups到其他的軸，對于2d，你可以這樣：
1、分解出X軸
2、分解出Y軸
3、在此分解出X軸
這些步驟反復的被執(zhí)行直到遞歸到一定的深度。
所有的對象都高興的分離著，沒有groups產(chǎn)生。
對象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有一個更好地了解。在輸入?yún)^(qū)所定義的值是在一個group中有多少個對象的時候才會停止遞歸。數(shù)值越低，你實際上是在提高遞歸的層級（計算更慢）。所以你告訴了運算："試著通過進一步的劃分來創(chuàng)建更小的group"。如果你設置了值為1。每個group只允許有一個對象。如果你設置的值太高（計算更快）你會得到更大的groups。這可以被看作一個在遍歷和RDC之間的一個混合因子，以便一個group中包含有5-10個對象的話會效率更高。
-------
下載源文件