云风的 BLOG -- IT技术博客大学习 -- 共学习共进步！

• 一个 VLA （可变长度数组）的实现

VLA （可变长度数组）是 C 语言在 C99 之后加入的一个很方便的语言特性，但是 MSVC 已经明确不支持 VLA 了。而且 Linux 的内核代码中曾经使用过 VLA ，而现在已经移除了 VLA 。看起来，VLA 带来的安全问题比它的便利性要多。但是，日常用 C 语言做开发时，经常还是需要变长数组的。既然直接用 C 语言的 VLA 有诸多问题，那么还是需要额外实现一个比较好。C 没有 C++ 那样的模板支持，一般的通用 VLA 实现很难做到类型安全。即使用 C++ ，STL 中的 vector ，这个最常用的 VLA 实现，也不总是切合应用场景的。比如，std::vector 它的数据一般还是分配在堆上，而不是栈上。相比原生创建在栈上的数组，它可能性能有影响且有可能制造更多的堆内存碎片。

• 用邻接表实现无向图

今天在扩展我们游戏中的管道系统时，又遇到了实现一个无向图的问题。之前的管道系统，每节管道的邻接管数量有限，所以我用了类似树的方式储存，在每节管道上直接放了一个固定大小的数组，保存该节管道的上下游节点。对于液体管道系统，这套数据结构工作的很好。今天，我们的另一个系统需要一个有点不一样的管道。它没有方向，每个节点可以有很多的邻接点。例如电线拉成的网络、导热管构成的网络，都是这样的。这是典型的无向图结构。我重新考虑了数据结构，用邻接表实现了一版。我把节点的数据和节点的邻接关系分开到不同的数据结构中，这样方便单独把管道连接模块独立出来复用。首先，用一个有序的数字 id 表示图中的节点。由于我们的图规模不会太大，16bit 的 id 就够用了。那么，相邻节点的连接关系就是图中的边，它可以用两个 id 连起来共 32bit 表示。由于是无向图，我们

• fbx 到 gltf 转换问题

我们的游戏引擎采用的资源格式是 gltf 2.0 。 gltf 在这几年发展很迅猛，我认为是 3d 文件格式中标准化做的最好的一个。可惜，游戏行业中，美术创作人员常用的 max maya 等工具对其支持还有瑕疵。Autodesk 在 2019 年作为 contributor 成员加入了 Khronos 组织，在 max maya 这些 Autodesk 工具中看到官方的 gltf 支持应该不会等太久。来自官方的消息，‎在 2020 的 3 月底，gltf 加入官方支持已经处于 Under Review 状态。希望今年内可以看到。因为 Unity 的流行，fbx 是游戏行业目前的实施标准。但 fbx 是一个私有格式，并没有任何公开的标准文档。而且其格式设计有很多历史包袱，甚至连字段名都因为有 typo 而在解析的时候有多个错别字兼容备

• 不变量及运算优化

去年的时候，我们对正在开发中的游戏引擎做了一点 profile 工作。后来发现，在场景中对象很多的时候，有一处运算占据了 10% 以上的 cpu 时间。当时我的判断是，这处地方值得优化，但并不是工作重点，所以就搁置了。问题的具体描述是这样的：我们的引擎每帧会将场景中的对象依次提交到一个渲染队列中，每个可渲染物件，除了自身的网格、材质外，还有它自身的包围盒（通常是 AABB），以及它在世界空间中的矩阵。我们有一套资源系统，场景中的对象会引用资源系统中的对象，这些资源对象是一个不变量，会被多个场景对象所引用。而资源对象又可以是一个树结构，比如一个模型就可以由若干子模型所构成。提交到最终渲染队列中的是不可再拆分的子模型的信息。也就是说，在场景管理的层次，对象的数量是远少于提交到渲染队列中的对象数量的。这就是为什么我们渲染每次重建渲染队列，而没有将每帧提交给渲染队列的列表持久化为一

• 裁剪和空间管理

