深入探索AOI算法的設(shè)計考慮因素

作者：co lin

【導(dǎo)讀】：網(wǎng)上關(guān)于AOI算法的文章很多了，但大多語焉不詳，一上來就9宮格十字鏈表，直接把人整懵。本文試圖由淺入深的介紹AOI算法的形成，希望能把AOI解決的問題，以及它的核心邏輯講清楚。如果讀完之后能所有啟發(fā)，那本文的目的就達(dá)到了。

AOI 算法是大型多人在線的游戲服務(wù)器中一個非常重要的基礎(chǔ)模塊，它很大程度上決定了服務(wù)器的運(yùn)行效率。那么什么是AOI呢？AOI全稱為Area Of Interest，翻譯過來叫感興趣的區(qū)域，通俗的講是一個游戲?qū)ο笤趫鼍爸械囊曇埃@個視野可以大到整個場景，也可以小到周圍幾米；它能觀察到視野中的其它對象的一舉一動，同時它也在某些對象的視野中，也被這些對象觀察著。

每個對象需要維護(hù)到兩個集合：

觀察者集合：就是關(guān)注我的對象集合，我的所有AOI行為都需要向這個集合發(fā)送事件，以便讓他們觀察到我的變化。

被觀察者集合：就是被我關(guān)注的對象集合，理論上只要有觀察者集合就夠了，為什么還需要維護(hù)一個被觀察者集合呢？因為有時候想主動檢查對象的狀態(tài)，比如怪物AI會定時檢查被觀察者集合的距離，決定是否發(fā)動攻擊；又比如釋放技能需要遍歷被觀察者集合，判斷它們是否命中。如果沒有被觀察者集合，就必須遍歷整個場景的對象。

有些游戲?qū)ο笸瑫r擁有這兩個集合，有些只擁有其中一個，假設(shè)場景中有玩家，怪物，NPC，掉落物：

圍繞這兩個集合，AOI算法的設(shè)計要考慮以下因素：

現(xiàn)在我們就一步步地探索AOI算法。

上帝視角

把整個場景當(dāng)成可見范圍，無論我走到哪里，都能看到場景中的所有對象。每個對象就像上帝一樣，能觀察到其他對象的行為。

這種做法是為最簡單直接的AOI管理，場景管理器只需用一個字典保存所有游戲?qū)ο螅碛幸粋€字典按對象類型保存對象集合就可以了。被觀察者集合和觀察者集合在需要的時候直接從場景管理器中取。

以一個玩家在場景中的行為看看AOI怎么處理

進(jìn)入

我進(jìn)入場景，取出所有對象，向我發(fā)送Enter(對象)事件，我會向客戶端發(fā)送對象集進(jìn)入的協(xié)議，這樣我的客戶端便能看到場景中的所有對象。

將我加入場景管理器。

取出其他玩家集合，向它們一個個發(fā)送Enter(我)，玩家會向它的客戶端發(fā)送我進(jìn)入的協(xié)議，這樣它就能看到我在場景中，即便我其實離屏幕很遠(yuǎn)也是這樣。

可能不需要向怪物集合發(fā)送Enter消息，因為怪物AI會自己去遍歷敵人。

離開

我離開場景，將我從場景管理器刪除。

取出玩家集合，向它們一個個發(fā)送Leave(我)事件，玩家會向它的客戶端發(fā)送我離開的協(xié)議。

可能不需要向我發(fā)送Leave(對象)事件，因為我跳場景后，客戶端會自動把場景中的對象刪除。

更新

我在場景中的行為稱為更新，比如移動，換裝，發(fā)技能等等，其他玩家應(yīng)該能看到我這些行為。

取出玩家集合，向它們發(fā)送相應(yīng)的事件，他們會向客戶端發(fā)送相應(yīng)的協(xié)議，這樣客戶端就能看到我的行為了。

上帝視角的AOI其實是非常簡單可靠的，如果預(yù)估場景中的對象最多幾十個，那么我建議直接用這種方式，它即足夠高效，也不用每個對象單獨(dú)保存觀察者集合和被觀察者集合，對內(nèi)存很友好，同時它很簡單，幾乎不大可能出錯。

但當(dāng)場景比較大，且對象數(shù)量達(dá)到數(shù)百上千的時候，這種方式就不適合了，因為每個對象的狀態(tài)更新需要通知上千個其他對象，交叉起來能達(dá)到百萬級別的量。再加上客戶端承受不了上千的游戲?qū)ο螅覀儜?yīng)該減少對象的視野。

減少視野

一旦限定了對象的視野，AOI算法就開始變得復(fù)雜；而且每個對象需要維護(hù)被觀察者集合和觀察者集合，內(nèi)存占用會大大增加。

