Posted on 2011-06-20 01:25
浩毛 阅读(17894)
评论(23) 编辑 收藏 引用 所属分类:
服务器开发
最近在优化游戏服务器的AOI(area of interest)部分,位置有关的游戏实体一般都有一个视野或关心的范围,
当其他实体进出某个实体的这个范围的时候,就会触发leaveAOI或enterAOI事件,并维护一份AOI 实体列表。
我们来考虑最简单的实现,假设区域R中有1000个Entity,当某个entity位置发生变化时,需要计算entity的AOI事件和列表,伪代码如下:
function onEntityMove(who)
for entity in entities do
if who <> entity then
计算who和entity之间的距离
如果who移动前entity在who的AOI范围内,且现在在范围外
触发who.onLeaveAOI(entity)
如果who移动前entity在who的AOI范围外,且现在在范围内
触发who.onEnterAOI(entity)
如果who移动前在 entity的AOI范围内,且现在在范围外
触发entity.onLeaveAOI(who)
如果who移动前在 entity的AOI范围外,且现在在 范围内
触发entity.onEntityAOI(who)
end
end
end
每次一个实体移动一次位置就要遍历1000个实体来计算,这 样做显然不行,效率太低了,
那么就需要引入场景管理,将区域R分成n个格子,每个格子维护一个实体链表,entity移动时,只遍历它所在的格子和周围的8个格子的实体链表,
再优化下,可以加入AOI圆和格子的碰撞检查,9个格子中再去掉没有相交的格子。。。等等
也有用四叉树来进行场景管理的。
还有些方案更简单,直接是画格子,按以实体为中心的九个格子进行位置广播, 实体从一个格子移动到另外的格子时触发事体。。好处是计算量简单,缺点是带宽占用大
我上面的方案都试过了,效率和带宽占用都不理想,最近终于弄出一个新的方案,现在的AOI计算量是我们服务器以前计算量的1/40-1/80,由于涉及到公司的保密制度,不便细说,上几个测试的抓图:
机器配置:win7 ,T5870 inter双核2G,2G内存
20个entity 随机运动计算一次所有entity AOI的时间在0.02毫秒左右:
220个实体,选择的实体AOI范围里有68个实体:
4000个实体,选择的实体的AOI区域里有465个实体
AOIDemo.exe 下载