« December 2021 | Main | February 2022 »

January 29, 2022

支持惰性展开和差异更新的 Lua 表

年前最后两天,陆续给我们组的同事批了假,都回家过年了。我留守在公司做点项目无关的东西。

最近在 skynet 的讨论版有人讨论配置表的更新问题。这几年,不管在公司内,还是从外部听见,总有人在讨论这个问题。我重新理了一下需求:

  1. 数据以 Lua table 的形式提供:支持 Lua 所有的内置类型:整数、浮点数、子表 、字符串、布尔量。可选支持函数、指针。
  2. 数据表通常有很多(冗余)数据,但大多数情况下只会用到一下部分,初始化的过程应尽量快。
  3. 如有可能,少占内存。数据表属于不变数据,应尽可能的在多个 VM 间共享。数据表应对 GC 有尽可能少的影响。
  4. 可以在不关闭 VM 的前提下,更新数据。
  5. 访问数据表应遵从 Lua 的使用惯例,并尽可能和原生表性能一致。

以上这些点很难同时全部满足,所以我给过许多不同的解决方案,都只是针对其中一部分需求。其中,性能最好的应该是 sharetable 这个方案,它是通过修改 Lua VM 的实现,做到了跨 VM 的数据共享。访问 VM 外的数据表的性能和本地数据完全一致。

如果使用传统方法,把数据放在 C userdata 里,例如 sharedata 方案,性能势必会打折扣。这是因为通过 metatable 读写数据,必须经过 Lua 的函数调用,它比 Lua Table 的访问要慢很多。

我这次做了一个中间方案,可供特别需求选用。

如果我们把数据全部放在 C 结构中,那么共享数据也就不成问题。为了提高 Lua 侧的访问速度,可以采用惰性复制的方式:未曾访问过的数据就留在 C 结构中、只要数据访问过一次,就复制到 Lua VM 中,后续访问就和原生数据结构完全一致。


那么、数据更新该怎么做?

如果我们让数据表只支持树结构,即节点不可以复用、不可以有环。同时,节点的 key 只可以是字符串和数字,那么,这个树状数据结构中,每个节点都有唯一的标识,即它从根节点开始抵达的唯一路径。

对于配置表的更新来说,往往不太修改表的结构,只动内部的数据。大多数场合,节点的 key 的名称都是有限的。如果我们收集所有 key 的名字,维护在一个集合中,并在更新过程中,只增不减。那么,我们就可以对每一个存在过的 key 赋予唯一的数字编号。同样,每一条通向数据节点的路径也可以有唯一的编号。

换句话说,一个节点,它的唯一标识如果是 a.b.c ,编号为 42 ,在未来的更新中,只要这个标识不变,就表示是同一个节点。a.b.c 可以在某次更新中被删除,但编号会永久保留。后续如果重建了 a.b.c ,编号依然是 42 。

基于这个原则,就可以方便的做数据表的数据更新。我们用一张弱表记录下所有被展开过的数据表的引用。一旦数据发生更新,就清光所有旧数据,并把这些表还原成(依赖唯一 id )待惰性展开的状态即可。这比 sharetable 的更新方案中,扫描整个 VM 找到被引用的共享表要高效的多。

我快速的实现了一下上面的想法:https://github.com/cloudwu/datatree

数据结构 datatree 分为两个部分。作为宿主,它是一个 Lua 结构,可以通过 update 方法更新数据。所有更新历史中的数据结构都被记录下来,但只保留最后一个版本的数据。

这个结构可以通过 pack 方法把最后一个版本的数据打包成一个 C userdata 。值得一提的是,这个 C 数据会被打包成一个连续的内存块,且内部没有任何指针。所以,你甚至可以把它直接保存到文件中,可以看成是一种 Lua 数据结构的持久化数据块。如果需要,可以用 mmap 映射到内存直接使用。

我们可以在不同的 VM 创建 shadow 对象,它的 update 方法接受前面打包的 C userdata 地址即可,并可返回一个能惰性展开的 Lua 对象。这个对象可以如普通 Lua 表一般使用。这个 update 的运行时间复杂度是 O(1) 的,只做非常少量的初始化工作。数据全部在在访问时按需从 C 结构中复制出来,而 C 数据结构被设计成可以方便的随机访问,展开每个节点的开销只和节点本身的数据大小有关,和包的大小无关。因为 update 对 C userdata 完全是只读访问的,所以它是线程安全的。


这个方案不仅仅可以用于 skynet 这种服务器环境。我觉得在客户端也可以使用。它的优势是避免大量数据的初始化开销。

相比之前的 sharetable ,劣势在于数据没有在 VM 间共享,多 VM 环境会浪费一些内存。且从 C 结构中复制数据到 Lua 中也有额外的一次性开销,只不过这个开销是分摊到很长一段时间上了。

January 18, 2022

我们需要一个怎样的动画模块