每種對象的視野可以不同，比如玩家的視野只比一個屏幕大一點(diǎn)點(diǎn)，有些BOSS需要更大的視野，而NPC可能視野為0，視野為0的對象不關(guān)注別人，只被別人關(guān)注。

看看減少視野后的處理

進(jìn)入

我進(jìn)入場景。

遍歷場景中所有對象，逐一比較它們和我的距離，如果對象在我的視野之內(nèi)，則向我發(fā)送Enter(對象)事件，此時這些對象會加入我的被觀察者集合，同時，我會加入到這些對象的觀察者集合。

同樣如果距離小于對象的視野，則向?qū)ο蟀l(fā)送Enter(我)事件，此時我會加入到對象的被觀察者集合，同時對象會加入到我的觀察者集合。

離開

我離開場景。

遍歷我的觀察者集合，向他們發(fā)送Leave(我)事件，此時我從對象的被觀察者集合中刪除，同時對象也會從我的觀察者集合刪除。

遍歷我的被觀察者集合，將我從這些對象的觀察者集合中刪除，將我的被觀察者集合清空。

更新

這里的更新不包括移動，因為移動會導(dǎo)致對象集合變化。遍歷我的觀察者集合，向它們發(fā)送相應(yīng)的更新事件。

移動

我移動的時候，被觀察者集合和觀察者集合都會發(fā)生變動，現(xiàn)在我們沒有好的辦法優(yōu)化它，只能這樣做：

遍歷場景的所有對象：

別被這段話繞暈，實際上它的邏輯是很清楚的，請仔細(xì)理解這段話。

可以看到移動是最大的性能瓶頸，每次移動需遍歷場景中的所有對象，如果每個人都在移動，那這個服務(wù)器的承載力可想而知。現(xiàn)在的優(yōu)化方向轉(zhuǎn)向如何減少對象的遍歷，稍微思索后，我們能得到一個解決方法：將場景劃分格子。

網(wǎng)格化

將場景劃分成等大的格子，1個格子大約為1/4屏幕大小，每個進(jìn)來的對象根據(jù)坐標(biāo)加入對應(yīng)的格子中，如下圖所示：

綠色框為屏幕大小，紅星為我，現(xiàn)在我們把最大視野限定為9宮格，這樣搜索范圍就縮小為9個格子，需要遍歷的對象數(shù)量大大減少。

進(jìn)入

我進(jìn)入場景，馬上計算出我所在的格子，并加入這個格子。

接下來的做法和上面的進(jìn)入完全一樣，只不過搜索的范圍變成這9個宮格子，具體不再描述。

離開

我離開場景，將我從格子刪除，

接下來的做法和上面的離開完全一樣。

移動

我移動的時候，遍歷9宮格的所有對象，然后執(zhí)行和上面的移動完全一樣的邏輯

如果我移動到新的格子上時，還要多處理一些事件：

如果對象均勻的分布在場景中，且場景足夠大，那這個優(yōu)化的效果是非常顯著的。

但如果像主城那樣，玩家大多集中在一個區(qū)域，服務(wù)器的壓力仍然會很大，原因是9個格子的玩家可能占了場景80%的玩家，這又退化成和遍歷場景所有玩家差不多了。

假如我們把要求降低一些：強(qiáng)制對象的視野固定在9宮格上，也就是說，只要我在這個格子中，不管怎么移動，視野都是周圍的9個格子，那事情就好辦了。每個游戲?qū)ο蟛恍枰S護(hù)兩個集合，直接從9宮格里取即可?，F(xiàn)在邏輯簡化成這樣：

這個過程看起來就是上帝視角的縮小版，如果我們對視野要求不那么高，這個做法和上帝視角一樣簡單可靠。我相信很多游戲的9宮格處理都是用這種，或者基于這種去優(yōu)化的。

這種做法的一個小小缺點(diǎn)是客戶端會收到一些屏幕外的對象消息，有點(diǎn)浪費(fèi)帶寬吧，如果我們把發(fā)消息做成批量加壓縮的方式，這種浪費(fèi)并不大。

十字鏈表

基于網(wǎng)格的優(yōu)化基本也就到這兒，如果想探索更多的優(yōu)化方式，只能換一種數(shù)據(jù)結(jié)構(gòu)，用十字鏈表，其核心思想是將所有對象結(jié)點(diǎn)鏈接在兩個鏈表上，一個按X值排序，一個按Y值排序，對象進(jìn)入場景后遍歷兩個鏈表，找到合適的位置插進(jìn)去；移動的時候，從對象位置前后遍歷兩個鏈表，和其他對象進(jìn)行判斷。

