云风的 BLOG

目前，我们用 ECS 管理游戏引擎中的对象。当游戏场景大到一定程度，就需要有一个机制来快速筛选出需要渲染的对象子集。换句话说，如果你创建了 100K 个 Entity ，但是只有 1K 个 Entity 需要同时渲染，虽然遍历所有可渲染对象的成本最小是 O(n) ，但这个 n 是 100K 这个数量级，还是 1K 这个数量级，区别还是很大的。

我们的 ECS 系统已经支持了 tag 这个特性，可以利用 visible tag 做主 key 快速筛选可见对象。但当镜头移动时，需要重置这些 tag 又可能有性能问题。重置这些 visible tags 怎样才能避免在 100K 这个数量级的 O(n) 复杂度下工作？

一个容易想到的方案是给 Entity 分组。比如在超大规模的场景下，我们可以按区块来分组。根据镜头所在的位置，可以快速的确定哪些 group 是关心的，哪些不必关心。

我首先想到的是用多个 world 来描述整个场景。每个 world 是一个 group ，按地理位置存放 Entity 。但这有明显的问题：渲染的有些环节是唯一的，比如 PreZ 阶段生成 Z Buffer 、后处理阶段处理屏幕空间的效果，这些需要多个分组一起处理。

所以，我还是倾向于给 Entity 加一个 group id 来区分它们。

如果把 ECS 看成是一个内存数据库，那么，我们的需求是 where 字句的查询功能。可以快速的筛选出 group id 属于某个集合的 Entity 。筛选合乎要求的所有 Entity 的成本应该是这类 Entity 的数量级，而不是 world 中所有 Entity 的数量级。

只有这样，才适合做大规模的场景，扩大场景对象数量的规模不影响渲染性能。

我希望这样一个分组功能相对已有的 ECS 特性是非侵入的，它最好不要修改已有的数据结构。在不使用分组功能时（小场景），不要影响基本功能。基于此，我设计了这样一个数据结构：

每个 Entity 可选一个（或多个） group 索引结构。group id 只能在创建 Entity 时赋予，并不可修改。我们在构建过程通过 group id 来维护这个索引结构。

该索引结构有四个字段：

uint64_t uid;
uint64_t lastid;
uint32_t groupid;
uint32_t next;

其中，uid 是 64bit 自增 id ，每个 entity 在创建时被赋予唯一 id ；groupid 是它所属的分组号；lastid 用于索引同组的前一个对象的 uid ，next 则用于快速定位前一个同组对象。

这个索引结构就是一个普通的 component ，实际存放在一个连续的数组中。因为 Entity 只能在创建那一刻赋予唯一 uid ，而 uid 又是单调递增的。所以，这个索引结构的内容的 uid 字段是严格有序递增的。

在这个索引结构中，依靠 uid / lastid 便可以按 groupid 自然分成若干组。而 next 字段描述的是同组的前一个对象在这个索引结构数组中的相对偏移量。

当 Entity 没有删除时，next 形成了链表，可以快速的遍历所有同组对象，而 lastid 可以用于双重校验。

一旦 Entity 删除，我们不必立刻更新这个链表。在下次遍历时，next 会指向错误的位置，但通过 lastid 可以快速修复链表（因为正确的同组对象所在的位置就在附近）。

利用这个索引结构，我们可以快速的遍历出同组的 Entity ，并打上 tag 。之后，就可以利用 tag 来正常检索了。对于大世界场景，我们按地图区块分好 group ，再利用镜头所在位置，快速计算出附近有哪几个 group 需要渲染，就可以快速生成 visible tags 。

除了用于维护 visible tags ，这个分组功能还可以用于快速删除不必保存在内存中的 Entity 。只要根据 groupid 删选出来再批量删除即可。

以上的工作在 这个 commit 中体现。

Posted by 云风 at 09:58 AM | Permalink | Comments (16)

今天在扩展我们游戏中的管道系统时，又遇到了实现一个无向图的问题。

之前的管道系统，每节管道的邻接管数量有限，所以我用了类似树的方式储存，在每节管道上直接放了一个固定大小的数组，保存该节管道的上下游节点。对于液体管道系统，这套数据结构工作的很好。

今天，我们的另一个系统需要一个有点不一样的管道。它没有方向，每个节点可以有很多的邻接点。例如电线拉成的网络、导热管构成的网络，都是这样的。这是典型的无向图结构。

我重新考虑了数据结构，用邻接表实现了一版。