最近这个项目,里面有大量的机械动画:采矿机、抽水泵、发电机、组装机、机械臂、等等。

我发现,我们自研的引擎的动画模块其实是不够用的。

我们在设计引擎的动画模块时,是按过去经常做的 MMORPG 里的需求来设计的。主要是控制 Avatar 的动作:走、跳、跑、攻击、等等。在从制作软件导入动画数据后,引擎需要做的加工主要是动画和动画之间的融合。例如,从走路过渡到跑步。还有在动画中加入一些运行时的控制:例如转头盯着物体、调整脚掌贴合地面。这些是用 IK 模块来实现的。

在这个项目中,我们大量的动画是让机械装置的很多部件运动。这固然还是可以套用已有的骨骼动画模块,但旧有的功能却会造成大量的浪费。

机械装置的部件繁多,每个小零件都有自己独立的动画。例如,一个齿轮会不断的旋转,另一个活塞在做往复运动。当我们在制作软件里把整体动画都调好后,所有部件放在一起,就会有一个非常长的动画循环周期。但实际上,单个零件的循环周期却非常短。如果把整体的骨骼动画一并输出,就会有大量的数据冗余。

如果按传统方式制作每部机器的动画,相应动画数据很快就膨胀到不可接受的地步。但如果简单的把机器按部件拆分开,单独制作简单动画,再在程序中组装起来,那么美术就难以创作。所以、我们还是需要对引擎的动画模块以及编辑器增加相应的支持,

因为我们没有足够的资源开发一个完善的骨骼动画编辑器(好像 spine 做的那样),即使开发出来,也很难媲美转移的 3d 动画创作工作;那么,只能退而求其次,做一个有限功能的动画组合编辑器。

我的构想是,美术可以在创作工具里为每个零部件创作动画,把它放在整体的骨架上,动画却单独导入到引擎的编辑器中。当我们编辑动画时,可以为物件创建多个 track ,每个 track 就只能置入一个零件的动画。但可以为这个动画在 track 上添加若干播放循环,每个循环的的开始时刻、播放速度。

然后运行时把物件的所有 track 相加,得到最终的动画。

如果换成人物动画,那么我们就可以把摇头、眨眼、挥手、这些局部运动都单独输出,每个局部动画都是在完整的骨架上创作的。只是大部分关节都是静止的。每个局部动画都有一致的完整的骨架,得到最终效果,只用简单相加即可。

对于机械运动,大部分零件都是做一些基本运动:匀速旋转、简谐震动等等。这些运动都是针对单个关节的。那么这样的简单运动不需要在外部创作工具中创作,只需要在编辑器中自动生成即可。因为引擎已经实现了 IK ,那么再在编辑器中加入 IK 的关联交互,就可以在编辑过程自动生成那些连带运动了。通过 IK 计算出来的运动轨迹,并不需要在运行时计算,可以在编辑时算好保存下来。这样可以减少运行时的复杂度。

在自己开发的编辑器中创作动画,虽然不如专业软件方便灵活,但可以最大限度的回避数据导入导出的复杂性。毕竟 3d 动画数据不如 2d 图片那么容易规范,我们之前大部分的开发精力都消耗在了处理和创作工具的数据交换上了。

January 10, 2022

流体系统

我们最近在开发的类似异星工厂的游戏中,一个重要的物流子系统就是流体系统。我个人觉得,它是所有子系统中最难实现的一个。

Factorio 的流体系统也经历过多次改动。在开发日志上有记载的就有三次:New fluid systemFluid optimisationsNew fluid system 2。作为一个 5 年近 2000 小时的老玩家,我感觉的到流体系统的修改一直在做,不只这三次;而且直到今天,流体系统在游戏中依然会出现一些反直觉的行为。

一个好的流体系统非常难兼顾高效和拟真。在 Factorio 的仿制品戴森球计划上线时,我饶有兴趣的想看看它是怎么做流体管道的,但让我失望的是,它几乎把流体系统砍掉了。

我在 Factorio 中非常喜欢流体系统的伴生玩法。所以,在我们的游戏中,即使我没有做传送带,也要做一个流体子系统出来。我们的设计直接参考了前面提到的几篇 blog ,并加入了一些我自己的想法。

一个好玩的流体系统要解决的几个问题:

  1. 流体系统和电力系统要有所区别,要体现出流体流动的过程,放入流体网络的流体,不应该瞬间遍布整个网络。

2.管道的分叉要公平。如果上游水流流到 T 口分叉,两个分叉如果管道是一样的,就应该均匀分流;合流也有同样的公平问题,分叉合流吸收支流的量也应该平均。

  1. 管道的流动规则只应该和管道内的液体量有关,不应该和管道建造次序(管道 id )相关。

  2. 流体在管道中流动,总量必须严格不变,不能因为浮点运算的缘故增加或减少。

  3. 引入抽水泵导致流体网络形成环路时,算法不应死锁导致流体无法流动或其它反直觉行为。

  4. 管道有升级空间,升级可以带来玩法上的改变。

