挑战6千人同区域移动 - QQ仙灵视野搜索算法优化之路

QQ仙灵是一款2D回合制大型多人同时在线MMO网游，采用经典的分区分服架构，玩法以休闲为主，并且单服万人级别高承载量。现在也正慢慢步入公测的步伐，随着在线的提升，单服在线提升的同时也让CPU火速飙升，有时甚至直接CPU封顶100%。经过perf性能分析，我们针对数据做了很多优化工作，其中一项重要优化内容是视野搜索算法优化。因为此项优化工作可能可以给大家日后相关工作的一个参考，所以在KM分享出来，希望对有需要的项目组有所帮助。

众所周知，MMO游戏服务器瓶颈在于以下两点：

1，  玩家频繁移动带来的视野搜索的性能消耗---CPU。

2，玩家各种行为动作所产生的广播包量---带宽。

以上两点问题会随着服务器承载在线的增加而愈加凸显，而与它们有交点的一个就是视野管理，要是能控制好视野处理，就能让服务器轻松很多。如何管理好万人承载服务器下的视野管理，让视野管理这块不成为QQ仙灵高承载在线的弱点。

在此仙灵后台经过借鉴成熟项目组的经验，再结合回合制游戏的特征来对视野管理进行了一些优化，效果是明显的，性能有很不错的提升，如下图：

图表 4 在3000人的对比下，明显看出老视野算法扛不住了...优化后视野算法依然轻松...

图表 6 优化后视野人数到190人,服务器CPU在50%左右波动,显示出优化后视野搜索强大的生命力!

图表 1 好热闹的人群啊

在此首先感谢三位同事在km及相关文档上的精彩分享，让仙灵在视野优化工作上有了灵感：

1、Rickli的两份关于视野优化的文章。见附件。

 《区域与视野算法实现》及《视野同步策略》

2、仙侠gloryliu 《QQ仙侠传Server端视野优先级控制》。

这篇文章精彩得很，一定要看看，仙灵视野优化灵感就从这开启了。

3、御龙Rainman 《国战型游戏服务器开发探索》

介绍了视野搜索的一些策略，分享了一些性能数据。

视野管理需求包括什么：

1，  角色的视野范围区域：一般来说就是客户端单屏范围（玩家600像素半径范围），这样让玩家只见到自己屏幕里的视野变动，无需关心屏幕外的世界。传统的视野搜索使用九宫格搜索法。

2，  单个角色可见视野人数：因为视野人数会决定了广播包量，必须给予一个合理的值。

角色内存视野上限=512个

角色一般视野上限=80至200个

角色近距离扩充视野上限=30个左右

         此值可以根据客户端性能来自动调节,也可以让用户自行选择想要的视野大小。

3，  单个角色视野搜索频率：一般角色进行位置变动时就会进行视野搜索，控制好搜索频率（例如2s一次搜索）

4，  角色视野进入策略（按照优先级别）：

a)         与玩家有关系的玩家优先进入视野（队员，师徒，情侣，夫妻，密友等）；

b)         摆摊摊位一定要进入玩家视野，也就是摆摊角色视野要超大；

c)         队伍人数未满的队长拥有更多视野，让别的需要组队玩家更容易完成组队；

d)         与角色近距离（三分之一视野距离）的玩家，可以允许进入角色扩充视野；

e)         老视野优先保留。

如何实现？

那么如何实现以上视野管理的需求呢？接下来，让我们一起来看看一个玩家是怎么看到地图上其它玩家的。请看附件rickli在的一份ppt，里面详细说明了视野的处理方式。

为了更好的描述，在此引入一些视野管理基础常识：

1，地图区域：为了快速管理地图上的object，我们采用mmog惯用的手法，化整为零！！一幅地图会被划分为N个面积等同的方形区域。在仙灵中，一个区域比较广阔，大概相当于4个客户端屏幕（2* 1024 * 2*768 = 2048*1536，一个客户端屏幕=1024*768）。

一幅大型游戏地图尽管里面有多漂亮的场景，多热闹的玩家交互，在程序猿眼里，这只不过一对标记了编号的区域而已吗，所以程序猿的眼里，游戏是多么“有趣”啊...真羡慕玩家看到的是美景...

2，  区域链表：玩家站在某个区域上，区域需要记录管理这批玩家，要在插入删除上有很好性能表现，就使用了双向链表结构，以角色为链表节点，把在同一区域内的玩家连成一条链。一个区域视其上面玩家的多少，极端情况是一个由数千个玩家节点组成的链表。

3，进出区域：玩家只能在地图一个确定区域上，如果因为移动而导致进出区域，会让玩家从一个区域的区域链表中退出，进入另一区域的区域链表。

4，视野搜索区域：当要进行视野搜索时，需要确定玩家的搜索区域，有可能是一个区域，有可能是数个区域，这决定于玩家所在当前区域的位置。

—  对象在一个区域里面移动，当视野范围始终在区域中，则只需搜索当前区域；

—  如果视野范围与上方区域交叠，则需搜索当前区域及上方区域；

—  当视野范围与左上方相邻区域交叠，则需搜索当前区域、上方区域、左上方区域、左方区域共四个区域；

—  进行其他情形的分析，可以得出不同的搜索区域构成一共有9种。

5，  玩家关注列表：也就是玩家的视野，关注列表的大小就决定了玩家视野的多少，QQ仙

灵原视野上限采用FFO的1024人。因为关注列表是一个需要频繁变更的单元，使用什么数据结构直接决定了视野性能的优劣。什么数据结构能让这个列表表现出高效的增删查呢？

