开发笔记:MMORPG场景同步AOI解决方案

MMO 游戏,需要解决的最重要的问题之一,就是如何把游戏世界中各种状态的改变通知给需要知道这条信息的玩家。
为此,需要为每个玩家设定一个AOI(Area Of Interest),当一个对象状态发生改变时,需要将信息广播出去,那些AOI覆盖到这条消息的玩家都会收到这条广播消息。

AOI 主要作用有两:
第一,服务器上的玩家或 NPC 状态发生改变时,将消息广播到附近的玩家。
第二,当玩家接近NPC时,进入NPC警戒区域,AOI 模块将消息发送给NPC,NPC再做出相应的AI反应。

目前游戏中 AOI 实现主要有3种:
第一种,最容易也是最笨的一种,玩家定期同步自己状态给服务器,服务器定期比较所有对象间的关系,发现可以触发 AOI 事件就发送消息。写法简单,不容易出错,但如果处理不好,效率往往是最低的。

空间切割网格算法

把整个场景用等分大的格子划分成一个个小区域,对象进入、退出、移动时都需要更新相应的格子对象列表。这种算法插入、删除对象都非常快,时间复杂度为O(1)。缺点是当对象在格子直接移动时,需要消耗大量计算时间。目前《幻想西游》采用的是这种算法。

场景划分

场景大小:200 200
格子大小:50
50
场景中需要划分等分大小的格子数: 200 / 50 200 50 = 16 个

效果如下图所示:

世界坐标与格子坐标

每个格子有对于的格子坐标,每个世界坐标可以轻易的转换成格子坐标。
世界坐标 (x, y) 转换成格子坐标公式为:(math.floor(x/gridWeidth), math.floor(y/gridHeight))
如世界坐标为 (80, 50),转换后对应格子坐标为 (2, 1)。

划分九宫格

每个格子都需要维护该格子内的对象信息,同时也需要维护关心该格子的观察者信息。
当对象处于场景某个格子时,该对象会有 9 个自己所关心的格子,对象可以观察并收到自己关心区域的 AOI 事件。
当然,对象所处的格子也会被其他格子的对象所关心。也就是说一个格子里面的对象可以作为观察者,观察周围格子内对象;同时也是被观察者,被其他格子内的对象所观察。

如图所示,当对象所进入格子 (2, 2) 时(红色区域),那么其关心的周围 9 个格子(浅蓝色区域)中任何一个发生 AOI 事件时,它都会收到相应的 AOI 事件消息。

对象进入场景

通知对象所处周围9个格子的其他对象 进入 AOI 事件。

对象离开场景

与进入相反,通知对象所处九宫格的其他对象 离开 AOI 事件。

对象移动

如果对象格子变更时,如图所示,对象纵向移动由(2, 2) 移动到 (3, 2),45度角移动由 (2, 2) 移动到 (3, 3):

会产生3种格子:

  • 对象离开视野的格子(灰色格子),通知对象离开 AOI 事件。
  • 对象进入视野的格子(橙色格子),通知对象进入 AOI 事件。
  • 取所有需要操作的格子的交集(浅蓝色格子),通知对象移动 AOI 事件。

十字链表算法

场景维护着两个双向链表(如果3D空间,则增加第3条),分别对应着 X 轴 和 Y 轴。
每个链表对象的坐标按从小到大排列,也就是 X 坐标值越小,排在越前面,Y轴同理。
此算法对象短距离移动时,很节省计算量,但涉及长距离移动时,计算量会非常大。

对象进入场景

遍历 X 轴 和 Y 轴两个链表,找出新增对象在两个轴中所处的位置,将新对象加入到指定位置,并根据新对象的通知范围(可动态设定)获得需要通知对象集合,发送 进入 AOI 事件。

对象离开场景

对象进入场景后,在 X 轴 和 Y 轴各保存了两个节点位置,可以通过这个位置,获取指定范围的的对象集合,发送 离开 AOI 事件。

###对象移动
与格字算法类似,对象移动后也会会产生3种对象集合:

  • 更新位置前的集合,通知 离开 AOI 事件。
  • 更新位置后的集合,通知 进入 AOI 事件。
  • 取上面两个集合的交集,通知对象 移动 AOI 事件。

处理上面产生事件顺序与格字算法相同。

分层 AOI

有了AOI算法,并不意味着能有满意的效果,假设场景里面放入10000人,那么按分布情况来说,即使有AOI算法,也会很糟糕,你会看到满屏幕的人,密密麻麻,卡的要死。这种情况下,玩家体验会很糟糕,所以可能需要进一步优化。
目前市面上见得比较多的解决方案有几种,一种是对单个场景分线,复制多个相同的场景副本,玩家随机进入某个场景的副本,以此来达到分流的目的。
另外一种方案,是从梦幻西游手游服务器AOI设计方案中看到的,设计一个分层AOI概念,也就是单个场景创建多个AOI对象。把玩家分通过某个规则,分在不同的层次。当人数增多时,可以动态进行分层,人数少的时候可以把层数合并回来,然后就是让玩家在人少的时候也能看到几个人,人多的时候还是看到几个人。这种优化放过来后,这是同一台服务器,效果大概是这样的,你在同一层里看到的都是你关心的人。这个感受就很好了。