entity的运动同步

关于运动同步这部分内容，我这里只是抛砖引玉，详细的内容可以参考知乎用户Jerish编写的网络同步在游戏历史中的发展变化，这篇文章附带有70多页图文并茂且参考文献非常详实的pdf，非常值得一读。

运动信息的表示

网络游戏中每个客户端都需要接收周围一定范围内的其他entity的状态，用来做各种内容显示与交互判定。在entity所带的状态信息中最基础的就是这个entity的locomotion运动信息，即位置、朝向、速度这三个部分：

struct vector3
{
    float x;
    float y;
    float z;
};

struct rotation
{
    float pitch;
    float yaw;
    float roll;
};

struct entity_locomotion
{
    vector3 position;
    rotation rotation;
    vector3 velocity;
};
  1. position 这个entity的世界坐标，表示为(x, y, z)三个浮点值，但是在不同的引擎和3D处理软件中所采用的坐标系(x, y, z)的轴朝向是不一样的，下图就是各种坐标系的典型代表

各种不同的坐标系

为了方便后续讨论，我们采取OpenGL中规定的右手坐标系，当玩家正对屏幕时，Y轴朝上，X轴朝右， Z轴朝玩家的坐标系

  1. rotation 这个entity的朝向信息， 表示为(pitch, yaw, roll)三个浮点值，这里也用图形来展示一下：
    1. pitch是围绕X轴旋转，也叫做俯仰角。当X轴的正半轴位于过坐标原点的水平面之上（抬头）时，俯仰角为正，否则为负
    2. yaw是围绕Y轴旋转，也叫偏航角。即右偏航为正，反之为负
    3. roll是围绕Z轴旋转，也叫翻滚角。向右滚为正，反之为负

pitch-yaw-roll

  1. velocity 这个entity的速度信息，表示为(x, y, z)三个浮点值，对应在这三个坐标轴上的速度分量

由于速度velocity可以通过位置的差异除以时间计算出来，所以有些实现中并不会直接同步velocity分量，而是通过在游戏循环中的entity::update(float delta_time)来更新速度。同时对于很多不要求精确的物理判定的游戏来说，entity的朝向保持为直立状态，所以只有yaw分量是有意义的，pitch和roll分量会被强制设为0。所以有些游戏中会将entity_locomotion进行简化：

struct entity_locomotion
{
    vector3 position;
    float yaw;
};

这样entity_locomotion的结构体大小就从9个浮点数降低到了4个浮点数，可以有效的降低数据同步量。

运动信息的精度

计算机里对于浮点数的存储表示由ieee 754这个标准规定的：

  1. 单精度浮点数即float采用32bit表示，开头1bit是符号位，后续的8bit是指数位，最后的23bit是尾数部分
  2. 双精度浮点数即double采用64bit表示，开头1bit是符号位，后续的11bit是指数位，最后的52bit是尾数部分

浮点数格式

目前除了Unreal Engine 5外基本所有的游戏引擎都使用float作为坐标轴的数值单位，由于float的尾数部分只有23bit，导致了当指数部分维持为0时小数点后有效位数只有7位。所以为了维持1cm的精度，地图上的与原点偏移的最大距离范围不能超过。如果为了维持1mm的精度，则与原点最大距离坐标的偏移值不能超过1km。如果将整个地球用浮点坐标来表示，考虑到地球的赤道周长为40000km，则在赤道上相邻的两个点之间的最小差异为80m，这种精度基本无法接受。在游戏环境下有很多系统都依赖于对大量的顶点数据执行相关计算，特别是物理和动画系统，在精度不够的情况下可能出现各种匪夷所思的结果，例如玩家模型的帕金森一样的抖动。而且这种异常情况基本都会出现在离地图原点很远的位置，将相关模型移动到地图原点之后这些怪异现象就会自动消失。这篇文章 还提到了UE4中的shader为了性能在移动端使用了半精度的浮点数即Float16出现的各种渲染异常。Float16这个半精度的格式里只有5bit给了指数，10bit给了尾数，导致了浮点精度只能达到0.001。

想要解决这个精度问题比较粗暴的解决方法是将坐标单位从float切换为double，这样小数点后有效位数将变成16位，这样就可以基本解决地球模拟甚至太空模拟的精度需求。其带来的坏处就是计算所要求的时间增加以及信息交换数据量的增加。

运动变化的产生

