« January 2019 | Main | March 2019 »

February 24, 2019

跟踪 Component 的修改

在 ECS 框架中,每个 System 在每次更新时,都遍历一类 Component 依次处理。这对于游戏的大多数场景都适用,因为游戏引擎要处理的对象通常是易变的。对于每个对象单独判断是否应该处理反而有性能负担。

但是,总有一些应用场景下,只对一类 Component 中的一小部分做修改,而没有被修改的对象可以保持上次的数据,而不必重复运算。在需要重算的对象数量远小于总量时,每个更新就很不划算了。

为了减少运算量,我们通常的解决方案是增加一个脏标记,修改时设置,设置它。这样就可以在处理的时候只处理被标记过的对象。常规的脏标记实现方案有两种,一是在 Component 上加一个 bool 字段,遍历的时候跳过没有标记的对象;二是在 Entity 上动态添加一个用于 tag 的 Component ,视作脏标记,遍历后再清除这个 tag 。

不过这两种方案在 lua 实现的 ecs 框架中,使用代价都比较大。

lua 和 C/C++ 不同,函数调用的成本相对比较大,为脏标记添加一个 set 方法不仅增加了运行成本而且也不符合 lua 的使用惯例(增加了使用成本)。我考虑用元方法来减少成本。

我们可以给需要跟踪的 Component 创建一个叫修改集 Modify 的结构,例如,如果要跟踪 transform 的修改,就创建一个 transform.modify 的修改集。这是一个特殊的有元方法的对象。对 transform.x 的修改,写作 transform.modify.x = newx 。这是一个更符合 lua 风格的用法。置脏的过程就隐藏在元方法里面。

modify 的实现依赖三张表。

  1. modify 对象本身,里面记录有关联的 entity id ,实际的数据区,元表。
  2. 持有修改后的数据的数据表。
  3. 元表,用来触发脏的行为。

工作起来是这样的,元表的 __index 关联到数据的数据表;元表先把 __newindex 关联在一个函数上,这个函数负责把 modify 关联的 entity id 添加到脏集合中,在第一次改写关联数据的时候触发。触发之后,修改 __newindex 元方法,直接引用和 __index 相同的数据表。

从第二次修改开始,就不再触发置脏的过程。元方法是有额外成本的,但 __index__newindex 关联到表而不是函数上,性能可以有极大的改善。

注意,读取 modify 结构本身是不触发置脏流程的。通常,业务逻辑只用关心老版本(上一帧)的 transform 状态;如果它必须关心当前帧是否有人修改 transform ,也可以主动查询 transform.modify 。

然后,我们提供 modify 集合的遍历方法,在一个独立的 system 中集中处理这一帧所有的修改集。在遍历之后,我们重置脏集合以及所有的 modify 的元表中的触发器。


我们实现这样一个机制的动机在于解决场景树的更新问题。场景树上的非叶节点的 transform 的修改会导致整个子树,另外,节点还有可能更换父亲,同样会导致整个子树的变化。

但是,整个场景的结构通常是稳定不变的,只有少量节点会经常更新自己的空间位置。我需要一个相对廉价的方案来决定场景树的哪一部分需要更新重算。

下一篇 blog 我将展开这个具体案例。

February 18, 2019

最近对 ECS 框架的一些想法

我们的游戏引擎采用 ECS 框架。最近一年的开发,为 ECS 框架的应用积累了不少经验。我在 blog 上也写过数篇 ECS 相关的东西:

Lua 下的 ECS 框架

ECS 中的 Entity

最近两个月,结合过去的经验,我们对最初设计的框架做了较大的调整。这主要是源于对框架要解决的事情的更深入的理解,以及在实践过程中针对典型场景总结出来的模式。

首先,我们去掉了 Lua 实现 ECS 框架的一些技巧 中提到的一些东西:Notify 机制被证明的过于复杂且可以有别的替代方案,这点下面那会展开讲;Component 的方法是多余的,当初加上它更多是因为 OOP 的惯性思维。

最大的改变是对 System 的思考。

System 的存在是为了解耦不同的业务,把引擎要解决的事情分成尽量不相关的部分,并可以用数据驱动其运行流程。

System 不能通过直接调用来传递状态。这是因为 ECS 框架解决的是大批量同类对象做类型的业务,我们希望针对批量对象做 Step A ,全部完成后,再做 Step B 。所以不能在针对单个对象完成 Step A 后立刻调用 Step B 的流程。

System 不能保存中间状态。这也是因为 ECS 框架处理的批量对象而不是单个。

只有加上这些限制,才能做到系统间解耦。但同时也衍生出难题:到底如何控制 System 运作的次序。

最初的设计中,我们对 System 的名字排序,然后针对性的标注有相互次序依赖的 System 的前后次序。可是当 System 数量上去后,这种全局式的描述次序会对使用人造成极大的负担。