簡單的描述是這樣子，可是當(dāng)你按這個思路去實現(xiàn)十字鏈表時，你會發(fā)現(xiàn)搜索觀察者和被觀察者都很慢，因為每種對象的視野可能不一樣，你沒辦法只前后遍歷一點(diǎn)點(diǎn)，有可能在很遠(yuǎn)的地方有一個對象在觀察著你，你只能整個鏈表遍歷，這樣的十字鏈表就沒什么意義了。

真正的十字鏈表，除了對象結(jié)點(diǎn)外，還需要一種哨兵結(jié)點(diǎn)，每個對象都帶有兩個哨兵結(jié)點(diǎn)，這兩個哨兵結(jié)點(diǎn)同樣被鏈接在X和Y鏈表上，哨兵結(jié)點(diǎn)也有坐標(biāo)，它們的坐標(biāo)剛好是對象坐標(biāo)與其視野半徑的差值，舉個例子：

對象A的坐標(biāo)是(100, 90)，假設(shè)對象的視野半徑是20，那么哨兵1的坐標(biāo)就是(80, 70)，哨兵2的坐標(biāo)就是(120, 110)，它們按順序加入鏈表，拿X鏈表舉例，如下所示：

先不去管B和C，a1和a2是A的哨兵，并且A移動后，哨兵也會跟著移動，以保持它們的距離總是視野的半徑。

那么哨兵結(jié)點(diǎn)的作用到底是什么呢？顧名思議，它們的作用是用來監(jiān)控跨越它的對象結(jié)點(diǎn)的：

假如有一個D結(jié)點(diǎn)原來的坐標(biāo)是(78, 69)，現(xiàn)在它移動到(82, 75)，坐標(biāo)變動后，D結(jié)點(diǎn)需要從原來的位置向前移，必定會跨過a1這個結(jié)點(diǎn)，此時a1判斷D是一個對象結(jié)點(diǎn)，且它原來的坐標(biāo)在A的視野之外，現(xiàn)在的坐標(biāo)到了A的視野之內(nèi)，就可以確定D進(jìn)入A的視野。哨兵向A發(fā)送Enter(D)事件：D會加入A的被觀察者集合，同時，A會加入到D的觀察者集合。

D在向前移動時，A也可能會進(jìn)入D的視野，這個是怎么判定的呢？別忘了D也是有兩個哨兵結(jié)點(diǎn)的，它們也跟著D向前移，其中一個哨兵越過A時判斷：原來A的坐標(biāo)在D的視野之外，現(xiàn)在A的坐標(biāo)到了D的視野內(nèi)，可以確定A進(jìn)入D的視野，于是哨兵向D發(fā)送Enter(A)事件：A會加入D的被觀察者集合，同時，D會加入到A的觀察者集合。

如此一來一回，各方就慢慢維護(hù)起觀察者集合和被觀察集合。離開視野的處理也是類似，這里就不再羅索，留給你們?nèi)ハ搿?/p>

總而言之，十字鏈表的的核心算法就是哨兵結(jié)點(diǎn)或?qū)ο蠼Y(jié)點(diǎn)在移動的時候，會跨過對方，在跨過的時候判斷進(jìn)入視野還是離開視野。

這個算法假設(shè)對象經(jīng)常靜止或小幅移動，對于大幅移動和進(jìn)出場景是小概率事件，這個假設(shè)用在網(wǎng)游剛好非常湊效，所以十字鏈表非常高效。

下面用一個幾何圖來幫助理解十字鏈表：

A移動到A'時，所需要遍歷的對象就在黃條覆蓋的區(qū)域，這個條越細(xì)表示遍歷的對象越少。

當(dāng)然也不是說十字鏈表很完美，它在角色經(jīng)常進(jìn)出場景的情況下就表現(xiàn)得不大好，因為角色每次進(jìn)來場景，都需要從X和Y的鏈表頭向前遍歷，直到找到自己的位置。這個時間復(fù)雜度是O(N)。遇到那種經(jīng)常跳場景去副本的游戲，十字鏈表可能會有點(diǎn)性能瓶頸。

針對這個問題，我想到了一種解決辦法，注意看了：

地標(biāo)結(jié)點(diǎn)越多越精確，但遍歷的結(jié)點(diǎn)也越多，這個需要實際實現(xiàn)的時候做試驗。

AOI算法大體就是這樣，大多數(shù)游戲用固定視野的9宮格算法就足夠了，如果人數(shù)太多，我們完全可以用場景分線或分層的方式，強(qiáng)制把人數(shù)降下來，因為人數(shù)太多，對客戶端的體驗也不會好到哪里去。

本文到此就結(jié)束了，希望對正在研究AOI算法的你有所幫助。

