作者：co lin

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

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

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

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

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

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

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

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

上帝視角

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

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

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

進(jìn)入

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

將我加入場(chǎng)景管理器。

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

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

離開(kāi)

我離開(kāi)場(chǎng)景，將我從場(chǎng)景管理器刪除。

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

可能不需要向我發(fā)送Leave(對(duì)象)事件，因?yàn)槲姨鴪?chǎng)景后，客戶(hù)端會(huì)自動(dòng)把場(chǎng)景中的對(duì)象刪除。

更新

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

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

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

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

減少視野

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

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

看看減少視野后的處理

進(jìn)入

我進(jìn)入場(chǎng)景。

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

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

離開(kāi)

我離開(kāi)場(chǎng)景。

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

遍歷我的被觀(guān)察者集合，將我從這些對(duì)象的觀(guān)察者集合中刪除，將我的被觀(guān)察者集合清空。

更新

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

移動(dòng)

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

遍歷場(chǎng)景的所有對(duì)象：

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

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

網(wǎng)格化

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

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

進(jìn)入

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

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

離開(kāi)

我離開(kāi)場(chǎng)景，將我從格子刪除，

接下來(lái)的做法和上面的離開(kāi)完全一樣。

移動(dòng)

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

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

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

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

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

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

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

十字鏈表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對(duì)玩家來(lái)說(shuō)：它能觀(guān)察到所有類(lèi)型的游戲?qū)ο?；同時(shí)它會(huì)被其他玩家和怪物觀(guān)察著；但它可能不會(huì)被NPC和掉落物觀(guān)察。所以它的被觀(guān)察者集合是所有類(lèi)型的游戲?qū)ο?，觀(guān)察者集合是玩家和怪物。

對(duì)于NPC和掉落物來(lái)說(shuō)：它不關(guān)心周?chē)膶?duì)象，所以它沒(méi)有被觀(guān)察集合；但它有觀(guān)察者集合，里面只有玩家類(lèi)型。

怪物多樣化一些：

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

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

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

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

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

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

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

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

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

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

把我從原來(lái)的格子刪除，加入新的格子。

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

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

離開(kāi)場(chǎng)景：取出周?chē)?格的對(duì)象，向它們發(fā)送Leave(我)事件。

移動(dòng)：

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

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

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

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

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

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

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

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

審核編輯：黃飛