一. 前言
在游戲程序中，利用空間數(shù)據(jù)結(jié)構(gòu)加速計算往往是非常重要的優(yōu)化思想，空間數(shù)據(jù)結(jié)構(gòu)可以應(yīng)用于場景管理、渲染、物理、游戲邏輯等方面。
二、多叉樹
2.1 四叉樹
四叉樹是很常見的一種 2D 碰撞檢測方法，實現(xiàn)手段也五花八門。不過在具體實現(xiàn)中要注意優(yōu)化細節(jié)，控制建樹時間消耗與建樹空間大小，特別是在 JS 語言環(huán)境下。但四叉樹的射線檢測、區(qū)域檢測效率比較高，樹更新很快，會產(chǎn)生物體多次劃分，空間占用大。
四叉樹的結(jié)構(gòu)在空間數(shù)據(jù)對象分布比較均勻時，具有比較高的空間數(shù)據(jù)插入和查詢效率（復(fù)雜度O(logN)）。
//示例：一個四叉樹節(jié)點的簡單結(jié)構(gòu)
struct QuadtreeNode {
Data data;
QuadtreeNode* children[2][2];
int divide; //表示這個區(qū)域的劃分長度
};
//示例：找到x,y位置對應(yīng)的四叉樹節(jié)點
QuadTreeNode* findNode(int x,int y,QuadtreeNode * root){
if(!root)return;
QuadtreeNode* node = root;
for(int i = 0; i < N && n; ++i){
//通過diliver來將x,y歸納為0或1的值，從而索引到對應(yīng)的子節(jié)點。
int divide = node->divide;
int divideX = x / divide;
int divideY = y / divide;
QuadtreeNode* temp = node->children[divideX][divideY];
if(!temp){break;}
node = temp;
//如果歸納為1的值，還需要減去該劃分長度，以便進一步劃分
x -= (divideX == 1 ? divide : 0);
y -= (divideY == 1 ? divide : 0);
}
return node;
}
2.2 八叉樹
八叉樹雖然包圍精確性沒 BVH 高（可用狀態(tài)壓縮改善）、占用空間較大（過度劃分），但是建樹和增刪非?？?，很適合用作物體的篩選。目前 98K 使用了八叉樹對模型包圍盒進行空間劃分，簡單高效的建樹比精確計算建樹（比如 BVH 建樹會有大量計算消耗）更加劃算。缺點和四叉樹一樣，射線檢測、區(qū)域檢測較快，樹更新很快， 會產(chǎn)生物體多次劃分，空間占用大。
2.3 應(yīng)用
相比網(wǎng)格，四叉樹/八叉樹主要是多了層次，它們可以進行區(qū)域較大的劃分，然后可以對各種檢測算法進行分區(qū)域的剪枝/過濾。
下面提幾個應(yīng)用（實際應(yīng)用面很廣）：
- 場景管理
特別適合大規(guī)模的廣闊室外場景管理。一般來說如果游戲場景是基于地形的（甚至沒有高度）（如城市、平原、2D場景），那么適合用四叉樹來管理。而如果游戲場景在高度軸上也有大量物體需要管理（如太空、高山），那么適合用八叉樹來管理。 - 碰撞檢測
類似上面感知檢測。不同劃分區(qū)域保證不會碰撞的情況下，就能快速過濾與本物體不同區(qū)域的其他潛在物體碰撞。 - 光線追蹤（Ray Tracing）過濾
光線追蹤渲染，可使用八叉樹來劃分3D空間區(qū)域，從而過濾掉大量不必要的區(qū)域。
三、二叉樹
3.1 BVH樹
四叉樹和八叉樹是以平均空間來劃分物體，劃分算法簡單，而 BVH 是對當(dāng)前物體集合進行空間的劃分，追求左右空間大小相對均衡且無相交。BVH 構(gòu)建的一般是二叉樹，劃分算法復(fù)雜。
主流物理引擎都有采用 BVH（層次包圍盒樹 (Bounding Volume Hierarchy Based On Tree)），因為其功能支持完備、查找精確性高、性能不俗。但是其在建樹和增刪改時要維護平衡樹，消耗很大。針對這個問題，有一些時序性的空間優(yōu)化方法，通過減少增刪改達到優(yōu)化目的，感興趣的朋友可以參考各大物理引擎中的實現(xiàn)方法。
3.2 BSP樹
BSP（Binary Space Partitioning Tree），二維空間分割樹，非常經(jīng)典，1993年在知名游戲 DOOM 里第一次被應(yīng)用，早期 CS 也是用 BSP 來做地形碰撞。BSP 通常通過計算得到一個合理的任意角度片面或者法線，然后對空間進行劃分。標(biāo)準(zhǔn)的 BSP 雖然高效，但樹構(gòu)建非常消耗時間，通常都是編輯器預(yù)處理，比較適合靜態(tài)模型或者靜態(tài)場景使用。
3D空間下要構(gòu)造一棵較平衡的BSP樹，則需要盡可能每次劃分出一個節(jié)點時，讓其左子樹節(jié)點數(shù)和右子樹節(jié)點數(shù)相差不多：
- 在一個平面形狀集合里，用其中一個平面構(gòu)造一個BSP樹節(jié)點時，需滿足它前方的平面形狀數(shù)和后方的平面形狀數(shù)之差 小于
一定閾值；若超過閾值則嘗試用下一個形狀來構(gòu)造。 - 一個麻煩的問題是當(dāng)2個平面形狀是相交時，即出現(xiàn)平面形狀既可以在前方也可以在后方的情況。這時候就需要一個將該形狀切割成兩個子形狀，從而可以一個添加在前方，一個添加在后方，避免沖突。
- 構(gòu)造完一個節(jié)點則移除對應(yīng)的平面，該節(jié)點前面的平面形狀和后面的平面形狀則作為兩個子平面形狀集合。
- 對這兩個子集合以重復(fù)步驟1、2繼續(xù)構(gòu)造出兩個子節(jié)點，并作為本節(jié)點的左右兒子。
- 最后所有平面形狀都被用于構(gòu)造節(jié)點，組成了一棵BSP樹。
//BSP tree節(jié)點結(jié)構(gòu)示例
class BSPTreeNode {
Plane plane; //平面
BSPTreeNode* front; //前向的節(jié)點
BSPTreeNode* back; //后向的節(jié)點
//Data data; //數(shù)據(jù)
};
由于需要進行N次劃分，每次劃分后，要在子集合里一個個挑選合適的平面（需要logN次遍歷），為了評定合適又需要與子集合里所有其它形狀比較前后位置（需要logN次比較），因此可以知道BSP樹構(gòu)造的平均時間復(fù)雜度為 O(Nlog2N)
判斷點在平面前后的算法：平面的法向量（A,B,C），則平面的方程為：Ax + By + Cz + D = 0;
將點（x0,y0,z0）代入方程得到 distance = Ax0 + By0 + Cz0 + D;
若 distance < 0 則在平面背后
若 distance = 0 則在平面中
若 distance > 0 則在平面前方
3.3 k-d樹
k-d樹（(k-dimensional tree)）是一棵二叉樹，其每個節(jié)點都代表一個 k維坐標(biāo)點：
樹的每層都是對應(yīng)一個劃分維度（取決于你定義第i層是哪個維度）
樹的每個節(jié)點代表一個超平面，該超平面垂直于當(dāng)前劃分維度的坐標(biāo)軸，并在該維度上將空間劃分為兩部分，一部分在其左子樹，另一部分在其右子樹
實際上，k-d樹就是一種特殊形式的BSP樹（軸對齊的BSP樹）。
//一種實現(xiàn)方式示例：二維k-d樹節(jié)點
class KdTreeNode{
Vector2 position; //位置
int dimension; //當(dāng)前所屬層的維度
KdTreeNode* children[2]; //兩個子樹
//Data data; //數(shù)據(jù)
};
k-d 樹是一種特殊的 BSP 樹，它基于動態(tài)計算的三個軸進行劃分。k-d 樹相比 BSP 可能精確性沒那么高，但是建樹時間大大減少，因為對軸劃分算法簡單，所以很適合使用
舉例，一棵k-d樹（k=2）的結(jié)構(gòu)如圖：
文章來源：http://www.zghlxwxcb.cn/news/detail-805231.html
根據(jù)第一層劃分維度為X，第二層為Y，第三層為X，
所以該k-d樹（k=2）對應(yīng)代表劃分的空間，看起來應(yīng)該是這樣的：
文章來源地址http://www.zghlxwxcb.cn/news/detail-805231.html
到了這里，關(guān)于空間數(shù)據(jù)結(jié)構(gòu)(四叉樹、八叉樹、BVH樹、BSP樹、k-d樹)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
