OldJiang.com

浩毛的博客

OldJiang.com
posts - 14, comments - 81, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理
最近在优化游戏服务器的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 下载

Feedback

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。[未登录]  回复  更多评论   

2011-06-20 09:20 by zuhd
记得云风当时的意思是把AOI单独弄出来做一个服务器进程。楼主这个demo做的很有意思

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。  回复  更多评论   

2011-06-20 12:09 by 杨粼波
基于2D的格子是肯定的。
基本上它是一个碰撞检测的算法。
分离出来一个逻辑服务器倒也是可以的,不过如果开发周期紧,也没必要这么做,因为这样比较耗时。如果设计得当,那么今后需要从分离也是容易的。

AOI挺重要的,设计得好可以减少不少广播流量,那可是可以大大的提高游戏服务器的负载呀。

不知道你是什么游戏,及时制还是回合制。根据业务逻辑不同,实现细节上会不同的哦。

你可以使用Sweep and Prune做第一阶段的检测,进行分组,计算量会小很多,然后再进行第二阶段计算,如果你还有其他的检测的话,比如圆形区域。关于这个算法,这是我查到的一些资料:
http://www.cppblog.com/tx7do/archive/2008/01/15/41185.html
http://www.cppblog.com/tx7do/archive/2008/01/15/41188.html
http://www.cppblog.com/tx7do/archive/2008/01/09/40817.html
http://www.cppblog.com/tx7do/archive/2008/01/09/40815.html


我帮你查了一些资料:
http://www.cnblogs.com/corefans/archive/2009/07/23/1529699.html
http://blog.codingnow.com/2008/11/aoi_server.html
http://blog.csdn.net/akara/archive/2009/11/28/4897185.aspx

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。  回复  更多评论   

2011-06-20 13:25 by Paw
呵呵 dome很有意思,可以参考下wow的开源私服服务端。。。

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。  回复  更多评论   

2011-06-20 14:47 by 浩毛
@杨粼波
再小的计算量,当4000个实体在一个TICK都要计算一次的时候(可以想象成4000个玩家和NPC都在一个服务器上移动), 也是很大的计算量

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。[未登录]  回复  更多评论   

2011-06-20 15:45 by 杨粼波
Sweep and Prune的话,4000个物体还能够接受。
我曾经做碰撞系统的时候,第一阶段Sweep and Prune耗费的时间几乎是微乎其微的。
如果要分离这个业务逻辑,我看,在线人数至少要几万以上。因为,分离意味着,它的计算量已经不是单机能够承受了。
最多的耗时,还是花费在了网络群发上面。

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。  回复  更多评论   

2011-06-20 16:34 by 浩毛
@杨粼波
AOI的计算,除了碰撞,还有很多消耗在维护每个实体的AOI列表上.

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。  回复  更多评论   

2011-06-20 16:39 by 浩毛
@杨粼波
谢谢你的热心,你帮我查的最后三个资料,我以前看过的,最早的实现方案就是参考了那些资料做的,效率不尽人意,我现在做的方案不是按照这些资料做的,不是按格子来做的.
你可以下载AOIDEMO来看下,里面统计的时间是 所有实体都在移动,计算和维护所有实体的AOI列表一次所花的时间,而不是只统计的选择的那个实体的AOI计算时间

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。[未登录]  回复  更多评论   

2011-06-20 18:08 by 杨粼波
嗯好。
反正不管怎么样,最优的实现了就行。

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。[未登录]  回复  更多评论   

2011-06-21 12:26 by 饭中淹
我能想到的就是细分区域的优化。

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。  回复  更多评论   

2011-06-26 11:34 by tankin
最近正搞这个,能分享,发一份代码给我么?谢谢
E-mail: tnag@163.com

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。  回复  更多评论   

2011-06-30 06:22 by 双杯献酒
说说实现原理吧,源代码就不用贴了。

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。  回复  更多评论   

2011-07-02 09:14 by tankin
最近实现了一种AOI方法,但还是不满意,对作者上面提到的1/40的算法很感兴趣,可否提供一个思路

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。  回复  更多评论   

2011-07-14 10:49 by yanx8844
很感兴趣,最近在研究这个方面的。

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。  回复  更多评论   

2011-07-29 10:11 by 抗美
你好,请问一下如何改变动态改变4叉树节点,因为人物要动的么!

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。  回复  更多评论   

2011-09-24 17:46 by 疯狂的火车
不是真的吧!!这么牛B,楼主可不可以提供一点思路啊,保密制度保到什么程度啊???
crazytrain*163.com

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。[未登录]  回复  更多评论   

2011-09-30 12:59 by zyb
请问你是用四叉树管理的么?每个entity有个可视范围,当entity移动时,需要先调整其在四叉树里面的位置,然后获取新可视范围区域内的entity集合(这里是关键!由于采用四叉树,可以通过给定范围,精确的找出小范围的目标entity),和老的集合比较,计算差集和补集,分别通知离开和进入消息。

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。[未登录]  回复  更多评论   

2011-12-20 23:20 by angle
大哥,你写的太好了,能给个源代码吗?23795598@qq.com 谢谢啦~~

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。[未登录]  回复  更多评论   

2011-12-20 23:21 by angle
大哥,你写的太好了,能给个源代码吗?237095598@qq.com 谢谢啦~~ 刚qq写错了!!!!

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。  回复  更多评论   

2014-10-17 22:25 by Area
说下原理也好嘛。

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。  回复  更多评论   

2015-07-12 17:13 by 洪宁静
拿出来,纯属为了炫耀?

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。  回复  更多评论   

2015-10-28 15:16 by lazy
http://docs2x.smartfoxserver.com/AdvancedTopics/advanced-mmo-api

估计作者是抄的这个做的,大家看看就知道了。。。不要再问他了。

# re: 游戏服务器的场景管理计算AOI终于搞出一个靠谱的方案了。。。  回复  更多评论   

2016-01-03 23:14 by 威尔斯
兄台给些思路交流交流可好?azhou1117@163.com

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


OldJiang.com