【记录向】网络多人游戏开发学习日记

dasasdhba

RT，先开坑，这次我使用的书籍是《网络多人游戏架构与编程》by Joshua Glazer, Sanjay Madhav

dasasdhba

[1] 从《星际围攻：部落》谈起
《星际围攻：部落》是 1998 年的网络游戏，那个年代什么网速我就不多说了，但这游戏能在那样的网络环境运行，其必然有着较大的学习价值。

1. 使用不可靠的协议
协议可以暂时简要理解为计算机之间传输数据的规定，以后再说。受限于网速，《星际围攻：部落》采取了不可靠的协议，也就是人为地将需要传输的数据分为了两类：

a. 保障数据：保障游戏运行的基本数据，如某玩家发起攻击的标识。
b. 非保障数据：扔了也无所谓游戏内核的数据，网速不够的时候就不考虑这一部分。

当然，保障数据也可以分一些优先级，比如在糖豆人中，玩家的运动数据应该要优先考虑。

2. 传输层概述
这部分会涉及到大量概念，后续会逐步学习，这里先作整体把握。《星际围攻：部落》的传输层从低到高可以简要分为：

a. 平台数据包模块：数据的最终传输形式
数据包是在网络中传输的有一定格式的数据集合，这一层其实是标准 Socket API 的封装。需要注意的是，由于《星际围攻：部落》采取了不可靠的协议，需要额外采取一些手段保证数据传输的安全性，这些手段在高层运作，之后再说。

b. 连接管理器：发送数据包
连接管理器用于抽象两台计算机之间的连接，它从上层流管理器接收数据，再将其传输给底层平台数据包模块。需要注意的是，连接管理器仍然不能保证数据传输的安全性，但它可以告诉高层，数据是否成功传输。

c. 流管理器：决定发送数据包
流管理器的任务是决定何时将数据发送给连接管理器，它也可以决定允许传输数据的最大速率，由此可以一定程度上防止服务器发送的数据量超出客户机的连接能力。

d. 游戏后台：请求流管理器发送数据包

d-1. 事件管理器：RPC 的简单形式
RPC 全称 Remote Procedure Call，其简单实现就是将事件的发起标识发送给事件管理器，事件管理器最终将其发送给服务器，由服务器来确认和执行这些事件。此外，事件管理器还负责为事件的优先级排序，它也可以追踪人为标记为“可靠数据”（即我们希望这些数据可靠，也就是“保障数据”）的传输记录，由此容易实现可靠性。（若可靠数据的记录出问题，就重新放入事件队列中再传输一次。）

d-2. ghost 管理器：“复制”动态对象
ghost 管理器用于将其他客户端需要“知道”的游戏对象的状态作传输，这里面当然也有优先级的问题。当一个对象应该被传输时，ghost 管理器将会给该对象赋予一些信息，称为 ghost 记录，包括 ID，状态，优先级等等。

d-3. 移动管理器：重要的移动数据
只是在《星际围攻：部落》中，玩家的移动数据尤为重要，所以单独处理。

e. 游戏模拟层：顾名思义。

dasasdhba

[2] 看看《帝国时代》
这同样也是上个世纪末发布的游戏，与《星际围攻：部落》采取 RPC 不同，在当年那样的网络环境下，《帝国时代》作为即时战略游戏必须想办法减少传输量。然而，这种策略放在现在仍然有着较大的借鉴意义，因此接下来我们简要看看。

1. 确定性锁步（deterministic lockstep）
实现这种策略的关键之处在于游戏需要同步的节点的行为都是确定性的，在此基础上，再通过“锁步”就可以保持同步。这样一来，需要传输的信息就只有“命令”，而执行命令则由客户机进行。

2. 轮班计时器——输入延迟
由于网络以及客户机性能等等因素，锁步会造成游戏卡顿（马造 2 联机）。举例来说，如果我输入了一个跳键，那么锁步机制就要求我输入的这个命令必须传输给其他所有客户机之后，这条命令才会被同时执行。为了防止游戏卡顿，《帝国时代》的处理方式是采取“轮班计时器”，即提供一个固定的“输入延迟”，在《帝国时代》中是 200ms。尽管输入延迟非常反直觉，但由于这个延迟可以相对固定，这至少会比不作任何处理每输入一个命令根本不知道会卡多久要强得多。
当然，要是连 200ms 延迟都不够用，这种情况如果继续运行必然会造成卡顿，为了保障其他网络通畅的玩家的游戏体验，如果一个玩家在较长一段时间都传输超时，那我们就把他请出游戏（掉线）。

