« March 2020 | Main | May 2020 »

April 30, 2020

游戏引擎中预制件的设计

Unity 推广了预制件 Prefab 这个概念,在此之前,Unreal Engine 里有个类似的东西叫做蓝图 Blueprint 。当然它们不完全是一种东西。我现在自己设计游戏引擎,更喜欢 Unity 中的 Prefab ,但我认为 Blueprint 这个名字其实更贴切一些。

当我们说制作一个 Prefab 的时候,其实制作的是一个预制件的模板。引擎运行时对应的那些数据,其实按照这个模板生产出来的。所以,工具制作出来的 Prefab 其实是一个 template ,所以,它本质上就是一张蓝图。但因为 Unity 深入人心,所以我还是打算基于把这个东西叫预制件。

对于 ECS 系统来说,预制件是一组数据,通常保存在文件中,可以以该资源文件的内容为模板,来构造一组 Entity。注意:预制件作为资源文件时,和贴图、模型数据等这些资源文件是不同的。贴图之类的资源,映射到内存后,就是一个数据块或一个引擎中的 handle ,可以被共享使用。但预制件本身只是一个模板,它用于生产数据,本身不是数据。从这个角度讲,如果把预制件文件当作资源纳入资源管理模块统一管理的话,预制件资源对应的是一个 function (生成器)而不是 table (数据集)。

预制件本身是通过引擎的工具制作而成的,如果我们把场景也看成一个嵌套而成的大的预制件模板生产出来的产品,那么预制件编辑器其实就是场景编辑器。

从编辑好的场景转换为(预制件)模板,其实就是从预制件生产出一系列 Entity 的逆过程。这是一对针对构成 Entity 的 Component 的序列化和反序列化过程。

因为 Entity 是 Component 的聚合,而 Component 就是纯数据,对于单个 Entity ,序列化每个 Component 都不是难事。难点在于多个 Entity 之间的关系该如何描述?

游戏场景中的物件是以树状层次结构堆砌在一起的。我们需要描述谁是谁的父亲,谁是谁的孩子。在运行数据中,描述这些关系的字段中,通常都是 entity id 。但我们是不能直接把这些 id 持久化的。在我们引擎之前的设计中,我们将这些 id 先转换为 GUID ,然后再做序列化工作。反序列化时再转换为 entity id 。而在最近的重构中,我反思了这一块的设计,感觉这并不是一个好方法。

理由:

  1. 如果缺少 schema ,我们很难知道 Component 中的 entity id 字段做自动的转换。为此,我们之前的 ECS 框架设计中,要求为 Component 描述非常具体的 schema 。而在最近的重构中,我觉得引入一个繁复的 schema 获得的好处比引起的麻烦多得多。毕竟我们的开发语言 Lua 惯例上是不考虑数据的 schema 的。
  2. 建立 Entity 之间的联系未必只是在数据结构中把 id 填对就够了。它往往在构建流程中还需要额外做一些事情。对于单个 Entity ,可以用类似构造函数的范式去解决;但是对于多个 Entity 往往需要等这些 Entity 都创建好后,才能进一步的建立起联系。我们现在的 ECS 框架设计中,引入了消息机制来解耦;但是还是需要一个额外的过程去发送这条消息。
  3. 预制件模板能用来生产多个 Entity ,这些 Entity 既有内部之间的相互引用,还可能有对外的引用。内部之间的引用并不需要全局 GUID 来描述,而对外的引用 GUID 其实无法解决问题。这是因为,预制件并不是预制好的一组数据(刚才已经解释过),而是预知数据的模板方法。所以这里的 GUID 语义上就不指代某个具体的对象。当我们把一个 Prefab 实例化两次后,其实生成的是两套对象,相互是独立的。
  4. 预制件是可以嵌套的。即预制件可以由若干预制件构成。但,一个预制件引用另一个预制件特定的一部分却是没有意义的。因为上面已经分析过,预制件描述的是一组相互有关联的 Entity 的聚合体的构成方法(模板),聚合体中的部分并不具备完整的语义(无法描述出部分构造的方法)。故而,给预制件中的部分生成一个全局的 GUID 就失去了意义。

那么该怎么设计?

这里有两个问题:其一,我们怎么生产出一个预制件数据文件;其二,我们加载这个文件并根据数据生产出实物的 API 应该有怎样的行为。

第一个问题和引擎的工具链有关,第二个问题涉及的是引擎运行期的 API 设计。它们是相关的问题,对我们现阶段的引擎开发来说,又是一个先有鸡还是先有蛋的问题。这类问题通常都比较头痛。需要一起来考虑。

