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 模块中展示出来,就成了必须考虑的设计点。

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

April 19, 2022

蒙皮数据的压缩

传统的蒙皮数据需要在模型顶点上存两组数据,其一为该顶点受哪些骨头的影响,其二为受这些骨头影响的权重。因为 GPU 的对齐影响,通常游戏中会将同一顶点受影响的骨头数量上限设为 4 。如果不做任何优化,骨头总数在 256 以下时,每个顶点需要 4 个字节保存骨头编号,再用 4 个 float 表示分别的权重。

因为权重之和总是为 1 ,所以,只用 3 个 float 也是可以的(第四个权重通过简单的计算就可以得到)。

因为权重总是 0-1 之间的数字,所以 32bits float 的精度远超所需,我们也并不需要浮点数。所以用 16bits [0,65535) 甚至 8bits (0,255] 来表示 0-1 的权重也够了。

所以,蒙皮一般至少占用 64bit 的定点数据 (4+4 bytes) 。

如果想进一步压缩,就需要一些复杂的技巧了。这两天读了几篇关于动画蒙皮数据压缩的 paper ,挺受启发的。

首先是这一篇 Vertex-Blend Attribute Compression

阅读全文 "蒙皮数据的压缩" »

April 12, 2022

Lua binding 中正确的 callback

今天修了个 skynet 中的 bug :在 Lua 中重新设置 callback 函数会失效。

skynet 已经有 10 年的历史了,十年前,某些 lua 的惯用法我还不太熟悉。比如,如果一个 C 框架的接口设置了一个回调函数,如何将其 binding 到 Lua 函数上,我当初没有想到好的方法。

最为传统的方法是把 Lua callback function 放到 Lua 的注册表中。当 C 框架的 callback 发生时,在 C 版本的 callback 函数中去查找 Lua 注册表中的 callback function ,然后用 pcall 执行它。

几乎大部分 C 模块的 lua binding 都用这个方案来封装 callback 函数。但它有一个最大的问题:调用 lua callback function 时,Lua 的状态机 L 如何传递。

阅读全文 "Lua binding 中正确的 callback" »

March 29, 2022

全民大规模新冠检测方案的一些想法

今天吃饭的时候和同事聊起最近上海深圳等超大城市全民新冠检测的问题。我认为现有方案有极大的改进空间。

千万级的全民检测,需要动用的资源是非常可观的,如果我们能优化这个过程,收益也会极其可观。现有的集体检测已经是相对独立个体分别检测做过优化了:通常是很多人放在一起混检,这样减少了检测成本。但我认为这是远远不够的。

现在自测盒的成本已经很低,至少一个自测盒的零售价格远低于我自己去医院做一次检测。所以我认为,如果全民自测的话,单从检测成本上来说,可能也是划算的。而且,对于群体检测,完全可以全家用同一个检测盒,这样如果是阳性,家庭成员就算没有全部感染,也最少是个密接。这比社区混检有效很多。

至于自测盒可能准确度不高的问题,完全可以自行多次自测来弥补。而目前采取的社区集体混检的形式,反而造成了人群密集,增加了病毒传染的风险。

但是,在千万级人口的城市中全民自测,显然结果是不可信的,这是我下面想谈的主要问题:如何设计一个方案,即降低了全民检测的成本,又能保持结果的可信度。即:如果有人自测发现自己阳性(或干脆不想自测),因为恐惧隔离而瞒报的问题。

阅读全文 "全民大规模新冠检测方案的一些想法" »

March 23, 2022

层次组件的问题

最近思考了 ECS 框架中的一些问题。

具体业务中,有许多组件的构成非常复杂,本质上数据是有层次结构的。用一个二维表的结构很难清晰表述。它还牵扯到另一个问题:是否需要支持一个实体有多个统一类型的组件。例如,玩家实体身上多个装备栏、多个技能 Buf 该如何表达?

我有一些不成熟的想法,还没有具体落地,先记录一下:

阅读全文 "层次组件的问题" »

March 18, 2022

effekseer 的 shader 转译

我们的游戏引擎一开始是自己实现的粒子系统 。在实现完之后,做配套编辑工具的阶段,开发工具的同学建议换成其它开源的成熟系统,这样就不必花太多精力在维护一套工具了。

他推荐了 Effekseer ,并完成了 Effekseer 和我们引擎的整合工作。

最近,我在推特上看到有个同学也在寻找 bgfx 下的粒子系统的方案,他希望有一个比 bgfx 自带粒子演示更完善的东西,同时又表示整合 popcorn 实在是过于麻烦。我向他推荐了 effekseer 。

阅读全文 "effekseer 的 shader 转译" »

February 25, 2022

ECS 中的对象引用

我们很难避免在 ECS 系统中相互引用 Entity 。而我对 ECS 模式的使用是鼓励去引用的。为此,我对许多常见依赖引用的模式给了对应的解决方案。

最近的一个 luaecs 开发版本中,提供了一种 Lua 层面的引用方案 :在创建 Entity 时,可以指定一个 table 作为该对象的引用。系统会更新它,让它保持为一个有效的(形如 select 过程中的)迭代器。这样,业务层就可以随时通过它 sync entity 中的数据。

我一直不是太喜欢这个方案,所以一直再考虑不同的解决方法。念念不忘 必有回响。昨天,我尝试了一个新的、更满意一点的方案。

阅读全文 "ECS 中的对象引用" »

February 23, 2022

信息茧房

最近一个月,无论我打开推特,还是微博豆瓣,每天都被“徐州八孩母亲事件”刷屏。在公司吃工作餐的时候,也和同事聊过这个事件。从我的角度看,此事的热度之高,持续时间之久,近年罕见。能读到我的 blog 这一篇的同学,相信都对这件事的来龙去脉不会太陌生。如果你不了解,那么 google 一下“徐州八娃女”或是“丰县铁链女” 就能找到很多信息。

但是,我很清醒的知道,热度只存在于自己所在的这么个小圈子。我相信在中国社会中,不知道此事的人群才是大多数。就算在微博上百万转发,也不会有所改变。毕竟,翻墙的人还是少数。而墙内的微博微信,都帮助人们把各自的信息茧房建设的很好。

阅读全文 "信息茧房" »

February 14, 2022

Factorio 的乐趣

我玩 Factorio 有记录的时间已经超过 2000 小时了。从它上 steam 的第一天我就开始玩,但大部分时间花在最近两年。

我在 steam 上的推荐语最初只有一句话,很能代表我初见这个游戏的感觉:“这个游戏满足了我对城市建设、物流调配、自动化建造、甚至还有铁路模拟,等等类型游戏的一切梦想。”

小时候最爱凯撒系列,它代表了当时城市建设和物流游戏的巅峰,我从中发现了无穷的乐趣,这是让我第一天就买下 Factorio 的缘故。

阅读全文 "Factorio 的乐趣" »

Misc

Categories

Archives

Recent Comments