3. 同步
确定性锁步在理想情况下，即每台客户机处理命令的结果都相同，自然不必考虑同步问题，可惜这只是理想情况。需要强调，处理的结果必须完全相同，即使差距十分微小，这也会随着时间的推移而被无限放大。举例来说，在跨平台联机中（如糖豆人，PC 端和 NS 端可以联机），不同的主机其浮点数的精度和舍入方式可能不同，这就极有可能造成执行命令的一些微小差距。因此，需要有检查同步的机制，具体怎么实现以后再说，这里只是阐述必要性。当然，检查同步还能顺便反作弊。

dasasdhba

[3] TCP/IP 模型
现在我们来逐步了解网络游戏开发必备的计算机网络知识。


1. 起源：分组交换
在分组交换发明之前，数据传输的方式是通过专线直接传输，每条传输线每次传输只能用于一个目的。分组交换取消了这个限制，其原理是将要传输的信息分成小块（即分组），称为数据包，这样同一条线路就可以同时传输来自不同的分组的数据，而当某一组的数据到达目的地之后，再重组即可，这不会影响其他组数据的传输。然而，理想很美好，要想真正实现，则需要一个统一的分组规则——协议。分组交换的发明者 ARPANET 便制定了 BBN Report 1822 协议，最终演变成了今天的 TCP/IP 协议。


2. 游戏开发者需要了解的部分
我们的目标是做网络游戏开发，因此不必将此模型完全理解，通常我们只接触最上层，但了解底层以及底层如何影响上层也会很有帮助。总之，接下来我们将 TCP/IP 协议粗略分为五层，从上到下依次是：
a. 应用层
b. 传输层
c. 网络层
d. 链路层
e. 物理层


每一层各司其职，满足上一层的需求，但它们有一些公有的职责：
a. 传输层面：
* 接收上一层的数据
* 通过添加头部/尾部，对数据作封装
* 将数据转发至下一层
b. 接收层面：
* 接收下一层传输来的数据
* 去掉头部/尾部，解封装传输来的数据包
* 将数据转发至上一层


接下来我们从下往上介绍各个层次，当然，我不打算介绍物理层，做游戏开发的又不会考虑怎么造网线和 WiFi。

dasasdhba

[插曲]
接下来几节将会是硬核的计算机网络相关知识，这部分说实话，你看我写的很有可能不如看专门的计网教材，因此我也不打算写的太详细。

dasasdhba

[4] 链路层
链路层的任务是提供一种网络实体之间通信的方法，该方法需要实现源主机封装信息，通过物理层传输信息，目的主机接收封装好的信息并从中提取所需的部分。

1. 帧
链路层的数据传输单元称为“帧”，而链路层则需要做以下四件事：
a. 定义主机的唯一标识方法，方便帧数据对接收方进行编址。
b. 定义帧的格式，包括目的地址的格式和所传输数据的格式。
c. 定义帧的长短，以便确定上层每一次传输所能发送的数据大小。
d. 定义一种将帧转换为电子信号的物理方法，这样数据才能通过物理层传输。

需要注意的是，帧的传输是不可靠的，诸如物理介质损坏以及电子信号干扰等因素都有可能导致帧的丢失，链路层也不负责检查帧的传输是否成功（所以不可靠），这部分工作由更上层负责。

2. 链路层协议
链路层协议是指规范了上述 abcd 的规则，理想情况下我们希望它统一，但遗憾的是，对于 d 而言，不同的物理介质通常需要不同的协议。举例来说，双绞线对应的协议是 Ethernet 系列，无线电波对应的协议是短程/远程无线网络协议系列，短程通常是 WiFi，远程则是 4G/5G。通常做网络游戏开发并不需要了解这些因为 d 而各不相同的协议，但对于 abc 来说，我们就有一套相对统一的规则了，下面以 Ethernet 为例作说明。

也许是因为双绞线是最早的物理介质，所以最开始 Ethernet 协议族在统一了 abc 的前提下，发展出了不同的系列，这些我们没必要了解，但是了解 abc 的部分是必要的。

