云风的 BLOG

我们的游戏引擎的 GameUI 使用的 RmlUI 。我的想法是用成熟的 CSS 来描述 UI 的呈现，借鉴 web 前端开发的方法来制作游戏的 UI 。

但我不想嵌入太复杂的 Web 渲染引擎，而且游戏的需求也会有所不同，所以我选择了轻量的 RmlUI 。同时，为了和游戏的开发语言一致，我们使用 Lua 而不是 javascript 来控制 CSS 。

在使用 RmlUI 的过程中，一开始我们尽量和上游保持一致，修复了不少 Bug ，并合并到了上游。后来发现我们有很多需求和上游不同，需要大刀阔斧的做一些改动，所以就 fork 了一个自己的分支。

最重要的两个改动是：第一，完全实现了 Lua Binding ，因为原有的实现非常低效和复杂，很多接口设计不合理。做大规模的接口变化必须破坏向前兼容，这是我们 fork 分支的主要动机。

第二，废弃了 RmlUI 自己实现的排版模块，换成了 Facebook 维护的 Yoga 。

迁移到自己的分支上后，我们陆续对 RmlUI 的代码进行了不少重构。

最近，发现了 RmlUI 原有的一个 Bug ，有时修改了一个 css 节点属性后，会影响另一个不相干的节点的属性。仔细研究后，判断这是它固有的设计失误造成的。

我们知道，css 非常灵活，每个节点的属性都可以被很多数据源影响。如果我们不做任何优化，推导一个节点上的属性会是一个相当昂贵的操作。所以，必须对其做一些缓存。

而 RmlUI 的属性缓存算法有一些设计问题，它是根据节点的 C++ 对象指针做缓存索引的。这势必会因为对象的删除重建所影响。（因为内存指针的值有可能重复）且这部分代码实现的非常繁杂，我思考后觉得重新设计和实现会更好。

首先定义问题：

每个节点的属性表其实是一个 kv 对的数组。其中 k 是一个 enum ，范围不大（小于 100 种）且不会重复；v 是一个对象。而这个对象一定可以从文本序列化而来（因为源头的数据都是用文本书写的）。

这些属性表是由若干属性表合成的。合成方式有两种，从预定义的类型中继承以及从 DOM 的父节点继承。后者会受属性是否可以继承所影响，哪些属性可以从父节点继承是一开始就确定好不会改变的。

每个节点最终的属性表会以一种特定的次序从若干属性表合成而来。

如果我们把属性表看作一个对象，那么合成表 A 和 表 B 就能视为 A * B ，其中 * 是合成操作。每个节点上的表都可以看作是一串数据表连续合成操作的结果 A * B * C ....

如果我们要做缓存，就应该缓存任意两个表 A * B 的结果，即可提高性能。

我们可以把属性表分成两类，一类是元素数据表，一类是两张表的合成结果。对于前一类表，由使用者来维护其生命期，而后者可以完全由缓存模块管理。因为一旦缓存失效，使用者都可以想办法重建它们。

我用 64bit ID 来指代属性表（其中奇数用来指代数据表，偶数用来指代合成表），如果数据表被释放，或合成表从缓存中消失，ID 不会回收，这样，我们很容易知道哪些 ID 还是有效的，哪些已经无效。

至于属性表的内容，可以额外再做一层 Cache ，对它们 Interning 。相同内容的属性表内部其实指向同一份数据。

对于合成表，一开始只用记住引用的是哪两张表，合成操作可以推迟到最后的求值之前。如果有源头表改变，那么需要清理之前的合成结果。

我在实现以上想法的时候，专门思考了内部的数据结构该如何设计更好。其中有点意思的是关于合成表的 Cache 的结构。

所有的合成表都是由 Cache 管理的，用户不复杂它们的生命期。即，如果你计算 A * B = C ，那么 C 的生命期是不用自己管理，但做（弱）引用。既然是 Cache 管理，就有失效的时候。因为每个节点上的表都是一系列表联合作用的结果，所以当结果失效后，用户直接把合成过程重新做一遍即可。这个过程可能很长，我们需要尽量 Cache 中间变量。

合成表首先应由一个 LRU 队列所管理。我直接使用了一个固定大小（4095）的数组，内部用双向链表串起来。这样，对任何一张表求职，都可以方便的把它调整到队列的最前面。

然后，我们需要两种途径快速索引 LRU 队列中的对象。从 ID 索引，以及从两个 ID 的组合索引。即，如果 A * B = C 计算过，那么从 (A, B) 可以快速索引到已经创建过的对象 C 。

每张索引表我采用一个 8191 大小的数组作 hash 表。它的大小比 Cache 大一倍，所以几乎不应该碰撞。但碰撞从理论上无法避免，在解决碰撞冲突上，我的设计比较特殊，既不是开散列表，也不算闭散列表。