由于 System 本身不保存状态,所以我们设计了 Singleton 用于保存 System 的状态,以及充当 System 间数据交换的载体。同时,我为 System 设计了 init 方法,一般用来初始化对应的 Singleton 。这些 Init 方法必须是有序的,这就需要在 System 定义时描述清楚相互依赖关系。利用依赖关系做拓扑排序,不仅仅可以筛选出关联的 System 集合,还可以决定它们的初始化次序。后来,我们发现这些依赖关系不仅可以用于初始化流程,更新过程其实使用这个次序也并非不可。但这也促使我思考,init 流程是否应该是个特殊的东西,还是应该放到一个抽象层中。

对于客户端来说,所有的 System 并非服务于单一事务。例如做渲染的 System 和做物理模拟,动画计算的 System 就是相对独立的事务。它们的更新频率都不相同。还有处理输入设备消息的 System ,如果放在渲染流程中,即每个渲染帧主动去检查是否有输入,看起来也很浪费。

综上所述,我认为我们有必要对 System 分组。不同的组由驱动框架运转的代码编码在不同的地方:例如,外部输入消息产生时,驱动消息处理的 System 组;每个渲染帧驱动渲染更新 System 组;时钟用来驱动每个固定频率的物理帧及动画帧。

其实,我们可以把 System 看成一个无状态的函数对象,它针对某些 Component 处理了某种事务。但它又不仅仅是一个 update 函数,我们还需要定义它们之间的相互依赖关系。从这个角度,init 流程其实只是一个分组而已。这样,一个 System 可以看成是多个函数对象的聚合,每个函数对象处于不同的分组中,而 System 在定义时则描述出和其它 System 的依赖关系,以及对特定 Singleton 的依赖。

Init 这个 System 组只被调用一次,且不应由 World 的创建过程默认驱动,而应该把调用职责交给使用框架的人。这样,使用者就可以灵活的决定在 World 反序列化结束后,所有数据都安置妥当,再驱动 System 的初始化流程。Init 也不再是 ECS 框架的底层概念,而被看成是一个和其它分组平等的概念而已。

Component 的新建和移除也是很多 System 所关心的事情。之前我设计了 Notify 方法来处理它们,但实际用起来并不顺手。我现在认为,应该放在独立的分组里。比如,增加新增对象 System 组和删除对象 System 组。但这会导致对象构建和删除过程的延迟处理,守望先锋的开发团队认为,删除对象可以也最好被延迟处理,但是创建对象最好是及时的。我就这个问题是这样约定的:

创建对象,我们立刻将对象(Entity) 立刻加入 World ,由创建者负责初始化该对象的状态,它有可能被当前帧更新,也可能在下一帧更新;但它和其它对象的交互,是放在下一帧的新建对象 System 组来完成的,例如,该对象被加到物理世界中的过程,就是物理 System 的新建对象函数来添加它;渲染 System 的空间裁剪器也是推迟到下一帧去处理它。

我为新增对象增加了一个 world:each_new(component_type) 迭代器,可以迭代出某类 Component 所有新构建的对象,每次迭代后,就自动从新对象集合中移除,也就是说,一个 Component 只会被迭代一次。

对于删除对象,每次调用 world 的 remove_entity 删除一个 Entity 或用 remove_component 删除 Entity 上的一个 Component ,都可以在后续的 world:each_removed(component_type) 中迭代到。和 each_new 不同,each_removed 可以迭代多次;直到使用者主动调用 world:clear_removed 清除。

world:clear_removed 其实是一个延迟删除的过程,推荐在每帧固定调用一次。它会清理暂时记住的被清除的 Entity id 集合,还会调用删除的 Component 的析构函数(如果定义了)。


另一个重构的部分是 Component 的类型系统。

我们为 Component 设计一个类型系统主要是为了解决两个主要问题:

  1. 作为一个数据驱动框架,我们需要对 World 做序列化和反序列化。编辑器需要持久化编辑出来的 World ,运行时可以从数据文件中读出序列化的结构,序列化必须依赖一个类型系统。

  2. 编辑器需要依赖类型系统,通过反射,生成 Component 的编辑控件。

Component 是基于类型系统定义出来的类型的,Component 往往是定义好的类型的组合。

我选择使用 lua 原本的语法来描述类型,目前看起来像这样:

p:type "NAME"
    ["temp"].a "int" (1)
    .b "OBJECT"
    [ "private" ].c "id" (0)
    .array "int[4]" { 1,2,3,4 }
    .any "var" (nil)
    .map "int{}" { x = 1, y = 2 }
    .color "color"

.name 定义了字段名,紧跟着一个字符串描述了类型,后面可选一个小括号定义出它的默认值。字段名前面还有若干可选的中括号,给该字段加上 tag 。这些 tag 供序列化模块和编辑器做类型反射时参考。