(1). MAC 地址
Ethernet 实现 a 的方式是 MAC 地址（media access control address），理论上，该地址为一个 48bit 的数字，唯一分配给连接在 Ethernet 中的各个硬件——网卡。
MAC 地址的具体构成我们没必要作了解，我们只需要知道它就是主机的唯一标识方法……吗？
很遗憾并不是。随着 MAC 地址的不断发展，现在许多网卡允许软件任意“修改” MAC 地址（准确地说，是“软件层面”上的伪装，硬件的 MAC 地址是写死的），48bit 也在逐渐升级为 64bit。
但我们没必要因为这件事就不再把 MAC 地址当作主机唯一标识，事实上不仅仅是 Ethernet 系列，大部分链路层协议都使用了 MAC 地址，包括无线网和蓝牙。也就是说如果有个人真的闲的没事瞎改 MAC 地址，还恰好跟别人冲突了，还恰好跟别人撞了同一条链路层传输路径，那……关我什么事（

(2). 帧的格式
帧由以下内容构成：
i. 前导序列与帧开始标志：帮助底层硬件接收帧
ii. 目标地址与源地址：MAC 地址
注：有一个特殊的地址 FF:FF:FF:FF:FF:FF 称为广播地址，表示将局域网中所有主机都发送该帧。
iii. 帧长度/帧类型：
≤1500 时表示具体的帧数据长度 46～1500bit
≥ 1536 时表示特殊的帧类型，对应特定的长度
iv. 帧数据
v. 帧检验序列（通常是 CRC32）

3. 链路层的不足
如果链路层没有不足，那我们就不需要什么网络层了。然而链路层确实有很多不足：
(1). 缺乏灵活性
假设用户是通过输入 MAC 地址来访问你的服务器，由于 MAC 地址与硬件绑定，要是某一天你的网卡烧坏了，换了个新的，那 MAC 地址也变成了新的，你的用户也访问不到了。
何况，MAC 地址都能改了，那别人随便都能伪装成你的服务器，那样的话……

(2). 缺乏安全性
链路层将会把帧转发给途径的所有主机，由主机来判定它该不该接收（比对 MAC 地址），这一方面要求全球的主机必须在同一个通路上，极大地增大了传输量，且其中任何一个主机的崩溃都可能造成网络瘫痪（虽然这传输量也大概率会造成网络瘫痪）；另一方面，如果我偏要接收所有传来的帧数据呢？那就没有任何数据安全性可言了。

(3). 缺乏兼容性
不同链路层的协议，仅凭链路层本身，是没办法实现相互转换的，那我通过网线发送的数据就发不到通过 WiFi 联网的手机，嗯……

因此我们下一节来看看网络层是怎么解决这些问题的。

dasasdhba

[5] 网络层
网络层的任务是在链路层的基础上提供一套逻辑地址的基础设施，以便于主机硬件的更换，便于主机群划分为子网，便于使用不同的链路层协议和物理介质传输信息。

1. 使用交换机
链路层那样遍历所有主机的办法实在是太傻了，我们可以将一个区域的所有主机全部连在同一个机器上——交换机。交换机将记录连接在其上的主机的 MAC 地址（或 IP 地址，之后会讲），所以帧数据就只需要遍历各大交换机即可。当然，随着网络的不断发展，现在也发展出了多层嵌套的交换机，不过原理还是那个原理。有人可能会有疑问，这样不是还是解决不了安全性的问题吗？答：废话，你以为运营商为啥能查到你的上网记录。但至少你隔壁没那么容易查到了。（你隔壁不会是运营商吧）

2. IPv4 协议
IPv4 是现在实现网络层需求的最常见的协议，它定义了三大系统：
* 为每台主机单独标识的逻辑寻址系统
* 定义地址空间的逻辑分段作为物理子网的子网系统
* 在子网之间转发数据的路由系统

下面我们依次来看。

(1). IP 地址和数据包结构
IP 地址是 32bit 数字，通常是以 . 分隔的 4 个 8bit 数字的形式展示，如：127.0.0.1
假设互联网上的每台主机都有唯一的 IP 地址，那么发送方发送数据就只需要指定接收方的 IP 地址即可（虽然但是，现在 IP 地址也能改，之后解释，我们暂且认为 IP 地址唯一）。

有了 IP 地址，就能定义 IPv4 数据包的结构，不过我们没必要了解太多，下面列出一些需要了解的：

