最近在優(yōu)化游戲服務器的AOI（area of interest)部分，位置有關的游戲實體一般都有一個視野或關心的范圍，
當其他實體進出某個實體的這個范圍的時候，就會觸發(fā)leaveAOI或enterAOI事件，并維護一份AOI 實體列表。
我們來考慮最簡單的實現，假設區(qū)域R中有1000個Entity，當某個entity位置發(fā)生變化時，需要計算entity的AOI事件和列表，偽代碼如下：
function onEntityMove(who)
for entity in entities do
if who <> entity then
計算who和entity之間的距離
如果who移動前entity在who的AOI范圍內，且現在在范圍外
觸發(fā)who.onLeaveAOI(entity)
如果who移動前entity在who的AOI范圍外，且現在在范圍內
觸發(fā)who.onEnterAOI(entity)
如果who移動前在 entity的AOI范圍內，且現在在范圍外
觸發(fā)entity.onLeaveAOI(who)
如果who移動前在 entity的AOI范圍外，且現在在 范圍內
觸發(fā)entity.onEntityAOI(who)
end
end
end
每次一個實體移動一次位置就要遍歷1000個實體來計算，這 樣做顯然不行，效率太低了，
那么就需要引入場景管理，將區(qū)域R分成n個格子，每個格子維護一個實體鏈表，entity移動時，只遍歷它所在的格子和周圍的8個格子的實體鏈表，
再優(yōu)化下，可以加入AOI圓和格子的碰撞檢查，9個格子中再去掉沒有相交的格子。。。等等
也有用四叉樹來進行場景管理的。
還有些方案更簡單，直接是畫格子，按以實體為中心的九個格子進行位置廣播， 實體從一個格子移動到另外的格子時觸發(fā)事體。。好處是計算量簡單，缺點是帶寬占用大
我上面的方案都試過了，效率和帶寬占用都不理想，最近終于弄出一個新的方案，現在的AOI計算量是我們服務器以前計算量的1/40-1/80，由于涉及到公司的保密制度，不便細說，上幾個測試的抓圖：
機器配置：win7 ,T5870 inter雙核2G,2G內存
20個entity 隨機運動計算一次所有entity AOI的時間在0.02毫秒左右：
220個實體，選擇的實體AOI范圍里有68個實體：
4000個實體，選擇的實體的AOI區(qū)域里有465個實體
AOIDemo.exe 下載