在还没看glory的文章之前，本人认为有序数组是最适合不过的，通过简单的二分查找插入，单次插入性能消耗才O(LogN)，重整视野性能消耗N*O(LogN)！

但是看了那篇glory文章之后，才发现无序数组在处理这个视野上更加精彩出色，更能从中实施各种视野策略，并且不会明显提升视野消耗。在此不再多说，大家有兴趣的一定要看看。

不过无序数组在管理视野上在删除一个视野单元时也有一个明显不足，只能遍历删除，很明显对于频繁进出视野操作而触发的删除视野动作会成为这个数据结构的弱点，与glory进行认真地探讨后，我当时提出了一个在双方视野单元上多记录一个在对方视野无序数组的索引位置，这样删除只需要直接按照记录索引进行删除即可。当然这是一个改进，但更进一步才发现，无序数组内的各个视野单元的内存位置很可能因为删除了其中任意单元而进行移动，显然维护索引又变成了一个比较艰巨棘手的问题，一不小心，就会导致双方视野乱了套，想到都头疼。当时还在怀疑自己是不是一个合格的程序猿，竟然想出这么乱的想法。然而希望总是在那么点灵感迸发的时候跳出来，头脑中突然告诉我一个结构“链表”，然后再进一步想到我们代码库中有一个优秀的算法“空闲数组链表”，附件中含代码…接下来，再分析了一下，“数组链表+节点索引”，简直是perfect，各项性能指标直达O(1)…可以看出新的数据结构，只要双方进入视野，它们的内存位置不会改变，只到双方离开视野才会同时删除，这样大大减少视野变化过程中的内存移动。（以上内容是一个探索优化视野之路的心里历程，也是我想和大家分享的内容）

下图 老视野处理数据结构：

下图 新视野数据结构：

表格 1上图展示了ABC三个角色互见时的内存结构

可以看到新老数据结构对比，有个重要地方：使用了空间换时间，增加了很多辅助数据来快速进行视野的增删处理，重整整个角色视野的理论速度在O(N)级别。 

6，  视野对称性：

当玩家A进入（离开）玩家B视野时，玩家B也必须进入（离开）玩家A视野。“伪”代码如下：

上图，保证双方同时进入视野

上图，保证双方同时删除视野

当前优化后的视野搜索步骤： 

Step1: 遍历老视野，找出不在视野范围内的视野单元，记录Uin到LeaveViewList中，并保证双方同时删除对应的视野单元。并标记所有还在视野范围内的视野单元对应角色=“我还在视野中啊”，伪代码如下：

Foreach（老视野列表）

{

         If (视野单元不在视野范围)

         {

                   双方出视野;

                   记录LeaveViewList

         }

          Else

          {

                   标记视野单元对应角色flag=IN VISION

          }

}

Step2: 遍历与角色有特殊关系的玩家列表，进preEnterList

Foreach(特殊关系)

{

      If （特殊关系玩家flag== IN VISION）

                   Continue;

                      Else

                      {

                                特殊关系玩家flag=I AM SPECIAL GUY

                                进入preEnterList；

      }

            }

Step3：计算玩家还有多少视野空间VisionRoom=总视野大小N - 当前视野人数，VisionRoom等于此次遍历要搜索到的目标数SearchObjCnt，为了让每次搜索量合理，设置如下：

SearchObjCnt  = (SearchObjCnt > 50 ? 50 : SearchObjCnt),即每次搜索到50个有效视野单元就终止吧

1，  把VisionRoom按照各搜索区域人数比例分到各个区域搜索名额中。

例如VisionRoom=20，搜索区域有两个，分别有300人的区域A，100人的区域B，那么

A区域分到四分之三的搜索名额=15人，

B获得名额=5人。

2，  按照名额遍历各个区域area，获得对应有效视野目标，记录进preEnterList中

Foreach(obj in area)

     {

            if (obj 不在视野中

      || obj 视野满

            || obj == IN VISION

            || obj == I AM SPECIAL GUY

     )

            {

                     Continue;

     }

    Else if (obj 与玩家超近视野距离

         && obj扩展视野未满)

    {

     标记obj  flag=Super Near

      }

     Else if(obj 在摆摊中

        &&视野上限未满)

    {

      标记obj  flag= Vendor（摆摊小贩）

     }

     Else if (obj 视野上限未满)

     {

             标记obj  flag=Normal

     }

    把obj放入preEnterList中

     If (搜索到有效目标==VisionRoom)

     {

           Break;

     }

   }

 Step4: 根据获得的preEnterList,，并根据obj的flag来判断obj视野空间是否符合要求，空间没问题的就保证插入到双方视野列表中，建立最后的EnterViewList, 并清空flag。

      Step5:

                 对EnterViewList与LeaveViewList

堆包给视野搜索者A，告知进出视野。

组包广播给List的Uin玩家，告知A进出他们视野。

 视野优化后性能数据对照截图：

图表 2 1000人同屏移动下优化前后性能对比

图表 3 从此图可看出，优化前后的CPU对照明显加大

图表 4 在3000人的对比下，明显看出老视野算法扛不住了...优化后视野算法依然轻松...

图表 5 新视野算法基本上在在线上涨时，性能呈现线性 递增

图表 6 尽管加大了视野人数到190人，性能消耗与110差不多。

图表 7    6000人在线下，不同视野数对照的性能消耗，可以看出新视野方案性能与视野人数上限关系不大。

本次分享完毕，本人才疏学浅，可能优化描述有所不完善，请大家多多见谅！

优化前后算法都是很简单的，大家怀着轻松的心情即可看懂，没什么高深的内容，仅仅是算法+数据结构的表达而已。