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