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

作者：co lin

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

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

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

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

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

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

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

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

上帝視角

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

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

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

進(jìn)入

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

將我加入場景管理器。

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

可能不需要向怪物集合發(fā)送Enter消息，因?yàn)楣治顰I會自己去遍歷敵人。

離開

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

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

可能不需要向我發(fā)送Leave(對象)事件，因?yàn)槲姨鴪鼍昂?，客戶端會自?dòng)把場景中的對象刪除。

更新

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

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

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

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

減少視野

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

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

看看減少視野后的處理

進(jìn)入

我進(jìn)入場景。

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

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

離開

我離開場景。

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

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

更新

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

移動(dòng)

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

遍歷場景的所有對象：

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

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

網(wǎng)格化

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

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

進(jìn)入

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

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

離開

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

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

移動(dòng)

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

如果我移動(dòng)到新的格子上時(shí)，還要多處理一些事件：

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

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

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

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

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

十字鏈表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對玩家來說：它能觀察到所有類型的游戲?qū)ο螅煌瑫r(shí)它會被其他玩家和怪物觀察著；但它可能不會被NPC和掉落物觀察。所以它的被觀察者集合是所有類型的游戲?qū)ο螅^察者集合是玩家和怪物。

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

怪物多樣化一些：

主動(dòng)怪的被觀察者集合是玩家；觀察者集合也是玩家。

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

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

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

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

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

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

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

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

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

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

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

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

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

移動(dòng)：

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

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

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

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

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

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

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

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

審核編輯：黃飛