我用 64bit 为一个 slot 的大小。因为原始数据是 4095 ，也就是 12 bits ，这个 slot 可以放下 5 个索引值，也就是说，理论上，最多可以碰撞 5 次。如果某个 hash 值真的碰撞了 5 次（非常罕见），那么就需要遍历整个 LRU 队列查找是否有第 6 个值。

附代码：https://github.com/cloudwu/stylecache

Posted by 云风 at 02:58 PM | Permalink | Comments (4)

我们引擎中使用的数学库已经修修补补很久了。期间积累了很多想法。最近在对引擎做性能优化，把一些找到的热点系统用 C/C++ 改写，顺便就重构了一下数学库，让它更好的兼顾 Lua API 和 C API 。

上一次对数学库的改进是三年前的事情了。这三年的使用，我们发现，基于一个栈的 DSL 虽然可以减轻 Lua 和 C 之间的通讯成本，但是使用起来并不方便。大部分时候，我们还是倾向更传统的接口：一次数学运算调用一次函数。而高复杂度的数学运算完全可以放在独立的 C 模块中完成。结合 ECS 系统，我们可以在 C side 集中批量处理相同但数量巨大的数学运算。

我们在很早以前就放弃了原来设计的 DSL ，只使用数学库的部分功能。趁这次重构，我打算把这些已经废弃的部分彻底删掉，并重新设计底层的数据结构，让它能更好的适应其核心特性。