角色的运动更新方法除了特殊逻辑（如传送）导致的强制位置更新之外，一般来说都是基于输入的物理模拟。这种方式需要在游戏读取按键输入，然后生成一个移动的方向向量。尝试将角色的物理模型移动这个方向向量，如果中途遇到障碍物，则需要针对性的处理。例如遇到斜坡需要上坡，遇到台阶需要爬升，遇到墙面需要贴着墙移动等等。每次移动完之后都需要重新寻找一下地面，来避免角色的脚底浮空，同时处理一下掉落、入水等特殊状态。

当角色拥有动画系统时，基于移动输入的位移系统就不够用了，需要引入根运动（Root Motion） ，也就是俗话说的动画驱动位移。这里引用一下UnrealEngine官方支持页面对RootMotion的介绍：

在游戏动画中，角色的碰撞胶囊体（或其他形状）通常由控制器驱动来执行位置更新。然后来自该胶囊体的数据用于驱动动画。例如，如果胶囊体在向前移动，系统就会知道在角色上播放一个跑步或行走的动画，让角色看起来是在靠自己的力量移动。但这种类型的运动并不始终适用于所有情况。在某些情况下，让复杂的动画实际驱动碰撞胶囊体（而非相反）是有道理的。这正是 根运动（Root Motion） 处理对游戏而言至关重要的原因之所在。

例如，假设玩家发起一次特殊攻击，在这种攻击中，模型已预先设定好向前冲的动作。如果所有的角色动作都是基于玩家胶囊体的，这样的动画会导致角色迈出胶囊体，从而导致碰撞数据与显示的模型完全不匹配，因为碰撞数据使用的是胶囊体的位置，而渲染的模型使用的是动画的位置。一旦动画播放结束，玩家就会滑回其碰撞位置。这就会产生问题，因为胶囊体通常用作所有计算的中心。胶囊体外的角色将越过几何体，不会对其环境做出适当的反应。另外，在动画结束时滑回他们的胶囊体也并不现实。

ue4_rootmotion_off

简单点的处理方法就是动画结束之后强制设置胶囊体到动画结束位置，但是这个解决不了动画播放过程中物理世界与渲染世界脱节的问题。还有一个简单取巧的方法就是对动画进行固定间隔的位置偏移采样，然后在启用这个动画之后，使用这个位置采样数据定期的去更新胶囊体的位置，在采样精度比较高的时候可以很大的缓解胶囊体与渲染模型之间位置偏差问题。不过在很多要求精确的物理判定的情况下这种方法还是不行，特别是动画系统受物理系统影响的时候。例如上图中向前冲锋起再停下的动画在前方有障碍物时应该要被障碍物阻挡住，但是由于物理查询依赖于胶囊体的位置更新。

所以对于这种有位移的动画的位置更新方案，最终演化成了性能消耗高但是最精确的动画驱动位移的方式。胶囊体的位置更新频率完全匹配当前游戏的更新频率，作为阻挡物的墙壁成功的停止了人物的前进动画：

ue4_rootmotion_on

运动同步的延迟

当联网客户端接收到了新的移动输入时，如何将这个输入引发的位置变化通知给服务器有三种做法：

  1. 客户端使用这个移动输入执行移动模拟，将模拟后的位置通知给服务器
  2. 客户端将移动输入发送到服务器，让服务器算出最新位置之后再返回给客户端
  3. 客户端本地用这个输入执行运动模拟，同时将移动输入发送到服务器，服务器也执行模拟

第一种方法是弊端是服务器此时会无条件的信任客户端，所以如果客户端使用了作弊手段时服务端将束手无策，相信玩过游戏的都见过那种开挂引发的飞天遁地。第二种方法变成了完全由服务器来生成位置，但是这种方法也有一个很严重的问题，即从按键被按下到客户端收到移动位置的更新之间的时间间隔可能会被拉的很长，带来了一种很不舒服的迟滞感。下图就图形化的描述了这个延迟的产生来源：

真实网络的延迟

  1. 输入延迟，这个是客户端逻辑帧收集按键输入的间隔，与客户端逻辑帧率负相关，在30fps的逻辑帧率下，按键延迟大概为15ms
  2. 客户端与服务器之间的延迟，大概30ms，对应的Round Trip Time也就是rtt就差不多60ms了，如果使用手机移动网络时对应的rtt可以达到100ms以上
  3. 服务器逻辑处理延迟，这部分在上图中没有体现，由于服务器要控制性能消耗，其逻辑帧率一般不会很高10hz-20hz左右，所以这个处理延迟可能也会有40ms左右
  4. 客户端渲染延迟，这就是在接收到新位置之后将相关数据传递到渲染线程处理完成所需要的大概时间，在30fps的渲染帧率下，其延迟大概为20ms
  5. 显示器显示延迟，这个是显示数据从传递到显存与真正在屏幕上展示出来的间隔，主流的显示器基本都大于60hz，所以这个的延迟大概为8ms可以忽略不计

