转载

分布式AOI处理

首先简要介绍下AOI的基本概念.

AOI的意思是area of interest,也就是关注区域.那么什么是关注区域.在游戏中,你能看到视野内其它对象的位置变化,各种各样的行为变化.NPC对象能根据自己附近的对象选择合适的AI行为.这里的视野和附近区域,就是一个对象的关注区域.

关注区域内的其它对象状态发生变化时,应该通知关注者.而关注区域由关注者自身所处的位置以及关注半径决定的.

当一个对象从关注者的关注半径外移动到半径内,则需要向关注列表中添加一个新的关注对象.反之则需要从关注列表内删除一个对象.

AOI在大型网络游戏中是容易成为瓶颈的部分.假如游戏内发生大型的热点事件,例如国战.则在某一个区域内将聚集大量的玩家.例如出生点或跳转点附近.因此如果可以将AOI处理分摊到多个进程中,将可以有效的提高游戏服务器处理热点事件的能力.

本文不打算详细介绍AOI处理相关的算法.想了解的朋友可以搜索九宫格或十字链表.

下面将进入本文的正题.

首先假设我们有一片大区域,在这片区域内的对象都可能产生交互.因此这片区域形成一块统一的AOI管理区域.进入这片区域的对象都要受到管理.

可以将这片区域分布到N个进程上.所有受管理的对象在这N个进程中都存在副本.这些副本对象被分成两类:master对象或ghost对象.master对象只能存在于一个进程中,其它进程中必然是ghost对象.

游戏对象发生位置变更时,将变更同步给所有的AOI对象.对于ghost对象只是简单的更新当前位置.只有master对象才会有进一步的处理.

AOI服务以固定的频率处理master对象.每当一个进程收到master对象变更时,就将对象添加到变更列表中,直到到达处理周期才会对变更列表中的对象进行处理.

通过将master对象均匀的分布到多个进程中,使得一片AOI区域能够处理更大的对象数量.

在极端情况下,可能会出现某个进程上聚集大量活跃且互相关注AOI对象的情况.这个时候就需要将通过负载均衡机制,将一部分master对象移动到负载相对较轻的进程中.因为所有进程上的AOI对象实际上都保存了游戏对象的副本信息(位置,是否隐身等).这个迁移过程只涉及到master标记的切换.

实现问题:

游戏对象位置变更需要通知给N个AOI进程.当然因为需要通知的数据只涉及到坐标信息,数据量不大应该不会成为太大的问题.当然也可以考虑多线程,主从进程模式.这样变更消息只要通告到两个进程即可.
只有master对象可以向应用通告AOI变化事件.考虑如下场景,有A,B两个对象,其master对象分别在两个AOI进程a,b中.假设a进程在的对象是masterA,ghostB,b进程中是masterB,ghostA.最开始的时候A,B都在对方的可视半径外.然后分别向一个中间点靠近.在某一时刻t,他们将会进入对方视野.如果让master和ghost对象都可以通告AOI事件.则对同一个进入视野的事件将会向应用进程通告两次.一次是由ghost对象触发,例如处理masterA的时候,触发A进入ghostB,另一个则是处理masterB时触发的A进入masterB.虽说应用进程可以处理这种重复事件,但重复事件太多毕竟会影响程序和网络性能.另一方面如果只有master对象可以触发AOI事件则会产生另外一个问题.如果一个master对象是静止的,那么它将收不到任何AOI事件.解决办法是对于静止对象或微动对象,可以使用一个更大的时间间隔来将其添加到处理队列中,保证其可以触发AOI事件.
需要对AOI进程进行健康度检查,如果其中某些进程出现故障或负载过高,可以将其中的master对象迁移到健康的进程上.
如何迁移master对象?当一个进程负载过高时,应该被迁移的是那些热点对象,也就是处于对象最密集区域中的那些对象.可以为每个master对象记录一个计数值,这个值是一个master对象被处理时扫描过的对象数量.根据这个计数值将master对象放在一个大根堆中,当需要迁移时只需要从这个大根堆中提取对象即可.
如果是因为进程出现故障需要迁移如何处理?应用进程中的每个对象记录自己的master对象在哪个AOI进程上,当接到AOI进程故障的通告时将这些对象的master对象分配到其它健康的AOI进程中.