浩毛的博客

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

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

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

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

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

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

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

AOIDemo.exe 下載