* 版本号：对于 IPv4，取值就是 4
* 片标识符，片标记，片偏移：用于重组分片的数据包（分片是因为帧数据的容量往往小于 IPv4 数据包的大小，所以得分一下）
* 生存时间（TTL）：用于限制转发次数
* 源地址和目标地址
注：目标地址可以是特殊的地址，可同时表示多台主机。

(2). 地址解析协议 ARP
为了最终使用链路层传输数据，需要将 IP 地址转换为 MAC 地址，这就是地址解析协议 ARP（address resolution protocol）。
不过，IP 地址和 MAC 地址可没有什么简单的函数关系，事实上它们两个之间根本没有关系，那 ARP 怎么办呢？答案是搜索。
首先 ARP 会建立一个“缓存表”，如果能从中直接找到结果，那最好，若不然，则进行搜索。
搜索的方式是向链路层全体主机发送 ARP 报文，其中有自家的 MAC 地址，IP 地址，以及目标的 IP 地址等信息。如果目标 IP 地址的主机收到了此报文，就会发送一个 ARP 报文，将自己的 MAC 地址发回去作为响应。得到了 MAC 地址后，也顺便存入缓存表中，这样以后就不用再搜一次了。（除非出错了）
嗯，所以又回到这一套上来了……但至少这样来说，ARP 报文本身没有数据包的信息，虽然有居心的人还是可以通过恶意发送 ARP 报文达到嗅探甚至窃取数据包的目的。
需要指出，显然不能指望用 ARP 来遍历链路层中的所有主机，我们需要类似交换机的办法，所以我们介绍子网。

(3). 子网
我们希望对 IP 地址作一些分类，使得一些 IP 属于同一个“子网”，方便管理和标识，所以我们引入子网掩码：子网掩码也是 32bit 数字，与 IP 地址有着相同的格式。
设某主机的 IP 地址为 A，某子网的掩码为 S，称该主机在这个子网中，若 A & S = C 为该子网预先设定好的常数。（& 为二进制“与”运算）
需要注意，子网掩码有格式要求，其二进制形式必须得由一串连续的 1 和 连续的 0 组成，举例：
255.255.255.0（即 111...11000...000）

在同一个子网中的主机不能够使用以下两个 IP 地址：
* 网络地址：即 C，用于判定。
* 广播地址：!S & C，与 MAC 地址中的广播地址类似，用于标识特定数据包发送给子网中的所有主机。

得益于子网掩码特殊的格式要求，我们可以将其直接简记为有多少个 1，且方便起见，我们也将网络地址（C）作记录。
这种记法称为 CIDR（无类别域间路由），格式是“网络地址/子网掩码二进制 1 的数量），举例：18.19.100.0/24

(4). 路由
有了子网，接下来我们考虑不同子网之间如何传输数据包，实现的关键便在于路由表。

路由表中的一行包含了三列：
* 目标子网：CIDR 格式的目标子网。
* 网关：如果你要给属于该目标子网的主机发送数据包，你只需要给这个网关发就行了，网关那边会负责进一步转发的；如果这一项为空，说明目标子网你通过 ARP 就能轻易到达了（大概率是你自己的子网），所以你自己发。
* 网卡：你需要用哪张网卡来发数据包。

嗯，那我从哪里知道这些东西呢？好吧，事实上这些东西都不用你来担心，因为这是互联网服务提供商（ISP）来搞定的事情。

那，路由表不需要更新吗？ISP 给我装好路由器了不就不用管了吗？呃，有一个特殊的目标子网：0.0.0.0/0 ，称为默认网络，不难验证任何 IP 地址都属于这个“子网”；嗯，路由表使用的时候是按顺序从上到下遍历的，一般最后一个就是这个默认网络，到这了就直接发给 ISP 的网关让它自己看着办了。

嗯，那我了解这些东西有什么用呢？好吧，用处不大，但有一件事情是必须要指出的：网络层协议是不可靠的。

首先是生存时间（TTL）的限制，数据包每经过一个路由器，就会 TTL-1，如果 TTL 归 0 了，那路由器就不认了，这个数据包就废了。（这主要是为了避免 IP 数据包在网络中的无限收发）当然，也有一些别的各种各样的原因，总之，IPv4 并不保证数据包能发到目标地址，发过去的顺序同样也不保证。

