剑网3同步策略
剑三同步策略
1. 概述
1.1. 什么是同步策略
同步策略是指将玩家所需要的数据，从服务器端传送给客户端的方法。
最简单、最原始的同步策略是将服务端上的所有信息都传送给客户端、每次服务端上的数据发生变化，都立刻通知所有客户端。显然，这种方法是不行的，带宽和计算量都承受不起。那么，就需要减少同步的数据种类，并且不需要每次数据变化都立刻通知客户端。
因为玩家位置的变化频率高、对游戏感受影响最大，所以抽取出来单独讨论。
1.1.1. 位置同步
由于带宽和计算量的限制，每个客户端仅同步周围的9个Region，这样可以极大的减少了同步数据量。但是因此跨越Region需要做一系列特殊处理。
某玩家A，原先在第6号Region，现在移动到了第11号Region中。那么他的同步范围就从1、2、3、5、6、7、9、10、11，变成了6、7、8、10、11、12、14、15、16。
需要做的处理有：
1． 通知玩家A，删除无需同步的Region中的场景物体（包括玩家、Npc、Doodad、子弹，下同）。对于玩家A来说，需要删除的是1、2、3、5、9这5个Region。
2． 通知1、2、3、5、9这5个Regoin中的玩家，玩家A已经移出了他们的同步范围。
3． 通知玩家A，8、12、14、15、16这5个新Region中已存在的场景物体。
4． 通知8、12、14、15、16这5个Region中的玩家，玩家A进入了他们的同步范围。
处理1中的操作可以全部在客户端完成。当玩家A在客户端从第6号Region跨入第11号Region时，会更新自己的同步范围，自动删除无需同步的Region中的场景物体，无需服务端通知。
处理2中的操作可以由广播的移动指令代替。当1、2、3、5、9这5个Region中的玩家收到玩家A的移动指令时，玩家A会最终走出他们的同步范围，走到第11号Region中，客户端可以在这时自动删除掉玩家A，无需服务端通知。
现在需要考虑的是如何减少处理3和处理4中传输的数据量。对此，剑网一和剑网三，有不同的策略，详细分析见后。
1.1.2. 其他信息的同步
可能会以较高频率变化、并且玩家关心的数据还有生命值和人物状态，可以考虑特别处理。剩余的其他数据，都可以靠指令方式同步，即客户端需要时向服务端请求，或者服务端发生变化时通知客户端。
1.2. 本文档讨论的要点
1. 明确同步策略的设计目标、运行环境参数、优劣的判断标准
2. 描述曾经提出过的若干种方案
3. 对比各种方案的优缺点，从而得出结论
2. 设计目标
2.1. 解决大规模群战时的延时问题
当玩家持续朝一个固定方向移动时，Region中的所有的新NPC和玩家都必须在他跨入该Region之前完成同步。对于9Region同步来说，这个时间间隔就是玩家跨越一个Region所需要的时间。
由此得到公式：Interval = RegionWidth / PlayerVelocity。
其中RegionWidth为恒定值16m，
PlayerVelocity为[0,16]m/s，
因此Interval为[1,+∞]s。
如上所述，设计目标为最长在2秒内，同步完所有新Region（3-5个）中的NPC和玩家。如果可以优先同步移动方向上的Region，可能效果可以更好。
为了实现这个设计目标，将格子的尺寸从0.5m*0.5m改成了1m*1m（2005.05.09）。
2.2. 降低占用的带宽
降低带宽包括以下三方面：
1. 降低平均传输量，根据用户状态调整同步频率；
2. 降低同步数据占总数据比例，尽量利用命令同步的信息，以减少状态同步；
3. 削平峰值，如果需要一次性同步大量数据（跨Region），需要分次同步。
2.3. 缓解客户端与服务端的数据不同步现象
主要是坐标的不同步，其次是血量和人物状态
3. 环境参数与名词约定
3.1. 说明
参数分为四种：
l 常数，这个无需解释了；
l 设计指标，即预想需要达到的运行环境参数，一般会分为一般指标和峰值指标；
l 经验数值，没有经过实际测量，而是根据经验评估得到的数值，所有未标注的来源的数值，都是经验数值；
l 实测数值，经过剑网测量得到的数值，会附上数值的测试条件和原始记录。
3.2. 参数列表
1. 同时在线的玩家数量 一般指标 4000 峰值指标 6400
2. 在城市内的玩家比例 设计指标 40%
3. 在野外的玩家比例 设计指标 30%
4. 在副本内的玩家比例 设计指标 30%
5. 参加群战玩家的数量 一般指标 200 峰值指标 300
6. 每个Region的NPC数量 设计指标 <=1.5
7. 玩家移动的最高速度 常数 16m / s = 1格子/帧
8. 每组服务器的最大带宽 常数 100 Mb/s
9. 每个客户端的平均上行带宽 实测数值 180 Byte/s 注1
10. 每个客户端的平均下行带宽 实测数值 1.7 KB/s 注1
11. 游戏每秒运行的帧数 常数 剑网一:18 剑网三:16
注1：原始数据参见文档《剑网客户端数据包分析》，这两个数据的计算公式如下：
平均流量 ＝ 城内平均流量×40％＋城外打怪平均流量×60％
其中的40％和60％由2、3、4这三项设计指标得到。
3.3. 名词约定
1. 状态同步 无论数据是否变化，定时的将数据传送给客户端的同步方法
2. 指令同步 仅当数据发生变化或者客户端发起请求时，才将新数据传送给客户端的同步方法
3. Npc 对于剑网一，Npc中包含了玩家；而对于剑网三，Npc和玩家是完全分开的
4. 逻辑数据 剑三中的逻辑数据是指：角色的当前坐标、目标点坐标、移动速度、角色状态机状态、显示相关的魔法状态、当前生命值百分比、当前内力值百分比、当前怒气值百分比。这些数据的特点是：1 平时同步时必须同步的基本数据；2 改变的频率非常高
5. 显示数据 剑三中的显示数据是指：角色的显示资源、角色的名字、角色的阵营。这些数据的特点时：1 只和显示以及攻击判定有关；2 一般不会改变
4. 剑一的同步策略描述与分析
4.1. 概述
剑网一的数据同步主要依靠每2帧（剑网一每秒18帧）发送一次的状态同步数据包实现。当遍历Region时，每间隔一帧，会从本Region的Npc（包括玩家）列表、Obj（对应剑三的Doodad）列表中各挑选出一个，将其数据组成对应的同步数据包，发送给本Region以及邻接的8个Region中的所有玩家。从另一个角度来看，每个玩家每秒最多会收到9×9＝81个Npc的状态同步数据包。
4.2. 伪代码与数据结构
4.2.1. 伪代码描述
4.2.2. 协议包结构定义
typedef struct tagNPC_NORMAL_SYNC : public tagProtocolHeader
{
DWORD ID; //Npc或者玩家的ID
DWORD MapX; //X坐标
BYTE Camp; //阵营
BYTE State; //状态
DWORD MapY; //Y坐标
BYTE LifePerCent; // 生命的2048分之几的低8位
BYTE Doing; // 高3位为生命的2048分之几的有效高3位，低5位为Doing
} NPC_NORMAL_SYNC;
sizeof(NPC_NORMAL_SYNC) = 17
typedef struct tagOBJ_SYNC_STATE : public tagProtocolHeader
{
BYTE m_btState;
int m_nID;
} OBJ_SYNC_STATE;
sizeof(OBJ_SYNC_STATE) = 6
4.3. 计算与分析
至此，我们很容易就可以计算出每个玩家的最大状态同步流量：
Fmax = 17 * 81 = 1377B/s
唯一会影响这个数值的因素，是同步范围内的9个Region中是否有空的Region。由于存在空Region的概率不大，因此我们可以近似的认为
Favg = Fmax * 0.9 = 1240B/s
对于单个客户端，状态同步流量占平均下行流量的比例为：
P = Favg / 1700 = 73%
同时，根据第二章中的环境参数，可以计算出一组服务器（也就是一个完整的游戏世界）的状态同步流量：
F1 = Favg * 4000 = 4.96MB/s = 39.7Mb/s
F2 = Favg * 6400 = 7.94MB/s = 63.5Mb/s
假设一个Region中有N个Npc（包括玩家），则依靠状态同步得知这个Region中的所有Npc（包括玩家）的时间为：
T = N / 9
-------------我是分割线，计算至此结束------------
从以上计算大结果，很容易看出Npc（包括玩家）状态同步的流量是优化带宽占用的关键。因此，其他数据的就没有分析的必要了。
剑网一的状态同步策略的特点：
1. 总带宽只和玩家数量有关，且是线性关系。因此玩家数量确定时，占用带宽非常稳定，不会出现波动。
2. 玩家跨越Region时，同步到新Region中的所有Npc（包括玩家）的时间，与Region中的Npc（包括玩家）的数量成正比。
5. 剑三的同步策略描述与分析
5.1. 对剑网一优化余地的讨论
首先，再次明确一下优化的目标（详见第二章）。最重要的是提高群战效率，其次是减少带宽占用，再次是改善用户感受。
具体的优化手段如下：
5.1.1. 消除所有的冗余数据
所谓冗余数据，也就是无效的信息。状态同步的数据，单单对于发现新玩家这一功能来说，有很大的冗余比例。因为状态同步数据的发送，并不考虑客户端是否已经知道这个玩家，而只是不断的循环发送。如果我们要提高发现新玩家的效率，那么只有提高状态同步的频率。同时，状态同步还负责校正客户端数据，而校正客户端数据，并不需要很高的发送频率，这就带来了矛盾。
所以，如果我们能把状态同步中发现新玩家这个功能剥离开，有新的协议和代码来实现，就可以很容易的消除冗余的信息。而状态同步本身，由于剥离的发现新玩家的负担，只需要负责校正客户端数据，发送的频率和数据包的大小都可以降低很多。
5.1.2. 细分状态同步中各种数据的同步频率
区分城内和野外玩家的同步策略。城内和野外玩家的关注点是不同的。在城内时，玩家并不会关注周围人的生命值和内力值（如果剑三还像剑一一样城内不能战斗的话），而且这些数据也不会经常改变，所以它们的同步频率就可以适当降低。
区分战斗和非战斗状态玩家的同步策略。非战斗状态时的同步频率可以少许降低，这时对于Npc的生命值和内力值的关注度不高。
区分玩家的目标和非目标的同步策略。战斗时，玩家对于战斗目标的生命值和状态是非常敏感的，对周围玩家或者Npc的生命值和状态的敏感程度要低一些。
5.1.3. 依据移动方向决定同步数据的发送顺序
5.1.4. 尽最大可能利用每一个Bit
对于剑网三，同步坐标点的最大范围是：
X ∈ [0, CELL_LENGTH * REGION_GRID_WIDTH * MAX_REGION_WIDTH - 1]
Y ∈ [0, CELL_LENGTH * REGION_GRID_HEIGHT * MAX_REGION_HEIGHT – 1]
其中，
CELL_LENGTH = 32，
REGION_GRID_WIDTH = 32，
REGION_GRID_HEIGHT= 32，
MAX_REGION_WIDTH = 64，
MAX_REGION_HEIGHT= 64，
因此，
X ∈ [0, 2^15 – 1]
Y ∈ [0, 2^15 – 1]
这样，一对坐标只需要4Bytes就可以表示了
-----------------------我是分割线-----------------------
在同步数据包中，另一个占用空间很大的就是Npc或者玩家的ID了。
一个方法是客户端接收到了服务端第一次同步的ID之后，上传一个客户端约定的1Byte或者2Byte的对应序号，以后的同步采用短序号。这样做的主要出发点是，客户端只知道有限的Npc和玩家，短一些的序号足够表达了。其代价有三方面：
1. 在服务端，为每个玩家连接维护一个长短序号对应表
2. 在服务端和客户端，发送和接收数据包时，需要进行序号的转换
3. 可能会带来一些短序号重复的问题
如上所述，这种方案的代价较大。
另一个方法是服务端尽可能将某些ID相同的数据包合并，这样可以共享一个ID。按照状态包的发包频率，区分成若干数据集合，这些集合分别是每1秒发送一次的、每10秒发送一次的、每1分钟发送一次的（间隔时间的只是举例）。
5.2. 新同步策略的描述
5.2.1. 移动坐标同步
问题和难点：如何保证Npc或玩家在服务端与客户端的移动路径和位置一致，Npc或玩家在不同客户端的移动路径和位置一致。由于网络延时等原因做到完全一致是不可能，但是要做到较好的玩家体验，移动流畅，操作自如。存在三种影响玩家体验的情况：
1． 玩家发出移动操作后，不能立即响应，如《传奇》
2． 当游戏卡的时候，移动时经常将角色拉回到原来的位置，如《剑网》
3． 移动流畅操作自如，但是瞬移外挂容易横行，如《魔兽》
这是由于不同的技术手段和做法引起的问题：
1． 移动完全以服务端为准，客户端移动前与服务端同步
2． 移动以客户端为准，服务端校验并修正
3． 移动完全以客户端为准
《剑网3》是如何解决的？此处只讨论同步，不讨论服务端客户端如何进行移动处理。
《剑网3》策略：变种的以客户端为准，服务端校验修正；
如何实现的呢？
1． 历史位置记录，服务端记录角色一段时间内的位置坐标，比如记录角色最近10秒钟每帧的位置坐标和速度等数值；
2． 同步源坐标和目标坐标，移动指令数据包中携带角色移动时的其实位置及目标地址；
3． 同步移动时刻帧，客户端及服务端在移动同步时，通知事件发生时刻帧，剑网3所有数据包都携带了此信息。
服务端处理：角色的移动主要由客户端触发，服务端进行校验处理；当服务端收到数据包后，校验数据包中源坐标与当前服务端角色源坐标是否相等，如相等服务端角色移动处理，否则修正客户端移动位置及状态。
但是网络同步存在延时，只是这样不加其他的处理的进行校验，会存在很多数据包都不能通过校验，这将会有如上第二种不好的操作感。剑网3对校验做了改进，方法就是校验前预处理，根据数据包中的移动时刻帧取到此时刻服务端角色的位置坐标，再进行源坐标校验。
存在两种可能性，1、数据包中的帧数小于服务端当前运行帧（客户端跑的慢） 2、数据包中的帧数大于等于服务端当前运行帧数(客户端跑的快)
Ø 客户端慢：所有数据包基本都应该属于这种情况，针对这种情况，采用了回滚机制，历史位置记录上场了，服务端首先将角色的位置回滚到数据包帧时刻位置，然后进行校验工作；
Ø 客户端快：针对这种情况，服务端会进行移动处理，赶上客户端快的部分，然后进行校验。不过这属于异常情况，如果出现，三个原因：1、服务端机器太差，撑不住；2、客户端Bug；3、恶意外挂。因为客户端的运行帧是服务端同步的，正常情况下客户端不可能快。
通过这样处理校验通过的机率很高，基本上不可能出现频繁修正客户端角色位置，达到避免第二种操作感的效果。
由于服务端对客户端的移动同步坐标进行校验修正，外挂是很难得逞地，避免瞬移。
客户端处理：客户端需要做的事情有4件
1． 响应玩家移动操作，这个响应是立即的，只要玩家操作键盘移动角色，客户端立即做出移动的响应，并向客户端发出移动同步数据包。这样就不存在第一种不好的体验;
2． 处理其他角色移动，位置完全以服务端为准，当服务端同步过来的源坐标与客户端的当前的坐标不相符时，客户端首先将此角色移动到服务端的位置，再进行移动处理；
3． 处理自身角色移动，有可能服务端主动触发角色移动，如击飞等技能；
4． 处理自身位置修正，将自己移到服务端同步过来的位置，很少发生。
存在的问题：客户端在处理其他角色移动时，完全以服务端为准，可能会出现频繁修正其他角色位置，不过这对玩家体验影响不大。有熊掌还要鱼，太贪了吧。
5.2.2. 跨Region的处理
在剑网一中，玩家跨Region时，并不立刻通知相关的客户端；而在剑网三中，会有特定的数据包通知客户端。
客户端发现： 剑三中，新Npc和玩家的发现，主要依靠客户端的发现。如果客户端收到一个指令广播包（无论什么指令，跳跃、移动、发技能等等），发现其中的角色ID本地不存在，就会向服务器请求该ID的详细逻辑数据（逻辑数据的定义见名词约定部分）。
此处带来一个问题，非活动玩家（不会发送广播包的玩家，比如摆摊的）就永远不会被同步到了，这个问题通过强制同步机制解决。
强制同步：就是当角色进入一个新Region后若干秒（现在暂定2秒），强制发送在2秒内没有活动过的角色的资料。
实现方法如下：
首先：在所有的Npc和玩家的身上增机加两个个变量
1． m_nLastBroadcastFrame，记录上次做广播行为的游戏帧数；
2． m_nEnterRegionFrame[9]，记录跨入周围9个Region时的游戏帧数。
其次：在角色的每次Activate时，检查各个该Region的进入时间是否到了强制同步的时刻，如果正好到了，则发送强制同步信息。由于m_nLastBroadcastFrame的存在，我们可以避免发送所有在本角色进入该Region后发送过广播指令的角色的逻辑数据。
第三：变量更新
1． 只要有广播数据包发送就更新m_nLastBroadcastFrame成当前游戏帧数。其中，广播位置并不仅仅是位置的状态同步，还包括移动指令等一系列包含了玩家位置的广播数据包；
2． 每次跨Region的时候，都会将新进入的Region对应的m_nEnterRegionFrame[]刷新成当前游戏帧数。
5.2.3状态同步
5.3. 新同步策略的延时和带宽占用分析
//通知新加入Region的角色 : 17 Byte
struct G2C_NEW_CHARACTER_INTO_REGION : DOWNWARDS_PROTOCOL_HEADER
{
unsigned m_dwCharacterID : 32; //角色ID
unsigned m_nX : (MAX_REGION_WIDTH_BIT_NUM +
REGION_GRID_WIDTH_BIT_NUM +
CELL_LENGTH_BIT_NUM); //角色的X坐标
unsigned m_nY : (MAX_REGION_HEIGHT_BIT_NUM +
REGION_GRID_HEIGHT_BIT_NUM +
CELL_LENGTH_BIT_NUM); //角色的Y坐标
unsigned m_nVelocityXY : (CELL_LENGTH_BIT_NUM);//角色在XY平面上的速度
unsigned m_Doing : 5; //角色状态
unsigned m_Reserved : 2; //保留
unsigned m_nDestX : (REGION_GRID_WIDTH_BIT_NUM +
CELL_LENGTH_BIT_NUM +
MOVE_DEST_RANGE_BIT_NUM + 1);
//移动目标点X坐标上相对当前点的偏移
unsigned m_nDestY : (REGION_GRID_HEIGHT_BIT_NUM +
CELL_LENGTH_BIT_NUM +
MOVE_DEST_RANGE_BIT_NUM + 1);
//移动目标点Y坐标上相对当前点的偏移
unsigned m_nLifePercent : LIFE_PERCENT_BIT_NUM; //生命百分比
unsigned m_nManaPercent : MANA_PERCENT_BIT_NUM; //内力百分比
unsigned m_nRagePercent : RAGE_PERCENT_BIT_NUM; //怒气百分比
unsigned m_MagicState : MAGIC_STATE_BIT_NUM; //要显示的魔法状态
};
//通知客户端一个Region中的所有角色
struct G2C_ALL_CHARACTER_IN_REGION : UNDEFINED_SIZE_DOWNWARDS_HEADER
{
unsigned m_dwRegionX :MAX_REGION_WIDTH_BIT_NUM;//Region在地图中的X坐标
unsigned m_dwRegionY :MAX_REGION_HEIGHT_BIT_NUM;//Region在地图中的Y坐标
struct KSyncCharacter //15 Byte
{
unsigned m_dwCharacterID : 32; //角色ID
unsigned m_nX : (REGION_GRID_WIDTH_BIT_NUM +
CELL_LENGTH_BIT_NUM); //角色的X坐标在Region中的偏移
unsigned m_nY : (REGION_GRID_HEIGHT_BIT_NUM +
CELL_LENGTH_BIT_NUM); //角色的Y坐标在Region中的偏移
unsigned m_nVelocityXY : (CELL_LENGTH_BIT_NUM);
//角色在XY平面上的速度
unsigned m_Doing : 5; //角色状态机的状态
unsigned m_Reserved : 6; //保留
unsigned m_nDestX : (REGION_GRID_WIDTH_BIT_NUM +
CELL_LENGTH_BIT_NUM +
MOVE_DEST_RANGE_BIT_NUM + 1);
//移动目标点X坐标上相对当前点的偏移
unsigned m_nDestY : (REGION_GRID_HEIGHT_BIT_NUM +
CELL_LENGTH_BIT_NUM +
MOVE_DEST_RANGE_BIT_NUM + 1);
//移动目标点Y坐标上相对当前点的偏移
unsigned m_nLifePercent : LIFE_PERCENT_BIT_NUM; //生命百分比
unsigned m_nManaPercent : MANA_PERCENT_BIT_NUM; //内力百分比
unsigned m_nRagePercent : RAGE_PERCENT_BIT_NUM; //怒气百分比
unsigned m_MagicState : MAGIC_STATE_BIT_NUM; //要显示的魔法状态
}m_SyncCharacterList[1];
};
流量F = S * N(Packet)
= S * N(Player) * F(Player) * D(Player) * 9
在一般情况下：
数据包大小S = 17 Byte
玩家总数N(Player) = 6400
玩家密度D(Player) = 4 - 6个/Region
玩家激活的Region个数N(AR) = 6400 / 6 * 9 = 9600
Npc密度D(Npc) = 3个/Region
激活的Npc总数N(Npc) = N(AR) * D(Npc) = 9600 * 3 = 28800
玩家跨Region的频率F(Player) = 0.5 次/秒
Npc跨Region的频率F(Npc) = 0.1次/秒
F = S * (D(Player) + (D(Player) + D(Npc))) * 9 * N(Player) * F(Player) +
S * D(Player) * 9 * N(Player) * F(Npc)
= S * D(Player) * 9 * N(Player) * [ (2 + D(Npc) / D(Player)) * F(Player) + F(Npc)]