意圖

將對(duì)象根據(jù)它們的位置存儲(chǔ)在數(shù)據(jù)結(jié)構(gòu)中，從而高效地定位對(duì)象。

模式

一系列對(duì)象在空間上都有各自的位置。將它們存儲(chǔ)在根據(jù)位置組織對(duì)象的空間數(shù)據(jù)結(jié)構(gòu)中，可以更有效的查詢?cè)谀程幓蚰程幐郊膶?duì)象。對(duì)象位置改變時(shí)，同步更新數(shù)據(jù)結(jié)構(gòu)。

何時(shí)使用

這是存儲(chǔ)活躍的、移動(dòng)的對(duì)象的常用模式，也可用于靜態(tài)美術(shù)或世界地理，不同的情況使用不同的空間分區(qū)。

這個(gè)模式的基本要求是一系列有位置的對(duì)象，而使用太多通過位置尋找對(duì)象的查詢會(huì)到導(dǎo)致性能低下。

設(shè)計(jì)決策

劃分的是層次還是平面？

平面劃分是將空間劃分成平面格子的集合。

層次空間則是將劃分則是將空間分成多個(gè)區(qū)域，每個(gè)區(qū)域可以遞歸包含多個(gè)對(duì)象，直到每個(gè)區(qū)域都有少于最大數(shù)量的對(duì)象在其中。

如果是平面劃分：

平面數(shù)據(jù)結(jié)構(gòu)更容易實(shí)現(xiàn)。

內(nèi)存使用量確定，添加新對(duì)象不需要添加新劃分，空間分區(qū)的內(nèi)存使用可以事先確定。

對(duì)象改變位置時(shí)更新速度更快。層次空間分區(qū)可能需要多層間調(diào)整層次結(jié)構(gòu)。

如果是層次性的：

能更有效率的處理空的區(qū)域。

層次分區(qū)不分割空區(qū)域，大的空區(qū)域保存到單個(gè)劃分上，遍歷更方便。

處理密集空間更有效率。無層次的劃分沒有效率，將所有對(duì)象劃分到一起等于沒有劃分。

層次空間分區(qū)會(huì)自適應(yīng)地劃成小塊，每次只需要考慮少數(shù)對(duì)象。

劃分依賴于對(duì)象集合嗎？

動(dòng)態(tài)劃分，根據(jù)現(xiàn)有的對(duì)象集合在世界中的位置劃分邊界。

目標(biāo)是均勻的劃分，每個(gè)區(qū)域擁有相同的單位數(shù)量。

如果劃分與對(duì)象無關(guān)：

對(duì)象可以增量添加。

對(duì)象移動(dòng)更快。

缺點(diǎn)是劃分可能不均勻。對(duì)規(guī)劃控制的不夠細(xì)致，如果對(duì)象擠在一起，空區(qū)域上浪費(fèi)了內(nèi)存，這回造成更糟的性能。

如果劃分適應(yīng)對(duì)象集合：

想BSPs和k-d樹這樣的空間劃分世界，讓每部分都包含接近相同數(shù)目的對(duì)象。需要在劃分邊界時(shí)，計(jì)算每邊各有多少對(duì)象。層層包圍盒是另一種為特定集合對(duì)象優(yōu)化的空間分區(qū)。

可以保證劃分是平衡的。如果每個(gè)區(qū)域的對(duì)象的數(shù)量保證一致，就可以保證游戲世界中的所有查詢都會(huì)消耗同樣的時(shí)間。在需要固定幀率時(shí)，這種一致性比性能本身更重要。

一次性劃分一組對(duì)象更加有效率。

如果劃分與對(duì)象無關(guān)，但層次與對(duì)象有關(guān)：

四叉樹，擁有固定分區(qū)和適應(yīng)分區(qū)兩者的優(yōu)點(diǎn)。

四叉樹初始將整個(gè)空間視為單一的劃分。如果空間中對(duì)象數(shù)目超過了臨界值，就將其切為四小塊。我們遞歸地做相同的事情，這種劃分適應(yīng)了對(duì)象集合，但劃分本身沒有移動(dòng)。

對(duì)象可以增量增加。

移動(dòng)對(duì)象快。

分區(qū)是平衡的。

對(duì)象只存儲(chǔ)在分區(qū)中嗎？

可以將空間分區(qū)作為游戲?qū)ο蟠鎯?chǔ)的唯一地方，或作為更快查找的二級(jí)緩存，使用另一個(gè)集合包含對(duì)象。

如果它是對(duì)象唯一存儲(chǔ)的地方：

這避免了內(nèi)存開銷和兩個(gè)集合帶來的復(fù)雜度。兩個(gè)集合需要保證集合之間的同步。

如果其他集合保存對(duì)象：

遍歷所有的對(duì)象更快。存儲(chǔ)對(duì)象在第二集合可以提供直接遍歷的方法。兩個(gè)數(shù)據(jù)結(jié)構(gòu)，可以根據(jù)情況進(jìn)行優(yōu)化。

參加

下一步可以學(xué)習(xí)的常見的結(jié)構(gòu)：Grid、Quadtree、BSP、k-d tree、Boundding volume hierarchy

每種空間分區(qū)數(shù)據(jù)結(jié)構(gòu)基本上都是將一維數(shù)據(jù)結(jié)構(gòu)擴(kuò)展成更高維度的數(shù)據(jù)結(jié)構(gòu)。

網(wǎng)格式連續(xù)的桶排序。

BSPs、k-d trees和包圍盒是線性搜索樹。

四叉樹和八叉樹是多叉樹。

參考

《游戲編程模式》