January 18, 2022

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

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

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

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

阅读全文 "我们需要一个怎样的动画模块" »

January 10, 2022

流体系统

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

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

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

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

阅读全文 "流体系统" »

December 24, 2021

难产的 Lua 5.4.4

2021 年 12 月 21 日,Lua 发布了 Lua 5.4.4 rc2 。

Lua 5.4.4 这个版本相当难产。之前几个小版本从 rc1 到正式发布最多只有十几天,而这次这个版本已经过去一个月,看起来还不能正式发布。

因为,就在 rc2 发布几个小时后,在邮件列表的讨论中,有人就发现了一个 bug 。有趣的是,这个 bug 并不是 Lua 5.4.4 引入的,而已经存在了 10 年以上。

阅读全文 "难产的 Lua 5.4.4" »

December 16, 2021

异星工厂的机械臂模块

最近在做一个类似异星工厂的以自动化生产为主题的游戏。虽然我们的设计中,虽然我们的物流系统和异星工厂有许多差异(暂时没有设计传送带),但是我们也有类似的机械臂系统。

机械臂以一个固定的方向,让物品短距离移动,从一端转移到另一端。它用来把物品在物流网络和生产机械之间转移。我们在实现这个系统时,修改了几次方案,我觉得有点意思,值得记录一下。

阅读全文 "异星工厂的机械臂模块" »

November 16, 2021

C 中访问 Lua 配置表的优化

这两天写代码时用到之前写的一个对 Lua 配置表的 cache 模块 。感觉用起来还是不够简洁方便。我今天动手重新设计了一下。

需求是这样的:

项目有非常多的配置信息保存在 Lua 的 (树状层级的)table 中,大部分逻辑代码直接用 Lua 的语法便可直接访问。但是,有少量有性能要求的业务是在 C 中实现的,C function 中也需要读取这些存放在 Lua 中的配置数据。

配置项随着项目开发,变更非常频繁。如果我设计一个小语言,定义出配置表,用代码生成的方式把表项翻译成对应的 C/C++ 结构,再在 C side 根据 Lua 中的数据重建一组 C 数据也未尝不可。这就是 google protobuf 官方采用的方式(用代码生成的方式,根据数据的 schema 构建出 C++ 类,让 C++ 可以方便访问这些数据)。

但我不想搞得这么复杂(浪费?)。大部分业务循环次数很多,而需要读取的配置表象却比较单一(反复取相同的条目)。所以,虽然第一次通过字符串 key 逐级解析 Lua 配置表或许较为低效;但只要在 C side 用一个 cache 模块缓存下高频访问的配置项应该就能解决性能瓶颈。

阅读全文 "C 中访问 Lua 配置表的优化" »

November 12, 2021

ECS 中同类关联数据的处理

如之前我在 ECS 模型下的处理模式 中所言,ECS 模式下最难处理的是同类 Component 之间有相互联系的情况。

最方便 ECS 处理的数据是相互独立的,每个数据单元都不和其它数据单元产生联系;如果多个数据单元会有故有的联系时,当可以把它们看作是同一个实体(Entity)下的不同组件(Component)时,那么就可以借用 Entity 的概念来处理它们。我们依旧可以按固定的次序去迭代这些数据。

但是,在复杂系统中,无可避免的,同类数据相互之间也可以产生联系。例如:场景管理中,节点之间有父子关系,计算节点的空间状态的过程对数据的遍历次序有要求。且计算过程还需要访问父节点的状态。解决这类需求是 ECS 框架的一大挑战。

阅读全文 "ECS 中同类关联数据的处理" »

October 23, 2021

米勒拉宾素数检验

今年 1024 程序员节公司搞活动,让我做一次分享。我在分享会上谈及程序优化时,说道优化算法减少时间复杂度的优化往往比优化代码本身更优化。举的一个例子就是检测一个整数是否是素数的问题。

米勒拉宾素数检验法比普通方法有数量级上的性能提高。当时我说道,这个算法的原理其实并不复杂,其证明过程有高中数学知识就可以理解,并不需要多深奥的数学知识。

会后,有同学提出了疑问。他怀疑一个高中生真的能看懂 wikipedia 上的解释 。仔细读了一遍后,我认为,对于中学生来说,难懂的可能只是其中的一些专有术语罢了,那些中学数学课本上没有引入。其内核还是挺好懂的。而且,这篇中文版写的(以及排版)不太好,远没有英文版清晰 。或许只要看英文版就立刻明白了。

我也许可以写一篇没那么多术语,但也不够严谨的解释。

阅读全文 "米勒拉宾素数检验" »

October 12, 2021

球面地图网格的设计

最近几年有很多基于球体地图的游戏,包括今年颇有好评的戴森球计划。

大多数在球面打格子分割地图的游戏,会采用六边形网格。但是,只靠正六边形网格无法铺满整个球面。必然会留下 12 个五边形。因为用正六边形铺满球面时,其实是在尝试用正 20 面体逼近球体。如果我们将正 20 面体做平面展开,每个三角形面中划分多个正三角形,每 6 个三角形合成一个正六边形,但中间的 12 个交接点必然是 5 个三角形缝合。只要处理好这个五边形,尝试用六边形网格做游戏是个合适的选择。