先看第一个问题,可能我们面临两个具体需求:

  1. 我们需要从外部工具,例如 max maya 等建模工具中导入模型数据。一般是 fbx gltf 等通用格式。我需要引擎能直接使用。那么最好能一致的将这些通用格式文件转换为我们的预制件文件。即,一个 .fbx 或 .gltf 文件就能视同引擎支持的预制件文件。
  2. 当我们在编写场景/预制件编辑器时,需要复选已经编辑好的场景中的若干物件,为其生成一个预制件文件,供以后重复使用。

暂时我们先解决第一个需求就够了。它会是一个独立的工具。以后再实现第二个需求,它会是一个库共编辑器调用。有可能当我们实现完第二个需求后,这个库又可以反过来成为第一个需求中的工具的一部分。那就是后面重构的工作。

但是这两个需求面对的数据源是不一样的:前一个需求面对的是标准数据文件,后一个需求面对的是内存中的 Entity 。我们要考虑好,这个预制件文件的格式是怎样的,如果设计不好,即使现在把第一个需求的工具做好了,以后可能无法很好的编写第二个需求中要的库。

经过一番思考,我认为 prefab 文件中的数据应该分成两个大部分。

一个是 Entity 集合,及每个 Entity 的数据是怎样构成的,这些数据就是构成 Entity 的 Component 的序列化结果。我们不需要设计 Schema ,而让数据自描述,这样会更具弹性。

但在这些序列化数据中,不应该包括 Entity 之间的联系。例如,层次结构的描述就不应该包含在这些数据中。能保证每个 Entity 能独立地从数据中创建出来就够了。

第二个是如何为上面数据集中的 Entity 建立关联。我设想的是让俺组动作数据,每组由一个 action 的名字跟着若干 id 构成。这些 id 既可以指代第一部分中的 entity ,也可以指代某个外部 Entity 。例如,

mount 1 0

这样一行表示,我需要把第一个 entity 挂接在外部根对象(0) 的层次结构之下。

对于从预制件文件生产出运行时对象的 API 大概是 produce(prefab, entity_id) 。其中,prefab 是模板数据,从预制件文件中获得;entity_id 是可选的,如果提供,则是一个已经存在的 Entity 的 id 。

  1. 将预制件中描述的一组 Entity 基于数据创建出来,得到了一组 entity id 。
  2. 依次运行预制件文件后半段中的动作(前例中的 mount 那些),将参数中的内部 id 转换为第一步产生出来的 entity id 以及外部传入的 id 。
  3. 返回最终的 entity id 组,通常会被调用者忽略。

如需在编辑器程序中生成这样的预制件模板文件,对于前一部分,简单的序列化构成 Entity 的 Component 即可。

对于后一部分,因为我们的 ECS 框架中 Entity 缺少类型信息。所以我采用了一种粗暴但简单的方式:注册一组函数。每个函数可以自己探测要不要为每个 Entity 生成一个 action 。例如,mount 这个 action 对应的函数,会探测一个 Entity 是否属于场景层次结构中的对象,如果是,就生成一行 mount parent_id child_id ;否则就忽略。

prefab 可以嵌套。如果需要构建的 prefab 模板对应的数据源对象集合中有一个对象表明当初是用 prefab 构建出来的,那么它是一个场景上的虚拟节点,即只有场景场次结构的信息,而不具备渲染实体。那么序列化结果只是一个 prefab 的资源文件名。那么在 action 字段中,我们添加一个 produce id 行,即可让 prefab 构建流程能够递归的创建出每一级的对象。


此外还有一些细节,由于尚未去实现,这里就不展开。等这一块重构完成,可能还会发现新的细节问题。

例如:一个 prefab 可能是在另一个 prefab 基础上构建的。虽然一个 fbx/gltf 文件可以视为 prefab 使用。但我们的工具不具备修改 fbx 文件的能力。如果在编辑工具中导入一个 fbx 文件,又不想复制为自己的专有格式的话,那么对这样的预制件修改后的结果,就应该看成是一个 prefab + patch 得到一个新的 prefab 。

而另一方面,我们很可能需要把修改后的结果保存为全新的 prefab ,去掉对原有 prefab 的引用。

不是所有 prefab 都是场景层次结构上的物件。例如“平行光源” 就不存在于场景层次结构中,只是场景的一个属性。但是“平行光源” 这个东西作为一组数据,并会在运行时作为 Entity 存在于 world 中。它的处理方法必然和前面所述的 prefab 不太相同。