對玩家來說：它能觀察到所有類型的游戲?qū)ο?；同時它會被其他玩家和怪物觀察著；但它可能不會被NPC和掉落物觀察。所以它的被觀察者集合是所有類型的游戲?qū)ο?，觀察者集合是玩家和怪物。

對于NPC和掉落物來說：它不關(guān)心周圍的對象，所以它沒有被觀察集合；但它有觀察者集合，里面只有玩家類型。

怪物多樣化一些：

主動怪的被觀察者集合是玩家；觀察者集合也是玩家。

被動怪可以設(shè)計為沒有被觀察者集合，因為在它沒有被玩家攻擊之前，它是不關(guān)心周圍的環(huán)境，玩家攻擊它之后，玩家會進(jìn)入它的仇恨者列表，這是怪物AI的范疇了；它的觀察者集合是玩家。

對象視野的大小，這直接影響到集合的大小。

對象集合保存在哪里，有些做法是場景共享對象集合，有些則是每個對象單獨(dú)保存這兩個集合。

在進(jìn)入離開移動等事件中，如何更新對象集合。

如果它原來在我的被觀察者集合中，并且現(xiàn)在的距離已經(jīng)大于我的視野，向我發(fā)送Leave(對象)事件，此時對象會從我的被觀察者集合刪除，同時我會從對象的觀察者集合刪除。

如果它原來在我的觀察者集合中，并且現(xiàn)在的距離已經(jīng)大于它的視野，則向它發(fā)送Leave(我)事件，此時我會從它的被觀察者集合中刪除，同時它會從我的觀察者集合中刪除。

向剩下的觀察者集合發(fā)送移動事件。

如果它原來沒有在我的被觀察者集合中，并且現(xiàn)在的距離已經(jīng)小于等于我的視野，向我發(fā)送Enter(對象)事件，此時這些對象會加入我的被觀察者集合，同時，我會加入到這些對象的觀察者集合。

如果它原來沒有在我的觀察者集合中，并且現(xiàn)在的距離已經(jīng)小于等于它的視野，向它發(fā)送Enter(我)事件，此時我會加入到對象的被觀察者集合，同時對象會加入到我的觀察者集合。

把我從原來的格子刪除，加入新的格子。

假設(shè)舊的9宮格為OldGrid，新的9宮格為NewGrid，計算{NewGrid-OldGrid}集合，得到的這些格子即為新增的格子。然后對這些格子執(zhí)行和進(jìn)入完全一樣的處理：

進(jìn)入場景：進(jìn)入一個格子，取出周圍9格的對象，向它們發(fā)送Enter(我)事件，同時向我發(fā)送Enter(對象)事件。

離開場景：取出周圍9格的對象，向它們發(fā)送Leave(我)事件。

移動：

如果沒跨格子，直接取9格的對象，向它們發(fā)送移動事件。

如果跨過格子，計算{OldGrid-NewGrid}，向它們發(fā)送Leave(我)事件，向我發(fā)送Leave(對象)事件；計算{NewGrid-OldGrid}集合，向它們發(fā)送Enter(我)事件，向我發(fā)送Enter(對象事件；計算{NewGrid*OldGrid}集合，向他們發(fā)送移動事件。

首先需要像9宮格那樣限定一個最大視野，比如任何對象的視野都不會超過1.5個屏幕大小。

接著我們定義一些地標(biāo)結(jié)點(diǎn)，它們的坐標(biāo)在設(shè)定之后就不會改變，像是地圖里的地標(biāo)一樣。假如一個地圖的大小是1000x1000，我們可以創(chuàng)建10個地標(biāo)結(jié)點(diǎn)，每個結(jié)點(diǎn)的坐標(biāo)相距100大?。篗1(0, 0), M2(100, 100), M3(200, 200), M4(300, 300)。。。

創(chuàng)建場景的時候，就把地標(biāo)結(jié)點(diǎn)分別插入到X和Y鏈表中，地標(biāo)結(jié)點(diǎn)的坐標(biāo)不會改變，所以永遠(yuǎn)不用移動它們。

接著把這些地標(biāo)結(jié)點(diǎn)按順序保存在一個數(shù)組中：|M1|M2|M3...|，有了這個數(shù)組，我們就不用從頭移動了。

A進(jìn)入場景后，它算出：移動點(diǎn)=A的坐標(biāo)-最大視野直徑，然后在地標(biāo)數(shù)組中快速查找到最近的地標(biāo)結(jié)點(diǎn)(用二分查找法)，從這個地標(biāo)結(jié)點(diǎn)開始向前移動，移動過程中A就會進(jìn)入其他對象的視野。

A移動完成之后，A身邊的兩個哨兵結(jié)點(diǎn)開始向兩邊移動，移動過程中就會有一些對象進(jìn)入A的視野。

審核編輯：黃飛