3. IPv6
说实话，IPv4 地址虽然理论上能有 40 亿多个不同的，但还是被用完了。所以，就像 32 位升级至 64 位，我们引入 IPv6，这玩意的地址有 128bit，这下肯定够用了。当然，IPv6 也有不少改进，比如 NDP 取代了 ARP 等，这些就不细说了，毕竟……说实话短期看来还是 IPv4 是主流，现在国内也只有高校校园网支持 IPv6。

dasasdhba

[6] 传输层
网络层从底层上实现了不同主机之间的网络通信，但是在应用层面，假设我的电脑收到了一个 IP 数据包，那我怎么知道这个数据包是要发给我电脑上哪个软件来处理的。因此，我们需要传输层。

1. 端口
传输层实现的关键在于给主机的每一个进程绑定了一个特定的端口（port），这是一个 16bit 的数字。这个数字并不大，如何保证不同的进程使用的端口不发生冲突？这就需要额外标识了，而为了规范端口的使用和标识，协议和应用的开发者需要向 ICANN/IANA 机构注册所需要的端口，每一个传输层协议只能注册一个端口。但是需要指出，并不是所有端口都是可以注册的，其中用户端口（也称注册端口）的范围是 1024-49151，一般都是注册这些端口。而 1-1023 称为系统端口（也称预留端口），这些端口当然也可以注册（往往用于操作系统级别，安全要求较高），但我们肯定用不到。最后，49152-65536 称为动态端口，这部分端口不需要注册，想用就用，如果你发现某个动态端口被占用了，就尝试换一个。

总之，做网络游戏一般用动态端口就行了，顶多可能还需要去注册一个用户端口，但一般来说真的没啥必要。

注：IP 地址和端口经常由冒号连接在一起，从而表示一个完整的源地址或目标地址，举例：18.19.20.21:80。

有了端口之后，我们还需要传输层协议才能发送数据，接下来介绍几个。

2. UDP
UDP（user datagram protocol，用户数据报协议）是一个很轻量的协议，其数据报包含了一个 8 字节的报头，后面跟着数据，其中报头写明了源端口和目标端口，可以说是非常廉价的一类协议。

廉价不一定是好事，UDP 并不保证数据的顺序传输和准确到达，换言之这还是不可靠的。

3. TCP
TCP（transmission control protocol，传输控制协议）是在两台主机之间创建的持久性的连接协议，提供了可靠的数据流传输（终于可靠了，泪目）。这里的可靠指的是保证所有的数据都按序抵达接收方，其中实现按序的关键在于 TCP 报文引入了序列号和确认号（ACK，用于确认响应，在初始化的时候设置）用于保证顺序；实现准确到达的关键是源主机会等待来自目的主机的确认响应数据包，如果在一定时间内没有收到期望的确认，就重新发送。

当然，具体的实现流程远没有说的这么简单，由于 TCP 策略涉及到了重新发送数据以及跟踪期望的序列号，所以每一台主机都必须维护所有活跃 TCP 连接的状态。此外，TCP 的初始化也比较麻烦，这得从“三次握手”说起。

(1). 三次握手
假设主机 A 需要与主机 B 建立 TCP 连接，初始化的过程需要两步：
* 主机 A 随机选一个初始序列号（举例 1000），向主机 B 发送第一个报文：seq #: 1000, SYN（这是 sync 的意思，请求连接的时候用的）
人话：“主机 B，我想给你发一段以我这边是 1000+1 序列号为起始位置的数据流，收到请回复。”
* 主机 B 收到该报文，如果主机 B 愿意开放该连接，就会响应一个由主机 B 随机选择的初始序列号（举例 3000），由主机 A 给定的初始序列号+1 得到的 ACK 组成的报文：seq #: 3000, ack #: 1001, SYN ACK
人话：“主机 A，我同意了，我这里的响应报文的起始序列号是 3000+1，你接下来给我发 1001 吧。”

接下来，如果主机 A 成功得到响应，两个主机就正式建立 TCP 连接，其流程大概是：
* 主机 A 发送数据：seq # :1001, ack #: 3001, ACK
人话：“我给你发来 1001 了，收到请给我发 3001 回复。”
* 主机 B 发送响应：seq #: 3001, ack #: 1002, ACK
人话：“OK 我收到了，你继续发 1002。”

