# 同步算法 ## 同步算法 同步是网络游戏的核心课题，如《绝地求生》，每局战斗会有 100 名玩家参数，每个角色的位置、动作和属性都要同步给战场中的其他玩家，射击类游戏对同步的要求很高，稍有网络延迟，玩家就很难以瞄准目标，或者莫名其妙被打死，然而网络通信不可避免会存在延迟和抖动的问题，如果没能处理好，就会极大影响玩家的游戏体验。 不同类型的游戏对同步算法有着不同的权衡策略。射击游戏对精确度（如判定是否爆头）的要求很高，每局的玩家数量很多（如《绝地求生》每局有 100 名玩家参战），但好在同屏角色数量较少。而即时战略游戏（也称策略游戏）同屏的单位数量虽然很多（如英雄联盟），但好在每局游戏的玩家数不多。 ### 同步难题 为什么同步是网络游戏的一大难题，《球球大作战》都用到了“指令-＞状态”的同步方法。假设射击游戏也使用同样的方法，当玩家 A 按下方向键移动角色时会发生什么？客户端 A 会先向服务端发送操作指令（往哪个方向移动），然后服务端会计算角色 A 的新位置，再广播给所有玩家。服务端每隔一段时间如 0.2 秒调用一次 move\_update,计算角色的新坐标，然后广播移动协议。 这样的同步方法是可能产生问题的。 * 顿挫 服务端每隔 0.2 秒计算一次位置，并将新坐标广播给客户端。客户端收到移动协议后，如果简单粗暴地直接设置角色坐标，玩家会有明显的顿挫感。 举例来说，一开始角色处于位置 A，过了 0.2 秒突然变到位置 B，又突然变到位置 C，移动过程很不顺畅。 如果将同步频率提高到 24 帧/秒（即每 0.04 秒调用一次 move\_update），利用人眼的残影现象，理论上会让顿挫感消除，直觉上就像播放电影画面一样。然而，提高同步频率不仅会给服务端带来性能压力，而且无法达到预期效果。 * 打不中 网络质量的差异，会使得同一时刻各玩家看到的画面不同。角色 A 向左移动，角色 B 向右移动。由于客户端 A 的网络延迟较低，因此它能较早收到最新的移动协议，在玩家 A 的眼中，角色 A 刚好瞄准角色 B，于是开枪射击；但在玩家 B 的眼中，自己并未被瞄准。无论如何判定，总有玩家会感到不满意，如果判定为 打中，玩家 B 会感觉很奇怪，觉得自己莫名奇妙中了一枪；如果判定没打中，玩家 A 会很生气。 * 抖动和延迟 “顿挫”“打不中”这些问题都可以归结于网络的延迟和抖动，就算服务端的性能再好，设置很高的同步频率，也无法解决该问题。 A 端依次向 B 端发送数据。若使用 UDP，则有些数据会无法传达（图中用 X 标记的数据），有些数据会顺序错乱（图中用 ⊙ 标记的数据）； TCP 解决了不可靠和无序的问题，但与 UDP 一样的是，TCP 也不可避免地存在延迟，而且无论发送频率多平稳，接收频率也会很不稳定， 比如，A 端按固定间隔发送数据，但 B 端相邻的箭头有些相隔很近、有些则很远，我们把这种不稳定的现象称为抖动。 ![UDP和TCP两种协议的对比](/files/AC2zEBdp5UY8n9a5kGsr) | 特性 | UDP | TCP | | ----------- | --- | --- | | 不可靠(数据可能丢失) | 是 | 否 | | 无序 | 是 | 否 | | 延迟 | 是 | 是 | | 抖动 | 是 | 是 | 不同类型的游戏对延迟的要求也有所不同。根据经验，对于大型多人在线角色扮演游戏（Massively Multiplayer Online Role-Playing Game，MMORPG），玩家能容忍 0.1 秒左右的延迟；对于多人在线战术竞技（Multiplayer Online Battle Arena，MOBA）类游戏，玩家对延迟的容忍度通常很低。 由于网络抖动，每个协议包对于服务器可能是每帧都在发，但是客户端可不是每帧都会按时接收到。 ### 客户端障眼法 就像魔术，虽然是假的，却能给观众带来快乐一样，尽管网络延迟不可避免，但是在客户端实施点障眼法，玩家就能收获良好的游戏体验。 ### 插值算法 客户端收到移动协议后，不会直接设置角色坐标，而是让角色慢慢往目标点移动。服务端在 0 秒、0.2 秒、0.4 秒时分别发送了 3 条移动协议，告诉角色 A、B、C 三个点。当客户端收到 B 点协议时，不直接设置位置，而是让角色慢慢走向 B 点；收到 C 点协议时，再慢慢走向 C 点。使用插值算法，就算是以 0.2 秒一次的低频率同步，玩家也能有较好的游戏体验。 作为障眼法的代价，插值算法比“直接设置位置”存在更大的误差，客户端第 0.4 秒才走到 B 点，0.6 秒才走到 C 点，增加了 0.2 秒的延迟，无论如何，比起来直接设置位置，0.2 秒的延迟是值得付出的。 ![客户端插值算法示意图](/files/9HwUrjx7ypXSiOI2xx9s) 当 0.2s 时刻接收到需要走到 B 点，走到 B 点需要 0.2s，所以走到 B 的时刻是 0.4s，0.4s 时理应又收到需要走到 C 点，走到 C 点有需要 0.2s，走到 C 点时刻已经 0.6s 了。 ### 缓存队列 单纯的插值算法还不能解决顿挫问题，例如 0.4s 发的移动到 C 的消息可能 0.4s 时刻根本不会到达，可能要延迟很久，这么一来移动就不连续。 假设插值算法增加了 0.2 秒的延迟，即收到移动协议后，让角色花 0.2 秒的时间从当前位置移动到新位置。那么角色从 A 点走到 B 点（很短的距离）花费的时间为 0.2 秒，从 B 点走到 C 点（较长的距离）花费的时间也是 0.2 秒，移动速度发生突变，故而会影响玩家体验。 ![单纯优化插值算法的情形](/files/P0VMIpp38cWNDdDRo9RH) 客户端可以通过缓存队列来缓解速度跳变的问题，收到移动协议后，不立即进行处理，而是把协议数据存在队列中，再用固定的频率（比如，每隔 0.2 秒）取出，结合插值算法移动角色。“缓存队列”相当于是在客户端加一层缓存来缓解网络抖动的问题，这样做能够有效提高玩家的游戏体验。 ![客户端通过缓存队列解决速度跳变问题](/files/TBZiWMxNPB6nC6F0WQCJ) 客户端还可以动态调整取出的速度，当队列里积累了较多数据时，可以稍微加快，当队列中的数据很少时，可以稍微减缓，从而可以更好地抵抗网络抖动。但比起单纯使用插值算法，缓存队列付出的代价是误差更大。 结合插值算法和缓存队列，单靠客户端的优化就能够解决大部分同步问题。对于误差敏感的游戏类型如射击类，还可以通过主动方优先的策略提高玩家的游戏体验。也正是如此我们可以看到很多射击类多人对战都有外挂，而向英雄联盟之类的策略性游戏就很少。 ### 主动方优先 插值算法、缓存队列会加大不同玩家所见画面的差异，客户端画面差异越大，“打不中”“莫名奇妙被打死”的问题越有可能发生。对于这种问题，一般会采取三种应对策略。 ![A击中B的三种同步方式](/files/pWGgfcTK9uFJDjphXVIy) * 第 1 种：不管客户端的误差，一切以服务端的计算为准。例如第 3 章的《球球大作战》，不论玩家看到怎样的画面，小球吃到哪个食物、碰到哪个敌人都由服务端裁决。这是一种最权威也是最难实现的方案，因为该方案要求服务端具备完全的运算能力。 * 第 2 种：信任主动方。客户端 A 发送“我击中了 B”的协议，只要不是偏差太大（例如，角色 A 和 B 隔得太远），服务端就认定 A 真的击中了 B。这种方式会提高玩家 A 的游戏体验，但玩家 B 可能会感到“莫名其妙被打死”。 * 第 3 种：信任被动方。客户端 B 发送“我被 A 击中”的协议。这种方式会提高玩家 B 的游戏体验，但玩家 A 可能会感到“明明瞄准了却打不中”。 有时因为项目期限和开发难度的限制，很多游戏的服务端并不具备完全的运算能力。《球球大作战》的位置、碰撞能由服务端进行运算，是因为游戏很简单，计算量不大，但如果游戏很复杂，那么开发难度就会很大。有些项目会让客户端发送位置坐标，服务端只做转发，这样能减少很多工作量。如果服务端不具备运算能力，那么我们通常会选择第 2 种方案。这是因为“主动方”玩家更具活力，更有价值，要优先照顾他们的感受。“被动方”说不定正处于挂机状态，可能并不在游戏屏幕前。 虽然误差不可避免，但可以通过“主动方优先”的策略来进行应对，提高重要玩家的游戏体验。但搞不好就会开挂的非常多，向 GTAOnline 简直都是挂 B。 ### 各类同步方案 状态同步、帧同步，它们都属于同步方案。 ### 三种同步方案 根据服务端的输入输出内容，同步方案可以分为三大类，即 * 指令->指令 * 指令->状态 * 状态->状态 游戏中可能会采用其中的一种或几种方案的组合，服务端既可能接收指令或状态的输入，也可能输出指令或状态。 如《球球大作战》中服务端的输入是客户端发来的摇杆方向，输出的是球的位置坐标，这种情况属于`指令->状态`同步。 比如一些射击游戏，客户端直接发送角色的位置坐标，服务端只进行转发，这种情况属于`状态->状态`同步。 | 方案 | 客户端运算能力 | 服务端运算能力 | | ------ | ----------------------------- | --------------------- | | 状态->状态 | 客户端运算，服务端转发有点，即时表现玩家体验好，但容易作弊 | 校验能力 | | 指令->状态 | 先行表现 | 服务端运算，有效杜绝作弊，服务端负载压力大 | | 指令->指令 | 帧同步，可以同步大量角色，容易错乱 | 校验能力 | 如《球球大作战》的`指令->状态`为例，由于所有的逻辑运算都在服务端，因此可以有效杜绝玩家作弊。 但是，如果玩家按下前进按键后，要等 0.2 秒才能看到效果(假设服务端的运算频率是每秒 5 次)， 那么玩家将会感到游戏体验不佳。`先行表现`也是一种常见的优化方法，在玩家按下前进的同时， 客户端就会让球向前移动，若稍后服务端发来的新位置与`先行移动`到的位置接近，就不管它， 如果相差太远，就在做调整。 ### 适用场景 不同的同步方案适用于不同的游戏。 | 游戏类型 | 最适用的方案 | 原因 | | ------------- | -------------------- | --------------------------------------------------------------------------------- | | 射击(FPS) | 状态->状态 | 对实时性要求高，玩家打出一枪后期待马上看到效果，用客户端运算的方案，能给玩家即时反馈，由于同一个场景的玩家可能很多，因此不适合用帧同步的方案 | | 即时战略(RTS) | 指令->指令(帧同步) | 需要同步大量单位，如果使用状态台同步，则意味着需要同步大量数据，而指令->指令 只需要同步小部分的操作指令 | | 竞技(MOBA) | 指令->指令(帧同步) | 对公平性要求较高，即对误差的要求较高，从原理看，帧同步可以保证多个客户端的误差很小 | | 角色扮演(MMORPG) | 指令->状态 | 同一个场景中的角色较多，不适合帧同步。如果需要较好地防止作弊，需要开发时间充裕，则最好使用指令->状态的方案 | | 开房间休闲类(球球大作战) | 指令->指令 或 指令->指令(帧同步) | 若对实时性要求较低，但对防作弊的要求较高，则适用 指令->状态 的同步方案。若需要同步大量单位，如球球大作战的基础上加个食物随机飘动的需求，则适合使用帧同步的方案 | ### 天涯明月刀 《天涯明月刀》是一款动作角色扮演类游戏，场景部分采用“状态-＞状态”的同步方案，辅之以服务端强校验 ![游戏天涯明月刀位置同步示意图](/files/GTdp31yyssxrOLtkZLwk) 不采用完全的“指令-＞状态”方案，是因为《天涯明月刀》的场景结构、技能触发规则都很复杂，如果完全由服务端运算，则负载太高，所以服务端通过采用低精度的地图数据和较低的运算频率来降低负载。虽然服务端的运算结果不是很精确，但它足以应对作弊行为。“服务端同步运算”也意味着较高的开发成本，为了在服务端处理 3D 大地图，开发团队花费了很多精力。 ### 王者荣耀 竞技游戏《王者荣耀》采用了“指令-＞指令”（帧同步）同步方案，一方面是为了保证游戏的公平性，需要选用误差较小的方案；另一方面是需要同步的单位较多，算上小兵，一屏可能会有数十个单位。 ![王者荣耀同步单位示意图](/files/Vg1HooOSXOz2ptHOvxZI) 《王者荣耀》选用帧同步也是经过了诸多因素的权衡，无论是“指令-＞状态”，还是《天涯明月刀》那样的服务端强校验，都会有较多的服务端开发工作。而《王者荣耀》开发初期工期很紧，选用“指令-＞指令”的同步方案，可以有效减少服务端的工作量，客户端除了底层的“帧同步”模块之外，其他业务逻辑就像做单机游戏一样，较为简便。另外，“帧同步”也较容易实现战场回放的功能，只用把一场战斗的所有指令存储起来，逐一播放即可。 帧同步对网络质量的要求很高，为降低延迟，《王者荣耀》所采用的协议是自研的可靠 UDP，关于可靠 UDP。 ### 绝地求生 包括《绝地求生大逃杀》，在内的射击游戏大多采用“状态-＞状态”同步的方案。射击游戏对即时反馈的要求很高，如果采用“指令-＞状态”的方式，那么数据经由服务端运算再传回，就会导致较高的延迟，从而影响玩家的游戏体验。此外，射击游戏对物理碰撞精度的要求较高，需要精准判断子弹是否打到敌人、子弹是否被掩体挡住等问题，出于性能考虑，服务端会采用较低精度的地图，因此这类游戏需要依赖客户端的运算能力。 帧同步方案不适用于这类游戏，因为地图很大，客户端难以完整计算整张地图的逻辑。使用“状态-＞状态”同步，客户端只需要关注玩家周围的事务即可，计算量较小。 依赖客户端运算的游戏一般很难防止外挂作弊，飞天外挂，人物可以很不自然地在天上飞。 ### 帧同步 如王者荣耀使用 指令->指令 同步方案，将计算量交给客户端。然是每个客户端的硬件配置和网络环境不同，对于相同指令。很难保证不同的客户端能有完全一样的计算结果。 例如，同样执行 向前走 的命令，运算能力强的客户端可能会让角色走得更远。帧同步 是一种综合技术，在`指令->指令`方案的基础上，增加了一些用于不同客户端能有相同 运算结果的机制，再配合客户端的障眼法、可靠 UDP 等，提供良好游戏体验。 ### 帧同步究竟是什么 让多名玩家同时操作，玩家 A 按下向右按钮，玩家 B 按下向左按钮，客户端将这些指令发送给服务端，每一回合，服务端都会收集指令，然后将它们组合广播出去，客户端收到后分别执行，将角色 A 右移，再将角色 B 左移，两个客户端的画面保持一致。 把每一回合称为一轮，假设每一轮的时间都是 0.1 秒，客户端虽然 0.1 秒才同步一次数据，但是可以用障眼法来提高游戏体验。比如，把每一轮分为 4 个表现帧，当客户端收到“以 10 米/轮”的速度向左移动 1 轮，会转换成以“2.5 米/帧”速度向左移动 4 帧。这种转换可以让玩家感觉像在连续移动。 ### 帧同步两大难点 1. 从客户端看，各硬件和软件环境不同，要保证 同样的输入 能有 同样的输出，例如，同样是“移动 0.1 米”，由于浮点数精度不同，“0.0999999999999979”表示“0.1”，有些则会用“0.0999755859375”表示。一次次的误差积累，时间一久，不同客户端的画面可能就会出现很大的差异。 2. 帧同步对网络质量的要求很高，每回合 0.1 秒，意味着如果延迟高于 100 毫秒，就基本没法玩了，100 毫秒是最大值，这就要求大部分时间延迟要低于 50 毫秒。 客户端发送给服务端的操作指令 ```lua local msg = { _cmd = "client_sync", --协议名 turn = 3, --轮 ops = { --操作指令 [1] = {"move",0,1}, --向(0,1)方向移动 [2] = {"skill",1001},--释放技能1001号技能 } } ``` 服务端收集所有客户端的操作之后，将广播“所有玩家在第 N 轮的操作指令”的协议 ```lua local msg = { _cmd = "server_sync", --协议名 turn = 4, --轮 --各玩家的操作指令 player = { [1] = { --玩家101的指令 playerid = 101, ops = { [1] = {"move",0,1}, [2] = {"skill",1001} } }, [2] = { --玩家103的指令 playerid = 103, ops = { [1] = {"move",1,1} } } } } ``` 服务端要管理很多场战斗，每场战斗需要对应一个战斗服务（战斗服），由战斗服来实现帧同步功能。每场战斗都会开启新的战斗服，如 agent 管理、登录服务。 战斗服需要保存几个数据，myturn 代表服务端当前的轮(回合数)，ops 用于保存整场战斗的操作指令，players 是玩家列表，用于记录参与战斗的玩家。 ```lua --战斗服全局数据 local myturn = 0 --轮 local ops = {} --客户端的所有操作 local players = {} --玩家角色列表 ``` 收到玩家的操作协议之后，战斗服先把其存入 ops 表，考虑到客户端可能出错，如发送了错误的轮数，对此进行一些判断，保证一旦存入玩家某一轮的操作，就不再变更。 ```lua --战斗服消息处理 --处理客户端协议 function msg_client_sync(playerid, msg) --丢弃错误帧 if myturn ~= msg.turn then return end local next = myturn + 1 --下一帧 ops[next] = ops[next] or {} --已经存入，不再变更 if ops[next][playerid] then return end --插入 ops[next][playerid] = msg.ops end ``` ```cpp 0------------------->101{} ops->1略 102{{"move",1,0}} 2略 103{{"skill",1003}} 3略 4-------->101{{"move",0,1},{"skill",1001}} 102{} 103{{"move",1,1}} ... ``` 只有战斗服保存了整场战斗的操作指令，才能实现战场回放、断线重连等功能，若要实现战场回放，只需要在战斗结束后，保存 ops 表，在需要回放时模拟发送协议即可； 若要实现断线重连功能，则需要把断线期间的所有指令都发给断线的客户端，让其还原状态。 保存了客户端协议后，还需要把协议适时广播出去，战斗服需要开启定时器，每隔一段时间，判断是否收集了全部玩家的操作，如果收集完整则广播协议。 ```lua --战斗服定时逻辑 --每隔0.1秒调用一次on_turn function on_turn() local next_turn = myturn + 1 --下一轮 local next_op = ops[next] --取指令 local count = #next_op --计算收集到的指令数 if count >= player_count then --player_count代表战场玩家总数 myturn = next--进入下一轮 smsg = tomsg(next_op)--生成消息 broadcast(smsg)--广播消息 end end ``` 上面的实现称为严格帧同步，因为每一轮要等到所有玩家都上报后，才能进行下一轮，服务端需要等待最慢客户端的数据，其实这显然是不现实的对于 P2P 局域网通信的联机游戏还有可能实现。严格帧的同步适用于网络环境很稳定且延迟较短的场景，如局域网对战类游戏，对于公网游戏，则需要做其他优化。 ### 确定性计算 各客户端软硬件环境不同，通过服务端控制进度(即轮数)可以解决运行速度差异的问题，但还是会存在几种可能的差异。 1. 浮点数精度 不同系统可能会使用不同的位数表示浮点数，精度不同。一种简单粗暴的方法是不适用浮点数，全部转为整数单数，如 “角色以 0.1 米/秒的速度移动 0.3 秒”，可以转换成“角色以 10 厘米/毫秒的速度移动 300 毫秒”，从而避免浮点数的运算。 2. 随机数 游戏经常会用到随机数，如技能有 30%的概率打出两倍伤害，如果客户端各自随机，那么结果也会有所不同，一种方法是，各客户端都使用同一套伪随机算法，具体做法是在战斗开始时，由服务端同步一个随机种子，然后基于相同的规则生成随机数。 3. 遍历顺序 如果使用“for(int i=0;i<100;i++)”的语句遍历数组，则可以确定数组的遍历顺序，但是如果使用 foreach 语句遍历数组，则不能完全保证顺序，foreach 只能保证把每个元素都遍历一遍，如果游戏逻辑依赖于遍历的顺序，foreach 可能会导致不同的计算结果。 4. 多线程、异步和协程 由于多线程、异步和协程的调度并不由开发者控制，因此如果游戏逻辑中使用这些技术，需要特别注意不同时间执行线程、异步和协程代码是否会导致不同的运算结果。 帧同步公式 ```cpp 相同的初始状态+求和(相同指令x相同规则)=相同的运行结果 |1.逻辑上，同样的时间间隔 |2.同样的浮点数精度 |3.同样的随机种子和算法 ``` ### 乐观帧同步 严格帧同步看似很好，它让快的客户端等待慢的，客户端误差很小，但网络环境不好，快的客户端就会频繁等待，体验糟糕。公网环境下，一般会采用 定时不等待 的策略，即乐观帧同步。 乐观帧同步 是指服务端定时广播操作指令，推进游戏进程，而不必等待慢的客户端。 ```lua --每隔0.1秒调用一次 function on_fixed_trun() mytrun = myturn + 1 next_op = next_op[myturn] smsg = tomsg(frame) broadcast(smsg) end ``` 不过乐观帧同步采取的收集策略更为复杂。 ```lua --乐观帧同步，战斗服消息处理 --收到客户端协议时 function msg_client_sync(playerid, msg) local next = myturn + 1 --太旧的不要，客户端是在太慢了 if msg.turn < myturn - 5 then return end --防止同一玩家同一轮的操作被覆盖 --用recv记录已经收到哪个玩家哪一轮的协议 recv[msg.turn] = recv[msg.turn] or {} if recv[msg.turn][playerid] then return end recv[msg.turn][playerid] = true -- 插入 ops = frames[next][playerid] ops = append(ops , msg.ops) --把msg.ops插入ops中，下一帧发出去 end ``` 乐观帧同步可以牺牲慢玩家的游戏体验为代价，以保证整体的正常运行。 无论采用哪种策略，帧同步都要保证处于同一轮的客户端有同样的状态，但由于快的客户端不再等慢的，因此客户端之间可能会有轮数的差异，进而导致游戏画面存在差异，可以设定最大允许的轮数差异，如果某客户端比别人慢 20 轮，实在慢的无药可救，只能踢出游戏，让玩家重连，重新进入战斗等。 ### AOI 算法 算法 AOI（Area of Interest，感兴趣区域）。射击游戏《绝地求生大逃杀》场景很大，且每个场景通常都会拥有大量角色，由于需要同步的消息量通常会很大，因此服务端要承受巨大的广播压力。如果战场中有 50 名玩家，每人每秒更新 5 次位置，那么服务端每秒要发送`50×50×5=12500`条位置协议，压力很大。一个场景放置了几百上千的怪物，如果这些怪物的信息要一次性同步给玩家，服务端的性能压力非常大。AOI 算法可以有效地缓解该问题。 ### 感兴趣区域 AOI 算法可以翻译成“感兴趣区域”算法，它基于角色扮演(MMORPG)、射击(FPS)类游戏“角色仅关心周为事务”的事实。在角色扮演游戏中，玩家只能与 附近的 NPC 和其他玩家进行交互，射击游戏也是如此，只能攻击较近的敌人，离得太远玩家根本看不到它们。 ### 实体模型 要使用 AOI 算法，需要规划好场景的抽象，玩家、NPC、怪物都能在场景中走动，而且只能与附近的元素进行交互。场景中的元素为了统一处理，实体模型的类结构会把角色、NPC、怪物都作为实体的派生类。 ```cpp //实体模型的类结构图 Entity(实体) Role(角色) NPC Monster(怪物) ... ``` 实体类至少包含 id、x、y 属性，包含 moveto、get\_sight 两个方法。调用 get\_sight 可以获取实体感兴趣区域内的其他实体。 ```lua function entity() local e = { --属性 id = 101, x = 120, y = 180, --方法 moveto = function(x,y) ... get_sight = function() ... --回调 on_enter_sight function(id) ... on_leave_sight function(id) ... } return e end ``` 实体类还可以包含 on\_enter\_sight 和 on\_leave\_sight 两个回调，当有实体进入或走出感兴趣范围时，就会分别调用 on\_enter\_sight 或 on\_leave\_sight 方法。 若 F 向左移动进入 A 的感兴趣区域，实体类就会调用 A 的 on\_enter\_sight 方法。当调用 on\_enter\_sight 方法时， 服务端就会通知客户端执行加载模型资源的操作，相反，当调用 on\_leave\_sight 方法时， 服务端就会通知客户端执行卸载资源的操作，以节省内存。 做好抽象后，根据具体的实现方式，这些方法和回调可能会有不同的运行效率，但不会影响上层的游戏逻辑。 AOI 的具体实现方法有很多种，其中最简单粗暴的方法是，调用 get\_sight 时，遍历场景中所有的实体， 只返回距离较近的实体，但显然这种做法效率较低。“九宫格”是一种业内常用的、效率较高的算法。 ### 九宫格法 九宫格是一种常用的 AOI 算法，能通过较低的计算复杂度寻找角色周围的实体。先把游戏场景划分成一个个小格子，格子尺寸依照客户端一屏能看到的范围而定。 ```lua space = { --格子 ceils = { [0] = { [0] = {101, 102}, [1] = {}, ... [7] = {}, }, [1] = { [0] = {}, ... [7] = {}, }, ... } } [0,0][0,1][0,2][0,3][0,4][0,5] [1,0][1,1][1,2][1,3][1,4][1,5] [2,0][2,1][2,2][2,3][2,4][2,5] [3,0][3,1][3,2][3,3][3,4][3,5] ``` 可以把角色周围的 9 个格子当作它的感性区域，如果客户端角色位于 s(1,2)格子内，那么其上下左右周围的其他 8 个方格共 9 个都是其感兴区域，直接在 space.ceils 内查找就行了获取它感兴趣的实体，运行效率为 O(1)。 为了保证 space.ceils 中实体数据的正确性，在角色移动时，需要同时维护 space.ceils 表，开销也不大。由于角色的位置具有连续性，因此可以认为它移动前后要么是在同一个格子中，要么就是在周围的 8 个格子中，总共有 9 种情况，因此称为“九宫格”。 如果移动前后角色在同一个格子中，则无需进行特殊处理，如果角色向右跨过格子，则需要给左边三个格子内实体发“离开”的通知。再给右边三个格子的实体发“进入”的通知。 ```lua --九宫格算法lua function moveto(x, y) local ceils = space.ceils --新坐标所在的格子 local new_cx, new_cy = get_ceil_idx(x, y) --旧坐标所在的格子 local old_cs, old_cy = get_ceil_idx(self.x, self.y) --保证格子连续地移动 if math.abs(new_cx - old_cx) > 1 or math.abs(new_cy - old_cy) > 1 then return end --移动 self.x = x self.y = y --九种情况 --情况1：还在原来的格子 if new_cx == old_cx and new_cy == old_cy then --无需处理 end --情况2：向右走 if new_cx == old_cx+1 and new_cy == old_cy then --通知左边三个格子离开 on_leave(self.id, ceils[old_cx-1][old_cy-1]) on_leave(self.id, ceils[old_cx-1][old_cy]) on_leave(self.id, ceils[old_cx-1][old_cy+1]) --从原来格子离开 remove(self.id, ceils[old_cx][old_cy]) on_enter(self.id, ceils[old_cx+2][old_cy-1]) on_enter(self.id, ceils[old_cx+2][old_cy]) on_enter(self.id, ceils[old_cx+2][old_cy+1]) --添加到新的格子中 add(self.id, ceils[new_cx][new_cy]) end --更多情况... --向周围9个格子广播移动协议 broadcast_move(self.id, ceils[new_cx][new_cy]) broadcast_move(self.id, ceils[new_cx+1][new_cy]) .... end ``` 对于场景很大、角色很多的游戏，使用 AOI 算法不仅能够减少广播量，还能用它减少物理碰撞的计算量。如球球大作战为例，小球只会与周围的球发生碰撞、只能吃到周边的食物，若使用 AOI 算法，则只需要检测小球是否与感兴趣区域内的实体发生碰撞即可。 ### 可靠 UDP 无论采用哪种同步方案，无论是否使用 AOI 算法，网络延迟总是越低越好。特别是帧同步，基本要求网络延迟能稳定在 50 毫秒以内，而 TCP 即使禁用 nagle 算法也很难达到这个要求。在 C++中，禁用 Nagle 算法通常涉及到设置 TCP 套接字选项。Nagle 算法的目的是在发送小数据包时将它们组合成更大的数据包，以提高网络效率。但在某些情况下，禁用 Nagle 算法可能更有利，比如对于实时性要求较高的应用程序。 ```cpp // 设置套接字选项禁用Nagle算法 int flag = 1; if (setsockopt(sockfd, IPPROTO_TCP, TCP_NODELAY, (char*)&flag, sizeof(int)) == -1) { std::cerr << "Error setting TCP_NODELAY option\n"; close(sockfd); return 1; } ``` ### 三角制约 通信领取的三角制约关系，是指无论使用何种方法，通信的“低延迟”、“低带宽”、“可靠性”不可三者兼得。 * UDP:低延迟，可靠性差，带宽高 * TCP:高延迟，可靠性高，带宽高 假设 A 端在同一时间发送了三份一字节数据，UDP 直接发送它们，不管它们是否能正常到达对端；TCP 则会先发送一字节，等收到 B 端的确认信号之后再发送下一个字节（假设滑动窗口设置为 1），如果在指定时间内没有收到确认信号，则说明数据可能丢失，需要重传。TCP 的延迟高于 UDP，由于增加了确认信号机制，贷款也会随之增加。 由于运营商 提速降费 的背景下，低带宽 称为一个可以权衡的因素，“低延迟 可靠 高带宽”的通信协议更加符合游戏的需求，较为普遍的做法是在 UDP 的基础上，增加一些可靠性的机制如，UDP 将每一份数据发送 3 次，就算某份数据未能到达，也还有另外的备份，虽然牺牲了带宽，但降低了数据丢失的概率，还可以在此基础上增加确认重传的机制，实现低延迟的可靠 UDP。 几种现成方案，实际项目，大多会使用一些现有的第三方可靠 UDP 方案。 ### 几种现成方案 | 方案 | 说明 | | ------ | ---------------------------------------------- | | KCP | 该协议以比 TCP 多浪费 10%\~20%的带宽为代价，换取平均延迟降低 30%\~40% | | QUIC | 由谷歌推出的可靠 UDP | | ENet | ENet 是一个相对轻量、简单可靠的 UDP 通信库 | | RakNet | RakNet 是一个基于 UDP 的网络库，起初是为游戏开发而设计的 | | UDT | 基于 UDP 的可靠网络协议 | KCP 已用于很多款商业游戏，证明它是行之有效的，原始算法由 C++编写，只有两个源文件，非常便于 集成到服务端系统中。 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://gaowanlu.gitbook.io/note/you-xi-ye-wu/func_dev_readme/part20.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.