「毁灭战士3」源码就是“保持简洁”的证明 - 文章 - 伯乐在线
& 「毁灭战士3」源码就是“保持简洁”的证明
假如你在网上搜最好的C++源代码。「毁灭战士3 | Doom 3」的源代码肯定会被提到好多次，这篇就来证明此事。
我花了一些时间通读了 DOOM3 的源代码。这可能是我见过的最干净最漂亮的代码了。
DOOM3是公司开发 发行的视频游戏。该游戏为id Software赢得了商业上的成功，已售出350万多份拷贝。
在日，id Software维持开源传统，发布了他们上一个引擎的。这份源代码已经被很多开发者审查，这里就有个fabien反馈的例子（）：
DOOM3 BFG是用C++写的，一种庞大的语言，它既能写出优秀的代码，但也让人憎恶到眼睛流血。幸运的是，id Software退而求其次，使用C++子集，接近于“带类的C”，如以下几条约束：
没有引用（使用指针）
使用常量（Const everywhere）
很多C++专家不建议使用“带类的C”这样的方法。然而，DOOM3从2000开发至2004，没有使用任何现代C++机制。
让我们使用 CppDepend 来看看源代码，探索它得特别之处。
DOOM3有少量的几个工程组成，这儿有它的工程列表和一些类型统计。
这里还有他们之间的依赖关系图：
DOOM3定义了很多全局函数。但是，大部分内容实现是在类中。
数据模型使用结构体定义。为了在源代码中对结构体的使用有个更具体的理解，在下图中将它们以蓝色分块显示出来。
在图表中，代码被表示为树形图，树形图表示法能使用嵌套的矩形来表示树状结构。而树结构用来表示代码分层结构。
工程包含命名空间。
命名空间包含类型。
类型包含函数和域（field）。
我们可以观察到它定义了许多的结构体，比如DoomDLL 40%的类型都是结构体。它们被有条理地用来定义数据模型。该实践已经被很多工程所接受，这种方法有个最大的缺点是多线程应用，结构体的public变量并非不可改变的。
为何支持不可变对象，有个重要原因：能显著地简化并发编程。考虑下，写个合格的多线程程序是个艰巨的任务吗？因为很难同步线程访问资源（对象或者其他OS资源）。为什么同步这些操作很困难呢？因为很难保证在资源竞争状态下多线程对多个对象进行正确的读写操作。假如没有写操作呢？换句话说，线程只访问这些对象，而不做任何变动？这样就不再需要同步操作了！
让我搜索下只有一个基类的类：
几乎40%的结构体和类都只有一个基类。通常，OOP（面对对象编程）使用继承的好处之一是多态，下面蓝色标明了源代码中的虚函数：
超过30%的函数是虚函数。少数是纯虚函数，下面是所有虚基类列表：
只有52个类被定义为虚基类，其中35个类只是纯接口，也就是这些接口都是纯虚函数。
我们来搜搜使用了RTTI的函数
只有非常少的函数使用了RTTI。
为保证只使用OOP最基础的概念，不使用高级设计模式，不过度使用接口和虚基类，限制了RTTI的使用并且数据都定义为结构体。
至此这份代码跟很多C++开发者所批评的“带类的C”没太大区别。
其开发者的一些有趣的选择，帮助我们理解它的奥秘：
1-为有用的服务提供公用的基础类。
许多类是从idClass继承下来的：
idClass提供如下服务：
创建实例化
2-方便的字符串操作
一般来说，字符串是一个项目里用的最多的对象，许多地方需要使用它，并且需要函数来对其进行操作。
DOOM3定义了idstr类，几乎包含了所有用的字符串操作函数，无需再自己定义函数来接受其它框架所提供的字符串类。
3-源代码与GUI框架（MFC）高度解耦
很多工程用了MFC后，它的代码就会与MFC类型高度耦合，并且在代码的任何一处都能发现MFC类型。
在DOOM3里，代码和MFC是高度解耦的，只有GUI类才会直接依赖它。下面的CQLinq查询可以展示这点：
这样的选择对生产力有很大的影响。事实上，只有GUI开发者才会关心MFC框架，其它开发者不应该被强制在MFC上浪费时间。
4-提供了非常好的公共函数库（idlib）
几乎在所有项目中都会用到公共工具类，就如以下查询的结果：
正如我们所看到经常使用的就是公共工具类。假如C++开发者不使用一个良好的公共工具框架，那就会为解决技术层面问题花费大部分的开发时间。
idlib提供了很多有用的类用于字符串处理，容器和内存。有效促进了开发者的工作，并且能让他们更多的关注在游戏逻辑上。
5-实现非常易于理解
DOOM3实现了非常难的编译器，对于C++开发者而言，开发语法解析器和编译器不是件轻松的事。尽管如此，DOOM3的实现非常容易被理解并且编写得十分干净。
这儿有这些编译器的类的依赖图：
这儿还有编译器源代码的代码片段：
我们也看过许多语法解析器和编译器的代码，但这是第一次我们发现编译器是如此得容易理解，和整个DOOM3源代码一样。这太神奇了。当我们探究DOOM3源代码时，我们忍不住会喊：喔，这太漂亮了！
即使DOOM3选择了很基础的设计，但它的设计者所做的决定都是为了开发者能更多的关注游戏逻辑本身，并且为所有技术层面的东西提供便利。这提高了多大的生产力啊。
无论何时使用“带类的C”，你应该明白你自己在干什么。你必须像DOOM3的开发专家一样。但不推荐初学者忽视现代C++建议而冒险。
关于作者：
可能感兴趣的话题
这里面用的是vs 编辑器么，还可以用SQL 来查看代码。Doom 的代码看着确实挺舒服的，只用最基本的c++，挺好。
关于伯乐在线博客
在这个信息爆炸的时代，人们已然被大量、快速并且简短的信息所包围。然而，我们相信：过多“快餐”式的阅读只会令人“虚胖”，缺乏实质的内涵。伯乐在线内容团队正试图以我们微薄的力量，把优秀的原创文章和译文分享给读者，为“快餐”添加一些“营养”元素。
新浪微博：
推荐微信号
（加好友请注明来意）
– 好的话题、有启发的回复、值得信赖的圈子
– 分享和发现有价值的内容与观点
– 为IT单身男女服务的征婚传播平台
– 优秀的工具资源导航
– 翻译传播优秀的外文文章
– 国内外的精选文章
– UI,网页，交互和用户体验
– 专注iOS技术分享
– 专注Android技术分享
– JavaScript, HTML5, CSS
– 专注Java技术分享
– 专注Python技术分享
& 2017 伯乐在线近期游戏热闻(3/3) DOOM3 网络架构 - 知乎专栏
{"debug":false,"apiRoot":"","paySDK":"/api/js","wechatConfigAPI":"/api/wechat/jssdkconfig","name":"production","instance":"column","tokens":{"X-XSRF-TOKEN":null,"X-UDID":null,"Authorization":"oauth c3cef7c66aa9e6a1e3160e20"}}
{"database":{"Post":{"":{"contributes":[{"sourceColumn":{"lastUpdated":,"description":"因为热爱游戏，所以不管玩游戏也好，做游戏也罢，能把人生当游戏，不断地探索新的乐趣，并以此为生，此之谓“游戏于人间”。 \n\n而立之后，时常感叹交流得太少。若能常漫步于游戏人之间，分享心得体会，不失为一趣，寓“行走于游戏人之间”之意。","permission":"COLUMN_PUBLIC","memberId":376263,"contributePermission":"COLUMN_PUBLIC","translatedCommentPermission":"all","canManage":true,"intro":"游戏开发相关的随笔","urlToken":"gu-lu","id":8105,"imagePath":"2b4ab237b72d9adc998f0c2e6f3559b5.jpeg","slug":"gu-lu","applyReason":"","name":"游戏人间","title":"游戏人间","url":"/gu-lu","commentPermission":"COLUMN_ALL_CAN_COMMENT","canPost":true,"created":,"state":"COLUMN_NORMAL","followers":5626,"avatar":{"id":"2b4ab237b72d9adc998f0c2e6f3559b5","template":"/{id}_{size}.jpeg"},"activateAuthorRequested":false,"following":false,"imageUrl":"/2b4ab237b72d9adc998f0c2e6f3559b5_l.jpeg","articlesCount":38},"state":"accepted","targetPost":{"titleImage":"/7ca3edba68e_r.jpg","lastUpdated":,"imagePath":"7ca3edba68e.jpg","permission":"ARTICLE_PUBLIC","topics":[,41002],"summary":"本文是系列的第三篇：本文绝大部分为较简短的记录，进一步的描述请。架构客户端把输入采样等玩家动作发给服务器，服务器回之以 PVS 内的压缩后的状态快照。C/S 架构图 Doom3 做到了…","copyPermission":"ARTICLE_COPYABLE","translatedCommentPermission":"all","likes":0,"origAuthorId":0,"publishedTime":"T22:47:20+08:00","sourceUrl":"","urlToken":,"id":975114,"withContent":false,"slug":,"bigTitleImage":false,"title":"(3/3) DOOM3 网络架构","url":"/p/","commentPermission":"ARTICLE_ALL_CAN_COMMENT","snapshotUrl":"","created":,"comments":0,"columnId":8105,"content":"","parentId":0,"state":"ARTICLE_PUBLISHED","imageUrl":"/7ca3edba68e_r.jpg","author":{"bio":"程序猿一枚 : )","isFollowing":false,"hash":"ba6dba6ce8c68be8fdbb15","uid":52,"isOrg":false,"slug":"mc_gulu","isFollowed":false,"description":"","name":"顾露","profileUrl":"/people/mc_gulu","avatar":{"id":"v2-dde66a7e5c8c0fec9a020cde8a1a2bef","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},"memberId":376263,"excerptTitle":"","voteType":"ARTICLE_VOTE_CLEAR"},"id":411119}],"title":"(3/3) DOOM3 网络架构","author":"mc_gulu","content":"本文是系列的第三篇：本文绝大部分为较简短的记录，进一步的描述请。架构客户端把输入采样等玩家动作发给服务器，服务器回之以 PVS 内的压缩后的状态快照。C/S 架构图Doom3 做到了同样的玩家输入序列总是能产生同样的结果，因为以下两点得到了保证：除玩家输入外整个系统的确定性 (system-wide deterministic)不管渲染性能如何，整个游戏的逻辑状态总是以 60 fps 的频率更新C/S 时间线服务器以 10-20 Hz 的频率向客户端发状态快照。由于快照是一个 rtt 之前的状态，客户端需要回到那个时间点上去处理这个“过去的”状态，然后再基于这个状态重新预测并刷新所有物体在当下的状态，如下图：预测示意图 (Prediction at the client with a snapshot rate at 20Hz and a ping of around 80 milliseconds)由于玩家输入的频率 (input per second) 远低于逻辑处理的频率 (60 Hz)，一个合理的推论是，最接近当下的几个逻辑帧，继续沿用与之前同样的输入一般是安全的。客户端使用服务器同步过来的其他玩家的输入来预测其接下来的运动，这些物理响应的机制与服务器上的真实逻辑是一致的。与 Quake 3 不同的是，玩家在屏幕上看到的渲染结果与真实的逻辑状态是无时差的 (注意是无时差而不是 100% 绝对准确)，因此不需要像 Q3 那样在本地延时比较大时需要充分考虑提前量，因为系统把下发同步的预测也完全实现了。系统的确定性保证了服务器和客户端可以运行完全一致的逻辑 (dead reckoning)，因此得到至少与服务器上一样好的行为预测结果。Quake 3 的 bot 已经展示了通过算法来预测玩家移动可以达到什么样的程度，即使用慢速导弹武器 (火箭筒 RL) 也可以非常精确地命中。(Q3 bot 使用考虑碰撞检测的简化物理逻辑来预测玩家在之后的位置)与 Quake 3 不同，Doom 3 的服务器和客户端使用同一份代码来更新/预测实体的状态，这样不用担心早先提到的互相干扰，开发新的单人模式 (并兼容多人) 也变得更简单了。通信基于 UDP 的轻量级 reliable / unreliable 实现 (最小化额外负担)对于大多数状态同步而言，像 TCP 那样重发价值不大，因为被重发的状态十有八九因为过期已经不再有意义。Doom 3 实现了下面这样一个基于 UDP 特性的 FPS 通信架构层次结构图上行和下行均为单连接，同时可发送 reliable & unreliable 的消息 (前者确保抵达)，后者用于输入 (c2s) 和状态 (s2c) 的同步，只有非常特定和关键的消息使用可靠方式发送。这个网络系统被设计为不间断地生成一个不可靠消息流 (unreliable stream) (包括 10-20Hz 的状态同步和更高频的输入同步)，可靠消息被驼运 (piggy back) 在这个不可靠消息流上 (蚂蚁搬家)。具体实现上，可靠消息被先缓存在队列里，每一个都由一个不可靠消息搭载着发出，ack 后再发下一个 (ack 直接借用了对面过来的 unreliable stream) 这样整个信道实现了最重要的保证：(通过1:1的驼载)任何一条可靠消息总是能在首个紧接着的不可靠消息之前抵达。 (the message channel guarantees that a reliable message arrives before the first next unreliable messages comes through)此外，对于不可靠的信息流，客户端的发送频率比服务器高3-4倍 (可靠消息的运输和响应能力)，这样的话来自服务器的可靠消息是不需要 timeout 机制的，因为接下来的几个客户端消息没有 ack 的话，服务器就可以直接重发了。Unreliable Message Headers整个系统的大部分信息是来自服务器的状态快照 (Snapshots) 和来自客户端的玩家输入 (User Commands)，这些业务数据都通过 unreliable message 传递。(message header 如下图所示)服务器：32 位 game id 里包含了游戏本身的识别 id，地图信息和关键的业务设置8 位的 message type 用来区分本条消息的类型。客户端：首个 seq id 是最近收到的服务器消息的序列号 (用于 ack)，unreliable message 本身是不需要 ack 的，但是当需要的时候，服务器可以在特定的时间点上用这个 seq id 检查客户端是否有及时的反馈。game id 用于环境的合法性校验，没通过校验的话，服务器会追加一条完全配置信息，用于指导客户端去尝试进入正确的环境。快照的 seq id 用于差异压缩 (delta compression)同样也有 message type。快照 (snapshots)下图是下发快照的构成和完整的操作序列：快照包含的几项关键信息：序列号 (seq id)帧编号 (frame id)帧时刻 (frame time)客户端领先的时间量 (client ahead time, 参考客户端最近一次发上来的时刻及延时)实际的业务数据信息 (以下信息均做了差异压缩)：entity states 是与上次快照相比较的状态变化pvs bit string 是 pvs 的完整可见状态列表 (这个信息由服务器随时下发更新)pvs 无关的游戏状态更新其他玩家的指令信息用户指令 (User Commands)下图是上行的用户指令构成和完整的操作序列：调试用的客户端预测毫秒数这一组用户指令中，第一个的所在帧编号后续的每个 user command 对应接下来的一帧，反映了输入的变化差异压缩Bit Packing移除逻辑上的无用位。如 Health (HP) 虽然是 32 位整形，但实际在 0-100之间，只需 7 位就够了。浮点精度大部分取值范围不大的情况下 (如实体的移动速度，角度，朝向等) 只需要半精度。差异压缩 (Delta Compression)变量级的差异压缩。如果一个变量没变过，就写一个 0 (1 bits) 如果变过，就写 1 (1 bits) + 实际变量内容 (bit packed)实体级的差异压缩。快照之间的差异比较基于一个包含完全实体信息的公共基 (common base)当进出某个客户端的 pvs 时开始/结束同步pvs 差异压缩。每个实体 1 bit 则 4096 个完整信息会消耗 512 字节由于不同帧之间 pvs 变化不大，可以按组压缩，每组 32 bits如果任何一组没有实体进出 pvs，写个 0 (1 bits)假设 pvs 没有任何变化，4096 个对象只需要 16 字节客户端随着 User Commands 上报的 ack 频率远高于下发快照的频率，所以丢包也没关系。服务器一旦收到 ack 就可以更新公共基并用 reliable message 通知客户端做同样的改动，驼运机制保证了 reliable message 总是先于新快照抵达客户端，这样被 ack 的快照总是能在处理新快照前被用于更新客户端的公共基。这样，公共基的状态维护就可以保证是整体上同步的消息压缩 (0-compressor)上面的差异压缩会产生大量的 0 (没有变化)，所以开销最小也最有效的压缩是针对 0 的特殊处理。每次处理 3 位，如果中间有一位不为 0 就保持不变，否则继续读，直到遇到不为零的情况，此时写下三个零 (3 bits) 和重复次数 (3 bits)最大压缩比为 4:1，这里可以用不同的位数但 3 被验证为实际压缩比最高的。举个例子：000'000'000'010'000'000'000'000'110'000'000'000'000'000会被压缩为000'011'010'000'100'110'000'101这个例子里压缩比为 14:8。反过来也可以针对这种压缩方式对快照中的变量排列进行优化。把变量按照改变频率分组放在一起，以促使产生更多的连续 0。效果bit packing: 10-15%delta compression: 90%+zero-compressing: 15-50%更多的潜在改进快照的公共基是从空状态开始的，实际上对于任何一个已加载地图，可以从一个已完全初始化的状态开始，避免一上来的流量开销一些使用 reliable 的事件只要不影响游戏的逻辑进行 (如特效，光照等) 可以改成 unreliable 并缓存一下一些本来是同步过来的实体本质上只是游戏逻辑的衍生，是可以由客户端自行维护的客户端的预测可以改得更加细粒度开发者应可更容易指定哪些不需要预测 (直接使用快照的插值)可以随时关掉某个实体的同步 (比如挂了的怪物) 纯粹由客户端接管可以把所有的实体以同样的频率更新加以改进，让那些不那么重要的实体以较低的频率更新 (LOD-syncing)对于不重要的实体，客户端的多帧预测往往可以合并为较少的较大帧 (降低运算量)[系列完]Gu Lu[]","updated":"T14:47:20.000Z","canComment":false,"commentPermission":"anyone","commentCount":0,"collapsedCount":0,"likeCount":140,"state":"published","isLiked":false,"slug":"","lastestTipjarors":[{"isFollowed":false,"name":"TsingsonQin","headline":"闲居深圳,喜欢懒睡/摄影/越野/口琴/音乐, 越野e族深圳切大队成员，2016年广东口琴嘉年华的策办人, 深圳第一家专职口琴培训机构创办人, IPTV/OTT类高效分布式点播直播平台技术咨询(曾于UTstarcom经历8年的IPTV架构师/产品线经理, 前视维IPTV产品经理/总架构师)","avatarUrl":"/v2-62b10ddde141c70b2dde17e_s.jpg","isFollowing":false,"type":"people","slug":"tsingson","bio":" 口琴音乐/亲子启智/户外越野/黑白摄影","hash":"2ee1b877a29c4683bdc6","uid":00,"isOrg":false,"description":"闲居深圳,喜欢懒睡/摄影/越野/口琴/音乐, 越野e族深圳切大队成员，2016年广东口琴嘉年华的策办人, 深圳第一家专职口琴培训机构创办人, IPTV/OTT类高效分布式点播直播平台技术咨询(曾于UTstarcom经历8年的IPTV架构师/产品线经理, 前视维IPTV产品经理/总架构师)","profileUrl":"/people/tsingson","avatar":{"id":"v2-62b10ddde141c70b2dde17e","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false}],"isTitleImageFullScreen":false,"rating":"none","titleImage":"/7ca3edba68e_r.jpg","links":{"comments":"/api/posts//comments"},"reviewers":[],"topics":[{"url":"/topic/","id":"","name":"网络编程"},{"url":"/topic/","id":"","name":"游戏开发"},{"url":"/topic/","id":"","name":"游戏编程"}],"adminClosedComment":false,"titleImageSize":{"width":378,"height":237},"href":"/api/posts/","excerptTitle":"","column":{"slug":"gu-lu","name":"游戏人间"},"tipjarState":"activated","tipjarTagLine":"觉得有用就请我喝 1/3 杯咖啡吧 :)","sourceUrl":"","pageCommentsCount":8,"tipjarorCount":1,"annotationAction":[],"hasPublishingDraft":false,"snapshotUrl":"","publishedTime":"T22:47:20+08:00","url":"/p/","lastestLikers":[{"bio":" 口琴音乐/亲子启智/户外越野/黑白摄影","isFollowing":false,"hash":"2ee1b877a29c4683bdc6","uid":00,"isOrg":false,"slug":"tsingson","isFollowed":false,"description":"闲居深圳,喜欢懒睡/摄影/越野/口琴/音乐, 越野e族深圳切大队成员，2016年广东口琴嘉年华的策办人, 深圳第一家专职口琴培训机构创办人, IPTV/OTT类高效分布式点播直播平台技术咨询(曾于UTstarcom经历8年的IPTV架构师/产品线经理, 前视维IPTV产品经理/总架构师)","name":"TsingsonQin","profileUrl":"/people/tsingson","avatar":{"id":"v2-62b10ddde141c70b2dde17e","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},{"bio":"系统性设计 设计师↙点“查看详细资料”","isFollowing":false,"hash":"e5c953cbdfe","uid":88,"isOrg":false,"slug":"herosone1","isFollowed":false,"description":"普通人请看答案和设计专栏！\n正义之士看收藏夹，其他是给你懂的看的。\n关注本人则会被垃圾信息淹没！/\n《挑战者II天幕之战》1999年，设计师设计了保护罩封锁地球，但他的真正身份却是另一时空的叛军领袖，已经逐渐消逝的记忆，却在一偶然机会被唤起……/\n逼乎网，装逼有道理就牛逼，爱因斯坦吹牛和现实一致就牛逼。/\n果壳网流氓神猫也是我，果壳日志已禁用，故于日志里回复最近发生的事，由于只能回复100页，所以从最后一日志倒过来在每个日志写回复。政治不便写云里雾里，技术性文章是清晰的。/\n这不是小学，答案看不懂不教。我的答案很快精简删除只保留对自己有用的。/\n学多久才能随心所欲？所以我设计很快很贵。\n凡人畏果菩萨畏因。舍利子，是诸法空相…\n天之道损有余而补不足。人道反之。孰能有余以奉天下？其唯有道者。","name":"herosone1","profileUrl":"/people/herosone1","avatar":{"id":"9dab99e26dc2578ddfc839d7c6d1dd92","template":"/{id}_{size}.png"},"isOrgWhiteList":false},{"bio":"gamer","isFollowing":false,"hash":"57d8b31cd43d182fdcede048","uid":44,"isOrg":false,"slug":"tang-xiao-ming-24-63","isFollowed":false,"description":"","name":"唐小明","profileUrl":"/people/tang-xiao-ming-24-63","avatar":{"id":"da8e974dc","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},{"bio":"成为一个很厉害很厉害很厉害的人。","isFollowing":false,"hash":"ace6ff613c366d19dc4b8eba","uid":40,"isOrg":false,"slug":"cai-shu-xue-qian-78","isFollowed":false,"description":"燃烧殆尽，总好过黯然消失","name":"渡边彻","profileUrl":"/people/cai-shu-xue-qian-78","avatar":{"id":"da8e974dc","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},{"bio":null,"isFollowing":false,"hash":"cbdad1726","uid":72,"isOrg":false,"slug":"hu-chen-shuo","isFollowed":false,"description":"Jake","name":"胡宸硕","profileUrl":"/people/hu-chen-shuo","avatar":{"id":"v2-1c5f1c33a92d6c1dbce035","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false}],"summary":"本文是系列的第三篇：本文绝大部分为较简短的记录，进一步的描述请。架构客户端把输入采样等玩家动作发给服务器，服务器回之以 PVS 内的压缩后的状态快照。C/S 架构图 Doom3 做到了…","reviewingCommentsCount":0,"meta":{"previous":{"isTitleImageFullScreen":false,"rating":"none","titleImage":"/50/2ffcda3ae0b0f_xl.jpg","links":{"comments":"/api/posts//comments"},"topics":[{"url":"/topic/","id":"","name":"游戏编程"},{"url":"/topic/","id":"","name":"游戏开发"},{"url":"/topic/","id":"","name":"网络编程"}],"adminClosedComment":false,"href":"/api/posts/","excerptTitle":"","author":{"bio":"程序猿一枚 : )","isFollowing":false,"hash":"ba6dba6ce8c68be8fdbb15","uid":52,"isOrg":false,"slug":"mc_gulu","isFollowed":false,"description":"","name":"顾露","profileUrl":"/people/mc_gulu","avatar":{"id":"v2-dde66a7e5c8c0fec9a020cde8a1a2bef","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},"column":{"slug":"gu-lu","name":"游戏人间"},"content":"这一篇是上一篇的自然延续，但内容上独立成篇，实际上描述了 id software 从 DOOM 1 开始的若干款 FPS 游戏在网络架构方面的演化。同样的，更多的细节可参考和 Quake III Arena 网络协议规范(非官方) (看起来在互联网上已经找不到链接了)。本文是系列的第二篇：一般性说明游戏网络架构通常体现在四个要素的平衡上：一致性，响应性，带宽，延迟 (consistency, responsiveness, bandwidth and latency requirements)“Multiplayer gaming is about shared reality.”FPS 游戏的状态通常表现为一个实体列表：玩家，怪物，导弹，门等，这些实体 (entities) 与其全部作为不同的元素去区分对待，不如提供一个公共的结构和接口来简化通信。“Networking in first person shooters is all about synchronizing the state of multiple copies of the same game entities such that all players experience the same changes and events in the virtual environment.”为了达到即时同步这些状态的目的，有些实现方式需要参与者去管理和维护其自有的那份拷贝，通过施加一致的逻辑来推动所有的状态去同步地更新，而另一些实现则是随着时间的流逝不断地比较和发送最小的状态变化和差异。P2P 模型 (DOOM)DOOM (1994) 的网络模型是完全同步的 P2P 系统。该系统每秒钟对玩家的动作 (move/turn/use/fire, etc.) 采样 35 次 (得到一个 tick command) 并发送给其他所有玩家，每个玩家都接受来自所有玩家的 tick command，当某个玩家收到所有其他玩家的下一帧 tick command 后，该玩家的本地游戏状态推进到下一帧。这样的后果是全局性的延迟 (每个玩家从做出动作到收到反馈的响应时间) 由最慢网络连接的玩家决定。这个网络模型逻辑上非常简单，但存在这些问题：所有玩家都需要主动维护完美的状态同步，由于硬件不同(有时甚至是未初始化的变量)等引入的不一致，会让每个参与者细微的不同被累积下来，导致参与者之间显著的视觉和逻辑的差异。这种不一致的引入很难查，因为只有当它们累积起来才会有明显的效果，而等感觉到差异时，真正的问题已经发生很久了。完全同步的网络无法跨平台。不同的硬件上，由不同编译器生成的汇编指令有时会产生轻微不同的行为 (浮点指令尤甚)。随着玩家数量增长，延迟会迅速变得难以接受。而且只要有一个玩家的网络有波动，会影响到所有人的体验。随着玩家数量增长，带宽需求会指数性地同步增长。同步网络由于只发送 tick command，所有玩家必须同时启动游戏 (来保证游戏状态的一致性) 无法做到随时的加入和退出。由于玩家本地维护了所有的状态，方便了作弊的实现。Packet Server (包的简单中继)这个模型在原版 DOOM 的基础上增加了一个 Packet Server，负责转发所有的 tick command。玩家不再直连其他所有玩家，而是连到这个服务器 (某个玩家机器上) 以获取最新的状态。这样改进后，同步量降低了，而且如果一个玩家很卡，只会影响到他自己的游戏体验。但上述的大多数问题依然存在。Client Server (Quake I/II/III)Quake I/II/III 实现了比较典型的 C/S 架构 (1996)，这个模型中服务器负责所有的逻辑判断，客户端本质上只是一个渲染终端。玩家把自己的操作和输入发送给服务器，收到一个实体列表用于渲染。服务器把压缩后的快照发给客户端 (10-20Hz) 客户端使用这些快照来插值或推导出平滑连贯的体验 (interpolates between, or extrapolates from the last two snapshots)。在一般情况下(比如在古代的引擎Quake 1中)，客户端收集到用户命令后发送给服务器，此后就在等待服务器返回新的游戏状态。这是很笨的。在Quake 3中，客户端不会傻等，而会预测可能的游戏状态，其实预测状态所用的代码跟服务器端的代码是一样的，所以服务器端的状态和客户端的状态往往是一致的。如果确实不一致，则“服务器为准原则”将生效。\"Quake III Arena 网络协议规范(非官方)\"响应性和预判这个模型同样有响应性问题，从输入的采样和发送到屏幕反馈同样需要一个 roundtrip 延时。为了克服延时客户端预测了玩家的下一步行动 (在中有提到)。玩家的输入在发出去的同时，本地立刻处理，而环境状态做了上文说到的 interpolate/extrapolate，也就是说玩家看到的自身是 (可预计的) 操作结果，而其他人是过去的状态。(这一点与魔兽世界是一致的) 这个 C/S 架构是异步的。对任何一个玩家而言，服务器的全局模拟落后于该玩家在本地的实际操作快照，而环境的状态同步更是落后于全局模拟。这个模型允许中途加入和退出 (除了做 server 的玩家，如果不是 dedicated 的话)。由于玩家的判断基于的是其他玩家过去的状态，实际的击中检测发生在晚些时候的服务器上，在延时较高的情况下，玩家需要不断考虑延时状况并打提前量才能在未来的实际判断中击中对方。延迟补偿的潜在问题半条命在这个基础上引入了一种特定的延迟补偿 (lag compensation)，当玩家向某个目标 (若干毫秒前的状态) 射击时，做实际检测的服务器会采用该目标若干毫秒前的状态来检验是否击中。这么做需要服务器把之前一小段时间的状态持续地保存下来，这样不仅增加了实现复杂度，而且导致了某种程度的不一致性。延时高的玩家反而更容易因为补偿获得更有利的判断，严重影响游戏体验 (实例见第六页末尾，值得一读)。这种补偿只能对目标的位置回滚，而所有其他环境状态的改变却已无法倒退，这也会影响实际的体验。工程问题：逻辑和预测代码分离Q3 里服务器上跑的逻辑代码 (\"game code\") 跟客户端跑的渲染和预测代码 (\"client game code\") 实现在物理上不同的模块里，但却需要对彼此的内部细节非常清楚 (才能保证预测和实际行为的一致性)。这个强耦合使得扩展游戏变得很困难，这也是难以实现单人游戏模式的原因之一。有时使用 Q3 引擎的游戏得为多人模式和单人模式发布两个不同的 exe，其中单人模式直接使用 game code 来简化逻辑流程。插值/推导的局限性由于快照的接收频率往往低于实际渲染的帧速，就需要上文提到的 interpolate/extrapolate，考虑物理模拟和交互的话，(为了跟服务器逻辑一致) 推导会增加额外的实现复杂度。这些插值对位置数据很有效，但其他一些状态很难插值，有时性能也是问题，比如四元数的 slerp 就挺费的 (提到了相关的优化)压缩、状态同步冗余、固定字长Quake III 里只有在 PVS 内的实体才会被同步状态，而且被同步的是压缩后的与上一次同步比较的差值 (delta compressed relative to the entity states from a previous snapshot) 这导致的结果是如果一个物体频繁进出 PVS 就没法做 delta 比较，总是发送完整状态，会导致不少冗余的同步量。为了提高网络通讯速度，降低带宽，Quake 3中采用了压缩的技术。这并不是指用一些压缩算法来直接压缩数据。而是指，在传送游戏状态数据时，只传送改变了的游戏状态，而不是全部发送过来。一般来说，这个叫做Delta技术。\"Quake III Arena 网络协议规范(非官方)\"出于简化，Q3 使用了固定长度的同步结构，导致不少字段被不同的功能各种复用，一晦涩复杂度就上去了。[本文完，系列待续]Gu Lu[]","state":"published","sourceUrl":"","pageCommentsCount":0,"canComment":false,"snapshotUrl":"","slug":,"publishedTime":"T20:46:55+08:00","url":"/p/","title":"(2/3) DOOM/Quake I/II/III 网络模型的演化","summary":"这一篇是上一篇的自然延续，但内容上独立成篇，实际上描述了 id software 从 DOOM 1 开始的若干款 FPS 游戏在网络架构方面的演化。同样的，更多的细节可参考和 Quake III Arena 网络协议规范(非官方) (看起来在互联网上已经找不到链接了)…","reviewingCommentsCount":0,"meta":{"previous":null,"next":null},"commentPermission":"anyone","commentsCount":10,"likesCount":107},"next":{"isTitleImageFullScreen":false,"rating":"none","titleImage":"/50/aaaf8325bb06eadba47b51a6dce6f657_xl.jpg","links":{"comments":"/api/posts//comments"},"topics":[{"url":"/topic/","id":"","name":"计算机图形学"},{"url":"/topic/","id":"","name":"游戏开发"}],"adminClosedComment":false,"href":"/api/posts/","excerptTitle":"","author":{"bio":"招3D游戏前端，好学基础扎实","isFollowing":false,"hash":"792cbf5d4edb31cb51795e","uid":32,"isOrg":false,"slug":"yesbaba","isFollowed":false,"description":"","name":"燃野","profileUrl":"/people/yesbaba","avatar":{"id":"7cc1b50eda68","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false},"content":"常规的地形使用4张diffuse贴图进行混合，用一张权重图的rgba通道表示每个diffuse贴图的权重，实现出来的地形可以有4种不同的地面，4种之前可以过渡。对于面积很大的地形，4张diffuse图就使得表现受到局限，显得单一了。解决方法有2：1，切分地形为多个小块，但要能同时编辑多块地形，处理地形边界。2，让一个地形能混合更多的贴图。本文是关于第二种方法的，并且不增加drawcall，shader计算量也没有太多增加。思路是把所有要混合的图做成一张Atals，比如最上面的贴图，4x4的能有16种。但权重图仍然只有一张RGBA的话，就得单个通道能区分开4张图才行。RGBA通道分别表示4x4的一列，R的取值是0-255（color32算的话），可以分成4段：0-63，64-127，128-191，192-255分别表示一列中的某一行，某一段内的取值表示权重，0是0%，63是100%，精度降低到原来的1/4。GBA通道同理。刷地形的工具保证任一点的所有权重加起来是63。算格子和格子权重的大致代码如下（shader里颜色是0-1）\t\n\tfloat4 splat_control = tex2D(_Control, IN.tc_Control); //权重图\n\tsplat_control = min(splat_control, fixed4(0.999, 0.999, 0.999, 0.999));\t\t//防止1的出现\n\thalf4 gridIndex = floor(splat_control * 4);\t\t//每一个通道表示那一列中从下到上第几个,[0,3]。\n\thalf4 gridWeight = floor(splat_control * 256) - gridIndex * 64;\t\t//每个格子里的权重值,[0,63]。\n把uv还原到一个格子里的算法uv0 = frac(IN.uv_Splat0) * float2(0.25, 0.25) + float2(0, gridIndex.r * 0.25);\n下面是效果示例，带发现光照的。这个做的是sample4次贴图，4列之间是可以过渡的，同一列的格子没法过渡。想过渡的话得sample16次贴图或者用条件判断，从性价比上用不到。“2”贴图之间是很硬的切换，其他之间是有过渡的。注意事项：1，diffuse atlas的mipmap如图红色区域部分的瑕疵，原因是使用了错误的mipmap层导致的。之前单张diffuse图的时候，uv是连续的从0到无穷，1.x跟0.x是sample出同样的内容，1两边的值是连续的，但内容是平铺的。现在变成格子之后uv也得分段去找对应的格子，uv=(0-0.25, 0-0.25)的格子跟uv=(1-1.25, 1-1.25)的格子内容是一样的，但uv却不连续了。gpu底层是通过相邻像素的uv差值来判断应该用哪个mipmap，差值越小说明越接近应该用最精细的mipmap0，差值越大就用越粗糙的。格子平铺的时候边缘uv从0.25到1.0差了0.75，就会用很粗糙的mipmap，而不是边缘的地方仍然用高精度mipmap，造成了格子边缘的线。解决方法是传入额外的参数调用tex2D告诉它实际的uv插值，ddx和ddy用来做这个tex2D(_Splat0, uv0, ddx(IN.uv_Splat0), ddy(IN.uv_Splat0))\n函数解释详见下面的参考。所有atlas带mipmap需要平铺的都要解决这个问题。2，权重图的filter modePoint采样适合来算格子id，这个不会出什么错，别超过最大格就行。Bilinear适合算格子的权重，过度自然，但是在边缘可能采样出超过本格子范围的值，比如64-127的格子，可以采样出小于63或大于127的值。所以用一个中间方案，一部分用point一部分用bilinear，point采样值小于某个格内权重阈值时（比如6）用point的，超过的话用bilinear的，这样尽管大于6才开始过度，但是过渡是正确的。unity里的terrain贴图是它引擎设置的，要想sample2次可以把权重图copy一份，但是这就有内存代价了，这个图是不压缩的，的RGBA要多占5M都内存吧，算上mipmap。3，在unity里如何改写terrainInspector刷格子编辑器代码是在unityEditor写的，c#的，可以反编译出来，仿照着实现一边是可以的就是代码多了些。另一种方式是继承terrainInspector至改写特定的方法，这样代码量就少很多了，把OnSceneGUI里刷贴图的部分改一下支持刷16格工作量并不大。参考资料1，《天下》手游，它的地形是用4x4的atlas，但更复杂还能混合出带反射的水，并且一个通道表示0-15的格子。细看能看出来有的过渡边缘比较糙，估计跟点采样有关。2，解释了如何计算使用哪层mipmap的原理3，cg library里tex2d、ddx、ddy","state":"published","sourceUrl":"","pageCommentsCount":0,"canComment":false,"snapshotUrl":"","slug":,"publishedTime":"T21:12:10+08:00","url":"/p/","title":"用Atlas实现多张贴图混合的地形及注意事项","summary":"常规的地形使用4张diffuse贴图进行混合，用一张权重图的rgba通道表示每个diffuse贴图的权重，实现出来的地形可以有4种不同的地面，4种之前可以过渡。对于面积很大的地形，4张diffuse图就使得表现受到局限，显得单一了。解决方法有2：1，切分地形为多个小块…","reviewingCommentsCount":0,"meta":{"previous":null,"next":null},"commentPermission":"anyone","commentsCount":1,"likesCount":52}},"annotationDetail":null,"commentsCount":0,"likesCount":140,"FULLINFO":true}},"User":{"mc_gulu":{"isFollowed":false,"name":"顾露","headline":"","avatarUrl":"/v2-dde66a7e5c8c0fec9a020cde8a1a2bef_s.jpg","isFollowing":false,"type":"people","slug":"mc_gulu","bio":"程序猿一枚 : )","hash":"ba6dba6ce8c68be8fdbb15","uid":52,"isOrg":false,"description":"","profileUrl":"/people/mc_gulu","avatar":{"id":"v2-dde66a7e5c8c0fec9a020cde8a1a2bef","template":"/{id}_{size}.jpg"},"isOrgWhiteList":false,"badge":{"identity":null,"bestAnswerer":null}}},"Comment":{},"favlists":{}},"me":{},"global":{"experimentFeatures":{"ge3":"ge3_9","ge2":"ge2_1","appStoreRateDialog":"close","nwebStickySidebar":"sticky","qrcodeLogin":"qrcode","favAct":"default","default":"None","mobileQaPageProxyHeifetz":"m_qa_page_nweb","newMore":"new","iOSNewestVersion":"4.2.0","newMobileColumnAppheader":"new_header","sendZaMonitor":"true","homeUi2":"default","answerRelatedReadings":"qa_recommend_by_algo_related_with_article","wechatShareModal":"wechat_share_modal_show","liveReviewBuyBar":"live_review_buy_bar_2","qaStickySidebar":"sticky_sidebar","androidProfilePanel":"panel_b","liveStore":"ls_a2_b2_c1_f2","zcmLighting":"zcm"}},"columns":{"next":{},"gu-lu":{"following":false,"canManage":false,"href":"/api/columns/gu-lu","name":"游戏人间","creator":{"slug":"mc_gulu"},"url":"/gu-lu","slug":"gu-lu","avatar":{"id":"2b4ab237b72d9adc998f0c2e6f3559b5","template":"/{id}_{size}.jpeg"}}},"columnPosts":{},"columnSettings":{"colomnAuthor":[],"uploadAvatarDetails":"","contributeRequests":[],"contributeRequestsTotalCount":0,"inviteAuthor":""},"postComments":{},"postReviewComments":{"comments":[],"newComments":[],"hasMore":true},"favlistsByUser":{},"favlistRelations":{},"promotions":{},"switches":{"couldAddVideo":false},"draft":{"titleImage":"","titleImageSize":{},"isTitleImageFullScreen":false,"canTitleImageFullScreen":false,"title":"","titleImageUploading":false,"error":"","content":"","draftLoading":false,"globalLoading":false,"pendingVideo":{"resource":null,"error":null}},"drafts":{"draftsList":[],"next":{}},"config":{"userNotBindPhoneTipString":{}},"recommendPosts":{"articleRecommendations":[],"columnRecommendations":[]},"env":{"edition":{},"isAppView":false,"appViewConfig":{"content_padding_top":128,"content_padding_bottom":56,"content_padding_left":16,"content_padding_right":16,"title_font_size":22,"body_font_size":16,"is_dark_theme":false,"can_auto_load_image":true,"app_info":"OS=iOS"},"isApp":false},"sys":{},"message":{"newCount":0},"pushNotification":{"newCount":0}}}