网络游戏同步问题
文章是我转载的，没找到原作者地址。
介绍
作为一个程序，你想过网络多人对战游戏是怎么做出来的吗？
从外行的角度来看多人对战游戏是很神奇的：2个或者更多的玩家在同一个时间经历了相似的游戏经历，感觉他们就像在同一个虚拟世界中游戏一样。但是作为程序员我们却知道事实并不是他们想象的那样的，他们看到的绝大多数其实都是假象。他们所认为玩家间同时经历的很多事件其实只是一种逼真的模拟。不同玩家间或多或少会存在不同步，程序员就是让这些不同步在玩家眼中变得同步起来。 by rellikt
P2P的回合类通信游戏
最开始的时候游戏的网络拓扑模型是P2P结构的，所有的机器都是P2P网络中等价的节点，他们互相发送需要的信息，不需要任何中转。这种网络拓扑模型在很多RTS游戏中还很常见，甚至很多程序员在思考网络的时候第一个想到的模型就是这个模型，因为这个模型和我们平时人与人间的交流模型的确很像。by rellikt
这个模型的基础思路是把游戏抽象成为一轮一轮的回合，在每个回合中把所有的输入转换成一个个指令，然后在每个回合的开始时候处理这些指令，这些指令导致的行为自然会推动游戏状态机的运行。我们在一个类似SC的RTS中最常见的指令会有：移动，攻击，建筑等。选用这个模型的话，我们只要保证所有的用户都有相同的指令集，并且他们的初始状态相同就不会有问题了。
以上这段介绍对于一个类似SC1的RTS游戏的网络模块来说，可能有点太过于简单了。事实上我也只是说了个大概的概念，如果你有兴趣可以参考这篇介绍帝国时代的论文。
以上提到的网络拓扑模型看上去的确是简单实用，但是同时这个模型的简单也带来了以下的一些限制：
这个模型的在可重演性上是要求相当高的：因为我们只负责指令的同步，不负责指令具体运行结果的同步，我们很可能会发现因为一个步兵在寻路的时候稍微走的有点不一样的地方，就导致了一场战斗的结果大不相同。而这样情况导致的蝴蝶效应已经足够让我们游戏体验崩溃了。 by rellikt
这个模型的第二个缺点就是必须保证在一回合开始的时候，所有玩家的指令都已经到齐，不然这回合的指令就无法开始模拟。这就是说，所有玩家的延迟其实是取决于延迟最大的玩家的延迟。RTS为了解决这个问题，通常会设置一些前摇动画和音乐来让玩家以为指令已经开始模拟了，但是实际上真正指令开始模拟的时间肯定是会和玩家输入时间有延迟的。这些伪装对玩家很好的掩盖了这点。
这个模型的最后一个缺点就是玩家必须从一开始就加入游戏。也就是说通常这里游戏的模式是在大厅中开一个房间，然后玩家加入游戏开始玩，这种模式不会允许玩家中途加入。虽然把从开始到中途加入这段时间的指令存起来，然后让想加入的玩家进行模拟，然后再加入是一种在理论上可行的解决方案，但是这个方案牵涉到的问题对游戏中的可预测性，可同步性的要求非常高，另外指令多了模拟时间也是问题，至少现在还没看到哪个这类模型的游戏做出了类似的尝试。 by rellikt
尽管我们上面提到的这个模型有种种令人不满意的缺点，但是在现实中的RTS游戏(比如星际1，红警1，帝国1)里面基本都采用了这个模型，因为这类游戏中我们会操作成千上万的单位，要一个个的去同步每个单位的状态是不科学的，我们只能去同步指令，然后通过指令去同步游戏，推动游戏状态机的正常运行。
事实上在最新的RTS游戏中可能已经抛弃了P2P模式，但是回合类通信的概念还是会得到保留，否则是无法完成成千上万个单位的同步的。
但是时代在进步，游戏的类型也是千差万别的。原始的P2P的回合制在现代的很多其他类型游戏中已经基本被抛弃了。接下来我们来看看在Unreal，Quake，Doom中引入的FPS游戏的网络模型吧。
客户端/服务器端模型（C/S）
在最初的Quake游戏中，Doom采用的也是P2P的回合制通信模型，结果发现除了局域网低延迟高带宽的情况，其他的情况下游戏性都不能让人满意。by rellikt
事实上，玩家的确可以通过虚拟局域网的软件来模拟局域网，然后通过局域网的模式进行连接。但是连接的情况实在是很悲催。那些用蜘蛛网上网的玩家就不提了（14.4kbps PPP connection或28.8kbps猫上网）。他们肯定是最杯具的。就是有宽带的玩家也不见得能好到那里去。因为P2P模型带来的高延迟在FPS类游戏中是无法被很好的掩盖的，对玩家输入的正式模拟必须等到所有玩家的指令到达以后才能处理，也就是说你的延迟取决于当前玩家中延迟最烂的那个，如果说你的队友中有300ms延迟的，那么你点一下射击键，就得过300ms以后才才会做出射击模拟。这样的情况让很多网络不好的玩家只能望洋兴叹了。
为了让更多网络不好的玩家也能正常的玩。1996年，John Carmack在推出Quake的时候使用了C/S架构取代掉了传统的P2P架构。C/S架构和P2P架构不同，P2P在每个客户端都会运行游戏逻辑，游戏显示等完整的游戏，因此P2P对于游戏的可重演性要求是相当高的。C/S架构的概念就是在服务器端跑所有的游戏逻辑和输入响应，在客户端只跑所有的游戏显示，这样的话客户端只需要把自己需要的一些状态同步下来，把用户输入发给服务器端，然后显示结果就可以了。 by rellikt
拿传统的FPS来说，理想的C/S结构中，客户端只需要发送自己的输入比如移动，转身，开火给服务器端，然后再从服务器端把自己和周围可见玩家的位置，朝向，动画状态等信息同步下来，做一下合理的插值，使其各个角色看起来足够流畅，然后显示出来。一个基本C/S架构的FPS就完成了。
比较一下上面两个模型，我们发现C/S架构最大的优点就是把延迟从最卡的玩家的延迟改变为和服务器连接的延迟。另外使用这个架构中途加入玩家的概念也很容易就能实现了。最后在发包上面来说，在带宽上的要求也低了不少。只需要把输入发给服务器端就够了。
但是纯理想的C/S模型还是有不足的地方，那就是延迟，FPS对于延迟的要求是相当高的，互联网上两个端点间的lag有300ms是很正常的，如果说一个转身指令要等300ms以后才能响应的话，以9s/m跑步的速度来算，玩家就已经跑出将近3m了，也许早就掉到沟里面去了。
为了让更多使用烂网络的玩家能够加入到游戏中，John Carmark在推出Quake的时候也引入了客户端预测的新技术。by rellikt
客户端预测
其实在早期的FPS游戏中，我们的确会碰到按一个键要等半天才能反应的情况，而这个时间就是和你的网络延迟有关的，有些强的玩家甚至能够适应这种情况，提前做出预判操作。但是在现代的FPS游戏比如COD等游戏中，你已经再也不会有这种体验了，那我们现代的FPS游戏是用什么手段来移除这些延迟的呢？
这部分的技术一般分两块：客户端预测和延迟补偿。这些技术在Unreal引擎中的网络部分中都有介绍。这里我们着重先讨论一下关于客户端预测的概念。
John Carmack在推出Quake的时候提到：我会在新的Quake中引入客户端预测的概念，也就是说客户端不只是简单做一些同步和显示。他们还会做预测，也就是说在得到服务器端数据之前，客户端就会预先对输入的结果做预测并且预测其他可见玩家的行动，并且立即进行显示，这会使得现在的客户端需要物理，游戏逻辑在本地运行。原本完美的C/S模型在这里就显得不那么完美，但是还是让我们面对现实吧，现实本来就不完美。by rellikt
我们现在的情况就是客户端在接受到本地输入以后会直接运行一部分的游戏逻辑代码，对用户状态进行判断，然后进行模拟，再显示出来，客户端不会等到服务器端的数据到达以后再进行模拟了，这样说来对客户端来说延迟已经不存在了。
但对于客户端预测来说，重点其实不在预测上，而是在同步上。我们只需要使用相同的代码，预测自然就不会有问题了。但是当服务器和客户端对于结果出现分歧的时候怎么同步就是一个大问题了。
谈到这里你就会想，如果说客户端已经预测了游戏的进程，为什么不让服务器端去同步客户端的结果呢？这样的方案看上去是不错的，但是附带而来的作弊问题却是很严重的，如果服务器不进行模拟，而是简单的同步玩家状态，那么瞬移，无敌等外挂就会很常见了。玩家只需要模拟这些，发出对应的包就可以了。现在流行的许多MMORPG中的外挂就是这种同步而产生的结果。事实上由于对于服务器性能上的考虑，MMO中往往只会最简单同步一些状态信息和事件信息。 by rellikt
因此在Unreal的实现中Tim Sweency决定让服务器和客户端分别模拟游戏，来实现用户端预测来消除延迟。Tim Sweency在Unreal Networking Architecture中写道“The Server is The Man”.
既然这样的话，我们很容易想到一个有趣的问题。我们的原则是用户状态以服务器模拟为准，客户端必须即时同步服务器上的状态，使自己的行为和服务器上的一致。现在的问题是：由于延迟是客观存在的，所以服务器上的数据总是比客户端的要慢。事实上客户端能够同步到的数据只能是ping值（数据包在客户端和服务器端一个来回的时间）以前那个时间点的数据。
如果客户端只是简单同步当前获得的服务器端的数据，那么结果就是，客户端会把ping值以前的状态给同步回来，而做出的修改就正好是我们要做的客户端预测的那部分，如果真的这么做，那么我们的客户端预测就完全是无意义的存在了。by rellikt
这里Tim Sweency采用的方法是采用两个环形的缓冲，一个记录客户端的状态，我们称其为状态缓冲，一个记录客户端的操作，我们称其为操作缓冲，这两个缓冲的长度应该长到至少可以容纳ping值这段时间的状态和操作。我们每过一个固定的时间把客户端状态写入状态缓冲，每个操作都会被写入操作缓冲。当服务器端同步来的数据到达客户端以后，我们先提取这个服务器端数据所带时间点，然后把这个时间点以前的数据从客户端的两个缓冲缓冲中释放掉，然后再把状态缓冲中最接近的那个时间点状态数据提取出来，从那个状态开始用操作缓冲中存的操作数据进行操作模拟，最后得到现在的状态，再用得到的这个状态来进行插值，同步。事实上在客户端为了消除延迟我们一直在进行回滚然后重演的过程，这个ping值越大，我们需要回滚和重演的时间就越多，同时在得出的新状态中可能需要插值和同步的幅度也会越大。
Unreal中就是这么处理延迟的，这个技巧运用得当的话，可以很有效的把延迟给掩盖掉。Tim Sweency在Unreal的白皮书中说，如果我们的游戏的可重演性越好，我们需要的插值就越少，甚至在其他客户端和环境变量不变的情况下，我们是几乎不需要任何的插值和修改的。事实上在Unreal中，往往只有撞上敌人或者被火箭弹打飞了才会用到插值修改。
换句话来说只要不涉及到其他玩家的操作或者有人作弊，那么我们采用的客户端预测往往是很准确的。by rellikt
结论
关于客户端预测我现在只想谈这么多了。如果下期有时间我会再写一些关于延迟补偿的概念或者在本文中直接修改。就是延迟补偿技术的存在，是用户能在延迟的情况下照样弹无虚发，体验不到延迟的感觉
有关位置同步的方案实际上已经比较成熟，网上也有比较多的资料可供参考。在《带宽限制下的视觉实体属性传播》一文中，作者也简单提到了位置同步方案的构造过程，但涉及到细节的地方没有深入，这里专门针对这一主题做些回顾。
最直接的同步方案就是客户端在每次发生位置改变时都向服务器报告 ，服务器再转发给周围的其他玩家，其他客户端将对应的游戏实体移动到新的位置上。
但是这样存在一个问题，每个玩家的位置都是自己先开始移动，一段时间之后才在其他玩家的客户端上表现出来。如果只是希望每个客户端上看到的游戏对象都同时开始移动，那可以让玩家的每一步操作都由服务器确认之后再执行，这样误差将缩减到不同客户端之间的网络延时差。但是显然的，这样的做法不可能真正被采用，因为这将使得玩家的游戏体验非常的糟糕。有谁能忍受连每走一步路都要卡一下的游戏呢？
既然一定存在先后时间差，那需要一种方法来让不同客户端上看到的玩家位置不至于有太大的误差，尤其是不能有影响到游戏公平性的误差存在。根据误差出现的直接原因：时间差，我们应该能够想到一个解决方案，那就是让其他客户端设法弥补掉这段时间差内少走的距离。这样的话也就要求我们的消息包中多带一个开始移动的时间数据，用于其他客户端在收到这个消息包时计算对应的玩家实体已经移动过的时间和距离。
我们以一个实际的例子来说明如何减少这种误差的影响。假设玩家A以速度V从P1点去到P2点，A的网络延时为T1，在A旁边有个玩家B，他的网络延时为T2.B收到服务器转发过来的移动包时，A在其自己的客户端上已经移动了T1+T2的时间，在这段时间内他自己已经走过了V*（T1+T2）的距离。如果这时在B的客户端上开始将实体A从P1移动到P2，那显然两个客户端上看到的A的位置始终存在V*（T1+T2）的误差。
为了使A在B客户端上显示的位置与其实际位置的误差尽可能的缩小，一个简单的做法是直接将A的位置向前拖V*（T1+T2）然后开始移动，这样两者之间的误差便消除了。但这样会使得客户端的显示太鲁莽，要让其看起来平滑一些，我们可以考虑使用一些算法，比如计算出A从当前位置走到P2点还需要的时间，然后加快其速度使其在规定的时间内到达P2点，这样A和B看到的最终时间是相同的，但中间过程还是存在较多误差。另一种较好的做法是先让A以一个可接受的较快速度移动到其当前应该所在的位置稍前一点的地方，然后以正常速度移动到P2点，这样后面的移动情况与其实际移动情况基本吻合了。
看起来这个方案很完美，但是这里却忽略了一个问题：我们假设的是每次移动时都知道玩家要去的确切位置。这在靠鼠标点击来移动的2D游戏中是正好合适的，但是在WOW一类的靠键盘来移动的3D游戏中却没有办法采用。WOW中的移动消息都只能向服务器报告当前的坐标及朝向信息。
这类移动的位置同步其实也可以采用类似方案，服务器将移动玩家的当前位置信息广播给周围的其他玩家，当然其中也包含了时间戳。当其他玩家收到这个移动包后，表示的是在过去的某个时间里该玩家移动到了这个位置。如果只是简单地将其对应的实体移动到这个位置，那同样的，也存在位置误差。
与上一种情况类似，如果我们知道该玩家的移动速度，再通过数据包中的时间戳，假设该玩家还在以相同的速度朝相同的方向移动，那我们也可以预测出该玩家从开始移动到现在这段时间内他走了多远了距离。我们也可以将其位置做适当的修正，并使其继续移动下去。
我们需要先停下来考虑一下这些算法的部分细节。其中出现了一些数据是否应该包含在我们的每个消息包中，也就是我们需要考虑的另外一个问题：移动同步的消息中应该包含哪些数据，以及这些数据到底应该向哪些玩家广播。
对于2D游戏的情况来说，我们的算法需要的数据有：玩家的速度V，玩家开始移动的时间T0，收到数据包的时间T1，玩家当前位置P1和玩家要去的位置P2.T1和P1从当前客户端上都可以取到，而速度V一般来说不会经常改变，至少不是每次移动时都不一样，所以我们可以为速度的改变设计单独的消息码，这样V值也是可以在客户端上取到的。最后，每个移动消息中包含的数据只需要有移动到的位置P2和开始移动的时间T0.
其他客户端在使用特定算法将玩家移动到P2后会将其停在此处，直到收到下一个移动包时再开始移动。而对于在移动过程中又收到了新的移动包的处理过程基本类似，不做过多描述。
对于3D游戏的情况，算法是基本相同的，但是没有目标点，替换为移动方向，比如是向正前方移动，还是向左或向右移动等。在这种情况下，只要没有收到玩家停止移动的消息，其他客户端上都会以最后一次收到的移动包的状态来继续模拟移动。
所以，在网络偶尔卡一下的时候也会出现一些奇怪的现象。比如WOW中，看到队友直冲冲地走下了悬崖，你刚喊了句“怎么掉下去了？”只见队友又从身后走出来，还冒出一句：“没啊，我就在你旁边！”
关于数据要向哪些人广播的问题，其实很简单，哪些人会看到这个玩家就需要向哪些人广播。不管是直接在主屏幕上看到还是在大地图上看到的代表其位置的一个点。但是，针对不同的人使用的广播策略还是存在差异。
在《带宽限制下的视觉实体属性传播》一文中提出了一个方案很值得参考。该方案提出的基础是因为3D空间透视的原因，离你很远的一个玩家移动了10米，最终在你的显示器上看到的位移可能只有一个象素；而离你不到一米的一个玩家虽然只移动了一米，但最终显示出来的位移可能会有几十个象素。所以，远处玩家的移动并不需要非常严格的关注，但近处玩家的移动同步需要非常高的优先级。
这个方案的实现还依赖于另一项技术要求，玩家的属性更新以一定的频率来进行，更新时比较一下当前属性值与上次更新时的属性值，如果存在差异则通知客户端更新，另外如果中间跳过了某次更新也不会对客户端表现及游戏公平性造成什么影响。比如这里要处理的玩家坐标，第一次移动到A点，第二次从A点又移动到B点，如果移动到A点的更新包没有发送，直接发送了移动到B点的更新包，这将不会对游戏逻辑产生大的影响。
这套方案基本上是为3D游戏的实体属性广播优化而设计的，在2D游戏中很难使用。一是斜45度视角的2D游戏中屏幕顶端、中间和底部任何一个位置上的玩家移动，其距离和象素比是完全相同的，因为画面不存在透视，所以也就没有远处对象更新频率低这一可能。另外2D游戏中的移动与3D游戏也存在差异，具体情况前面有详细描述，2D游戏中基本上每一次移动都需要广播，不能跳过哪一个，否则玩家看到的现象就是在乱跑，这也必将影响到技能的使用等游戏逻辑。
有关位置同步所涉及到的一些技术细节及优化方案上面描述了一部分，但是在实际的应用中是否会使用还是要看具体游戏的需求。比如大话类型的游戏，其本身对位置的精确同步就没有要求，两个客户端上出现一前一后的移动也不会影响任何的游戏逻辑，所以前面提到的同步方案可能都用不上。
而对于一些同步要求很高的游戏，如WOW中盗贼这类职业的需求，上面的方案可能还不够细致，还需要设计更加有效的同步方案。
另外，在位置同步过程中还有一个不容忽视的问题是外挂。我们不能像WOW那样完全依赖客户端，如果没有暴雪那样强硬的封号措施，游戏也就成为了外挂们的温床。所以，如何在服务器端模拟每个客户端的移动，如何检测出客户端是否存在作弊行为，也是需要重点关注的一个问题。
欢迎转载，转载请标明出处： http://www.jianshu.com/p/b4afda371729
