September 07, 2022

多线程串行运行 Lua 虚拟机

ltask 是一个功能类似 skynet 的库。我主要将它用于客户端环境。由于比 skynet 后设计,所以我在它上面实验了许多新想法。

最近碰到一个需求:我们的游戏引擎中嵌入的第三方 C/C++ 模块以 callback 形式提供了若干接口。在把这些模块嵌入 ltask 的服务中运行时,这些 callback 函数是难以使用全部 ltask 的特性。比如,我们的 IO 操作全部在一个独立服务中,引擎读取文件时,很可能是通过网络异步远程加载数据的。这些第三方模块通常没有考虑异步 IO 操作,都是以同步 IO 方式给出一个读文件的 callback 函数让使用者填写。

那么,怎样才能在这个 C callback 中挂起当前任务,等待 IO 的异步完成呢?

阅读全文 "多线程串行运行 Lua 虚拟机" »

September 02, 2022

路网中路径的储存

我们正在制作的游戏中,交通和物流是基于公路网的。公路网其实是以路口为顶点,路为边构成的(无向)图。因为我们有大量的车辆行驶在这个路网中,所以,我需要一个空间高效的方法储存这些车辆的路径。

在大部分情况下,我们的车辆都选择唯一的最短路径,也就是说如果从 A 路口到 B 路口存在一条制定好的路径的话,所有的车都会走这条路。基于这一点,我们可以对多条路径合并储存。

我选择用当前路口 id 和目的地路口 id 做 key ,把下一站路口 id 作为 value ,保存在一张 hash 表中。这样,先用 dijkstra 算法求出起点到终点的最短路线后,再把每一段路线用该结构保存下来即可。

当车辆到达某个路口,只需要用当前路口和它自己的目的地就可以索引到应该往哪个方向开。这个结构很适合保存在 Lua table 中,用元表触发尚未计算过的路径。而且这样一个路径表只是一个 cache ,随时可以清理重建。

阅读全文 "路网中路径的储存" »

August 12, 2022

空间优先的 protobuffer / json 解码器

今天同事给我转了一个帖子 ,说的是 golang 在处理大量并发 json / protobuffer unmarshaling 事务时,可能产生大量的 (10GB) 临时内存,无法及时回收的问题。

我的观点是:如果一个系统的某个模块有可能使用 10G 这个量级的内存,那么它必然是一个核心问题需要专门对待。核心问题应该有核心问题的考量方法,这不是 GC 之错,也并非手动管理内存一条解决之道。即使手工管理内存,也无非是把内存块之管理转嫁到一个你平常不太想关心的“堆”这个数据结构上,期待有人实现了一个通用方案尽可能的帮你解决好。如果随意使用,一样有类似内存碎片无法合并之类的问题,吃掉你额外的内存。如果它存在于你的核心模块,你一样需要谨慎考量。

阅读全文 "空间优先的 protobuffer / json 解码器 " »

August 05, 2022

为 luaecs 增加内置 64bit ID

去年设计 luaecs 时遗留了一个问题:如何引用特定 entity。一开始,我认为可以灵活使用 tag 系统来解决大部分问题;或者用户自己构建一个 64bit ID 的 component ,采用二分查找的方法来引用特定 Entity 。

今年初,我发现我们的自己的使用者和外部使用者都无法避免引用特定 Entity ,所以增加了一个非侵入式的引用方案

最近又围绕它做了一些讨论,让我重新考虑内置一个 Entity 引用的方案。

阅读全文 "为 luaecs 增加内置 64bit ID" »

July 28, 2022

RmlUI 的 style 缓存

我们的游戏引擎的 GameUI 使用的 RmlUI 。我的想法是用成熟的 CSS 来描述 UI 的呈现,借鉴 web 前端开发的方法来制作游戏的 UI 。

但我不想嵌入太复杂的 Web 渲染引擎,而且游戏的需求也会有所不同,所以我选择了轻量的 RmlUI 。同时,为了和游戏的开发语言一致,我们使用 Lua 而不是 javascript 来控制 CSS 。

在使用 RmlUI 的过程中,一开始我们尽量和上游保持一致,修复了不少 Bug ,并合并到了上游。后来发现我们有很多需求和上游不同,需要大刀阔斧的做一些改动,所以就 fork 了一个自己的分支。

最重要的两个改动是:第一,完全实现了 Lua Binding ,因为原有的实现非常低效和复杂,很多接口设计不合理。做大规模的接口变化必须破坏向前兼容,这是我们 fork 分支的主要动机。

第二,废弃了 RmlUI 自己实现的排版模块,换成了 Facebook 维护的 Yoga

阅读全文 "RmlUI 的 style 缓存" »

July 20, 2022

重构数学库

我们引擎中使用的数学库已经修修补补很久了。期间积累了很多想法。最近在对引擎做性能优化,把一些找到的热点系统用 C/C++ 改写,顺便就重构了一下数学库,让它更好的兼顾 Lua API 和 C API 。

上一次对数学库的改进是三年前的事情了。这三年的使用,我们发现,基于一个栈的 DSL 虽然可以减轻 Lua 和 C 之间的通讯成本,但是使用起来并不方便。大部分时候,我们还是倾向更传统的接口:一次数学运算调用一次函数。而高复杂度的数学运算完全可以放在独立的 C 模块中完成。结合 ECS 系统,我们可以在 C side 集中批量处理相同但数量巨大的数学运算。

