« July 2024 | Main | September 2024 »

August 24, 2024

一个简单的 C 模块管理器

我在用 C 构建项目,尤其是和 Lua 混合使用时,一直很头疼 C 没有一个统一的模块管理器。Lua 的模块管理虽然简单,但毕竟有且够用。一种方法是把 C 模块封装成一个个 Lua 模块,让 Lua 帮助管理,每个 C 模块是独立的,相互不可见。

但当 C 模块之间发生关系时,就比较麻烦。当然,简单的方法是通过链接器把它们都链接在一起,通过函数名前缀以区分。或是利用操作系统的动态库加载器来管理模块。

最近有了一点有趣的想法,觉得一个最简的模块管理器其实复杂度并不高。花了半天功夫实现了一下,感觉还不错。

https://github.com/cloudwu/cmod/

我在设计时,刻意回避了使用 macro 魔法,让它的接口保持原始的 C 风格。而且,实现上也不依赖任何内存分配函数,整个管理器需要的内存是一开始由调用者分配好一大块传入的。

这个管理器只管理函数指针,刻意没有去管理其它状态(比如类似事务、COM 管理的就不只是函数接口,还保留对象实例),但还是为每个管理器实例留有一个 userdata 指针,供使用者扩展。


其中的 import 函数,也就是通过字符串查找对应的模块,使用的是简单的 O(n) 遍历所有已注册模块的算法。如果接下来有性能需要的话,我会再加一个 hash 表做一些简单的 cache 。

August 18, 2024

32 位 handle 的一种生成方法

我倾向于在 C 程序里使用整数 handle ,而不是指针。尤其是需要做弱引用的时候。

我认为,一个好的 handle 生成算法,应该满足:

  1. 即使 handle 被销毁了,它这个数字也应该被保留,不应该被新的 handle 复用。posix api 里的文件 id 就不符合这一点。
  2. 提供一个 api 可以判断一个 handle 是否有效,其时间复杂度为 O(1) 。
  3. 从 handle 对应为对象的内存地址的时间复杂度应该为 O(1) ,不应该比指针有明显的性能问题。虽然 hash 表理论上可以满足 O(1) 的时间复杂度,但在糟糕的场景(hash 碰撞发生时)并不能保证这一点。
  4. 构造 handle 时间复杂度也为 O(1) 。
  5. handle 的数字位宽最好不要超过 32 bit 。

如是长期运行的程序,第一和第四个需求不能同时成立。但对于非长期程序,理论上 32bit 的数字应该是够用了。

比较简单的实现方案是用一个自增 id ,然后用一张 hash 表来保存 id 到指针的映射。但 hash 表不是严格的 O(1) 复杂度。在 skynet 中,我使用了一个简单的方法:自增 id 后,如果发现 hash 冲突,就再加一,直到不冲突为止。这个方法不能满足第 4 点需求。

当然,同时满足 5 点需求未必有多大的意义,但我最近想到一个有趣的方案,稍微实现了一下,感觉可以做到。

前提是:为了让 32bit 数字就够用,同时有效的 handle 不能太多(大多数场景是这样的)或是在同时有效的 handle 很多时,不要过于频繁销毁和创建很少的几个 handle 。

我们用一个固定 size 为 2^n 的整数数组来管理所有的 handle 。handle 对 size 取模,就是它在这个数组所在的 slot 。然后,我们只需要维护一个完美 hash 表,所有分配出去有效的 handle 都不在这张 hash 表中发生碰撞。这是可以用 O(1) 时间做到的:方法是,每次回收 handle ,都把该 slot 的高 (32-n) bits 加一,这个新的待分配的 id 绝对不会和已分配过的 id 重复。

和简单的循环自增 id 检查冲突的算法相比较,不仅仅是时间上更稳定。最主要的好处是,这个算法更难耗尽 32bit 的空间(发生回绕)。尤其在有效 handle 数量较多时,一旦发生碰撞,自增 id 的方式一下子就会跳过很多数字,而这些数字中大部分是从来没有使用过,本可以安全的分配出去的。

在 handle 销毁(回收时),同时把 handle 串在该数组里的 free list 即可保证下次 O(1) 时间就能完成新 handle 的分配。

举个例子:

如果我们限制最大有效 handle 数为 4 ,如果把 0 保留为无效 id ,那么分配四次后,handle 分别为 1 2 3 4 。

