浩毛的博客

最近在優(yōu)化游戲服務(wù)器的AOI（area of interest)部分，位置有關(guān)的游戲?qū)嶓w一般都有一個視野或關(guān)心的范圍，
當(dāng)其他實(shí)體進(jìn)出某個實(shí)體的這個范圍的時候，就會觸發(fā)leaveAOI或enterAOI事件，并維護(hù)一份AOI 實(shí)體列表。
我們來考慮最簡單的實(shí)現(xiàn)，假設(shè)區(qū)域R中有1000個Entity，當(dāng)某個entity位置發(fā)生變化時，需要計算entity的AOI事件和列表，偽代碼如下：

function onEntityMove(who)   
  for entity in entities do
    if who <> entity then
        計算who和entity之間的距離
        如果who移動前entity在who的AOI范圍內(nèi)，且現(xiàn)在在范圍外
           觸發(fā)who.onLeaveAOI(entity)
        如果who移動前entity在who的AOI范圍外，且現(xiàn)在在范圍內(nèi)
           觸發(fā)who.onEnterAOI(entity) 
         如果who移動前在 entity的AOI范圍內(nèi)，且現(xiàn)在在范圍外  
          觸發(fā)entity.onLeaveAOI(who)
          如果who移動前在 entity的AOI范圍外，且現(xiàn)在在 范圍內(nèi)
           觸發(fā)entity.onEntityAOI(who)
      end
  end
end
每次一個實(shí)體移動一次位置就要遍歷1000個實(shí)體來計算，這 樣做顯然不行，效率太低了，
那么就需要引入場景管理，將區(qū)域R分成n個格子，每個格子維護(hù)一個實(shí)體鏈表，entity移動時，只遍歷它所在的格子和周圍的8個格子的實(shí)體鏈表，
再優(yōu)化下，可以加入AOI圓和格子的碰撞檢查，9個格子中再去掉沒有相交的格子。。。等等
也有用四叉樹來進(jìn)行場景管理的。

還有些方案更簡單，直接是畫格子，按以實(shí)體為中心的九個格子進(jìn)行位置廣播， 實(shí)體從一個格子移動到另外的格子時觸發(fā)事體。。好處是計算量簡單，缺點(diǎn)是帶寬占用大

我上面的方案都試過了，效率和帶寬占用都不理想，最近終于弄出一個新的方案，現(xiàn)在的AOI計算量是我們服務(wù)器以前計算量的1/40-1/80，由于涉及到公司的保密制度，不便細(xì)說，上幾個測試的抓圖：

機(jī)器配置：win7 ,T5870 inter雙核2G,2G內(nèi)存
20個entity 隨機(jī)運(yùn)動計算一次所有entity AOI的時間在0.02毫秒左右：

220個實(shí)體，選擇的實(shí)體AOI范圍里有68個實(shí)體：

4000個實(shí)體，選擇的實(shí)體的AOI區(qū)域里有465個實(shí)體

AOIDemo.exe 下載