我认为我们的数学库最核心的特性是：所有的数学对象，包括矩阵、向量、四元数都是不可改写的值对象，有一致的外观。我将它表达为 64bit 的 id ，这样方便 Lua (或别的语言）binding 。

做 Lua binding 时，数学对象 id 是一个 lightuserdata 而非传统库用的重量级的 userdata 。这样用起来的代价和普通的数字相比，并无明显的额外负担。

即使不在 Lua 中使用，直接由 C/C++ 运用时，一个 64bit 的 id 也好过更大（且尺寸不等）的数据结构或智能指针的等价物。在 C/C++ 中使用，同样可以把矩阵这种重量的数据块当成和整数一样的轻量值。

做到这一点，最难的是对象生命期管理。我假设在使用中，大部分的数学对象都是即用即弃的，一道复杂的运算过程，只有最后一个环节被传入其它模块中。而其它第三方模块（比如物理、动画、渲染）通常会有自己的解决方案，并不依赖调用者来维持数学对象（矩阵等）的生命期。

所以，我们的数学库默认是在一块固定的临时内存块上分配数学对象的储存空间的。新的实现中，这块临时内存最多是 256 页，每页 1024 个 float4 的空间，最多可以保存 64K 个矩阵或 256K 个 vector4 。临时空间在渲染帧之间清理干净；同一帧内，对象是不会删除，一直有效的。

分配临时对象使用最简单的 bump allocator ，创建一个新对象 id 只需要一次加法，所以几乎和栈上分配同样高效，故而我们不再需要考虑把数学对象放在栈上还是堆上的问题。

对于需要持久引用的对象，可以把临时对象区的数据复制到一个永久对象区。和之前的实现不同，永久对象区的对象使用了部分的引用计数，这样可以减轻多次引用的代价。

对应的 api 是 mark 和 unmark ，可以理解为，如果一个 id 你想永久引用，那么就调用 mark(id) 生成一个新的永久 id 记住，当你不用的使用再调用 unmark(id) 放弃引用。当传递引用的时候，如果接收方也想引用它，同样需要再次 mark ；而实现可以选择内部增加引用，也可以额外再生成一个副本。

因为我们把所有的 id 都视为不可改写的数学对象，所以选择引用同一块内存还是复制数据得到新的副本，对使用者来说都是等价的。

unmark 不应被视为 delete 或 release ，因为它并不立刻回收内存，所以 id 被 unmark 后，还可以继续使用到帧末。这样，对于应用传递来说，并不需要刻意在传递引用时刻意调用 mark 来保证 id 的有效性。（这和传统的智能指针的引用方案是不同的）

这次重构，我增加了两个重要的新特性。这是在我们几年的使用经验中总结出来非常必要的功能。

其一，增加了 NULL 类型。接口中应出现数学对象的地方都可以传一个 NULL 对象，以和正常的矩阵等对象区别开。

这会让接口设计更具弹性。在永久引用的数据结构中，也可以把 NULL 作为默认值，方便做某些优化。比如，对于合成 SRT 到一个矩阵的接口，允许传 S/R/T 的任意参数为 NULL，减少计算量。

其二，增加数组类型。准确的说，任何数据对象都是数组，只不过默认数组长度为 1 。一个矩阵数组可以被视为单个矩阵（数组的第一个元素）；也可以用 index 这个（轻量） api 取出数组中的某个特性元素。

有了这个特性，可以更方便的表达类似 AABB （两个向量），视锥体（六个向量）等对象；C API 设计时也可以更方便的返回多个计算结果（返回一个数组即可）。

我花了三天时间做完了重构的工作，可以在 https://github.com/cloudwu/math3d 看到现在的版本。Lua 库是我们主要使用的部分，但 mathid 这个子模块可以供 C/C++ 直接调用。

Posted by 云风 at 09:45 AM | Permalink | Comments (1)

我们的游戏场景是由若干场景节点构成的，每个场景节点是一个 Entity 的 Component 。而一个复杂的场景可以在编辑器中生成一个预制件 Prefab，像搭建乐高积木那样堆砌已经做好的部件。关于预制件的设计，之前有过两篇 blog 讨论。分别是：游戏引擎中预制件的设计 和 预制件和对象集的管理 。

就目前的使用经验来看，几乎所有游戏中的 Entity 都是从 Prefab 实例化得来的。一个 Prefab 会实例化出 n 个 Entity ，但这 n 个 Entity 的生命期管理却很麻烦。

最自然的想法是：所有的 Entity 都必须是场景树上的节点（拥有场景组件），当我们删除一个场景节点时，它所有的子孙都一起移除。

这个做法有两个问题：

1. 如果一个 Entity 被间接移除（祖先被删除），持有它的引用该如何处理？传统的方法是，只能对 Entity 保持弱引用。一般用 Entity ID 作弱引用。我们在对 Entity ID 解引用时，应检查引用是否有效。

2. 有些 Entity 未必是场景节点，但也需要合理的自动化生命期管理怎么办？传统的方法要么让所有的东西都必须是场景节点，要么把这个东西变成场景某个节点的一个组件附着在场景节点上。

我不喜欢上面提到的传统解决方案。因为：生命期管理和场景管理其实是两件事。场景管理是按树结构组织的，而生命期管理更适合用集合这种结构。所有需要被管理的东西不应该都必须在场景树上。

动态给 Entity 增加 Component 的能力看似有用（我们的 ECS 系统刻意不支持它），但只是为了把一个不相干对象的生命期和另一个对象绑定起来，就强行把它作为 Component 和场景的 Component 组合在一起，我觉得也是对 ECS 的滥用。

回头来看 Prefab 。我们应当把它看成是对 Entity 组合的持久化，它持久化了 Entity 本身的数据，以及 Entity 之间的关系。然后，我们可以在运行时将持久化的模板实例化。

既然，prefab 的 instancing 是创建出一组预先设计好的 Entity 及其相互关系的主要方法；那么，销毁它们的过程也应该是对称的。即，如果我们通过 prefab 一起创建出 n 个 entity ，那么也应该让这 n 个 Entity 一起销毁。应该避免只销毁其中的一部分。

在实践中，我们销毁部分 Entity 往往是因为拿出了部分 Entity 挂接到已有的场景树上；或是让其它 Entity 挂接在它的挂接点上。前者拆分了生命期管理集，后者扩大了生命期管理集。

我最近重构了引擎中挂接这个特性。避免了场景节点间的任意挂接行为。挂接变成了某种弱引用，而不改变原本固有（在 Prefab 中预设）的场景树形态。就避免了这个问题。所以，理所当然的，就可以实施更简单的生命期管理了。

现在的方案是，当 prefab instancing 时，它在创建一组 Entity 的同时，还会返回一个 instance id ，用来引用这组 Entity 的生命期。这个 instance id 只用于一件事，就是日后销毁这组 Entity ，而不能做任何其它事情。控制这些 Entity 还是要通过 Entity ID 或 select 特定的 Component 完成。

这样，我们的系统的每个 Entity 都具有两个 ID ，一个是唯一的 EntityID ，另一个是被 prefab instancing 时赋予的 instance ID 。前者用于引用具体的 Entity ，后者用来在上层管理生命期。底层既然有通过 Entity ID 销毁特定 Entity 的接口；但上层不可以使用这个接口，而只能通过 Instance ID 销毁一组 Entity 。

在实现的时候，用一个小技巧就可以把两个 ID 合二为一。

用一个 64bit 数字作为 Entity ID ，即使 Entity 被销毁，新的 Entity 也不会复用旧 ID 。这样可以通过 ID 实现弱引用。

EntityID 是在 prefab instancing 的过程被赋予的。我们采用 48+16 的形式。有一个单调递增的 48bit 内部 ID ，每次 prefab instancing 时加一。当一次 instancing 的 Entity 新建数目少于 64K 时，剩下的 16bit 可以完美表示每个 Entity ，两者合并就得到最终的 Entity ID 。如果有巨大的 Prefab ，它会构建超过 64K 的 Entity 也没有关系，继续递增那个 48bit 内部 ID ，就可以有新的 64K 集合可用。当 prefab instancing 结束，我们看一共用了多少个 64K 集合，就能生成唯一的 Instancing ID 了。

比如，某次 instancing 过程生成了100K 个 Entity ，内部 ID 一开始是 42 ，那么这个过程就用掉了 42 和 43 两个内部 ID ，表示 64K + 36K 两组 Entity 。所以 Entity ID 是从 42 << 16 开始，到 (43 << 16) + 36K 结束。

最终的 Instance ID 就是 42 << 16 | 2 ，表示这个分组是从 42 开始的连续两组。Entity 身上不必专门记录 Instance ID ，只需要取 Entity ID 的高 48bit ，是 42 和 43 的都属于这个分组。

Posted by 云风 at 03:49 PM | Permalink | Comments (6)

前段时间我们给引擎增加了对象分组的功能 。做这个特性的动机是当整个游戏世界中的对象数量远超同时需要处理（显示）的对象数量时，有一个快速筛选出待处理代码集合的机制。

在使用过程中，我陆续发现了这个特性的其它用途。

过去的某个游戏项目中，曾经遇到这么一个需求：游戏中需要为玩家生成一个头像，这个头像是由很多部分构成的。有玩家的肖像、名字、等级、修饰用的图标等等。这个头像可能同时在屏幕的很多位置显示。

如果场景是一个简单的树结构，那么，每个出现头像的地方，都是一个构成头像元素的子树。这样，场景中就可能出现完全一样的多份子树。固然我们可以用一个通用接口构造这个子树出来，但是，一旦这个玩家的属性发生变化，就需要针对所有场景中出现的同类子树进行修改。这需要为每个玩家额外维护一个列表，引用所有头像在场景树中出现的位置。这无疑增加了数据结构的复杂性。

一个自然的想法是，场景不再是一颗树，而是一个有向无环图。玩家头像在场景中可以出现在多处，但子树只有一份。这颗子树的根节点可以有多个父亲。这样，需要修改时，我们只需要改动一处。

在 Ejoy2D 中，我实现了这个机制。但总觉得有些别扭，因为底层的数据结构还是变得复杂了。

目前我们正在用新引擎开发游戏，遇到了同样的问题。我们在做一个类似异星工厂的游戏，里面有许多小细节。在许多场景元素（工厂、机械爪、运输无人机等等）中会挂接一些小元件。玩家可以看到这些小东西在游戏中的流动。比如，机械爪抓起一个铁板，放入目标容器中，玩家可以在场景上看到这个过程；工厂外的空地上也能看到铁板的增减。

我们一开始用构建新的对象，挂接到对应的挂接点上的方法来实现。一旦不需要这些小元件后，再将其删除。

一开始并没有太大问题。但当场景上这些小元件数以千计时，构建删除对象变成了性能热点。毕竟，设计之初，我们认为对象的创建和删除不应该是频繁的操作，并没有为之做什么优化。固然、我们可以优化对象的构建删除过程。但这些小元件本身还可能是由多个底层对象组合而成的，构建全新的对象怎么说都是个重量级的操作。

就我们这个游戏来说，场景中动则数以百计这些小元件。我觉得更好的方法是同一种东西（比如一个齿轮）只创建一个实例，而这个实例可以挂接到多个挂接点上。

我第一时间想到的是过去用过的有向无环图的方式，但内心是拒绝的。继而，我想到了最近实现的分组功能。目前实现的分组，对同一组对象打上 Tag 是一个相当廉价的操作，时间复杂度只和需要打 Tag 的元素个数有关。如果，我们让齿轮、铁板这些小元件独立创建出来，不放在场景中，而是单独分配一个分组 id ；那么找出同一个 group id 的成本也只和同一 id 的对象个数有关。大多数情况下，这个个数是 1 。该操作也是 O(1) 的。

剩下的工作只是增加一种虚拟节点的场景对象类型。它除了有场景对象该有的场景组件外，只有一个 group id 的引用。当需要渲染这个虚拟节点时，只需要根据 group id 找到对应分组的所有对象（通常只有一个对象），这些对象的世界矩阵是创建时一次计算好的，可以视为被摊平的对象集合，把这个集合中所有对象乘上虚拟节点的世界矩阵，就可以在正确的位置渲染。

总结：游戏世界是由多棵树构成的森林。只有其中一棵树是当前场景待渲染的。这个渲染树上可以有若干虚拟叶节点，它引用了森林中的其它树。对于非渲染树，每棵树上的所有节点被归于同一个分组。这些节点按分组平坦的放在同一个集合中。

Posted by 云风 at 03:15 PM | Permalink | Comments (11)