这时,如果我们把 2 销毁,重新分配的话,新的 handle 是 6 而不是 5 (因为 5 和 1 会发生 hash 碰撞)。这时,再销毁 6 然后分配一个新 handle ,这个新的 handle 会是 6+4 = 10 。

在这个算法中,是不是之后所有新增 handle 都比 10 大呢?并不是。如果销毁 1 ,再分配的话,会得到 5 ,5 比 10 小。

这个算法获得的 handle 的数值并非单调递增的,它比自增方案更节省全部的数字空间。


如果这个数组满了怎么办?一般我们不用考虑这种情况,应该一开始规划好上限(例如 posix 的同时打开文件数就有上限)。但若是想解决,也可以倍增 size 。只不过 rehash 的过程比较复杂:不光是要把已有的有效 handle 重新填在新数组中,还需要额外标记那些可能用过的 slots 。

我写了一个简单的实现:https://gist.github.com/cloudwu/dcbf583f7034ef6c0f8adec3f76860f0

借助这个数据结构,我们就可以把同类对象分配在一个大数组中,然后用 handle 索引它们,和指针相比,几乎没有额外的开销。并且有如下好处:

  1. 可以简单的判断一个 handle 是否有效(指针无法安全的做到这点),容易写出健壮的代码。
  2. 方便做持久化。
  3. handle 可以用于 C/S 同步。

August 13, 2024

基地建设(工厂)类游戏的玩家体验

这两天思考了一下,基于工厂生产的基地建设类游戏给玩家提供的核心体验到底是什么?以及,我们去年被取消的游戏到底还差点什么。接下来我要制作的游戏的注重点应该在哪里。

我玩的时间比较长的两个基地建设类游戏:异星工厂和缺氧,它们的玩法其实差异很大,但却给人一些近似的体验。对于这个问题,我想过很多次,得出的结论是,它们的确有一些共通之处:

玩家在玩这两个游戏时的情感体验过程非常类似,大致是这样的:

  1. 玩家开始了解基本规则。对于异星工厂来说,就是采集原料,生产加工,生产科技瓶,推进科研发展;对于缺氧来说,是建造设施用来提供小人的各种生存所需,不要让他们死掉。

  2. 让玩家了解游戏的终极目标。这通常是建设一项宏伟的工程。异星工厂和缺氧的原版目标,不约而同的都选择了制作并发射火箭逃离所在星球。

  3. 玩家根据完结游戏的目标和已经了解的游戏规则,在心里做出通关(或是解决阶段性目标)的计划。

  4. 玩家在实施计划的过程中遇到挫折。这通常是发生了一些未曾预料的意外。这个意外并不是系统额外强加进来的,反而是在已透露给玩家的规则下合理发生的。所以,玩家会觉得是自己对规则理解的不够,而不是来源于设计者的恶意。

  5. 玩家修正自己的计划,重新理解游戏系统。如果挫折时由游戏规则内在随机性带来的(缺氧中略微多见),玩家学会应对这些随机性,随之增强自己对抗游戏的自信;而异星工厂(尤其是关闭战斗后)是一个无危机的游戏。但还是会随着自己管理的工厂规模变大,需要更新物流方案,不然生产效率会逐步降低。

  6. 游戏适时介绍一些新系统。在缺氧中变现为一些未曾预料的挑战(比如温度控制在初期没有表现),同时引入新的应对策略;在异星工厂里表现为新的物流方式(火车、无人机等),可以用来提升效率,但这些对玩家是可选的。

  7. 玩家根据新系统迭代自己的计划。


结论:

这类游戏不能将规则简化到一眼望穿,一定要避免变成一个放置游戏,需要提供足够的细节。这些细节的作用是:虽然核心规则可以让玩家做出计划,预测目标该如何完成,但在微观上很难准确预测,细微的偏差会产生混沌效应。即,小小的行为偏差会引起结果的巨变。

一定要给玩家提供一个 "为了结束游戏” 而建立 "长期计划图景" 的舞台。如果缺少这一点,无论是异星工厂的传送带玩法,缺氧的生存玩法,都不足以吸引玩家长期玩下去。

也就是说,微观玩法是帮助玩家建立核心体验的手段,而玩家的核心体验并不在玩这些玩法的游戏过程,而在做出规划然后实施规划上。