今天想谈谈游戏引擎中 Culling 模块。当场景中的可渲染对象很多，而当前会被渲染的对象相较甚少的时候，我们通常会启用一个 culling 的过程。Culling 会想办法剔除一些当前不必渲染的对象，避免这些对象提交到 GPU ，让 GPU 承担剔除的过程。这样可以减少 CPU 到 GPU 的带宽。最基本的 Culling 是用相机的视锥体和对象做一个相交测试，如果对象和视锥体不相交，则可判定它不必渲染；复杂的 Culling 还包括遮挡测试，如果一个对象完全被墙体挡住，那么也不必渲染。这篇只谈前者。

• 选择开源项目的几点原则

我们在开发软件的过程中，总有一些模块的需求是普遍的，除了自己开发，使用一个具备合适的 License 的开源项目也是个不错的选择。在一个程序员的职业生涯中，总会有那么一个阶段，不太愿意使用别人开发的代码。如果不是受项目进度压力所迫，宁愿自己实现。这并非是因为相信自己总能做得更好，而是希望少受牵制，能够自由发挥。而且，写代码往往比理解代码更简单。整合多块不同团队开发的代码也更难保证项目各个部分的一致性。

• 内存的惰性初始化

我们公司上海的工作室的一个 MMO 项目做服务器压力测试。谈及优化，涉及到服务器中使用的 C 模块。他们把同一套 C++ 加上 namespace 编译了很多份，供多个服务使用。我很好奇，一般来说，Lua 的 C 模块是可以供多个 vm 共用的，并不需要实际链接很多份。仔细探究发现，原来这个代码中用到了一些全局对象（singleton 模式）。我本能的觉得全局对象的设计中透着糟糕的味道，在逐个分析每个全局对象的必要性时，发现了一个有趣的东西：寻路模块。寻路模块本身的实现是没有持久状态的，场景地图的障碍信息是独立出去的静态不变数据，全局共享，这是合理的设计。但是一个无状态的 pathfinding 对象却被实例化了很多份，供不同的服务独立使用。

• 让 lua 运行时动态切换操作系统线程

最近我们在开发引擎时遇到一个和操作系统有关的问题，想了个巧妙地方法解决。我感觉挺有意思，值得记录一下。在 ios 上，如果你的程序没能及时处理系统发过来的消息（比如触摸消息等），系统有机会判定你的程序出了问题，可能主动把进程杀掉。完全自己编写的应用程序，固然可以把处理消息循环放在最高优先级。即使有大量耗时操作，也可以通过合理的安排代码，不让消息处理延后。但作为引擎，很难阻止使用者阻塞住主线程做一些耗时的操作。所以，通常我们会把窗口消息循环和业务逻辑分离，放到两个不同的线程中。这样，消息处理线程总能及时的处理系统消息。

• ECS 中的概念缺失

经过长时间的思考和实践，最近一个多月，我们的 ECS 框架做了较大的调整。其中一部分工作已经在前一篇消息发布订阅机制中介绍，另一部分工作其实开展的更早，但因为我想多沉淀一段时间再写。到本周基本基本改动完毕，可以总结一下了。 ECS 框架几乎只在游戏开发领域提出，我认为这主要是因为目前只有在游戏领域，周期性的大量对象的状态变换才是主流行为。而在其它人机交互领域，响应外部事件才是主流。这是为何 System 在游戏领域如此重要的原因。

• 游戏引擎中的资源生命期管理问题

最近我们开发中的游戏引擎在修理资源管理模块中的 bug 时，我提出了一些想法，希望可以简化资源对象的生命期管理。其实这个模块已经被重构过几次了。我想理一下它的发展轨迹。最开始，我们不想太考虑资源的生命期问题，全部都不释放。当然，谁都明白，这种策略只适合做 demo ，不可能用在产品中。因为我们整个引擎的框架是用 lua 搭建，那么，最直接的想法就是利用 lua 自带的 gc 来回收那些不被引用的资源对象。我不太喜欢这个简单粗暴的方法。因为首先， gc 不会太及时，其次 gc 方法触发的时机很难控制，容易干扰正常的运行流程。图形显示模块是时间敏感的，如果因为资源释放占用了 cpu 的话，很容易变成肉眼可查的卡顿。

• 资源文件的转换问题