据戴森球计划的开发日志所述,开发团队也曾考虑过六边形网格方案,后来觉得不合适又回归四边形。我猜想多少和戴森球计划参照的游戏原型异星工厂是四边形网格有点关系。我也觉得在四边形网格上设计这种传送带游戏更舒适。不过,相比目前戴森球计划中用的方案:从赤道到两极,沿着纬线圈一圈圈减少网格数量;我更喜欢网格能完全对齐的方案。

阅读全文 "球面地图网格的设计" »

September 18, 2021

Paradox 脚本语言的一点研究

因为一直给群星维护汉化 Mod 的缘故,我花了不少时间去理解 Paradox 的配置脚本语言。

我认为它用了类 lisp 的语法来描述数据。用数据去描述游戏逻辑。P 社的游戏都有玩家共建的 Wiki 提供了丰富的资源来帮助玩家创作 Mod 。学习它的脚本语言是非常容易的。

最近一段时间,我仔细阅读了 Wiki 中所有关于 Modding 的文章,相比之前零星的了解,算是做了一次系统的学习。

这套脚本语言还是以配置数据为主,但也提供了很多逻辑控制手段,很值得学习。

阅读全文 "Paradox 脚本语言的一点研究" »

September 13, 2021

带娃玩桌游的一些记录

云豆目前 7 岁,可可 4 岁半。我从三年前就不断尝试带娃玩桌游,实际能玩的下去的并不多。最近一段时间是云豆接受桌游的爆发期,很多游戏都玩得津津有味,非常值得记录一下。

首先是我认为 4~6 岁可以玩进去的游戏。这类游戏不多,具体和娃的天性相关很大。我在网上参考别家的娃爱玩的游戏尝试了一堆,大多是玩不下去的。核心问题是:孩子太小的话,很难理解 “规则” 这件事。许多游戏即使能玩,也是破坏了规则,玩个热闹而已。

在我家能重复玩的这类游戏有这么几个。

阅读全文 "带娃玩桌游的一些记录" »

August 24, 2021

内存对齐问题和编译器优化

昨天在公司内部的“不作不死”(程序员)群里,有同学贴了个知乎上的帖子 。表示这个问题居然关闭 gcc 的 builtin-memset 就解决了,感觉很玄学。

我说,这个感觉才是对的。关于文章中表达的 “添加编译选项-no-builtin-memset后,一切就正常了。然后大家都如释重负,不但解决了问题,又学到的新知识。” ,我认为这“如释重负”对于程序员来说才是种不正常的感觉,正常应该是“更加困扰”了才对呀。

到底是怎么回事,文章线索不全,无法判断。不过我直觉上感觉和我前几个月在我们这个“不作不死”群里讨论过的另一个问题非常相似。

阅读全文 "内存对齐问题和编译器优化" »

August 20, 2021

预制件和对象集的管理

最近在用自研引擎开发项目时,发现了一些问题。在解决问题的同时,也逐步对之前的设计做了一些调整。一开始只是一些小修复,慢慢的发展成了大规模的代码重构。

最开始源于我重新设计了 ECS 框架。在新设计下,可以用 C/Lua 混合组织数据。为未来优化热点做好准备。我们借此机会重新思考了 ECS 框架下应该如何组织代码的问题。发现一个关键点就是,要尽量去掉系统中对象之间的引用关系。每类对象最好是成组分批的处理业务,每个模块都只做最简单的事情。但同一件事情尽量处理更多的数据、对象。

比如对象的构建和销毁,通常会随着对象构成的复杂度上升而演变为一件越来越复杂的事务。我们之间在设计 ECS 框架时,就设计了大量的机制来正确执行 Entity 的构建流程。一个 Entity 可以由若干 Component 类型动态组合,并非每个 Component 都能独立初始化。有时它们是相关联的。例如 A B C 组合成一个 Entity ,初始化 A 和 B 后,才能根据 A B 的结果初始化 C 。

阅读全文 "预制件和对象集的管理" »

July 27, 2021

Tag set 的数据结构优化

在最近实现的 ECS 库中,Tag 是一种非常重要的数据结构。它是一类特殊的 Component ,不携带数据,但会关联到同一 Entity ,最重要的用途是用于筛选。我在设计 Comonent 的数据结构时,采用了一种简单的数据结构 。它采用连续内存储存的数组,按 Entity id 有序排列。并在查询算法上做了一些优化,可以使得大部分查询时间小于 Log(N),接近常量时间。

但是,这样做的代价是插入和删除操作都是 O(n) 的。为了避免大量的插入删除操作堆积在一起时,整体的时间复杂度变成 O(n^2) ,我禁止 Component 的删除,而删除 Entity 改为标记,待一帧结束后一起删除。这样,可以让批量删除保持在 O(n) 的复杂度。

阅读全文 "Tag set 的数据结构优化" »

Misc

Categories

Archives

Recent Comments