总的来说从按下按键到看到反馈，整个流程的延迟都会在140ms以上，而人体对于大于100ms的延迟已经感觉很明显了，电子竞技选手可能对于大于60ms的延迟都无法忍受。我们观察这个总体延迟的各个组成部分，发现网络与服务器处理占了绝大部分，纯客户端自己的延迟只有40ms左右。所以对于那些对于反作弊要求严格同时延迟敏感的游戏，基本都会采用第三种的移动同步方案，即双端同时模拟。但是这种同时模拟又可能会产生客户端与服务端的状态不一致，所以还需要搭配一个定期检查纠正的机制，即客户端上传输入时也带上自己模拟的结果状态，服务器会检查这个客户端模拟结果是否与当前自己模拟的结果的差异在一定范围内，如果超过了指定误差范围则拒绝这个模拟结果，同时将服务器自己的模拟结果发送到客户端来强制纠正。Vavle的起源引擎就使用了这样的模拟纠正：

起源引擎的客户端服务端同步模型

上面这种双端同时模拟的方法可以很好的解决主控客户端的延迟问题，但是仍然没有解决客户端A的主控角色产生的位置变化通过服务器同步到客户端B延迟过大的问题。因为这个位置同步执行路径跟上图中是一摸一样，必须要经过服务器，消息传递所需要的100ms是完全无法优化的。

单纯的模拟角色的位置同步延迟大有些时候也将就能接受，因为玩家的关注点一般都是在自己控制的角色身上。其他角色如果保持着稳定的延迟的话，这些角色的动作看上去也算是有一点连续性和流畅度。但是互联网的网络状态其实是一个非常不可控的，如果出现了突然的延迟增大或者丢包重传，这种脆弱的连续性和流畅度就被打破了。

运动同步延迟

以上图为例，客户端A操纵的角色正以100cm/s的速度移动，初始位置为0，同时每隔100ms往服务端汇报最新位置。但是由于网络的不稳定性，A在第一帧发出的数据在另外一个客户端B里是第二帧收到，发出的第二帧数据在第四帧收到，发出的第三帧数据在第五帧收到，发出的第四帧数据在第八帧收到。这样连续的帧到达B的间隔分别为100ms,200ms,100ms,300ms，使用位置偏移除以间隔时间，B客户端里A对应角色的速度就是100cm/s, 50cm/s, 100cm/s, 33cm/s，速度无法保持恒定，变动很大，从而表现为一种抽搐感。

运动的插值与预演

除了这个由于延迟不稳定导致的第三方客户端里角色移动不连续之外，上面的转发式移动同步还有一个非常严重的问题：客户端B接收到的客户端A的最新位置已经是100ms之前产生的了，此时客户端B里展示的A的模型所在位置并不是最新的位置，例如在上图中的第八帧的位置差异已经是40cm了。这样的不匹配会导致各种技能物理判定出现问题。为了同时解决延迟不稳定和位置落后的问题，需要引入插值，这里包括两种插值：

  1. 内插值(Intepolation)：已确定的主控端过去位置P0和现在位置P1，模拟端执⾏从P0到P1之间的平滑插值(线性或非线性均可)以使渲染表现平滑的插值⽅法，我们叫它内插值。它的特点是插值的两端点都是已确定的历史位置。

  2. 外插值(Extrapolation)：已确定的主控端过去位置P0和速度V等，模拟端使⽤P0和V等来模拟主控端的运动轨迹以使渲染表现平滑的⽅法，我们叫它外插值。它的特点是起始端点已知,运⾏的终点已越过已确定值的边界(外插值叫法的理由)。

简单来说内插值负责追赶目标点，而外插值负责预测目标点。只使用内插值来平滑移动的话，会导致平均延迟的增大。因为此时接收到的最新位置会被当作目标位置来追赶，而不是立即设置位置，这样会导致到达此位置的时间更加延后。使用外插值则需要服务器往客户端多传递速度信息，这样才能计算出一个rtt之后这个模拟角色的位置，但是此时角色在延迟不稳定时仍然会有不连续的体验。所以一般来说这两个插值方法会一起使用，即模拟端先用外插值计算出当前模拟角色的位置P0，然后再使用内插值逐渐的将当前模拟角色的实际位置P1去追赶P0。这样的双插值合用的方法也就是常说的Dead Reckoning影子追踪方法。

dead reckoning