August 08, 2024

gameplay 框架设计总结

游戏行业从业 20 多年,一直在做底层开发,即使是帮助其他团队写上层游戏逻辑,也都是实现某些特定的功能模块。直到最近,我想单独开发游戏,才好好想想架子该怎么搭。

从最初的原始 demo 开始,由于缺乏经验,写着写着经常有失控的感觉。好在一个人做,重构的心理负担不大。想改的时候,停下来花上两三天全部重写也不太所谓。最近总算顺畅了一点,感觉需要整理一下思路,所以写一篇 blog 记录一下。

任何复杂的软件问题,都可以通过拆分为若干子问题减少复杂度。

我认为,游戏的上层逻辑,即 gameplay 部分,主要分为三块:数据模型、外在表现和人机交互。

“数据模型”是 gameplay 的核心部分,即把游戏的画面等外在表现以及图形界面、操作控制(鼠标键盘控制器等)等剥离后的东西。如何判断一个模块是否属于数据模型,是否有不属于它的部分没有拆分出去,最简单的方法是看它是否有直接调用游戏引擎的代码。拆分干净后,这块不应该包含任何与图形、界面、时钟、控制输入有关的接口。除了一些必要的文件 IO 接口(主要是用来读取 gameplay 相关的策划数据,写 log ,做数据持久化等),也不应该涉及任何 OS 的 API 。

这样,我们就可以方便的对它进行整体或局部的测试。必要时还可以更换游戏引擎,甚至从文本 roguelike 换到 3D 表现都不会受影响。

“外在表现”当然是指游戏的画面表现、声音声效等等,通常这由游戏引擎实现,但还会有大量的代码存在于 gameplay 的实现中。这一块代码也会维护大量的状态,但不会涉及数据持久化。简单的判断方法是:如果游戏保存进度时,所有这里的所有状态都可以舍弃,下次读取进度后,这些状态又能被重建,而玩家不会感觉丢失了任何数据。

“人机交互”是游戏软件必要的部分,如果没有“人”的存在,游戏也就没有意义了。这块分为两个部分:图形界面用于展示游戏的数据给人看,同时接收一些来至界面的间接输入;控制器(包括并不限于手柄鼠标键盘触摸屏等)对游戏的直接控制。

对于联网游戏,还应包括第四大块:“网络输入”。这篇 blog 仅讨论非联网游戏。


对于“数据模型”这块,我在编码时,把这个起名为 gameplay 。可以进一步的分为两大类:被动对象 Object 和 自治体 Actor 。

Object 我认为应按类别分类,每类对象聚合在一起管理。它们可以是场景上的物件、游戏角色等这种会在表现层上找到对应物的东西,也可以是任务清单这种不在表现层呈现的东西(可能会在界面上呈现)。在实现 Object 时,应该理清它的数据和操作这些数据的方法。

对于数据部分,应该在早期就考虑如何持久化,即游戏的 Load Save 该如何实现:通常就是对每类对象的每个个体单独做持久化。为了实现持久化,每个 Object 都应用 id 管理,id 和 typename 是它们的共有属性。

其它数据应该尽量保持相互独立,避免相互引用。如非必要,不提供额外的数据控制的方法。因为一旦要提供特定的方法操作数据,往往是因为多项数据相互关联,必须用单个方法去控制它们来保持一致性。基于这个原则,Object 不应该提供像 update 这样的方法。所以,Object 是静态数据集合,它是被动的。

那么,游戏是怎么运转起来的呢?我们可以再实现一系列的自治体 Actor 。每个 Actor 对应了游戏世界中的一个实体,它可以关联一个或多个 Object ,通过读写 Object 的数据控制它们。大多数游戏在 gameplay 层面不会遇到太大的性能问题,所以这里不考虑并行处理。虽然 Actor 逻辑上是各自独立的,但串行处理可以避免考虑并发读写 Object 的问题。

Actor 使用消息驱动。不同类的 actor 有不同的 update 函数来处理每个 tick 的行为,可以处理消息。游戏世界接收外界输入只能通过向 actor 发送消息完成。actor 通常实现为一个状态机,这样可以让游戏世界中的虚拟角色在不同状态下有不同的行为。actor 需要维护许多的数据中间状态,同时也要考虑持久化问题,但大部分内部状态不应该持久化。大多数情况下,应保证只持久化状态机当前状态的名字就够了。其余运行时状态应当可以根据它重建。