(2). 意外情况
刚才提到了，如果没有收到响应就会重复发送数据，但实际情况非常复杂，TCP 也针对性地作了各种优化，包括但不限于流量控制，拥塞控制等。这些我们不必了解，但必须指出，拥塞控制中的一环——Nagle 算法，是网络游戏玩家的克星，尽管它有效减少了带宽的使用，但会带来巨大的延时。万幸的是，TCP 实现一般允许我们关掉这个 Nagle 算法，嗯，所以有需要的话别忘了。

(3). 断开连接
正常情况下，发送方发送 FIN 标识，接收方也以 FIN 响应后，就进入了准备断开连接的状态，因为如果之前有还没发过去正在尝试重发的，那还是会继续尝试重发。如果全部发完了，发送方就会再发送一个包含 FIN 标识的报文响应刚才接收方 FIN 报文的 ACK，表示可以正式断开连接了。当然，超时的意外情况也会导致断开连接。

dasasdhba

[7] 应用层
应用层的主要作用就是将底层的东西人性化，这样才能方便使用。

1. DHCP
要想给子网中每一台主机分配唯一的 IPv4 的地址，雇佣一个网络管理员来手动分配的话，效率也太低下了。方便起见，我们希望分配 IP 地址的过程自动化，这就是 DHCP（dynamic host configuration protocol，动态主机配置协议），它允许主机在接入网络的时候请求自动配置相关信息。

具体来说，主机接入网络的时候，会创建一个 DHCPDISCOVER 消息，包含自己的 MAC 地址，并使用 UDP 协议发送到 255.255.255.255/67（广播）。当 DHCP 服务器收到的时候，就把可用的 IP 地址发给该主机。

2. DNS
DNS（domain name system，域名系统）建立了域名→IP 地址的映射，众所周知我们进入网页只需要输入一个“网址”，这实际上是域名，实际情况是这样的：
计算机把域名发给预先配置好的 DNS 服务器的 IP 地址，让它帮忙查询一下这个域名对应的 IP 地址是啥，查到了就把 IP 地址发给你，这样你就可以访问网站了。
所以自然的，域名是需要注册和购买的，这些我们就暂且不提了。

dasasdhba

[8] NAT
接下来我们来填 IPv4 地址不够用的坑，解决方案便是 NAT（network address translation，网络地址转换）。

1. NAT 网络
首先引入公网 IP 的概念：称一个 IP 地址为公开可路由的，若互联网上任意正确配置的路由器都可以给这个 IP 地址对应的主机发送数据包，也俗称公网 IP。

既然 IPv4 地址不够用，那可以采用类似交换机的思想，我们只需要保证子网中 IP 地址的唯一性，而将这个子网通过一个公网 IP 连接到互联网，这样就配置了一个 NAT 网络。

2. 数据包重写
为了实现 NAT 网络，路由器的 NAT 模块需要将数据包进行重写，也需要记录发送者，具体来说：

(1). 连接公网 IP
若某个 NAT 网络中的一个本地主机要想给某个公网 IP 发送数据，发过去自然没问题，但如果将自己的本地 IP 地址发过去，那对面就没办法响应了。因此，路由器 NAT 模块需要将该数据包改写，替换源 IP 地址为这个 NAT 网络的公网 IP，这样对面就能把数据发回给路由器了。但是，路由器应该进一步把这个数据发回给谁？

(2). NAT 表
路由器为了确定收到的数据包应该发给本地网路中的哪个主机，建立了 NAT 表，在本地 IP 想要给公网 IP 发送数据包时，记录了源 IP 地址和源端口号，并随机选取一个没有被使用过的端口号重写数据包，同时用于标识，这样一来 NAT 模块就能正确地将公网 IP 那边响应的数据包转发至本地主机。

(3). 无法解决的问题
上述方案只能解决本地主机与公网 IP 的连接，试问属于两个不同 NAT 网络的主机如何连接？若想直接连接，这要求用户手动配置路由器 NAT 模块的转发，将带有特定源端口号的数据包重写并转发到自己的主机。就两台主机也就罢了，如果是几十台主机呢？何况，就算只考虑两台主机的连接，我们一般也不能去要求玩家来配置这些乱七八糟的东西，不然谁玩啊。因此，我们陷入了死局，NAT 填了一个坑又挖了新的坑，这也是为什么我们的网络游戏通常需要服务器。