关卡也不可完全视为是场景实物的层叠堆砌,它还包含了上一段提到的 “平行光源” 等额外的对象。如果有和关卡有关的代码,我也希望可以纳入 prefab 的统一管理。从这个角度看,prefab 就会更接近 Unreal 的蓝图的概念。

April 15, 2020

资源模块的重构

这篇是对 游戏引擎中的资源生命期管理问题 的延续。

最近对我们游戏引擎的资源模块做了一次重构,大概花了一周的时间,其中核心模块的代码实现花了 2 天。比之前的方案简洁很多。新方案的设计是基于以下原则来实现的:

  1. 引擎应该围绕数据来设计。ECS 更是数据驱动的模型。
  2. 数据全部都用一致的数据结构来表达,方便统一处理。因为我们采用 lua 做开发,所以,一切数据都是 lua table 。我们的引擎与其说是基于 lua 开发,不如说是基于 lua 的数据结构开发。即使某些模块因为性能因素用 C/C++ 实现,操纵的还是 lua table 。读写 lua table 的性能和读写 C struct / array 相比,并无显著的劣势。
  3. 在使用上尽量不区分外部不可修改的静态数据和运行期动态修改的数据。
  4. 惰性加载,延迟异步加载,替代资源,这些尽可能的隐藏起来,不必对外透露细节。尽可能的减少外部干预。
  5. lua 虽然有 metatable 这个神器,可以帮助我们抹平不同数据、不同策略之间的差异。但不要过多依赖语言特性。

我们的 Component 本质上就是树状的数据结构表达的一组数据。对 Lua 来说,就是一个带或不带层次的 table 。同样,我们也可以把一切外部数据都视为相同的树状表。

所以,一个外部资源文件的加载器,就可以写成:通过一个资源文件名初始化的状态机,产出一张 lua 表。lua 表中可以是 lua 支持的数据类型,如 number string 这些,也可以是引擎再加工的 handle ,如 texture, vb, ib, framebuffer 等。

运行时任何的数据都可以表示为一个普通的 lua 表,也可以是一个资源文件名+字符串路径引用的子树。通过 metatable 的机制,在使用上可以是一致的。但这个 metatable 的行为,可以根据数据的状态:在内存,不在内存,等进行不同的处理。

资源文件我倾向于把类型信息编码进去,也就是不采用额外的 schema 描述。这样,任何保存在文件中的数据,都可以用一致的表达方法。但是,根据不同的资源类型,可以实现不同的加载器。加载器更多的作用是进行数据到运行时的翻译工作:比如,把一块贴图数据变成贴图的 handle 。

因为引擎是围绕数据工作的。所以创建一个 Entity 就是从一个 prefab 文件实例化出来的。prefab 文件本质上就是 Entity 的初始化数据集。在引擎的使用层面,我们甚至不必提供用纯代码构造 Entity 的 API ,唯一的 API 就是从文件实例化,然后允许用户进一步修改。

这样,产生 prefab 文件的工具,就成了日常工作流的一部分。我们之前的开发流程并不是这样做的,我们之前尽可能的用人去写代码来做底层的开发,测试,脱离了工具。导致工具的开发从引擎开发中剥离了出去。正在做引擎的人不依赖正在做工具的人,虽然解开了依赖性,也造成了不吃自己的狗粮。毕竟,最终引擎的用户,面对的就是一个开发工具,而不仅仅是引擎的库。这次对工作流的调整,修改希望终结这种 现象,让工具变得更好用。

之前一直没有这样做的原因之一是我们的脚手架还没有搭建稳定。这里有一个先有鸡还是先有蛋的问题。脚手架没有完工,会让工具无法正确工作,如果库的开发过多依赖尚未稳定工作的工具,则会影响开发本身。这个结就无法解开。而经过了一年多的开发,是时候拆脚手架了。


回到资源模块这个话题。

我们对运行期的数据,如果引用的是资源文件的一部分,就将其实现为一个代理对象。这些代理对象按所属资源文件分类,分别管理。我为每个资源文件中的每个子树都生产一个代理。理论上,整个游戏所引用的这样的数据块的总量是固定的,这个代理对象本身不一定包含真正的数据,它的内存占用是有限的,所以我永远不清除这些代理对象。减少管理的复杂度。

当代理对象代理的数据在内存中时,它指向加载器加载出来的数据表。我们可以通过代理对象的元方法监测数据的使用情况。虽然监测本身有成本,但可以随时将元方法更换为对数据表的直接引用,提高性能。

注:lua metatable 的 index 如果指向一张普通 table 时,性能大大高于指向一个函数。

如果我想知道一张贴图最近是否有人使用,只需要把这张贴图的代理对象的监测方法,以一定周期性的抽查,比如在过去 5 分钟,抽查 100 次。如果没有使用,就可以认为它可以暂时清理出内存。