例如:游戏中一个工人,接收了一个任务订单,需要从 A 处拿取一个货物送到 B 处。

  • 订单是一个 Object ,数据内容有起点和终点的位置,货物的总类和数量等信息。
  • 工人是一个 Object ,数据内容有它的当前位置、携带物、订单号等。
  • 有一个 Actor 作为工人的控制器,它用于控制工人的行为,比如申请订单、接收订单、执行订单等。

而执行订单的过程,又可以分成若干步骤:

  1. 确定去 A 点的路径
  2. 移动到 A 点
  3. 获取物品
  4. 确定去 B 点的路径
  5. 移动到 B 点
  6. 放置物品

这些步骤,有些是可以立刻完成的,有些则需要若干 tick 。对于需要很多 tick 才能执行完的过程,必定存在一些中间状态,这些状态不必参与持久化。这些运行时的临时状态应当可以被重建。比如,在“移动”这个步骤,一旦外界环境发生变化(例如场景变化了,路程可能被封堵),actor 收到消息,就会把状态机切换到“寻路”这个步骤,之前“移动”步骤的执行过程所创建的中间状态就不需要了。

设计持久化方案是一个优先级很高的事情。因为在考虑持久化时,就会认真设计数据模型。修改数据模型,如果同时考虑不破坏持久化功能,也会更谨慎一些。

不要简单的将 持久化 等同于把 Object 和 Actor 的运行期内存数据结构简单的序列化。持久化更像是把运行时的对象还原为一系列的构造参数,下次加载时可以通过这些参数重新构造运行时结构;而运行时结构往往会考虑性能因素构造成更复杂的数据结构,数据结构中存在一些复杂的相互引用关系。

例如:订单系统的运行时结构可能是 id 到 订单的映射表,这样方便从订单 id 查询到订单。但在做持久化时,把订单保存在一个顺序列表中更好。


如何把数据模型表现出来呢?这要看引擎是用什么模式工作。

一般会有两种模式:立即模式(Immediate Mode)和保留模式(Retained Mode)。引擎也可能根据渲染不同类型的东西混合提供两种模式。

如果是立即模式,那么每帧画面由“表现层”(代码中,命名为 visual )遍历“数据层”的 Object 取出其状态,提交渲染即可。

如果是保留模式,一般我会在表现层为数据模型里的 Object 建立对应的 visual object 。对应关系可以是 1:1 ,也可以是 1:n 即一个数据 object 对应多个 visual object 。而数据层记录每个 tick 的状态变化,最后用消息队列的方式仅把变化传递到表现层。根据这个状态变化消息,修改 visual object 的状态,同步给引擎渲染。

无论是什么模式,都不会在数据模型中直接调用渲染引擎的 API ,数据模型也不会直接持有 visual object 的引用。

渲染层一般不会直接给数据模型中的 Actor 发送消息,而只会读取(不会改变) Object 的状态数据。但如果表现层有额外的反馈设计,比如有物理系统,让物理系统可以对游戏世界发生反馈,一些属于纯表现的,就在表现层自己消化。另一些会影响数据模型的,就会变成一个消息源,向 Actor 发送消息。可以把它们看成是交互层的一部分。


交互层通常分为 HUD 、GUI、Controller 。大部分用户输入来至于 Controller :手柄、鼠标、键盘等。需要对这些设备的原始输入根据场合做一些转换,避免直接处理诸如鼠标按下、手柄摇杆向左这样的消息,而应该转换为更高阶对 gameplay 有意义的消息:例如变成发起攻击、跳跃,向左行走等。还有一些输入来自于 HUD 或 GUI ,更应当避免在 GUI 的代码中直接访问数据模型,更不要直接控制表现层的 visual object ,而应该先转换成 gameplay 的消息。

例如:“存盘”就应该是一条消息,而不应该是直接的函数调用。保存进度和读取进度在消息处理过程中应该只做一个标记,而在每个 tick 末尾再检查这个标记做对应操作(通常是先 save 再 load )。这样才能更简单的保证数据一致性。

最终在每个 tick ,这些交互层产生的消息会分发发到数据模型中的 actor 。actor 的 update 驱动了整个 gameplay 的状态变化。