云风的 BLOG

这两天和同事讨论一个问题，我写了个小玩意。

事情起因是，我们公司上海的工作室的一个 MMO 项目做服务器压力测试。谈及优化，涉及到服务器中使用的 C 模块。他们把同一套 C++ 加上 namespace 编译了很多份，供多个服务使用。我很好奇，一般来说，Lua 的 C 模块是可以供多个 vm 共用的，并不需要实际链接很多份。仔细探究发现，原来这个代码中用到了一些全局对象（singleton 模式）。

我本能的觉得全局对象的设计中透着糟糕的味道，在逐个分析每个全局对象的必要性时，发现了一个有趣的东西：寻路模块。

寻路模块本身的实现是没有持久状态的，场景地图的障碍信息是独立出去的静态不变数据，全局共享，这是合理的设计。但是一个无状态的 pathfinding 对象却被实例化了很多份，供不同的服务独立使用。

一开始，我很奇怪，一个无状态的寻路函数，为什么需要保存一个全局对象。读了代码后发现，寻路算法的初始化过程需要初始化一大块内存。具体说来，是一个大约 200x200x16 的三维数组，每个单元大约有 16 字节。算法就是很基础的 A* pathfinding ，在这么个三维网格中寻路。需要以开始这个三维数组的内存为全零。大约是 10M 内存。在高频调用下，memset 10M 内存是不小的开销。

实现者为了节省初始化的时间，在每个格子中记录了一个 64bit 的版本号，每次寻路递增版本，使用这些格子时判断一下格子的版本号和当前版本号是否一致，以此为标准来判断这个格子在当前轮次是否有初始化过。

由于真正的寻路过程往往只使用这 10M 内存中的极少空间，所以节约了大量的初始化时间。但这需要全局保留块内存，不能每次寻路都重新构造这么一个对象。

我想了一下这个问题。它本质上的需求是一个 3d 稀疏矩阵。原本我们用一个 hash 表也可以做到，只需要用三个维度的索引连接起来做 key 即可。但是实现者认为这样可能会有不确定的性能问题，宁愿使用空间换时间的方式以巨大的平坦内存结构来让操作这个稀疏矩阵的时候可以以 O(1) 的代价访问。但是，就带来了这一大块内存每次使用的初始化问题。

表达空间的稀疏矩阵除了 hash 表，还有很多方法，比如 KD tree ，八叉树等等，但无论从实现复杂度和访问效率上恐怕都没有说服力。我想，既然服务器上没有空间开销问题，那么能不能从根本上实现一个惰性初始化的内存结构呢？

这里是我随手写的几行代码，我认为可以解决这个问题。

假设 cpu 的 cacheline 是 64 字节，字长是 64bit ，我想以 64 字节为单位去初始化内存是最有效的（把一个字节清零和把 64 字节清零速度是一样的）。那么，10M 内存就可以划分成大约 156K 个段落。我们可以用 1 bit 记录每个段是否有初始化，在访问内存前查看对应的标记位就可以决定是否应该先把对应段落清为零。

156K 个标记位大约需要 2400 个 64bit 的字，也就是将近 20K 的内存来保存。如果也不想初始化这 20K 内存的话（因为大部分格子不会访问到），那么可以依法炮制一个 2 级标记。这一级，我们把这 20K 内存分成 64 段，每段 300 字节左右。最终，我们就用一个 64bit 的字来控制它们的初始化。

最后，用 gcc 开 O2 优化看了下最终生成的汇编代码，感觉编译器优化的结果很好。

这个项目使用的地图高达 4000x4000x16 格。里面保存了网格状的障碍信息。而服务器这个寻路模块要解决的是 NPC 在地图中攻击附近的玩家时能够绕过障碍物的问题。

也就是说，这个寻路模块并不需要解决长距离寻路，要处理的也仅仅是绕开附近的障碍物。且障碍物是静态不变的。

这些场景并不是特别复杂的迷宫，障碍的拓扑结构很有限，所以这个巨大的障碍数组中的信息密度非常之低。我认为，既然花了这么大的空间代价去保存障碍信息，无非就是想让寻路算法简单高效。但其实，这么大的空间，已经足够把 "地图上每个点到附近不太远距离内的任意目标点的路径" 全部记录下来了。

只要经过预运算，用合适的数据结构储存，我们完全可以在 O(1) 时间查询出任意一条路径。具体怎么操作，我下篇 blog 再写。

Posted by 云风 at 10:23 AM | Permalink | Comments (9)

粒子系统中，势必会引入多种材质。要么按材质分为不同的管理器对象，要么把所有粒子片放在一个管理器下，但增加材质的属性。

如果是前者，即使粒子的其它属性都有共性，也无法一起处理；而后者，则涉及材质分类的问题。

我们不大可能在渲染阶段无视粒子的材质属性，每个粒子片都单独向渲染器提交材质。因为无论是面片粒子，还是模型粒子，都应该批量提交粒子的空间结构数据，然后一次渲染。如果粒子是面片，那么就应该把一组粒子的顶点信息组织在同一个顶点 buffer 中；如果粒子是模型，就应该把每个个体的空间矩阵组织在 Instance Buffer 中。