Factorio 在流体系统改进的过程中,收集了大量玩家的建议,其中不乏专业人士。按 blog 的原话说,“differents kinds of engineers (mechanical, CS, electrical, ...), mathematicians, physicists, and even people with real pipes hands on experience.” 可见这个问题即有趣,又不那么简单。

我倒不想从真实物理角度去模拟流体在管道中的流动,因为它不够简单,而且很难保证确定性。我需要的是一个简单,但大致符合直觉,好玩的系统。


我在 Factorio 的新手阶段,完全搞不懂流体系统的运作原理。但它的流体系统是符合直觉的,所以并不妨碍我游戏。换为制作者身份,就不能再搞不清楚了。

比如:为什么在 Factorio 里,水管越长流动就越慢,必须加泵来改进流速?

这个问题体现了流体系统和传送带系统的不同,引出了不同的物流问题需要玩家解决。

传送带无论多长,只要你塞满传送带,那么你在传送带一段放入一个物件,同时就能从另一端取走一个物件。传送带的速度决定的仅仅是它单位时间能传送的物品个数,和你铺设传送带的长度无关。

但管道则不然,管道的长度会决定你可以通过管道以怎样的速度传输流体。游戏中,如果管道过长,玩家必须在一定数量的管道间加一个抽水泵来维持流速。

这是为什么呢?我玩了很久才明白。

因为,一个固定在一端生产,另一端消耗的管道,是永远塞不满的。流体主要靠势能发生流动。管道内流动的稳定状态是一个斜面。没有水泵的管道,当你把它视为一个整体时,这个斜面的坡度就越平缓,流速就越慢。而当坡度越平缓,管道的入水口留给进水的空间就越小,游戏中的表现就是,入口几乎是满的,一个 tick 塞不了多少水到系统内,而出口几乎是空的,一个 tick 流不了多少水出去。


想明白这点,就可以设计出一个简单的流体流动算法。

如果不考虑抽水泵的因素,我觉得最简单的算法就是把流体看成是静态的,在每个时刻,流体的流动方向和流速仅和每节管道中的水位有关。流体永远从高水位向低水位流动。水位差决定了一节管道大约可以向临近的管道流多少流体。

这样的算法比 Factorio 的还要简单,Factorio 除了考虑水位,还考虑了当前的流速,即上个 tick 液体的流动量。我试过一版类似的算法,感觉还是过于复杂,很难同时满足前面列出的条件。

一开始的想法是,每节管道最好可以同时运算,相互不干扰。这样更方便后期做并行优化。尝试过两版实现后,我放弃了这个想法。因为当管道有多个输入和输出时,独立的运算很难保证液体在流动后不超出管道容量的限制。

即,若一节管道可以装 200 单位的水,如果它独立计算,很难保证它内部的流体在减去流出量且加上流入量后,总量不超过 200 。在我玩的另一个游戏“缺氧”中,设计了容器的压力值和承压能力限制,允许流体容器偶尔超过它的容积,但增加它的压力直到破裂。我觉得虽然玩法丰富了,但不确定性更多,bug 也变得更多。比如在缺氧中,你就可以用特殊的技巧制作一个无限存水的容器出来。

我最终选择对流体管道排序,按次序来处理流动。

在不考虑水泵时,遵循以下步骤:

  1. 每节管道计算当前水位,和邻接管道水位做比较,决定当前 tick 的流动方向。在接收流体的管道上记录每个上游管道可能输入的流体数量(根据水位差计算出来),记作预留空间。

  2. 根据流动方向做一次拓扑排序,从最下游排到最上游。每个 tick 记录下排序结果,cache 起来供下个 tick 使用。一旦在处理过程中发现上下游比上个 tick 反向,就局部重排。

  3. 根据排序结果,依次处理每节管道的流出。流出量不应超过接收方为它的预留空间(步骤 1 计算,同时在本步骤中调整)。如果有多分支流出,流体数量小于下游预留空间总量,就按预留空间比例分配。流出后,计算剩余空间,和为上游预留空间相比较,如果剩余空间总量小于预留空间总量,则按比例重新分配预留空间。

为了保证计算的确定性,我没有采用浮点数,而全部采用用整数计算。但和 UI 表现相比,扩大了 100 倍。它实际上是一种定点数表示。在上述步骤中需要按比例分配时,不做小数切分,最小单位为 1 。同等水位差分流时,多个支流流量差不超过 1 。

加入水泵是相对简单的。

水泵的抽水是无视水位差的,按泵速把水泵输入端的流体在泵速和水泵容积的限制下把尽可能多的流体抽到泵内。然后将泵视为普通管道,让其中的流体按上面的步骤依照水位差自然流动。