当代理对象代理的数据不在内存中时,可以把数据所属的资源文件下所有相关的代理对象共用同一个元表,这样,就可以用 O(1) 的代价修改所有对这个文件的引用的代理对象的行为。针对不同类型的资源,可以有不同的策略。

有些小文件,加载起来并不慢,我们可以采用直接阻塞式的惰性加载方案。一旦应用层访问到不在内存的数据,就阻塞住线程,把数据加载进来。

对于某些大文件,例如贴图,可以采用异步加载的方式。先用一张已经在内存的替代贴图顶上。并把加载操作提交到 IO 线程。待加载完毕后,再统一替换。

如果有一些特殊的大文件,即想做异步加载,又无法用替代物顶替,还提供的主动查询的 api 查询一个 lua table 背后的数据是否在内存。不过这需要上层业务了解更多细节,暂时只是在资源管理模块的 api 中预留了这个能力,并没有真的使用。


为了抹平普通运行数据和资源数据的区别,并允许运行时修改那些原本引用的是外部静态资源的对象,提供了一个叫 patch 的 api 。

我们规定,对 Component 的全部或部分的修改,必须通过 patch 进行,即 data.foo = patch(data.foo, { ... } ) 这样的形式。第二个参数就是要修改的内容,用 lua 表的形式提供(允许有树层次)。为了减少使用者的失误(例如拼写错误),不允许通过 patch 增加或删除原有数据中不存在的项。

如果想更自由的修改数据,也可以用 data.foo = patch(data.foo, {}) 先打一个空的 patch ,这样会把 data.foo 的第一层转换为运行期的普通表,然后就可以用标准 lua 语法对这一层自由修改了(删除已有项,或增加新项目)。

April 10, 2020

场景层次结构的排序

这篇是对 场景层次结构的管理 的再思考。

最近在重构引擎的场景管理模块。主要动机之一,还是觉得现在已经实现的东西(由于需求不断增加)太复杂了,以至于老在修补其中的 bug 。

经过了几天的思考后,我决定把场景管理中的一部分挪出来,单独作为一个模块。那就是对层次结构的排序。

具体是这样的:

游戏场景中的物件都处于一个树结构的某个层次节点上。之所以是一个树状的层次结构,是因为物件本身的某些属性的值是由层次结构中的父节点中的属性决定的。

典型的需求是物件的空间位置,通常在节点本身记录的是一个相对父节点局部空间的矩阵。但渲染模块处理物件,则需要计算这个物件在世界空间的位置,即世界矩阵。

还有一些类似的东西,例如,我们可以给一个节点设置一个材质,如果子节点未设置别的材质的话,则希望继承父亲的材质。

总的来说,每个节点的属性并非只记录在节点身上,还可能受父亲和祖先的影响。


标准的树结构是在每个对象中都保存一个父节点的引用,以及一组孩子的引用。但我不喜欢这样的数据结构。

首先,但这有明显的数据冗余,A 如果是 B 的父亲的话,这个关系同时记录在 A 的孩子引用中,也记录在 B 的父亲引用中。数据冗余会增加复杂度,滋生 bug 。bug 容易导致冗余数据的不一致。

其次,遍历树结构比遍历线性平坦结构需要更复杂的迭代器,也就是说,迭代过程的状态更复杂。尤其对于我们的 ECS 框架来说,保持迭代过程的简洁非常重要。

最后,一旦树结构中出现环,会让一些非常严重的 bug 滞后表现出来。而检查树结构的错误状态的成本也是比较高的。


我们一开始设计场景管理模块时就摒弃了这种传统的数据结构。我认为,场景对象只需要保留父节点 id 就足够了。内存中即有完整的场景层次结构。大多数物件并不关心自己的孩子有哪些,如果业务层真的需要遍历自己的孩子,完全可以额外再记录下来。

但这样设计的缺点也是明显的:在不做额外处理时,场景中的物件是无序的。

如果我们需要读取的场景物件的某个属性依赖父节点的状态,那么就需要上溯完整的祖先链。例如,计算物件的世界矩阵,就需要将自身的局部矩阵乘上父节点的局部矩阵,以及所有祖辈的矩阵,直到根节点。

对于处理整个场景来说,很多矩阵乘法都是多余的。

如果是用传统的树结构,因为遍历是有序的,遍历过程总能保证祖辈节点比后代先处理到,所以就可以减少重复的矩阵乘法。

那么,在现有的平坦结构(每个节点只保存父节点的引用)下,有没有办法也做到有序遍历呢?