3. NAT 穿越
我们使用 UDP 和一台第三方主机（服务器）来解决不同 NAT 网络的主机的连接问题，即 NAT 穿越问题，这种方案被称为 STUN（simple traversal of UDP through NAT）。

这种方案原理上并没有多高深，既然 NAT 网络中的主机连接公网 IP 没有问题，那两台来自不同 NAT 网络的主机只要连接到同一个公网 IP 并让这个公网 IP 的主机交换信息不就行了。当然这样有点浪费了，事实上我们的服务器只需要将双方的本地 IP 地址，公网 IP 地址，端口等信息作交换，并让它们利用这些信息自动配置 NAT 模块的转发即可。

嗯，所以跟 UDP 有啥关系？没啥关系，只是信息量小，只需要交换一点信息嘛，用 UDP 就行了。

dasasdhba

[插曲 2]
我们介绍完了计算机网络基础知识，这些内容都非常偏底层，然后这里简单介绍一下 Socket：Berkeley Sockets API 提供了进程与 TCP/IP 模型各个层之间通信的标准方法，它已经被移植到了每个主要的操作系统和编程语言，可以说是网络编程中名副其实的标准，也可以说是网络游戏开发中最常用的网络构建方法。

关于 Socket 的使用，在足够了解网络基础知识的前提下，学起来是不难的（如果不考虑安全性等乱七八糟的问题），这里不打算作介绍。尽管我使用的书籍中以 C++ 的 Winsock.h 库为例作了介绍，然而我打算直接采用游戏引擎来构建网络游戏，顶多也就 NAT 穿越的时候需要写一些轻量一点的程序挂在云服务器上。（而且就算真有这需求我会更愿意用 Python，毕竟……嗯）

接下来我打算先实践一下 Godot 实现 NAT 穿越，整个简单的 demo 玩玩，然后我们再回来探讨诸如网络游戏连接的拓扑结构，游戏同步的各种办法等等。

dasasdhba

[9] Godot 实现 NAT 穿越
NAT 穿越俗称内网穿透，[8] 中曾介绍了 STUN 实现，但是仅仅只是在原理层面上作了介绍，并未涉及具体的操作方法。然而，关于内网穿透其实已经有很多成熟的方案可以拿来直接用，因此我们不必太担心，下面给出几类方案。

1. 使用现成插件
https://godotengine.org/asset-library/asset/1052
这是一个通过 UDP 打洞实现 NAT 穿越的 Godot 插件，通过在第三方服务器从配置其提供的程序实现，可以参考使用范例。

关于第三方服务器，最简单的方案是租云服务器，这里不讨论什么云服务器好用，自行了解吧。

2. 使用 UPnP
官方文档：https://docs.godotengine.org/en/stable/classes/class_upnp.html
使用方法足够简单，文档中也给出了例子，唯一需要注意的是并不是所有设备都支持或开启了 UPnP。

最后，关于 demo，这个我自己做完以后会放项目地址，就不在此记录实现过程了。

dasasdhba

[10] 网络拓扑
网络拓扑是指游戏过程中不同主机之间的连接方式，对于不同类型的游戏，采取合适的网络拓扑是很重要的。
下面介绍两类最常见的网络拓扑。

1. 客户端-服务器
在这种模型中，一个游戏实例被指定为“服务器”（这与实现 NAT 穿越所采用的第三方服务器并不完全是一回事），而其他游戏实例都被指定为“客户端”。具体来说，客户端只能与服务器通信，而服务器负责与所有客户端的通信。
需要注意，这种结构在多人连接的情况下是严重不对称的，客户端只需要连接服务器，而服务器却需要连接所有客户端。对于玩家特别多的情形，考虑到玩家的网络情况不一定足够好，一般不能指望选定某个玩家来做服务器，此时我们一般会配置一个“权威”服务器（如果这样搞，那也不需要 NAT 穿越了）。

如果我们使用权威服务器，那么这个服务器其实有很多没必要做的工作，比如它根本不需要渲染任何图像。一般来说，称一个服务器为专用服务器（dedicated server），若它只运行游戏状态并与所有客户端通信。而另一种极端的服务器，也就是作为服务器的同时也实现了客户端的所有功能的那种服务器，被称为监听服务器（listen server），一般是指定网络最好的玩家主机来做这个服务器。

