云风的 BLOG

这两天写代码时用到之前写的一个对 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 配置表的优化" »

云风 提交于 12:26 PM | 固定链接 | 留言 (2)

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

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

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

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

云风 提交于 02:27 PM | 固定链接 | 留言 (5)

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

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

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

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

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

云风 提交于 09:06 AM | 固定链接 | 留言 (4)

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

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

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

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

云风 提交于 11:28 AM | 固定链接 | 留言 (13)

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

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

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

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

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

云风 提交于 10:23 AM | 固定链接 | 留言 (16)

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

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

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

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

云风 提交于 01:08 PM | 固定链接 | 留言 (8)

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

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

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

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

云风 提交于 03:01 PM | 固定链接 | 留言 (11)

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

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

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

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

云风 提交于 03:18 PM | 固定链接 | 留言 (6)

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

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

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

云风 提交于 10:26 AM | 固定链接 | 留言 (11)

最近在公司内做了一次两小时的分享，介绍了一下我最近几年对 ECS 模型的一些想法以及最近在项目中的应用心得。

我分享的主题不叫 ECS ，而用了一个更宽泛的名字 Data oriented design 。因为我不想局限在 Entity Component System 这些具体名词上。从 wikipedia 上看 ，DOD 的提出是源于游戏软件对性能的追求， 它主要围绕的都是其数据在内存中的组织形式不同。和 C++ 这类可以直接控制对象内存布局的 OOP 的语言的默认布局相比，DOD/ECS 的数据布局对 CPU Cache 更好友一些，从而可以获得更好的性能。

如果从这个角度看，如果不是用 C/C++ 这些可以直接控制数据内存布局的语言，采用 ECS 的意义很小。

但是，我觉得 ECS 的意义不仅在于此，它的更重要的意义在于在数据层面对业务解耦。从而引导实现者实现内聚度更高的模块。

阅读全文 "ECS 模型下的处理模式" »

云风 提交于 03:28 PM | 固定链接 | 留言 (9)

我想用 C 实现一个内存紧凑的 ECS 框架，希望数据结构足够的简单，且能管理海量的对象。所以我让每个 component 就是一个不包含任何引用的 struct ，并带有一个 32bit 的 id 。并把这样的一个数据结构放在一块连续内存中。

这个 id 没有对外暴露的 API （不是 entity id ），可以在运行过程中调整。如果两个不同类型的 component 有相同的 id ，即认为它们同属一个 entity 。id 的作用是管理 component 的生命期，以及在遍历 component 时，可以找到同个 entity 上其它的组件。

对于我的应用场合来说，最多的操作是遍历单类 component 的集合。这种操作在这个数据结构下特别简单，就是 for 循环遍历一个简单的数组。但有些系统会需要在处理一个 component 时，找到它归属的 entity 上的兄弟组件。由于我不想用额外的内存建立这些 component 间的联系，所以这个开销就会特别大。如果不做任何优化，查找是 O(n) 的，n 为组件的数量。这显然不能接受。

第一步优化，我让组件在组件集数组中保持有序，按 id 排序。id 本身在分配的时候是单调递增的，所以只要 32bit id 不回绕就能一直保持有序。一旦回绕，我们重排一下即可。对于有序的数组，用二分查找可以减少到 O(log N) 的时间复杂度。

如果 N 特别大（十万以上）时，还是比较慢的。那么，有没有可能对二分查找做进一步优化呢？我做了一点尝试。

阅读全文 "带猜测的二分查找算法" »

云风 提交于 02:05 PM | 固定链接 | 留言 (8)

最近在尝试做一个类似异星工厂的游戏原型。由于最终希望在内存有限的手机上运行，所以不得不考虑内存如何有效利用的问题。

这是因为，我在玩异星工厂（加上一些 mod ）时，发现 PC 内存能占到 10G 以上，且这些内存大部分都不是图像资源，是实打实的逻辑数据。我稍微估算了一下，在一些内容丰富的 mod 中，游戏内的对象能够达到数十万，甚至上百万之多。用传统方法使用的内存势必以 G 计算。

如果希望同样的逻辑跑在手机上，我希望把逻辑数据控制在 500M 之下。除了从游戏玩法做做一些限制外，还需要对逻辑占用的内存精打细算。

阅读全文 "缓存在 Lua 中的配置表" »

云风 提交于 06:20 PM | 固定链接 | 留言 (7)

这两天想给一个想法做个简单的原型，因为涉及人机交互，需要在屏幕上绘制一些简单的交互元素。当然，现在有很多工具可供利用。过去遇到这种事情，我会尝试用已有的各种开源游戏引擎（我尤其推荐 PICO-8），或是直接在浏览器中用 css/javascript 写等等。

最近几年我玩了大量 RogueLike ，想尝试一下在 console 下用 ascii 字符来拼凑画面。这很有趣，能让我回忆起小时候 Apple ][ 上花掉的大把时光。同时我想用 Lua 来做开发，却不想引入 ncurses 这样的第三方库。最好能用几分钟就可以从零搭建起开发环境。

最好的选择当然是用 ANSI escape code 通过标准输出在 console 界面上作画了。

阅读全文 "ANSI escape code 及 Lua 封装" »

云风 提交于 10:30 AM | 固定链接 | 留言 (10)