为什么这个网络游戏同步算法一段时间以后就不同步了?
[问题点数：30分，结帖人u]
为什么这个网络游戏同步算法一段时间以后就不同步了?
[问题点数：30分，结帖人u]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
2014年11月 VC/MFC大版内专家分月排行榜第三
匿名用户不能发表回复！|
每天回帖即可获得10分可用分！小技巧：
你还可以输入10000个字符
(Ctrl+Enter)
请遵守CSDN，不得违反国家法律法规。
转载文章请注明出自“CSDN（www.csdn.net）”。如是商业用途请联系原作者。网络游戏同步问题 - 博客频道 - CSDN.NET
paxhujing的博客
&&&&&&&作为一个程序，你想过网络多人对战游戏是怎么做出来的吗？
&&&&&&&从外行的角度来看多人对战游戏是很神奇的：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那样完全依赖客户端，如果没有暴雪那样强硬的封号措施，游戏也就成为了外挂们的温床。所以，如何在服务器端模拟每个客户端的移动，如何检测出客户端是否存在***行为，也是需要重点关注的一个问题。
排名：千里之外
（7）（2）（2）（4）（12）（0）（2）（1）（2）（8）（1）（2）（5）（1）（1）（0）（1）（1）小谈网络游戏同步 -
小谈网络游戏同步
　　同步在网络游戏中是非常重要的，它保证了每个玩家在屏幕上看到的东西大体是一样的。其实呢，解决同步问题的最简单的方法就是把每个玩家的动作都向其他玩家广播一遍，这里其实就存在两个问题：1，向哪些玩家广播，广播哪些消息。2，如果网络延迟怎么办。事实上呢，第一个问题是个非常简单的问题，不过之所以我提出这个问题来，是提醒大家在设计自己的消息结构的时候，需要把这个因素考虑进去。而对于第二个问题，则是一个挺麻烦的问题，大家可以来看这么个例子：
　　比如有一个玩家A向服务器发了条指令，说我现在在P1点，要去P2点。指令发出的时间是T0，服务器收到指令的时间是T1，然后向周围的玩家广播这条消息，消息的内容是“玩家A从P1到P2”有一个在A附近的玩家B，收到服务器的这则广播的消息的时间是T2，然后开始在客户端上画图，A从P1到P2点。这个时候就存在一个不同步的问题，玩家A和玩家B的屏幕上显示的画面相差了T2-T1的时间。这个时候怎么办呢？
　　有个解决方案，我给它取名叫
预测拉扯，虽然有些怪异了点，不过基本上大家也能从字面上来理解它的意思。要解决这个问题，首先要定义一个值叫：预测误差。然后需要在服务器端每个玩家连接的类里面加一项属性，叫TimeModified，然后在玩家登陆的时候，对客户端的时间和服务器的时间进行比较，得出来的差值保存在TimeModified里面。还是上面的那个例子，服务器广播消息的时候，就根据要广播对象的TimeModified，计算出一个客户端的CurrentTime，然后在消息头里面包含这个CurrentTime，然后再进行广播。并且同时在玩家A的客户端本地建立一个队列，保存该条消息，只到获得服务器验证就从未被验证的消息队列里面将该消息删除，如果验证失败，则会被拉扯回P1点。然后当玩家B收到了服务器发过来的消息“玩家A从P1到P2”这个时候就检查消息里面服务器发出的时间和本地时间做比较，如果大于定义的预测误差，就算出在T2这个时间，玩家A的屏幕上走到的地点P3，然后把玩家B屏幕上的玩家A直接拉扯到P3，再继续走下去，这样就能保证同步。更进一步，为了保证客户端运行起来更加smooth，我并不推荐直接把玩家拉扯过去，而是算出P3偏后的一点P4，然后用(P4-P1)/T(P4-P3)来算出一个很快的速度S，然后让玩家A用速度S快速移动到P4，这样的处理方法是比较合理的，这种解决方案的原形在国际上被称为（Full
plesiochronous），当然，该原形被我篡改了很多来适应网络游戏的同步，所以而变成所谓的：预测拉扯。
　　另外一个解决方案，我给它取名叫
验证同步，听名字也知道，大体的意思就是每条指令在经过服务器验证通过了以后再执行动作。具体的思路如下：首先也需要在每个玩家连接类型里面定义一个TimeModified，然后在客户端响应玩家鼠标行走的同时，客户端并不会先行走动，而是发一条走路的指令给服务器，然后等待服务器的验证。服务器接受到这条消息以后，进行逻辑层的验证，然后计算出需要广播的范围，包括玩家A在内，根据各个客户端不同的TimeModified生成不同的消息头，开始广播，这个时候这个玩家的走路信息就是完全同步的了。这个方法的优点是能保证各个客户端之间绝对的同步，缺点是当网络延迟比较大的时候，玩家的客户端的行为会变得比较不流畅，给玩家带来很不爽的感觉。该种解决方案的原形在国际上被称为（Hierarchical
master-slave synchronization），80年代以后被广泛应用于网络的各个领域。
　　最后一种解决方案是一种理想化的解决方案，在国际上被称为Mutual
synchronization，是一种对未来网络的前景的良好预测出来的解决方案。这里之所以要提这个方案，并不是说我们已经完全的实现了这种方案，而只是在网络游戏领域的某些方面应用到这种方案的某些思想。我对该种方案取名为：半服务器同步。大体的设计思路如下：
　　首先客户端需要在登陆世界的时候建立很多张广播列表，这些列表在客户端后台和服务器要进行不及时同步，之所以要建立多张列表，是因为要广播的类型是不止一种的，比如说有local
message,有remote message,还有global message
等等，这些列表都需要在客户端登陆的时候根据服务器发过来的消息建立好。在建立列表的同时，还需要获得每个列表中广播对象的TimeModified，并且要维护一张完整的用户状态列表在后台，也是不及时的和服务器进行同步，根据本地的用户状态表，可以做到一部分决策由客户端自己来决定，当客户端发送这部分决策的时候，则直接将最终决策发送到各个广播列表里面的客户端，并对其时间进行校对，保证每个客户端在收到的消息的时间是和根据本地时间进行校对过的。那么再采用预测拉扯中提到过的计算提前量，提高速度行走过去的方法，将会使同步变得非常的smooth。该方案的优点是不通过服务器，客户端自己之间进行同步，大大的降低了由于网络延迟而带来的误差，并且由于大部分决策都可以由客户端来做，也大大的降低了服务器的资源。由此带来的弊端就是由于消息和决策权都放在客户端本地，所以给外挂提供了很大的可乘之机。
　　综合以上三种关于网络同步派系的优缺点，综合出一套关于网络游戏传输同步的较完整的解决方案，我称它为综合同步法（colligate
synchronization）。大体设计思路如下：
　　首先将服务器需要同步的所有消息从划分一个优先等级，然后按照3/4的比例划分出重要消息和非重要消息，对于非重要消息，把决策权放在客户端，在客户端逻辑上建立相关的决策机构和各种消息缓存区，以及相关的消息缓存区管理机构，如下图所示：
　　上图简单说明了对于非重要消息，客户端的大体处理流程，其中有一个客户端被动行为值得大家注意，其中包括对服务器发过来的某些验证代码做返回，来确保消息缓存中的消息和服务器端是一致的，从而有效的防止外挂来篡改本地消息缓存。其中的消息来源是包括本地的客户端响应玩家的消息以及远程服务器传递过来的消息。
　　对于重要消息，比如说战斗或者是某些牵扯到玩家一些比较敏感数据的操作，则采用另外一套方案，该方案首先需要在服务器和客户端之间建立一套Ping
System，然后服务器保存和用户的及时的ping值，当ping比较小的时候，响应玩家消息的同时先不进行动作，而是先把该消息反馈给服务器，并且阻塞，服务器收到该消息，进行逻辑验证之后向所有该详细广播的有效对象进行广播（包括消息发起者），然后客户端收到该消息的验证，才开始执行动作。而当ping比较大的时候，客户端响应玩家消息的同时立刻进行动作，并且同时把该消息反馈给服务器，值得注意的是这个时候还需要在本地建立一个无验证消息的队列，把该消息入队，执行动作的同时等待服务器的验证，还需要保存当前状态。服务器收到客户端的请求后，进行逻辑验证，并把消息反馈到各个客户端，带上各个客户端校对过的本地时间。如果验证通过不过，则通知消息发起者，该消息验证失败，然后客户端自动把已经在进行中的动作取消，恢复原来状态。如果验证通过，则广播到的各个客户端根据从服务器获得校对时间进行对其进行拉扯，保证在该行为完成之前完成同步。
　　至此，一个比较成熟的网络游戏的同步机制已经初步建立起来了，接下来的逻辑代码就根据各自不同的游戏风格以及侧重点来写了。
　　同步是网络游戏最重要的问题，如何同步也牵扯到各个方面的问题，比如说游戏的规模，游戏的类型以及各种各样的方面，对于规模比较大的游戏，在同步方面可以下很多的工夫，把消息分得十分的细腻，对于不同的消息采用不同的同步机制，而对于规模比较小的游戏，则可以采用大体上一样的同步机制，究竟怎么样同步，没有个定式，是需要根据自己的不同情况来做出不同的同步决策的
网游同步算法之导航推测（Dead Reckoning）算法：
　　在了解该算法前，我们先来谈谈该算法的一些背景资料。大家都知道，在网络传输的时候，延迟现象是很普遍的，而在基于Server/Client结构下的网络游戏的同步也就成了很头疼的问题，在保证客户端响应用户本地指令流畅的情况下，没法有效的保证的同步的及时性。同样，在军方也有类似的事情发生，即使是同一LAN里面的机器，也会因为传输的延迟，导致一些运算的失误，介于此，美国国防部投入了大量的资金用于研究一种比较的好的方案来解决分布式系统中的延迟问题，特别是一个叫分布式模拟运动（Distributed
Interactive Simulation）的系统，这套系统呢，其中就提出了一套号称是Latency Hiding & Bandwidth
Reduction的方案，命名为Dead
Reckoning。呵呵，来头很大吧，恩，那么我们下面就来看看这套系统的一些观点，以及我们如何把它运用到我们的网络游戏的同步中。
　　首先，这套同步方案是基于我那篇《网络游戏的同步》一文中的Mutual
Synchronization同步方案的，也就是说，它并不是Server/Client结构的，而是基于客户端之间的同步的。下面我们先来说一些本文中将用到的名词概念：
　　网状网络：客户端之间构成的网络
　　节点：网状网络中的每个客户端
　　极限误差：进行同步的时候可能产生的误差的极值
　　恩，在探讨其原理的之前，我们先来看看我们需要一个什么样的环境。首先，需要一个网状网络，网状网络如何构成呢？当有新节点进入的时候，通知该网络里面的所有节点，各节点为该客户端在本地创建一个副本，登出的时候，则通知所有节点销毁本地关于该节点的副本。然后每个节点该保存一些什么数据呢？首先有一个很重要的包需要保存，叫做协议数据包（PDU
Protocol Data
Unit），PDU包含节点的一些相关的运动信息，比如当前位置，速度，运动方向，或者还有加速度等一些信息。除PDU之外，还有其他信息需要保存，比如说节点客户端人物的HP，MP之类的。然后，保证每个节点在最少8秒之内要向其它节点广播一次PDU信息。最后，设置一个极限误差值。到此，其环境就算搭建完成了。下面，我们就来看看相关的具体算法：
　　假设在节点A有一个小人（路人甲），开始跑路了，这个时候，就像所有的节点广播一次他的PDU信息，包括：速度（S），方向（O），加速度（A）。那么所有的节点就开始模拟路人甲的运动轨迹和路线，包括节点A本身（这点很重要），同时，路人甲在某某玩家的控制下，会不时的改变一下方向，让其跑路的路线变得不是那么正规。在跑路的过程中，节点A有一个值在不停的记录着其真实坐标和在后台模拟运动的坐标的差值，当差值大于极限误差的时候，则计算出当前的速度S，方向O和速度A（算法将在后面介绍），并广播给网络中其他所有节点。其他节点在收到这条消息之后呢，就可以用一些很平滑的移动把路人甲拉扯过去，然后重新调整模拟跑路的数据，让其继续在后台模拟跑路。
　　很显然，如果极限误差定义得大了，其他节点看到的偏差就会过大，如果极限偏差定义得小了，网络带宽就会增大。如果定义这个极限误差，就该根据各种数据的重要性来设计了。如果是回合制的网络游戏，那么在走路上把极限误差定义得大些无所谓，可以减少带宽。但是如果是及时打斗的网络游戏，那么就得把极限误差定义得小一些，否则会出现某人看到某人老远把自己给砍死的情况。
Reckoning的主要算法有9种，但是只有两种是解决主要问题的，其他的基本上只是针对不同的坐标系的一些不同的算法，这里就不一一介绍了。好，那么我们下面来看传说中的最主要的两种算法：
　　　　第一：目标点 = 原点 + 速度 * 时间差
　　　　第二：目标点 = 原点 + 速度 * 时间差 + 1/2 * 加速度 * 时间差
呵呵，传说中的算法都是很经典的，虽然我们早在初中物理的时候就学过。
　　该算法的好处呢，正如它开始所说的，Latency Hiding & Bandwidth
Reduction，从原则上解决了网络延迟导致的不同步的问题，并且有效的减少了带宽，不好的地方就是该算法基本上只能使用于移动中的同步，当然，移动的同步是网络游戏中同步的最大的问题。
　　该方法结合我在《网络游戏的同步》一文中提出的综合同步法的构架可以基本上解决掉网络游戏中走路同步的问题。相关问题欢迎大家一起讨论。
有关导航推测算法（Dead Reckoning）中的平滑处理：
　　根据我上篇文章所介绍的，在节点A收到节点B新的PDU包时，如果和A本地的关于B的模拟运动的坐标不一致时，怎么样在A的屏幕上把B拽到新的PDU包所描叙的点上面去呢，上文中只提了用“很平滑的移动”把B“拉扯”过去，那么实际中应该怎么操作呢？这里介绍四种方法。
　　第一种方法，我取名叫直接拉扯法，大家听名字也知道，就是直接把B硬生生的拽到新的PDU包所描叙的坐标上去，该方法的好处是：简单。坏处是：看了以下三种方法之后你就不会用这种方法了。
　　第二种方法，叫直线行走（Linear），即让B从它的当前坐标走直线到新的PDU包所描叙的坐标，行走速度用上文中所介绍的经典算法：
　　　　目标点 = 原点 + 速度 * 时间差 + 1/2 * 加速度 * 时间差算出：
　　首先算出从当前坐标到PDU包中描叙的坐标所需要的时间：
　　　　T = Dest( TargetB – OriginB ) / Speed
　　然后根据新PDU包中所描叙的坐标信息模拟计算出在时间T之后，按照新的PDU包中的运动信息所应该达到的位置：
　　　　_TargetB = NewPDU.Speed * T
　　然后根据当前模拟行动中的B和_TargetB的距离配合时间T算出一个修正过的速度_S：
　　　　_S = Dest( _TargetB – OriginB ) / T
　　然后在画面上让B以速度_S走直线到Target_B，并且在走到之后调整其速度，方向，加速度等信息为新的PDU包中所描叙的。
　　这种方法呢，非常的土，会让物体在画面上移动起来变得非常的不现实，经常会出现很生硬的拐角，而且对于经常要修改的速度_S，在玩家A的画面上，玩家B的行动会变得非常的诡异。其好处是：比第一种方法要好。
　　第三种方法，叫二次方程行走（Quadratic），该方法的原理呢，就是在直线行走的过程中，加入二次方程来计算一条曲线路径，让Dest(
_TargetB – OriginB
)的过程是一条曲线，而不是一条直线，恩，具体的实现方法，就是在Linear方法的计算中，设定一个二次方程，在Dest函数计算距离的时候根据设定的二次方程来计算，这样一来，可以使B在玩家A屏幕上的移动变得比较的有人性化一些。但是该方法的考虑也是不周全的，仅仅只考虑了TargetB到_TargetB的方向，而没有考虑新的PDU包中的方向描叙，那么从_TargetB开始模拟行走的时候，仍然是会出现比较生硬的拐角，那么下面提出的最终解决方案，将彻底解决这个问题。
　　最后一种方法叫：立方体抖动（Cubic
Splines），这个东东比较复杂，它需要四个坐标信息作为它的参数来进行运算，第一个参数Pos1是OriginB，第二个参数Pos2是OriginB在模拟运行一秒以后的位置，第三个参数Pos3是到达_TargetB前一秒的位置，第四个参数pos4是_TargetB的位置。
Struct pos {
&&& Coordinate X;
&&& Coordinate Y;
　　　Pos1 = OriginB
　　　Pos2 = OriginB + V
　　　Pos3 = _TargetB – V
　　　Pos4 = _TargetB
运动轨迹中(x, y)的坐标。
　　　x = At^3 + Bt^2 + Ct + D
　　　y = Et^3 + Ft^2 + Gt + H
（其中时间t的取值范围为0-1，在Pos1的时候为0，在Pos4的时候为1）
x(0-3)代表Pos1-Pos4中x的值，y(0-3)代表Pos1-Pos4中y的值
　　　A = x3 – 3 * x2 +3 * x1 – x0
　　　B = 3 * x2 – 6 * x1 + 3 * x0
　　　C = 3 * x1 – 3 * x0
　　　D = x0
　　　E = y3 – 3 * y2 +3 * y1 – y0
　　　F = 3 * y2 – 6 * y1 + 3 * y0
　　　G = 3 * y1 – 3 * y0
　　　H = y0
　　上面是公式，那么下面我们来看看如何获得Pos1-Pos4：首先，Pos1和
Pos2的取值会比较容易获得，根据OriginB配合当前的速度和方向可以获得，然而Pos3和Pos4呢，怎么获得呢？如果在从Pos1到Pos4的过程中有新的PDU到达，那么我们定义它为NewPackage。
　　　Pos3 = NewPackage.X + NewPackage.Y * t + 1/2
* NewPackage.a * t^2
　　　Pos4 = Pos3 – (NewPackage.V + NewPackage.a * t)
如果没有NewPackage的情况下,则Pos3和Pos4按照开始所规定的方法获得。
至此，关于导航推测的算法大致介绍完毕。
欢迎讨论，联系作者：QQ 181194&& MSN:
参考文献《Defeating Lag with Cubic Splines》
本站中所有文章以及图形均为作者本人、公司所有，本站所有资讯仅供参考，若有任何损失本站概不负责，请自行斟酌。
All Rights reserved.
This site is optimized for at least
resolution (hi-color) viewing
with a browser that supports style sheets.