我把节点的数据和节点的邻接关系分开到不同的数据结构中，这样方便单独把管道连接模块独立出来复用。

首先，用一个有序的数字 id 表示图中的节点。由于我们的图规模不会太大，16bit 的 id 就够用了。那么，相邻节点的连接关系就是图中的边，它可以用两个 id 连起来共 32bit 表示。由于是无向图，我们可以把较小的 id 固定在低位，这样边就有唯一的表示方法。

btw, 如果需要扩展到有向图，则需要留一个 1bit 表示它是有方向的。

如果不考虑访问效率，那么，只需要用一个数组把这些 32 bits 数据储存下来即可。（事实上，数据持久化时我只保存了这些数据，其它部分都可以快速重建）

但是,运行过程中还需要快速的从一个节点检索到所有关联的边。以用来处理能量在网络中的流动。

我在节点边对象上放了两个链表指向两个端点的边集合。所以，边的数据结构看起来就是这样的：

struct edge {
  uint16_t endpoint[2];
  uint16_t left;
  uint16_t right;
} ;

另外有一个 uint16 数组指向每个节点的第一条边。如果某个节点一条边都不存在，它可以指向任意一条边（通常是 0）。因为边本身可以反过来校验是否临接节点。

如果不需要快速动态增删边，还可以进一步压缩这个数据结构。每条边只需要 48bit 就够了。因为每条边只属于两个顶点，我们可以把其中一个顶点所属边的集合排列在一起，另一个集合用链表表示，这样就能省下 16bit 。

这里还有一个小技巧表示链表的结束，那就是把两个端点的 id 反过来储存。（一般情况下，第一个端点 id 一定比第二个小）。

例如有这样一张图：

1 - 2 - 3
|   |   |
4 - 5 - 6
|   |   |
7 - 8 - 9

它由 12 条边构成，我们可以按次序排列这些边：

[0] (1,2) 2
[1] (4,1) 5
[2] (2,3) 4
[3] (5,2) 5
[4] (6,3) 7
[5] (4,5) 7
[6] (7,4) a
[7] (5,6) 9
[8] (8,5) a
[9] (9,6) b
[a] (8,7) b
[b] (9,8) b

1 : 0
2 : 0
3 : 2
4 : 1
5 : 3
6 : 4
7 : 6
8 : 8
9 : 9

比如，想遍历 5 这个顶点的所有边，从下面的表查到它的第一条边在索引 3 的地方，也就是 (5,2) 5 。 因为 5 比 2 大，所有第二条边在 index 5 ，也就是 (4,5) 7。 因为 5 比 4 大，所以第三条边在 index 7 ，也就是 (5,6) 9。 这次 5 比 6 小，且 5 在前面，所以第四条边就在后一项：(8,5) a 。 8 和 5 是反的，这就是最后一项。

到此，四条边都找出来了。

我花了半天时间实现它。无向图在我的日常工作中不算常见，我只在读书时做习题时实现过。想到这样一个紧凑的数据结构还是挺满意的。实现完后又去 wikipedia 上查了一下，发现早有人提出过一个基本一样的想法了 :) 不过我后面那个压缩的方案不知道有没有前人实现过。

Posted by 云风 at 09:48 PM | Permalink | Comments (12)

VLA （可变长度数组） 是 C 语言在 C99 之后加入的一个很方便的语言特性，但是 MSVC 已经明确不支持 VLA 了。而且 Linux 的内核代码中曾经使用过 VLA ，而现在已经移除了 VLA 。看起来，VLA 带来的安全问题比它的便利性要多。

但是，日常用 C 语言做开发时，经常还是需要变长数组的。既然直接用 C 语言的 VLA 有诸多问题，那么还是需要额外实现一个比较好。C 没有 C++ 那样的模板支持，一般的通用 VLA 实现很难做到类型安全。即使用 C++ ，STL 中的 vector ，这个最常用的 VLA 实现，也不总是切合应用场景的。比如，std::vector 它的数据一般还是分配在堆上，而不是栈上。相比原生创建在栈上的数组，它可能性能有影响且有可能制造更多的堆内存碎片。

我认为一个通用的 VLA 库，应该做到：

1. 强类型支持，且不需要每次调用相关 API 时都指定数据类型。
2. 当我们在栈上使用 VLA 时，应该尽量接近原生数组的性能，尽可能的避免从堆上分配内存。
3. VLA 可以方便的在函数间传递引用。
4. VLA 的引用可以持久保持。
5. 访问 VLA 的数据可以被 inline ，尽可能的避免额外的函数调用。