如果材质属性只是一个 id 或材质对象指针，作为一个属性关联在粒子对象上的话，不同材质的粒子是无序的，怎样的数据结构可以方便管理呢？

在 粒子系统的设计 中，提到我们的管理器按 ECS 结构设计，管理器管理的是属性间的关联而非数据，这给材质属性的容器实现提供了极大的弹性。

如果单个粒子管理器同时呈现的最多的材质数量非常少，比如 8 个，那么最直接简单的方法是给每种材质一个单独的属性，用 tag M0 排到 M7 即可。这样，我们只要用管理器的 api 直接筛选对应的 tag 就可以得到每种材质的对象集合。

但如果材质种类很多，我觉得独立 tag 的方式就不合适了。

我首先想到的是可不可以单独设计一个材质容器的数据结构。对管理器来说，容器只需要支持向里面添加新数据、重新排列数据两个接口，具体容器是什么无所谓。对渲染来说，最重要的是可以快速遍历出同一材质下的所有对象。

比较直接的方法是用 id 来表示材质，为每个材质 id 都建立一个数组。如果不考虑对象删除，又因为粒子的材质一旦创建也不会修改，所以向容器添加一个新对象，就是根据添加的对象的材质 id 分别添加到对应的数组中。这样，渲染的时候，就可以简单的遍历对应材质的数组了。

对象删除是一个难题。因为上面的数据结构中，没有建立对象和材质的反向映射关系。所以这是一个 O(n) 的操作：需要遍历所有的材质数组，找到要删除的对象在那个数组中，才可以删除。

但好在渲染本身就需要遍历所有材质的所有对象，我们可以把两件事情一起做。管理器在删除对象的时候是靠一个 remap 表来通知容器重组内部数据的，比如 remap （7 : 1) 表示把 7 号移到 1 号，并将 1 号删除。我们可以暂时把 remap 信息记录在一个映射表中，在渲染遍历的时候对每一项多做一个查表操作，判断是否已经被删除或移动了编号（从 7 号材质变成了 1 号材质）。

但我在实现的时候，发现代码写起来非常的麻烦。写了一个小时之后，我停下来思考是否有更简单的做法。

我重新考虑更直接的数据结构：让材质属性就是一个 id 。在渲染阶段，只需要对这个材质属性数组做一个排序就够了。排完序后的材质属性，相同的材质自然就连在一起。

一开始我没有优先考虑这个数据结构的原因是，排序是 O(N * log N) 的，最坏可能到 O(N*N) 。而按上面的方法，渲染则是 O(N) 的（遍历完所有材质属性就够了）。

那么有没有方法用 O(N) 的时间复杂度完成材质的分类呢？

我认为只要加上一点合理的限制就可以了。比如限制同时使用的材质不超过 255 个。那么我们就可以获得两点好处：1. 用一个字节就可以储存材质 id 。2. 可以用桶排序。

因为我们的管理器中管理的是材质属性在容器中的序号，而且管理器能保证序号是连续的（删除对象会重排序号）。所以，我们可以在渲染环节，在栈上建立一个临时的一个序号数组；而材质上限是 255 个的话，建立一个 [255] 的桶数组即可。

// particle_id  is uint16_t if MAX_PARTICLE less than 64K
struct material_context {
  particle_id index[MAX_PARTICLE];
  particle_id head[MAX_MATERIAL];
};

一开始，只需要把 head[] 初始化为空（此处为 INV , INVALID_PARICLE），而 index[] 不需要初始化。

如果有 10 个粒子对象，假设它们的材质 id 为 0 1 0 1 0 1 0 1 0 1 0 。也就是奇数项是 0 号材质，偶数项是 1 号材质。我们遍历这个数组一次，就可以完成分类。

head[] 保存的链表的头索引，此处，head[0] 为 9 head[1] 为 8 ，即最后添加进去的项；index 中每一项都是同材质链表上的 next 索引。此处为 { INV, INV, 0, 1, 2, 3, 4, 5, 6, 7 } 。

这个数据结构中保存了两条链表：9 - 7 - 5 - 3 - 1 - INV 和 8 - 6 - 4 - 2 - 0 - INV 。

遍历这个链表也很容易：

static inline particle_id
material_begin(struct material_context *ctx, material_id matid) {
   return ctx->head[matid];
}

static inline particle_id
material_next(struct material_context *ctx, particle_id prev) {
  return ctx->index[prev];
}

for (particle_id i = material_begin(ctx, matid); i != INVALID_PARICLE; i = material_next(ctx, i) {
   ...
}

进一步，我们可以在整理后，记录下每个材质的对象个数，如果为零，就可以重新调整一下，把材质属性数组中最大的材质 id 映射成已经没有人使用的 id 。把 id 空出来供新材质使用。

我们引擎外层是用 lua 封装的，所以，所有的材质可以放在 lua 表中，用更长的 key （例如材质名）索引，不向应用层暴露内部的材质 id 。在 C 层上，则 cache 住最多 255 个材质对象以供渲染 api 直接取用。

这里保留一个材质 id 作为空材质。万一同时存在的材质超过了 255 个，就设置为空材质，渲染阶段直接跳过。

Posted by 云风 at 10:41 AM | Permalink | Comments (3)