我们在很早以前就放弃了原来设计的 DSL ,只使用数学库的部分功能。趁这次重构,我打算把这些已经废弃的部分彻底删掉,并重新设计底层的数据结构,让它能更好的适应其核心特性。

阅读全文 "重构数学库" »

July 08, 2022

ECS 系统中 Entity 的生命期管理

我们的游戏场景是由若干场景节点构成的,每个场景节点是一个 Entity 的 Component 。而一个复杂的场景可以在编辑器中生成一个预制件 Prefab,像搭建乐高积木那样堆砌已经做好的部件。关于预制件的设计,之前有过两篇 blog 讨论。分别是:游戏引擎中预制件的设计预制件和对象集的管理

就目前的使用经验来看,几乎所有游戏中的 Entity 都是从 Prefab 实例化得来的。一个 Prefab 会实例化出 n 个 Entity ,但这 n 个 Entity 的生命期管理却很麻烦。

最自然的想法是:所有的 Entity 都必须是场景树上的节点(拥有场景组件),当我们删除一个场景节点时,它所有的子孙都一起移除。

阅读全文 "ECS 系统中 Entity 的生命期管理" »

July 06, 2022

分组功能在挂接系统上的使用

前段时间我们给引擎增加了对象分组的功能 。做这个特性的动机是当整个游戏世界中的对象数量远超同时需要处理(显示)的对象数量时,有一个快速筛选出待处理代码集合的机制。

在使用过程中,我陆续发现了这个特性的其它用途。

过去的某个游戏项目中,曾经遇到这么一个需求:游戏中需要为玩家生成一个头像,这个头像是由很多部分构成的。有玩家的肖像、名字、等级、修饰用的图标等等。这个头像可能同时在屏幕的很多位置显示。

如果场景是一个简单的树结构,那么,每个出现头像的地方,都是一个构成头像元素的子树。这样,场景中就可能出现完全一样的多份子树。固然我们可以用一个通用接口构造这个子树出来,但是,一旦这个玩家的属性发生变化,就需要针对所有场景中出现的同类子树进行修改。这需要为每个玩家额外维护一个列表,引用所有头像在场景树中出现的位置。这无疑增加了数据结构的复杂性。

阅读全文 "分组功能在挂接系统上的使用" »

June 14, 2022

给 ECS 增加分组功能

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

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

阅读全文 "给 ECS 增加分组功能" »

June 02, 2022

用邻接表实现无向图

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

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

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

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

阅读全文 "用邻接表实现无向图" »

June 01, 2022

一个 VLA (可变长度数组)的实现

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 ,尽可能的避免额外的函数调用。

阅读全文 "一个 VLA (可变长度数组)的实现" »

May 19, 2022

RogueLike 原型开发工具

我很喜欢 RogueLike 游戏,我是说字面意义上的像 Rogue 那样的游戏 。在这种游戏中,画面是最不重要的部分,只要能清晰表达出游戏需要的交互意义就够了。

我对用字符拼凑出来的游戏界面有种特别的爱好,小时候自制游戏就是从 text mode 开始的。 在今天,如果只是想验证一下某个游戏的原型,一个 Rogue 风,text mode 的交互界面,可能还是最省事的。因为你不必刻意的去准备美术素材,考虑这些素材如何和代码协同工作,制定繁杂的工作流。为游戏创作一点有趣的 ascii art 不仅不用太长的时间,可能还是写代码过程中的一点有趣的调剂。

前段时间在做项目中一个试验性模块时,我尝试做了一个简单的 Lua 库 帮助我用 text mode 搭建交互。最近又碰到一个更复杂的需求,评估了一下,基于 SDL2 做一个更完善一点的 RogueLike 库或许更一劳永逸。

阅读全文 "RogueLike 原型开发工具" »

May 07, 2022

游戏数据的展示

游戏的业务逻辑到画面呈现的过程和 GUI 系统在结构上有相似之处,又有一些不同点。

在软件设计时,我们通常倾向与把数据和展示分离。在 GUI 系统中,数据通常被称为 Model ,展示被称为 View 。典型的 MVC (及其衍生品 MVP/MVVM 等)模式就是建立在此基础上。业务逻辑修改 Model ,经过展示模块,把 Model 映射到 View 中呈现给用户。

传统的面向对象设计中,很多人倾向于按对象划分,每个对象有数据部分和展示部分。对于游戏,我不喜欢这种设计。我更倾向于把数据和展示完全分离,再用 id 把同一个对象关联其数据模块和展示模块中分离的实体。这是因为,游戏尤其是虚拟世界广阔的游戏,屏幕展示的仅仅是虚拟世界很小的一部分。在同一时间,大部分的数据都不必展示。甚至数据也未必存在于本地的内存中。

我倾向于把游戏软件切分为 gameplay 和 view 两个完全分离的模块,各自有独立的数据结构和设计。gameplay 应该可以完全独立于 view 运转,而让图形引擎关心且只关心 view 部分。在制作游戏软件时,如何解决好 gameplay 的信息如何在 view 模块中展示出来,就成了必须考虑的设计点。

阅读全文 "游戏数据的展示" »

Misc

Categories

Archives

Recent Comments