我之前的做法是在遍历前做一次拓扑排序。并对拓扑排序结构做若干缓存处理,让引擎做拓扑结构不发生大的变化时,重整次序的代价尽量的小。

但这次重构,我发现了一个更简单的算法,可以在一个简单的数据结构之上实现出来。


如果我们给每个场景物件都赋予一个独立的 id ,其中,根节点的 id 为 0。那么,我们要的其实是一个用物件 id 构成的有序队列。所有场景物件都在在这个队列中,且,每个物件的父亲都处于队列中自身的前面

满足这个条件的队列远不止一个,对树进行深度遍历得到的序列,以及对树进行广度遍历得到的序列都满足这样的约束条件,甚至在遍历孩子时打乱兄弟之间的次序也没有关系。可见,维持这样的次序是很宽松的,所以我们一定能找到很轻量的算法来保持队列的次序。

假设我们的系统一开始,这个有序队列是空的,然后,我们 监听了所有对物件的父节点引用的修改事件 。这个事件是一个二元组,即谁的父节点变成什么。当新节点创建时,即为 一个新的 id 和旧有 id 的二元组。如果我们想删除一个场景节点,则是将某个节点的父节点引用设置为空。

可想而知,场景的构建过程,就是处理一个个这样的消息逐步完成的。

为了后续处理方便,我再设置了一个索引表,记录下队列中每个节点 id 在队列中的位置,以及每个 id 的父 id 是什么。

接下来就可以处理消息了。处理这个二元组消息分这样几种情况:

  1. 如果是新节点引用旧节点,即创建了一个新 id 指向已有的 id 。那么,我们只需要把新 id 放在队列尾。因为已有 id 一定在它的前面。

  2. 如果新节点引用另一个新节点,即父子对都还不存在于队列中。那么,我们只需要把两个新节点都放在队列尾,父亲在前,孩子在后。同时,把父节点的父亲设置为根 id 0 。

  3. 如果是一个已有节点引用另一个节点(如果不存在则将这个新的父亲先家道队列尾),这就意味着,节点需要更换父亲,这样我们的队列次序可能被破坏了。需要调整队列,保持有序。

这是最复杂的情况。这时,应该查询一下父子两个节点在队列中的位置。假设子节点位置为 P ,父节点位置为 Q 。

如果 P > Q ,那么子节点依然在父节点的后面,什么都不需要做。

如果 P < Q ,那么,我们需要调整 P 和 Q 之间这一段,保持队列有序。这时,我们可以新建一个临时队列 T ,把 Q P 先放进去。然后遍历 P 和 Q 之间这一段,比较每个节点,若节点的父亲在 T 中,则把该节点加在 T 的最后;否则把这个节点向前挪,顶到 P Q 区间的前段。遍历完毕后,就可以把 T 补在 P Q 区间的后段。

关于删除节点,即把对应节点的父引用设为空。我们在遍历时,可以同时检查父节点是否为空,如果是,则将自己置空。这样就可以在遍历完毕后,找到删节点的所有子节点一并删除了。


我把以上的算法及数据结构单独放在一个 lua 模块中,这个模块仅仅管理这样的 id 构成的队列。因为算法逻辑较为复杂,我用 C 语言编写反而比 lua 实现更顺畅(性能也更好)。但数据结构则完全采用 lua table (表示那个有序队列)而不使用任何 userdata 。

这样,就可以灵活的被其它模块使用。

April 04, 2020

《程序员修炼之道》20 周年版已付梓

我翻译的 The Pragmatic Programmer 20th Anniversary Edition 已经摆上了书店的货架。今天收到了出版社快递来的几本样书。纸张挺精良的,对得起这本著作。听朋友说,京东上的预定也陆续到货了。我非常期待各位学友的反馈。

去年几乎是一口气翻译完的。倾注了颇多心血。一边翻译一边和身边的朋友分享,几乎每个读过的人都很喜欢。我希望每个程序员都能读一读这本书。即使你已经读过第一版,也绝对不能放过这个新版。我在翻译过程中一直在做新老版本的对照,能明显感到与时俱进的内容。而且即使是没怎么修订的章节,这次因为读得非常细致,也有很多新的领悟。

限于水平,这次的翻译一定会有差错。希望发现错误的朋友能不吝指教。我会尽力在重刷的时候修正过来。

另外,这次的译本同时拿到了 kindle 上出版的版权(挺不容易的)。kindle 电子版应该会在 2-3 月内上线。不太喜欢囤实体书的同学可以再等等。

勘误见这里: https://github.com/cloudwu/tpp_feedback/