影子跟随算法之FPS游戏中游戏同步性的实现
延迟补偿与坐标差值问题
在网络游戏中，延迟补偿是一个关键问题。例如，B客户端屏幕上显示A已经跑到东边了，但收到服务器消息称“A正在西边往北跑”，此时B客户端该如何处理呢？下面将介绍一种多年前实现的算法——影子跟随算法，它能简明扼要地解决此类问题。
影子跟随算法概述
影子跟随算法由普通DR（dead reckoning）算法发展而来。之所以将其称为“影子跟随”，是为了体现该算法同步策略的主要思想：屏幕上显示的实体（entity）会不断追逐它的“影子”（shadow）。
具体流程如下：
- 服务器向各客户端发送各个影子的状态改变信息，包括坐标、方向、速度和时间。
- 各个客户端收到信息后，按照当前情况重新插值修正影子状态。
- 影子状态是跳变的，但实体追赶影子的过程是连续的，因此整个过程显得平滑。
算法示例说明
假设有两个终端，前面的1号终端控制红色飞船P1向左飞，并将自身状态实时告知服务器。后面的2号终端接收到飞船P1的影子S1的状态（向左移动），然后让P1的实体追赶S1。
网络性能对实时游戏有着重要影响，其中带宽限制了实时游戏的人数容量，而延时则决定了实时游戏的最低反应时间。使用影子跟随算法可以轻松开发出如马里奥赛车或Counter Strike等游戏，下面详细介绍。
算法比较
帧间同步
不同客户端每帧显示相同的内容，键盘/时钟数据会传到服务器，服务器确认后所有终端做出响应。这种方式多用于局域网游戏，如红警（需要等待客户端）、街霸II的网络版（360）。可参考LockStep、TimeWrap算法，其网速要求高，但复杂度低，具体可查看旧文帧锁定算法。
插值同步
不同客户端显示不同步，但状态同步，常见的Dead Reckoning（或叫导航插值）就属于此类。该方法效果好，但复杂度高，常见于竞速类游戏和FPS游戏。
算法定义
时间
单位为帧（FPS = 10），开始时由服务器告知所有客户端，每5分钟进行一次同步。
玩家
每个玩家控制自己的实体，并在每一帧将状态改变告知服务器。
状态
状态数据包括实体ID、坐标、方向、速度和时间（帧）。
插值
收到新状态包后，根据其运动方向与时间，结合现有时间计算新状态。
跟随
实体持续追踪自己的影子，追上后与影子保持状态同步。
相位滞后
这是一个可选参数，实体与影子保持一定距离同步，类似于保持一定车距。这样在控制者突然停止时，可避免因网络延迟导致实体跑过了又被拉回来。
惯性移动
同样是可选参数，实体开始移动、停止或改变方向时都有加速度，使用该参数后可能就不需要相位滞后了。
由于网络延迟，每次服务器向各个客户端同步时间时，所有客户端的时间都会慢于服务器。但只要大家在一定误差范围内以相同的速度增加，就不会影响游戏。
网络延迟与同步问题
在公网平均130ms的Latency下，不存在“完全的”同步情况。要将用户带入快速的交互式实时游戏中，体验完美的互动娱乐，就需要消除或隐藏延时。
虽然让所有用户屏幕上呈现完全不同的表象是可行的，将这些不同表象融合在一个统一的逻辑中也是可行的，但需要根据具体情况，分清哪些问题值得解决，哪些可以忽略，弄清楚实时游戏中同步问题的关键所在，巧妙化解与规避问题，最终在适合普遍用户网络环境（200ms）中实现实时快速互动游戏。
案例解析
Counter Strike
- 惯性处理：为人物移动加上惯性，例如静止状态突然开始移动，需要0.5 - 1秒的加速过程；移动中突然停止也需要0.5 - 1秒的减速过程。这样可以实现无差别同步，无需相位滞后来避免拉扯影响用户体验。
- 开枪射击判断：开枪射击采用客户端判断。如果玩家看见对方在墙前面，开枪射中后向服务器发送“我击中你了”。此时可能真实的对方在墙后，表现为玩家看见自己打中对方（减不减血由服务器判断），而对方没看见玩家，觉得玩家穿墙打中了自己。
- 关键状态缓存：需要对关键状态进行缓存。如果别人向前连续跳五次，若每次取得状态都取到最高点，别人客户端上的影子和跟随的实体会奇怪地持续飞在天上。因此，需要将起跳和落地这两个关键状态缓存，实体追赶时只有追上第一个状态（一号影子）才能追逐第二个状态（二号影子）。
通过以上处理，在完全时间同步的情况下可以实现平滑的跑动、跳跃，开枪射击采用客户端判断后手感得到提高。不过，需要注意外挂问题，可通过Cheating Death等工具进行防范。
马里奥赛车
- 惯性使用：用该算法实现马里奥赛车很简单，影子和实体都使用惯性。由于赛车惯性大，不容易有突变的状态更新，所以效果会比FPS游戏更好。
- 道具处理：玩家碰到道具后，马上在屏幕上隐藏该道具的显示并通知服务器，由服务器决断道具归属。由于刚碰到道具就隐藏，不会出现碰到道具却在一段时间内无法取得的延迟现象。
- 道具系统实现：游戏道具系统实现较为容易。例如将当前第一名炸毁的道具，其描述为原角色 + 对象角色 + 约定发生时间。知道对象是谁以及什么时间发生，就无需过多同步，所有客户端和服务器在该时间让炸弹爆炸即可，这种手法类似即时战略游戏。
- 发射物同步：对于可以发射的乌龟壳这类有弹道的发射物，类似Quake里面的某些武器，需要进行同步处理。基本特性是服务器判断起决定作用，客户端同步判断。如果客户端与服务器都判断击中，那就判定击中；如果客户端判断击中而服务器判断没有击中，玩家会看到该角色似乎被打了一下，但很快又恢复速度向前冲。
由于赛车本身惯性大，同步效果较好，可以在更大的延迟情况下表现得和FPS差不多（如300ms效果相当于FPS的200ms）。
非可靠包处理
“影子跟随算法”支持非可靠传输协议。如果使用非可靠传输，可按照特定频率（如每秒10次）定时发送状态更新。因为协议中每个更新包除了位置外，还包含速度、方向和时间，甚至加速度，所以丢一个包没有关系，可以根据后来的包重新计算插值。只有关键状态更新时才需要可靠传输，这样可以避免TCP中丢包时RTO指数增长造成的延迟。
负面情况
该算法的缺点是无法像“帧间同步”算法那样，每次发送按键给服务器，服务器处理后再反馈结果。在局域网中（平均延迟 < 5ms），“帧间同步”效果相当于单机游戏一样即时，游戏性也能更复杂。而在Internet中（平均延迟130ms，设计基准200ms，每秒最多发送10个数据包），影子跟随算法难以实现像单机游戏那样复杂的场景互动和即时的动作判定。
许多策划在设计实时动作游戏时提出的很多设计难以实现，因为策划不容易明白哪些可以实现，哪些无法实现。即便程序员精通同步理论，策划也经常会遇到问题。当多数设计被程序员回复“无法实现”后，策划只能采取消极设计（砍掉很多有意思的互动元素），导致网络游戏的表现力至今仍远不如单机游戏。而且，大于100ms的判定时间很难做到即时。
此外，该算法编码复杂度比其他同步策略高。服务器需要计算一份影子数据，各个客户端也需要计算一份影子数据，还需要计算实体追赶，并且这三种计算都需要在相同的时钟下保持一致，这增加了编码与调试的难度。
总结
Internet的特点是“高带宽，高延迟”，从本质上说它并非为游戏而设计，因此Internet中绝对意义的同步是不存在的。“影子跟随算法”的核心思想包括时钟同步、客户端先行、平滑追赶。通过这三个特性，能够在近似时间同步的情况下，模拟各种物体的移动过程。
使用该算法的前提是设计者需要根据各个游戏的特性研究不同的优化技巧，策略因游戏而异。例如：
- 发送状态更新包时，不需要每次都发送，当客户端实体与自己的影子之间的误差大于某特定数值时才发送更新包。这样，玩家在原地做左右摇摆的小幅度移动，只要未超出范围，就无需发送新的状态更新，其他玩家机器上看起来该玩家是站着不动的。
- 当发现某客户端5秒钟没有响应时，将该人物的影子冻结，避免为了等待某个数据而影响游戏进行。
- 本算法需要客户端与服务器维护相同的时钟，每5分钟同步时，直接根据服务器的时钟替换当前时钟，无需重新计算所有影子的位置，因为后续的状态数据会马上刷新这些状态，也无需考虑测量到的PING值，该算法与PING具体值无关。
- 当发现策划案子不可行时，寻找近似替代方案，如减少“一次性的”“决定性的”事件发生，延长导弹在空中飞行的时间，将敌人加入HP分多次打死，而非一击毙命等。