由于我的 C 代码大量的和 Lua 交互，如果 VLA 可以利用 Lua 来管理内存，而不直接使用 C 的内存堆，会是一个不错的加分项。这样、在 Lua 函数中临时使用 VLA 时，小块的内存便可直接在 C Stack 上分配；大块内存可以利用 Lua 的临时 userdata ，然后交给 Lua 的 GC 回收。我们在退出函数调用时，就不必显式的销毁 VLA 对象。

之前我写过好几版 VLA 库都不太满意。最近找到了一些技巧，重新实现了一版，以上的需求基本都满足了。

第一个棘手的问题是，C 语言如何做到通用且类型安全的 VLA ？我是这样解决的：

对于一个 VLA 对象，其实分两个部分，其一是用于数据访问的指针，我称之为访问器，其二是 VLA 本身的数据，包括实际数据和元数据。元数据一般有数组的大小、容量等，实际数据一般储存在连续内存空间中。

访问器本身需要契合 VLA 内部数据的类型。而 C 语言在泛型支持方面很弱，传统的方法是用 void * 来指代数据区，这就导致了很多 VLA 实现的 API 难以使用。

我的 VLA 实现引入了两个概念。对于 VLA 对象本身，我用一个抽象的 vla_handle_t 类型来保持引用，而访问器则选用 raw 指针，这个指针的类型直接是内部数据的类型。因为访问器本身可以以非常低廉的成本从 handle 构造出来，所以它并不需要持久保存。这就为宏技巧提供了空间。

所以，最终的 API 就是 vla_using(name, type, handle) 。这是一个宏，它的作用是在栈上创建出一个名为 name 的访问器，并通过 handle 关联相关的 VLA 对象。下面是一个简化的示意版本（实际因为需要实现更多功能，比这个复杂的多）：

#define vla_using(name, type, handle) \
    type * name; \
    vla_handle_t * name##_ref_ = &handle; \
    init_vla_accessor((void **)&name, name##_ref_);

在使用这个 api 时，栈实际多了两个变量。一个是用户指定名字的访问器，它就是一个原生指针，所以在访问数据时，和原生数组没有任何区别；同时，还在栈上记录了 VLA 对象本身的引用。当我们想对 VLA 对象操作时，访问它就可以了。比如，求 VLA size 的 API 也是一个宏：

#define vla_size(name) vla_size_(name##_ref_)

这个宏把指针访问器的操作转发到了对应的 VLA 对象 handle 上。

第二个问题是，如何兼顾堆和栈的内存使用。

如果只有一个 VLA 数据结构，当我们在栈上使用的时候，倾向于在数据结构中预留一块几百字节的临时空间。如果数据不超过这个空间，就不必申请堆内存。函数调用结束后，这些栈空间就立刻回收了。但如果我们需要持久引用 VLA 对象，这个预留的额外空间就显得太浪费了。当然可以显式的做两套实现，由使用的人根据场合分别用对应的方案。但还是需要把它们两者统一起来，这样才可以有一致的接口，当模块不关心细节时，可以一致的使用。

所以我选择用一个 handle 来表示不同实现的 VLA 。

第三个问题和 Lua 有关。在栈上的临时内存空间如果超出，我们就需要申请额外的内存维持更大体积的 VLA 。一般的实现中，这些额外的内存会从 C 的内存堆中分配。对应的，在函数返回时，需要释放这些内存。如果我们临时创建 lua 的 userdata 就没这个烦恼了。Lua 在退出 C 函数后，那些临时构造的 userdata 会失去引用，随后被 lua GC 回收。在 Lua 5.4 中，启用分代 GC 的话，这个回收非常及时。

所以，我们还需要第三种 VLA 实现：采用 Lua 管理内存。

Lua 的内存管理和传统 C 程序很不一样，它并不是配对的分配/释放调用，而是围绕引用进行的。我们在给 C 模块做 Lua binding 时也经常会遇到一个固定的 C Struct 中需要一个 VLA 对象的情况。这时，如果 VLA 也用 Lua 管理内存生命期的话，就不用给 C Struct 添加额外的 gc 元方法了，而只需要把 VLA 对象所使用的 userdata 通过 uservalue 引用在宿主对象上。

我们的 VLA 模块需要兼容这种用法。

综上所述，我初步实现了一版。

Posted by 云风 at 02:53 PM | Permalink | Comments (5)