深入探索AOI算法的設計考慮因素

作者：co lin

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

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

每個對象需要維護到兩個集合：

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

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

有些游戲對象同時擁有這兩個集合，有些只擁有其中一個，假設場景中有玩家，怪物，NPC，掉落物：

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

現在我們就一步步地探索AOI算法。

上帝視角

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

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

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

進入

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

將我加入場景管理器。

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

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

離開

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

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

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

更新

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

取出玩家集合，向它們發送相應的事件，他們會向客戶端發送相應的協議，這樣客戶端就能看到我的行為了。

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

但當場景比較大，且對象數量達到數百上千的時候，這種方式就不適合了，因為每個對象的狀態更新需要通知上千個其他對象，交叉起來能達到百萬級別的量。再加上客戶端承受不了上千的游戲對象，我們應該減少對象的視野。

減少視野

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

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

看看減少視野后的處理

進入

我進入場景。

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

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

離開

我離開場景。

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

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

更新

這里的更新不包括移動，因為移動會導致對象集合變化。遍歷我的觀察者集合，向它們發送相應的更新事件。

移動

我移動的時候，被觀察者集合和觀察者集合都會發生變動，現在我們沒有好的辦法優化它，只能這樣做：

遍歷場景的所有對象：

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

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

網格化

將場景劃分成等大的格子，1個格子大約為1/4屏幕大小，每個進來的對象根據坐標加入對應的格子中，如下圖所示：

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

進入

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

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

離開

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

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

移動

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

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

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

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

假如我們把要求降低一些：強制對象的視野固定在9宮格上，也就是說，只要我在這個格子中，不管怎么移動，視野都是周圍的9個格子，那事情就好辦了。每個游戲對象不需要維護兩個集合，直接從9宮格里取即可?，F在邏輯簡化成這樣：

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

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

十字鏈表

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

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

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

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

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

那么哨兵結點的作用到底是什么呢？顧名思議，它們的作用是用來監控跨越它的對象結點的：

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

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

如此一來一回，各方就慢慢維護起觀察者集合和被觀察集合。離開視野的處理也是類似，這里就不再羅索，留給你們去想。

總而言之，十字鏈表的的核心算法就是哨兵結點或對象結點在移動的時候，會跨過對方，在跨過的時候判斷進入視野還是離開視野。

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

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

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

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

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

地標結點越多越精確，但遍歷的結點也越多，這個需要實際實現的時候做試驗。

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

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

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

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

怪物多樣化一些：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

移動：

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

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

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

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

創建場景的時候，就把地標結點分別插入到X和Y鏈表中，地標結點的坐標不會改變，所以永遠不用移動它們。

接著把這些地標結點按順序保存在一個數組中：|M1|M2|M3...|，有了這個數組，我們就不用從頭移動了。

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

A移動完成之后，A身邊的兩個哨兵結點開始向兩邊移動，移動過程中就會有一些對象進入A的視野。

審核編輯：黃飛