我们上周在游戏引擎上面的工作中遇到一些 bug ，涉及到过去的一些设计问题。维持讨论了几天解决该问题的方案。今天终于把最终方案确定了下来，值得做一个记录。 bug 出在游戏资源文件的转换上面。游戏里用到的资源通常需要一个导入资源库的过程，例如你的原始贴图是一个 png 文件，但是引擎需要的是对应运行平台的压缩格式，windows 上是 dxt ，手机上是 ktx 等等。这个过程，在 Unity 等商业引擎中，是放在资源导入流程中。我们的引擎把这个转换过程放在虚拟文件系统这个层次。这个设计决策是因为，我感觉统一导入资源是个痛点，用的人通常需要等待导入过程。Unity 用了 cache server 来解决这个痛点，但我认为 cache server 也存在一些设计问题，这个会在后面再展开一次。

• 程序员应该怎样提高自己

经常有小（我 20 岁左右的）朋友问我，作为一个程序员该怎样提高自己。每个人的经历不同，所处环境不错，其实这个问题很难具体回答。不如好好写一篇总结，以后就不必每封 email 都重新写一次了。纵观我近 30 年的编程生涯，在每个时期，我看到的东西都不同。想必再过 10 年还会有变迁。我只能写写当下眼界所及之处。引我爱上编程，并乐此不疲的学习，是“我能写出更高效的代码”这种乐趣。如果一个人在学习编程开始，不努力让自己的代码变得更高效，发现不了优化的乐趣，我想他很难爱上编程。Don Knuth 说，Premature optimization is the root of all evil ，这句话背后的道理，不必一开始就强行接受。evil 最能蛊惑人心，但是我们需要它引入门。

• ECS 中的消息发布订阅机制

我们在实践 ECS 框架时发现，之所以 ECS 的概念诞生于游戏领域，是因为游戏程序往往都在周期性的处理一批对象，进行运算，根据上个周期的状态得到下个周期的状态。而传统人机交互的应用则是响应型的：即一个外部请求触发一系列的业务运作。如果你把游戏业务塞到响应型框架中，就会发现，不得不用时间去触发，业务响应的是 timer 。但这种情况下，timer 几乎没有携带任何状态，对单个 timer 的响应，是不可能做成无状态的：它本身就是整个游戏世界对上个状态的迭代。这种情况下，响应式框架就很低效。但是，如果框架完全做周期性自迭代，对外部输入事件的处理又远不如响应式框架灵活。如果只是简单的操作输入还好，比如手柄，我们可以每帧把手柄各个按键的状态置入世界，那么 System 在不断迭代时，直接把这些状态当作世界中某个单例的状态就好了。但更复杂的输入就没那么好做了。

• Windows 下重定向当前进程的 stdout 到网络连接

前段时间碰到一个需求，想把当前进程的标准输出重定向到一个 tcp 连接上。如果依照 posix 标准，调用一下 dup2 这个 api 就能搞定，但是 windows 并不是基于 posix 标准的操作系统，所以做起来要麻烦的多。我在 stackoverflow 和 msdn 上找了一番，没有看到什么靠谱的做法，所以自己折腾了一天。这里的难点在于：windows 上虽然有 _dup2 来模拟 posix 的 api dup2 ，但 fd 在 windows 上并不是内核对象， HANDLE 才是。fd 是在 runtime 层模拟出来的东西。msdn 上引用最多的一篇是：Creating a Child Process with Redirected Input and Output ，做的事情是创建一个子进程，然后重定向标准输入输出。

• 断点单步跟踪是一种低效的调试方法

断点单步跟踪的交互式调试器是软件开发史上的一项重大发明。但我认为，它和图形交互界面一样，都是用牺牲效率来降低学习门槛。本质上是一种极其低效的调试方法。

• 浅谈《守望先锋》中的 ECS 构架