但是影子追踪方法并不是万能的，只有在外插值正确的时候才能得到令人满意的结果，如果主控端出现了大幅度的方向变化，模拟端外插值的结果就会与真实结果出现很大差异，导致插值后的路径与真实路径很不一致。下图就是一个非常简单的例子，左边蓝色的是主控端，右边橙色的是模拟端，初始时位置都在P0,同时速度都同步好了，做一个直线匀速运动，这样在左边到达P1的时候右边也在P1。随后主控端开始转向，并到达了P2,但是模拟端在P1之后依然以匀速运动在做插值，导致P2的位置通知到模拟端时其位置已经到达了P3，由于位置差异过大需要开启转向修正到P2。所以此时的主控端蓝色路径与模拟端的橙色路径就出现了非常大的差异：

dead reckoning fail

这种大规模偏差的根本来源在于外插值，因为外插值等同于模拟端对主控端的⾏为预测。在同步数据到达前，主控端的⾏为主动或被动的改变，就会带来模拟端的错误结果。为了让外插值尽可能的准确，游戏行业又提出了输入缓冲的概念。主控端负责维护一个输入队列，每次接收到按键输入时都将移动输入放到这个队列中，同时将这个输入推送到服务器让其广播到所有的模拟端。主控端只有在队列中的输入个数大于一定值时才将队头的输入消耗掉进行模拟，而模拟端则使用接收过来的多个输入来构造多个未来位置来执行内插值:

移动输入的缓冲

但是使用这种输入缓冲的技术也会带来一定量的额外延迟，缓冲区越大则延迟越大，合适的缓冲区大小需要根据网络状态来确定。这个输入缓冲技术在知名游戏火箭联盟中使用了，他们在GDC2018上做了一下相关的分享:It IS Rocket Science! The Physics of Rocket League Detailed

延迟补偿

前面我们说的都是客户端的移动平滑技巧，这些都是表现上的优化，但是运动同步最重要的目的是为了让各种技能判定更准确更符合直觉。由于最后的技能仲裁方在于服务器，所以上述技巧只是让客户端的世界状态能够更加精确的匹配上同一时刻的服务器状态。即使当前客户端模拟的世界状态与服务器一致，并正确的向服务器汇报了其发出的子弹击中了目标，服务器也不能完全相信客户端，他需要去验证一下客户端汇报结果对不对。考虑到服务器客户端之间是有延迟的，所以当服务器收到这个子弹命中的报告时，目标可能已经离命中点挪开了一段距离，导致子弹命中失效。在这种仲裁机制下岂不是永远无法命中快速移动的目标？为了处理这种命中问题，游戏界又引入了延迟补偿(Lag compensation)技术。 所谓延迟补偿，就是服务器存储最近一段时间的多个世界状态快照，当客户端汇报其时刻t击中了目标A之后，服务器从快照中选取离时刻t时间差异最小的快照，找到其中A的位置，检查一下此时子弹是否能够击中。

延迟补偿

上图就是起源引擎中给的延迟补偿示意图，时刻t客户端看到的目标处于上图中的红色方框位置，而对应的服务端位置为上图中的蓝色方框。当命中汇报到服务器时，目标玩家已经移动到左侧了。此时服务器获取时刻t的快照，发现目标玩家此时的红色蓝色模型框可以被子弹正确的击中，于是对这个击中执行确认，并广播到所有客户端。

但是这个延迟补偿也会引发一些异常的结果，例如客户端A的玩家已经躲进掩体但是服务端后续告知其被客户端B的玩家在之前就击中了，因为玩家B的延迟比较高，所以执行击中判定延迟补偿的时候就会把A拉回比较古老的一个时间点。

在火箭联盟的GDC分享中也提到了延迟补偿带来的问题，如下图所示有一个圆形的球从上往下运动，左侧有200ms延迟的蓝色客户端朝右运动，右侧10ms延迟的客户端朝左运动：

延迟补偿失败

在后续的某个时候低延迟客户端撞到了小球并通知了服务器，服务器也验证通过了：

延迟补偿失败2

再过一段时间高延迟客户端也汇报其撞击到了小球，服务器启用延迟补偿发现也撞到了：

延迟补偿失败3

这样就发生了一次时间倒流。 假如撞击小球即可得分的话，服务端会给两个撞击都加分。只是加分的话带来的游戏体验还不至于很糟，如果撞击会导致小球运动受改变的话，此时在右侧客户端里就会发现这个球瞬移到右上方并向右侧移动。

这些由延迟补偿触发的错误数不胜数，所以实际的游戏中要谨慎使用。