当然，这种方案最大的问题就是客户端的延迟，导致延迟的重要原因是往返时间（round trip time，RTT），即使是最理想情况，RTT 一般也会超过 100ms。我们当然也有一些技术来“隐藏”部分延迟，这个之后讨论。

最后，如果服务器意外断开了连接，对于使用监听服务器的情形，可以另选一个其他玩家重新建立连接，但如果使用专用服务器，那可能就没什么好办法了。

2. 对等网络
在这种模型中，每个单独的游戏实例都与其他的所有实例连接。尽管对每个游戏实例来说，网络的开销增大了，但由于没有经过“服务器中转”，延迟在理想情况下其实减少了。
然而，由于不同游戏实例的网络状况不尽相同，在这种模型中最大的问题是同步。之前讨论过确定性锁步的方案，尽管概念上易懂，但实现上仍然相当复杂。

此外，在这种模型中，由于不存在服务器的概念，有单个玩家掉线也不会影响别的玩家。

dasasdhba

[11] 延迟
延迟的关键在于 RTT，如何最大化降低延迟的影响是开发网络游戏必须要考虑的问题。

1. 保守算法
在 RTS 类游戏中，延迟并不会太影响玩家的体验，因此可以直接不管。以客户端-服务器模型为例，客户端在保守算法中，只会向服务器发送执行某个输入的请求，服务器执行完毕后再将执行结果发送给所有客户端。这类客户端被称为沉默的终端（dumb terminal），尽管能明显感受到延迟，但至少其显示给用户的所有状态都是在那个时间点附近绝对正确的状态。

由于网络的影响，客户端收到的状态更新数据可能是跳跃的，直接生硬地采用这些数据更新画面会导致画面的不流畅，一个简单的解决方法是使用插值（常用三次样条插值）。需要注意，插值所需的时间必须要小于 RTT，为此我们可能需要对 RTT 作估计，通常只需要取平均值，这没有必要过于精确，只要能够基本保证插值时间小于 RTT 即可。

2. 客户端预测
既然我们可以对 RTT 作估计，那么我们也完全可以更进一步地直接利用估计的 RTT 作预测。具体来说，客户端从服务器收到的状态更新总是 RTT/2 之前的，因此我们可以在客户端收到的状态更新的基础上再模拟 RTT/2 的时间作为最终显示结果。

但是有一个问题，如何预测其他玩家？常用的办法是航位推测法（dead reckoning），假设玩家继续做当前正在做的事情，即假设其他玩家的输入保持不变。这样当然会造成偏差，有时候可能会很严重，不过我们有一些弥补的办法：

a. 即时状态更新：错了就算了，直接闪现回来罢。
b. 插值：1 中介绍过了。
c. 进一步插值：直接插值位置信息可能会造成明显的抖动，所以我们可以把速度加速度啥的全都进行插值，进一步使得我们的纠正过程不明显。

3. 客户端本地移动重放
上述办法能够隐藏客户端非本地玩家之外的延迟，但不能隐藏本地玩家的操作延迟，因为当本地玩家输入后，仍然只有在一个 RTT 之后才能看到自己的输入响应，使用航位推测和插值纠正对于本地玩家来说会非常不自然。

理想情况下，我们希望本地玩家认为它们的操作跟玩单机游戏一样，一个可能的解决方案是让客户端只从本地模拟得到本地玩家的状态，但这必然会使得本地玩家的状态与服务器那边的状态产生差别。

如果仅针对本地玩家的位置信息，流行的做法是采用重放（replay）法，我们记录本地玩家在 RTT/2 之内的所有输入序列，在收到来自服务器的 RTT/2 之前的状态更新后，用这一系列的输入序列进行模拟，由此就容易得到更为精准的模拟结果。

4. 用前摇来隐藏操作延迟
对于本地的攻击类等输入，本地移动重放并不能够隐藏其延迟，常用的小技巧是给这类操作做一个前摇，以争取一个 RTT 的时间。这种办法实际上破坏了游戏的设计逻辑，需要权衡利弊。

5. 服务器回退
对于一些本地玩家的关键性操作，如射击游戏中，为了保证玩家的体验，我们希望玩家在本地击中了目标就一定能击中，为此我们需要在发生了这类事情的时候在服务器端作回退操作。当然，这样会影响被击中玩家的体验，有可能他已经躲好了但因为网络延迟仍然被判为击中。总之，这也是一个需要权衡的问题。

878yfy

草，我明天考试就考这个（