今天读了一篇《守望先锋》架构设计与网络同步。这是根据 GDC 2017 上的演讲 Overwatch Gameplay Architecture and Netcode 视频翻译而来的，所以并没有原文。由于是个一小时的演讲，不可能讲得面面俱到，所以理解起来有些困难，我反复读了三遍，然后把英文视频找来（订阅 GDC Vault 可以看，有版权）看了一遍，大致理解了 ECS 这个框架。写这篇 Blog 记录一下我对 ECS 的理解，结合我自己这些年做游戏开发的经验，可能并非等价于原演讲中的思想。 Entity Component System (ECS) 是一个 gameplay 层面的框架，它是建立在渲染引擎、物理引擎之上的，主要解决的问题是如何建立一个模型来处理游戏对象 (Game Object) 的更新操作。

• Paradox 的数据文件格式

Paradox 是我很喜欢的一个游戏公司，在所谓 P 社 5 萌中，十字军之王和钢铁雄心都只有浅尝，但在维多利亚和群星上均投入了大量时间和精力。这些游戏基于同一套引擎，所以数据文件格式也是共通的。P 社开放了 Mod ，允许玩家来修改游戏，所以数据文件都是明文文本存放在文件系统中，这给了我们一个极好的学习机会：对于游戏从业者，我很有兴趣看看成熟引擎是如何管理游戏数据和游戏逻辑的。据我所接触到的国内游戏公司，包括我们自己公司在内，游戏数据大都是基于 excel 这种二维表来表达的。我把它称为 csv 模式。这种模式的特点是，基础数据结构基于若干张二维表，每张表有不确定的行数，但每行有固定了列数。用它做基础数据结构的缺陷是很明显的，比如它很难表达树状层级结构。这往往就依赖做一个中间层，规范一些使用格式，在其上模拟出复杂数据结构。

• 为什么 Windows 的文件系统会有盘符，使用反斜杠分割路径

今天同事在公司群里调侃问 Windows 能管理多少个盘。当超过 24 个盘的时候，盘符似乎是以 24 进制的方式增加的，也就是 Z: 后面是 CC: 到 CZ: 然后是 DC: 到 DZ: 。当有 600 个盘以后，或许应该用 CCC: 了吧？这也提醒我们，用正则表达式匹配 Windows 下的文件路径时，不可默认盘符只有一个字符。为什么 Windows 会有盘符这个诡异的东西呢？

• 在 Unity3D 的 Mono 虚拟机中嵌入 Lua 的一个方案

很多使用 Unity3D 开发的项目，都不太喜欢 C# 这门开发语言，对于游戏开发很多人还是更喜欢 Lua 一些。而 Lua 作为一门嵌入式语言，嵌入别的宿主中正是它说擅长的事。这些年，我见过许多人都做过 U3D 的 Lua 嵌入方案。比如我公司的阿楠同学用纯 C# 实现了一个 Lua 5.2 （用于在 U3D web 控件中嵌入 Lua 语言的 UniLua ）；还有 ulua slua wlua plua xlua ... 数不胜数。我猜测，a-z 这 26 个字母早就用完了。上面提到的项目的作者不少是我很熟悉的朋友，我们公司现在的 U3D 游戏也由同事自己实现了一套差不多的东西。所以我曾了解过这些方案。但我一直觉得这些方案要么做的过于繁琐，要么有些细节上不太完备，总是手痒想按自己的想法搞搞看。

• Lua 中 Cache 冷数据的落地

今天有同学跟我讨论了一下最近发现的一个 bug ，我觉得挺有意思的。需求是这样的：我们的系统中，有一些数据是从外存（数据库）加载进来的，由于性能考虑，并不需要每次修改这些数据就写回外存。希望在数据变冷后，定期落地即可。典型的场景是一个 cache 模块，cache 的是一些玩家的业务数据，可以通过 uuid 从数据库索引到。一旦业务需要访问玩家数据，cache 模块会从数据库加载对应数据，然后把数据表交出去。当业务再次需要这些数据的时候，cache 模块一旦发现数据存在于 cache 中，就直接交给玩家。 cache 模块还希望在数据很久没有被业务访问时，将这些数据写回数据库。我们的系统是基于 lua 构建的，数据 cache 模块和修改这些数据的逻辑在同一个 vm 里。难点在于，修改数据的业务逻辑是可以长期持有数据的，cache 模块需要正确感知这点。