这个系列是GAMES104-现代游戏引擎：从入门到实践(GAMES 104: Modern Game Engine-Theory and Practice)的同步课程笔记。本课程会介绍现代游戏引擎所涉及的系统架构、技术点以及引擎系统相关的知识。本节课主要介绍网络游戏的架构基础。
网络游戏的出现是游戏发展历程中的重要里程碑，基于互联网玩家可以同时和全球的其它玩家一起进行游玩。
网络游戏和单机游戏相比有很多难点，比如说如何保证每个玩家的游戏状态是一致的、如何进行网络同步、如何处理延迟和丢包、如何检测玩家的作弊行为、如何处理不同的设备和系统、如何设计高性能的服务器系统等等。这些网络游戏专有的问题都为游戏引擎的开发提出了更大的挑战。
所以网络游戏是一个非常复杂庞大的系统，在这一部分我们同样分为两节来介绍相关的技术。
Network Protocols
在介绍网络游戏相关的内容前我们先来介绍一下网络协议(network protocols)。实际上互联网的概念最早是由Vint和Robert提出的，他们设计了TCP/IP协议从而实现了不同设备基于电话线和卫星的通信。
The Problem of Communication
网络协议要解决的核心问题是如何实现两台计算机之间的数据通信，当软件应用和硬件连接不断地变得复杂时直接进行通信是非常困难的。
因此人们提出了中间层(intermediate layer)的概念来隔绝掉应用和硬件，使得开发者可以专注于程序本身而不是具体的通信过程。
在现代计算机网络中人们设计了OSI模型(OSI model)来对通信过程进行封装和抽象。
Socket
对于网络游戏开发来说一般不需要接触到很底层的通信协议，在大多数情况下只需要知道如何使用socket建立连接即可。
socket是一个非常简单的结构体，我们只需要知道对方的IP地址和端口号就可以使用socket建立连接来发送和接收数据。
建立连接时需要额外注意到底是使用IPv4还是IPv6，使用TCP还是UDP协议等问题。
TCP
TCP是最经典也是著名的网络协议，它可以确保发送端发送的数据包都按照顺序被接收端接收。
TCP的核心是retransmission mechanism，这个机制要求接收端收到消息后会向发送端发送一个ACK，而发送端只有接收到这个ACK之后才会继续发包。当然TCP实际使用的机制要比上述的过程复杂得多。
当TCP出现网络拥堵时会主动调节单次发包的数量。如果发包都能顺利地接收到则会提高发包数量以提升效率，反之则会减少发包数量以提升稳定性。
UDP
除了TCP之外人们还开发出了UDP这样的轻量级网络协议。UDP的本质是一个端到端的网络协议，它不需要建立长时间的连接，也不要求发送数据的顺序，因此UDP要比TCP简单得多。
在现代网络游戏中根据游戏类型的不同使用合适的网络协议，比如说对于实时性要求比较高的游戏会优先选择UDP，而策略类的游戏则会考虑使用TCP。在大型网络游戏中还可能会使用复合类型的协议来支持游戏中不同系统的通信需求。
Reliable UDP
同时现代网络游戏中往往还会对网络协议进行定制。以TCP为例，虽然TCP协议比较稳定但是效率过于低了，而且网络游戏中出现一定的丢包是可以接受的；而对于UDP来说它虽然非常高效但是却不够稳定。
因此现代网络游戏中往往会基于UDP来定制一个网络协议，这样既可以利用UDP的高效性又可以保证数据通信的有序性。
ACK及其相关技术是保证数据可靠通信的基本方法。
Automatic Repeat Request
ARQ(automatic repeat request)是基于ACK的错误控制方法，所有的通信算法都要事项ARQ的功能。
Sliding Window Protocol
滑窗协议(sliding window protocol)是经典的ARQ实现方法，它在发送数据时每次发送窗口大小的包然后检验回复的ACK来判断是否出现丢包的情况。
滑窗协议的一个缺陷在于它需要等待接收端的ACK才能继续发送数据，因此在很多情况下它无法完全利用带宽。
Go-Back-N ARQ
对滑窗协议的一种改进方法是Go-Back-N ARQ，当出现丢包时它只会把窗口内的包重新发送。
Selective Repeat ARQ
另一种改进方法是selective repeat ARQ，它只会重新发送丢失或损坏的包从而进一步提升带宽的利用率。
Forward Error Correction
在网络游戏中需要额外处理丢包的问题，因此我们在自定义网络协议时一般会结合forward error correction(FEC)的方法来避免数据的反复发送。
目前常用的FEC算法包括异或校验位以及Reed-Solomon codes两大类。
XOR FEC
异或校验位是使用异或(XOR)运算来恢复丢失数据的方法。这里需要注意的是当同时有多个包丢失时，使用异或校验位是无法恢复数据的。
Reed-Solomon Codes
Reed-Solomon codes是经典的信息传输算法，它利用Vandemode矩阵及其逆阵来恢复丢失的数据。
总结一下，在自定义UDP时需要考虑ARQ和FEC两类问题。
Clock Synchronization
有了网络协议后就可以开始对网络游戏进行开发了，不过在具体设计游戏前我们还需要考虑不同玩家之间的时钟同步(clock synchronization)问题。
Round Trip Time
由于网络通信延迟的存在，客户端向服务器端发送一个包后都需要等待一定的时间才能收到回包，这个间隔的时间称为round-trip time(RTT)。RTT的概念类似于ping，不过它们的区别在于ping更加偏向于底层而RTT则位于顶部的应用层。
Network Time Protocol
利用RTT就可以实现不同设备之间的时间同步。实际上不仅仅是网络游戏，现实生活中的各种电子设备进行同步都使用了RTT的技术。
在实际设备的时间同步过程中一般会利用层次化的结构来进行实现。
NTP的算法实际上非常简单，我们只需要从客户端发送请求然后从服务器接收一个时刻就好，这样就可以得到4个时间戳。如果我们进一步假定网络上行和下行的延迟是一致的，我们可以直接计算出RTT的时间长短以及两个设备之间的时间偏差。当然需要注意的是在实际中网络上行和下行的带宽往往是不一致的，因此这个算法也不是十分的严谨。
实际上我们可以证明在不可靠的通信中是无法严格校准时间的。不过在实践中我们可以通过不断的使用NTP算法来得到一系列RTT值，然后把高于平均值50%的部分丢弃，剩下的RTT平均值的1.5倍就可以作为真实RTT的估计。
Remote Procedure Call
Socket Programming
尽管利用socket我们可以实现客户端和服务器的通信，但对于网络游戏来说完全基于socket的通信是非常复杂的。这主要是因为网络游戏中客户端需要向服务器发送大量不同类型的消息，同时客户端也需要解析相应类型的反馈，这就会导致游戏逻辑变得无比复杂。
另一方面客户端和服务器往往有着不同的硬件和操作系统，这些差异会使得游戏逻辑更加复杂且难以调试。
RPC
因此在现代网络游戏中一般会使用RPC(remote procedure call)的方式来实现客户端和服务器的通信。基于RPC的技术在客户端可以像本地调用函数的方式来向服务器发送请求，这样使得开发人员可以专注于游戏逻辑而不是具体底层的实现。
在RPC中会大量使用IDL(interface definiton language)来定义不同的消息形式。
然后在启动时通过RPC stubs来通知客户端有哪些RPC是可以进行调用的。
当然真实游戏中的RPC在实际进行调用时还有很多的消息处理和加密工作。
Network Topology
Peer-to-Peer
在设计网络游戏时还需要考虑网络自身的架构。最经典的网络架构是P2P(peer-to-peer)，此时每个客户端之间会直接建立通信。
当P2P需要集中所有玩家的信息时则可以选择其中一个客户端作为主机，这样其它的客户端可以通过连接主机的方式来实现联机。
很多早期经典的游戏都是使用这样的网络架构来实现联网功能。
Dedicated Server
在现代网络游戏中更多地会使用dedicated server这样的网络架构，此时网络中有一个专门的服务器向其它客户端提供服务。
从实践结果来看，对于小型的网络游戏P2P是一个足够好的架构，而对于大型的商业网络游戏则必须使用dedicated server这样的形式。
Game Synchronization
在前面的课程中我们介绍过游戏世界是分层的。从玩家的角度来看，玩家的操作通过输入层一路向下到达游戏逻辑层，然后通过渲染器展示给玩家。
而在网络游戏中，除了单机游戏都需要的分层外我们还需要考虑不同玩家之间的同步。在理想情况下我们希望客户端只负责处理玩家的输入，整个游戏逻辑都放在服务器端。
由于延迟的存在，不同玩家视角下的对方可能会有不同的行为表现。
因此我们需要使用游戏同步技术来保证玩家的游戏体验是一致的。目前常用的同步技术包括快照同步、帧同步以及状态同步等。
Snapshot Synchronization
快照同步(snapshot synchronization)是一种相对古老的同步技术。在快照同步中客户端只负责向服务器发送当前玩家的数据，由服务器完成整个游戏世界的运行。然后服务器会为游戏世界生成一张快照，再发送给每个客户端来给玩家反馈。
快照同步可以严格保证每个玩家的状态都是准确的，但其缺陷在于它给服务器提出了非常巨大的挑战。因此在实际游戏中一般会降低服务器上游戏运行的帧率来平衡带宽，然后在客户端上通过插值的方式来获得高帧率。
由于每次生成快照的成本是相对较高的，为了压缩数据我们可以使用状态的变化量来对游戏状态进行表示。
快照同步非常简单也易于实现，但它基本浪费掉了客户端上的算力同时在服务器上会产生过大的压力。因此在现代网络游戏中基本不会使用快照同步的方式。
Lockstep Synchronization
帧同步(lockstep synchronization)是现代网络游戏中非常常用的同步技术。不同于快照同步完全通过服务器来运行游戏世界，在帧同步中服务器更多地是完成数据的分发工作。玩家的操作通过客户端发送到服务器上，经过服务器汇总后将当前游戏世界的状态返还给客户端，然后在每个客户端上运行游戏世界。
Lockstep Initialization
使用帧同步时首先需要进行初始化，将客户端上所有的游戏数据与服务器进行同步。这一过程一般是在游戏loading阶段来实现的。
Deterministic Lockstep
在游戏过程中客户端会在每一帧将玩家数据发送到服务器上，服务器接收到所有玩家的数据后再统一转发到玩家客户端上，然后由玩家客户端执行游戏逻辑。当然这种同步方式也存在一定的缺陷，当某个玩家的数据滞后了所有玩家都必须要进行等待。这种情况在一些早期的联网游戏中都很常见。
Bucket Synchronization
为了克服这样的问题，人们提出了bucket synchronization这样的策略。此时服务器只会等待bucket长度的时间，如果超时没有收到客户端发来的数据就越过去，看下一个bucket时间段能否接收到。通过这样的方式其它玩家就无需一直等待了。
bucket synchronization本质是对玩家数据的一致性以及游戏体验进行的一种权衡。
Deterministic Difficulties
帧同步的一大难点在于它要保证不同客户端上游戏世界在相同输入的情况下有着完全一致的输出。
为了保证输出的确定性我们首先要保证浮点数在不同客户端上的一致性，这可以使用IEEE 754标准来实现。
其次在不同的设备上我们需要保证相关的数学运算函数有一致的行为，对于这种问题则可以使用查表的方式来避免实际的计算。
除此之外还可以使用定点数来替换浮点数，从而避免浮点数导致的各种问题。
除了浮点数之外还要考虑随机数的问题，我们要求随机数在不同的客户端上也必须是完全一致的。因此在游戏客户端和服务器进行同步时需要将随机数种子以及随机数生成算法进行同步。
总结一下，保证客户端上游戏世界模拟一致的常用方法如下：
Tracing and Debugging
现代网络游戏的逻辑往往非常复杂，在玩家进行游玩时可能无法避免地出现一些bug，因此对于服务器来说检测客户端发送的数据是否存在bug就非常重要。一般来说我们会要求客户端每隔一段时间就上传本地的log，由服务器来检查上传数据是否存在bug。
Lag and Delay
为了处理网络延迟的问题我们还可以在客户端上缓存若干帧，当然缓存的大小会在一定程度上影响玩家的游戏体验。
另一方面我们还可以把游戏逻辑帧和渲染帧进行分离，然后通过插值的方式来获得更加平滑的渲染效果。
Reconnection Problem
由于网络的不稳定，玩家可能会不可避免地遇到断线的情况，此时我们还需要设计断线重连的机制。
实际上再进行帧同步时每个若干帧会设置一个关键帧。在关键帧进行同步时还会更新游戏世界的快照，这样可保证即使游戏崩溃了也可以从快照中恢复。
为了实现这样的功能可以使用quick catch up技术，此时我们暂停游戏的渲染把所有的计算资源用来执行游戏逻辑。
而在服务器端也可以使用类似的技术，从而帮助掉线的玩家快速恢复到游戏的当前状态。实际上网络游戏的观战和回放功能也是使用这样的技术来实现的。
Lockstep Cheating Issues
网络游戏中作弊行为的检查是非常重要的。对于帧同步的游戏，玩家可以通过发送虚假的状态来实现作弊行为，这就要求我们实现一些反作弊机制。
Lockstep Summary
总结一下，帧同步会占用更少的带宽也比较适合各种需要实时反馈的游戏。而帧同步的难点主要集中在如何保证在不同客户端上游戏运行的一致性，如何设计断线重连机制等。
State Synchronization
状态同步(state synchronization)是目前大型网游非常流行的同步技术，它的基本思想是把玩家的状态和事件进行同步。
进行状态同步时由客户端提交玩家的状态数据，而服务器则会在收集到所有玩家的数据后运行游戏逻辑，然后把下一时刻的状态分发给所有的客户端。
Authorized and Replicated Clients
状态同步中服务器称为authorized server，它是整个游戏世界的绝对权威；而玩家的本地客户端称为authorized client，它是玩家操作游戏角色的接口；在其他玩家视角下的同一角色则称为replicated client，表示它们仅仅是authorized client的一个副本。
State Synchronization Example
当authorized client执行了某种行为时首先会向服务发送相关的数据，然后由服务器驱动游戏逻辑并把相应的状态发布给所有的玩家。当其他客户端接收到更新后的状态时，再驱动replicated client执行authorized client的行为。类似地，authorized client行为产生的后果也是由服务器进行计算再发布给所有的客户端。这样的好处在于我们无需要求每个客户端上的模拟是严格一致的，整个游戏世界本质上仍然是由统一的服务器进行驱动。
Dumb Client Problem
由于游戏角色的所有行为都需要经过服务器的确认才能执行，状态同步会产生dumb client的问题，即玩家视角下角色的行为可能是滞后的。
要缓解这样的问题可以在客户端上对玩家的行为进行预测。比如说当角色需要进行移动时首先在本地移动半步，然后等服务器传来确定的消息后再进行对齐，这样就可以改善玩家的游戏体验。在守望先锋中就使用了这样的方式来保证玩家顺畅的游玩。
由于网络波动的存在，来自服务器的确认消息往往会滞后于本地的预测。因此我们可以使用一个buffer来缓存游戏角色的状态，这样当收到服务器的消息时首先跟buffer中的状态进行检验。当buffer中的状态和服务器的数据不一致时就需要根据服务器的数据来矫正玩家状态。
当然这样的机制对于网络条件不好的玩家是不太公平的，他们的角色状态会不断地被服务器修正。
Packet Loss
对于丢包的问题在服务器端也会维护一个小的buffer来储存玩家的状态。如果buffer被清空则说明可能出现了掉线的情况，此时服务器会复制玩家上一个输入来维持游戏的运行。
帧同步和状态同步两种主流同步技术的对比如下：
