《QQ仙侠传》Server端视野优先级控制
一．问题概述
1.1 、背景介绍
在大型多人在线游戏（MMOG）中，一个玩家的视野范围通常是有限的，即只能看到附近一定范围内的对象及其行为，同时也并不需要感知到足够远处对象的存在，实际上这与现实世界中的普遍规律也是比较的一致。
对于视野逻辑的实现，除了距离上的这个限制，一般也还会有一个数量上限，即一个玩家同时能看到的对象个数是有限的。这样做的主要目的，是为了在玩家过于密集时，使消息广播量得到有效的控制。
基于以上两点考虑，通常的实现是在玩家身上维护一个视野列表，并在自身及周围对象位置变化时进行更新。在《自由幻想》、《幻想世界》、《QQ仙侠传》等多款游戏中，都有类似的实现。
既然视野列表长度是有限的，当玩家过于密集时，就需要一个进入视野列表的优先级策略，这样才能够使游戏中玩家的视野逻辑尽量地接近自然、真实的情况。本文将会详细介绍一下在《QQ仙侠传》中，Server端在视野列表以及优先级控制方面的具体实现。
1.2、优先级策略
仙侠传中主要采用了两个优先策略：
1） 特殊关系优先
在现实世界中，拥有特殊关系的人们总是会更多地关注彼此，游戏世界也是如此。
可见范围内特殊关系玩家会优先进入视野，以便他们之间更多关注和交互。
在仙侠传中，目前考虑的特殊关系仅包括队友和夫妻，即联系密切的小规模团体。
2） 距离近者优先
可见范围内，距离较近的玩家，会被优先看到，这也是一种比较自然直观的策略。
仙侠传较早的视野算法并没有按距离优先，经常出现的情况是两个玩家约定交易地点，但跑到相同位置后确无法互相看到。距离优先策略可以很好地解决类似问题。
二．相关数据结构
2.1、视野列表
实际上NPC、怪物的分布及行为都是可受Server控制的，设计上可以规避分布过于密集的情况；玩家的行为才是无法控制和准确预期的，因此仙侠中仅针对玩家采用了视野列表的管理方式，后续文中的“视野列表”也是指“视野内的玩家列表”，不再重复说明。
仙侠传中目前的视野列表长度为60，数据结构使用定长数组，每个元素记录玩家对象的ID。考虑到仙侠传中ID是64位的，且视野列表会频繁的变动，我们并不保持列表的有序性，以此降低增删结点时带来的数据挪动。
同时视野列表应该具有对称性，即A和B两个玩家，或者互相都能看到，或者互相都看不到。这样主要是出于设计上的考虑，避免出现类似PK上的不公平的情况。
仙侠视野列表的特点可以概括为：有限性，对称性，无序性。
2.2、地图对象管理
为了展开视野优先级策略的思路介绍，首先简单介绍一下仙侠传地图对象的管理方式。仙侠传中将地图划分成格子单元Cell，每个Cell边长是32米，每个玩家的视野范围是以自身为中心的5×5格子方阵。地图中的对象由Cell进行管理，在Cell中串接成链表，这样就可以快速遍历到视野范围内的所有对象。下图2-1给出了一个比较直观的描述。
图2-1 地图Cell管理
玩家视野的距离限制，本质上我们是通过Cell方阵来确定的；如果区域内玩家足够密集，我们则按优先级策略进行取舍，得出合适的视野列表，以此达到对视野目标个数的限制。下面我们就来介绍一下仙侠传视野搜索算法的具体思路。
三．视野搜索算法思路
3.1、视野搜索主要步骤
视野搜索的主要步骤如下：
1） 基于当前位置，按照优先级策略，得出完整的视野列表；
2） 对比之前已有视野，归结出视野变化；包括离开视野列表、新进入视野列表，保持不变列表；
3） 对离开视野的玩家做相互删除操作，并互相通知；
4） 对新进入视野的玩家做同步增加操作，若对方视野已满，则可能会进行替换；
在具体实现中，通常有两种事件会触发进行视野搜索：一个是新进入地图时刻，如角色登录或地图间传送；另一个是当玩家的位置发生足够的变化时，如玩家移动了较远的距离。
对于玩家移动距离的判断，我们采用了类似Cell划分的思路，将地图划分成了更小的格子，如果移动前后玩家处于不同的格子中，则认为发生了足够的位移并重新进行视野搜索。
下面我们来看一下视野搜索中比较关键的部分，即得出带优先级的完整视野列表，在仙侠中是如何来做的。
3.2、计算完整列表
首先声明原有视野列表为：CurrList = { a, b, c, d …}
为实现玩家收集过程中的分级，我们定义多个收集队列，初始为空：
特殊关系： ColtList[0] = { }
0到5米： ColtList[1] = { }
5到15米： ColtList[2] = { }
15到30米： ColtList[3] = { }
30米之外： ColtList[4] = { }
遍历搜索玩家过程：
1） 取特殊关系成员，依次判断，如果距离在视野范围内则添加到ColtList[0]列表中；
2） 由视野中心Cell开始，按照由近至远的顺序，遍历视野5×5 Cell方阵。对每一个玩家，按距离计算得出其所属分级队列，添加到相应的ColtList[i]中；
3） 收集完毕后，按顺序依次从ColtList[0]、ColtList[1]、ColtList[2] … 中取出列表内的玩家，即为符合我们优先策略的队列；记为 ViewList = { 1, 2, 3 … }
其中对5×5 Cell的遍历时，根据玩家处在当前Cell中的不同位置，遍历顺序也有所不同。仙侠中共有4种遍历顺序，如图3-1为玩家位于当前Cell左上方时的遍历顺序，各种顺序实际上是以静态数组的方式预先在程序中定义。
图3-1 Cell遍历顺序示意
遍历Cell的过程中，出于效率的考虑，也可以采用适当的截断策略。比如视野列表最多60个玩家，当遍历达到300个玩家时即可中断，一般不会对结果产生明显的影响。在仙侠中目前对内圈3×3方阵采用完整遍历，在遍历外圈时发现数据足够则即时中断。
考察我们的优先级算法，可以发现其并不是一个严格的排序，只是一定规则下的分级，同时为了进一步减少计算，我们在距离计算时，使用了如下近似公式：
距离近似公式： C = A + B / 2
即直角三角形长边加上短边的一半，近似等于斜边的长度。可证明其最大误差在11％左右，平均误差在5％左右。在对距离要求不严格的时候，可以用来简化计算。
归结前后视野变化：
基于前文，ViewList是搜索后得出的即将更新的视野列表。但考虑到此前玩家可能一直在地图中，已拥有一个当时的视野列表CurrList，ViewList和CurrList可能存在交集，即刷新前后始终在视野中的玩家。同时我们也需要知道这两个列表的差集：
始终在视野对象： KeepList = ViewList ∩ CurrList
离开视野的对象： LeaveList = CurrList － ViewList
新进入视野对象： EnterList = ViewList － CurrList
对于KeepList我们不需要改变，也不需要做相互通知；
对于LeaveList我们需要同步删除，同时做互相删除；
对于EnterList我们需要同步增加，增加时可能会发生替换，并互相通知；
然而集合的交集、差集常规算法通常效率上不够优秀，需要先保证集合元素的有序性，排序的复杂度为O(N*LogN)，之后的交集差集计算复杂度为O(N)。在此为了规避常规集合运算，结合具体的问题环境，我们借助了一种在玩家身上打标记的计算方式，把集合运算的时间复杂度降低到O(N)，本质上这也是一种以空间换时间的做法。
标记法求视野前后变化：
由于视野列表本质上存储的是一批玩家，为快速的计算视野变化，我们在Player结构上增加一个字节的标记字段，默认值为0。归结视野变化的算法如下：
1） 首先首先遍历原有的视野列表CurrList，对其中所有玩家打上标记1；
2） 遍历新的视野列表ViewList，如果玩家已有标记1，则打上标记2，表示原有视野玩家；否则为新进视野的玩家，添加到EnterList中；
3） 再次遍历CurrList，如果标记仍然为1，则添加到LeaveList中，表示不在新视野中；遍历过程中顺便清空CurrList所有玩家的标记。
至此我们已经得EnterList、LeaveList两个列表，所需的时间复杂度为O（N）；
对于LeaveList玩家，双方同步删除一定可以操作成功，同时做相互通知即可；
对于EnterList玩家，我们需要考虑当对方列表已满时，做一个替换的处理。
3.3、视野更新中的替换规则
正如前面所说，视野的对称性是一个基本前提，在进行视野更新时，可能有这样的情况需要考虑：A需要将B添加的自己的视野中，但此时B的视野已满，无法同步增加。此时我们需要有一个合适的替换规则，在必要时将A强制添加到B的列表中。
在仙侠传中，我们使用了如下的处理方式：
1） 如果A与B为特殊关系，则强制替换
因为特殊关系成员的个数远小于视野列表上限，因此一定可以在B的视野中，找到一个目标进行替换；
2） 如果A与B的距离足够接近（小于15米），则尝试替换
尝试在B的视野列表中找到一个足够远的目标进行替换（跳过特殊关系玩家），找不到合适目标可不替换；
3） 查找替换目标时进行倒叙查找
虽然实现上我们没有保证视野列表的有序，但分析视野搜索算法，一般情况下距离较远的玩家更容易出现在列表的末端，为此倒叙查找可以更快的命中；
替换算法的时间复杂度为O(N)，因为使用了倒叙查找的方式，实际运行中通常很快即可命中。关于替换规则，其实可以根据具体项的自身情况加以权衡，选择合适的优化策略，目前仙侠采用的还是偏于简单的一种方式，细节上还有一些可改进的方面。
四．视野变更的消息通知
由于视野的对称性，当视野发生变化时需要做双方的同步通知。对于有玩家进入视野，首先需要收集新玩家的详细信息发给自己的客户端，同时也需要将自身的详细信息发给他们，对于离开视野的通知也是类似。仙侠中采用了以下通知方式：
对于自己的消息通知：
一次性收集列表中的玩家相关信息，构造一个消息包发给自己客户端；
对于对方的消息通知：
构造一个自身信息的消息包，以“组播”的方式按列表进行发送；
这里所说的“组播”是互娱架构平台组件提供一种高效的广播技术，相信互娱的同学都会比较了解，在此可以简单介绍一下。MMOG服务器一般采用接入层和逻辑层分开的架构，处理网络连接的进程tconnd，处理游戏逻辑的进程zonesvrd，两进程间使用Bus通道进行通信。组播是指当一个消息需要广播给多个玩家时，zonesvrd并不需要每个消息放入Bus一次，而只是放入一个Bus消息，同时在消息头中包含多个玩家的标识，在tconnd进程中才将消息依次分发到多个玩家的客户端。这样可以显著减少zonesvr与tconnd间的消息交互。
仙侠传中的视野变更，采用了一次收集和组播的实现方式，有效地减少了消息包量。
五．结语
本文较为完整地介绍了仙侠传视野列表及视野优先级控制的主体思路，具体实现中的某些处理细节可能也并未完全涵盖。另外算法的设计也总是依赖于具体问题和特定环境，相信针对众多具体的项目，必定会用有更多更好的设计实现。就仙侠传目前的实现而言，本身也有很多可以改进的方面，在此也很希望大家能够多提宝贵意见，笔者非常期待与大家的进一步探讨和交流，开拓思路，共同提高。