« November 2019 | Main | January 2020 »

December 24, 2019

ECS 中的消息发布订阅机制

我们在实践 ECS 框架时发现,之所以 ECS 的概念诞生于游戏领域,是因为游戏程序往往都在周期性的处理一批对象,进行运算,根据上个周期的状态得到下个周期的状态。而传统人机交互的应用则是响应型的:即一个外部请求触发一系列的业务运作。

如果你把游戏业务塞到响应型框架中,就会发现,不得不用时间去触发,业务响应的是 timer 。但这种情况下,timer 几乎没有携带任何状态,对单个 timer 的响应,是不可能做成无状态的:它本身就是整个游戏世界对上个状态的迭代。

这种情况下,响应式框架就很低效。

但是,如果框架完全做周期性自迭代,对外部输入事件的处理又远不如响应式框架灵活。

如果只是简单的操作输入还好,比如手柄,我们可以每帧把手柄各个按键的状态置入世界,那么 System 在不断迭代时,直接把这些状态当作世界中某个单例的状态就好了。但更复杂的输入就没那么好做了。

我们在一开始实践 ECS 框架时,很想保持整个模式的纯粹性,刻意回避了传统响应式框架里的东西,仅仅只添加了一个外部事件输入的消息队列。对于框架内部产生的事件,如组件的出生、销毁;内部对象的状态机状态切换引发的次生效应;物理系统抛出的事件,等等,都转换为状态的变化。由对应的 System 每帧去重复处理这些状态。

最近我觉得,刻意的在 ECS 框架中去回避一个事件系统是不对的。游戏业务本身也是一个混合体:混合了周期性的世界状态迭代模式和响应式业务处理模式。

所以我下决心给 ECS 框架增加一个完备的消息发布订阅模块。

由于我们的框架是用 Lua 编写的,所以这样一个模块可以做的远比 C/C++ 的类似框架更灵活。我们的每条消息都是一个 key/value 元组,用 lua table 承载,例如:{ type = "new" , eid = 42 } 就是一条消息,表示一个 id 为 42 的 entity 创建出来了。而鼠标消息则可能是 { type = "mouse", action = "move", x = 100, y = 200 } 。

所有的消息都通过 world:pub(message) 来发布出去。

而任何 System 都可以通过 mailbox = world:sub(pattern) 来订阅满足一类 pattern 的消息。这个 pattern 也是一个 key/value 元组,比如 { type = "new" } 表示关注所有的 new 类型的消息;{ type = "mouse" } 可以跟住所有鼠标消息,{ type = "mouse", action = "move" } 则可以精确到鼠标的移动,{ eid = 42 } 可以关注到 42 号 entity 上发生的所有事情(通常用于 log)。

任何 system 都可以通过 for msg in mailbox:each() do 来枚举信箱里所有的消息,并清空信箱。


看看背后的实现:

时间复杂度最高的部分在于 pub 消息的时候,目前的实现中,pub 的那一刻就已经把消息分发到了所有之前 sub 过的 mailbox 中了,通常会有 n 个 mailbox 关心这条消息。每个 mailbox 就是一个队列,所以迭代反而很简单。

我们的消息匹配(message matching)很灵活,规则却很简单:pattern 中的每一个 key/value 就是一个过滤条件,只有消息满足所有的条件,才会被投递到对应的 mailbox 中。如果不加优化,pub 的时间复杂度是 O(n*m) 的,n 是消息的长度,m 是系统中的 mailbox 数量。

但优化也比较容易,在 sub 时,建立索引 cache ,用空间换时间即可。

例如:在一次 sub 的 pattern 中,出现了一条 type = "new" 的条件,那么就建立一个 type:new 的索引表,把所有满足这个条件的 mailbox 都放在一个集合(候选集)中;同时不满足这个条件的 mailbox 也放入一个集合(排除集)。

其中,满足条件指明确写了 type = "new" 这个条件的 pattern 或是 pattern 中没有 type 这个 key 。不满足条件指,pattern 中有 type 这个 key 但 value 不是 "new" 。

这样,pub 一条消息时,根据消息中的一项,就能 O(1) 快速判断,这个条件能排除哪些 mailbox ,以及哪些 mailbox 是潜在的候选者。遍历完消息后,依然留在候选者名单中的 mailbox 就是筛选出来的。因为每次处理一个条件,最终候选集都会减小。为了减少比较次数,还可以对消息中所有条件对应的候选集的大小排序,先过滤候选集较小的那个条件,

这样,这个过程虽然还是 O(n * m) ,但 m 是最短候选集的长度而不是所有 mailbox 的个数,大多数条件对应的 m 为 0 (没有人关心)。

如果实际使用的时候,筛选条件五花八门,可能导致 cache 索引集占内存过多,我认为可以用元表机制做一些合并,或是标注一些条件不生成 cache ,而是退化成遍历的方式检查。

另外,对于常用的条件组合,还可以生成联合索引 cache 。当然,这些都是以后可以优化的地方。

December 21, 2019

程序员修炼之道第二版译者跋

文本在阐释中烟消云散 —— 尼采《善恶的彼岸》

2019 年 12 月 20 日,我终于用笨拙的中文把《程序员修炼之道》的第二版初步译完。距编辑侠少把英文电子版发送给我已经过去了 70 天。这两个多月里,翻译工作几乎占据了我所有的业余时间,真的很累,但却心甘情愿,并乐得其中。

侠少和我认识多年,他一直劝我再写一本和编程开发有关的书。虽然这 20 年职业开发生涯积累了很多想法,Blog 也坚持记录,但每当有动笔写书的念头时,心中便开始忐忑不安。甚至前些年写过半本关于 Lua 的源码欣赏的书,半途不甚喜欢,而将其废弃。

似乎每隔一段时间,我都会对编程这件事产生新的领悟。尤其是这几年随着儿女的前后到来,陪伴着他们的成长,明白了更多的道理。却越发的不敢写了。

《程序员修炼之道》曾是我最喜欢的一本开发实践方面的著作。在 20 年后,作者在旧版的基础上进行了大量的重写。得知新版已经付梓,我特别期待。务实的程序员 20 年的积累,会是多么的可观。我相信,自己将从这一新版中汲取大量营养。几乎是毫不犹豫地,就接下了翻译的任务。

从私心讲,我希望是自己,而不是其他任何人来用中文重新阐释这些思想。自己的深度还远不及这些前辈,若谈原创恐怕力所不及,但作翻译当是合格的。

我做过技术文档的翻译,汉化过游戏文本,翻译过一些技术书的部分章节。但像这样完整地翻译整本书并将付诸出版,还是第一次。工作启动后,难度远超我的预想。作者不仅引经据典,还大量使用了未传入中文世界的迷因及英语俚语。这让我经常为了一两个句子而反复 google ,流连于 wikipedia urbandictionary quora 这些网站。

感谢我的同事们,曾瑞宏、李焱、朱晓靖、刘阳、李熙龙、吕斌、陆志锴、他们在我翻译的过程中,指出了很多错误,陪我推敲词句。当然还有本书的编辑侠少,他做了大量的校对、改错、润色工作,在工作的 git 仓库上,可以看到大部分句子都有他修改过的痕迹。如果你觉得译文理解起来还算流畅,那都是他的功劳;若是发现了什么技术错误,全是我的责任。

翻译是译者用自己的思想,换一种语言,对原作者想法的重新阐释。鉴于我的学识所限,误解错译在所难免。如果你买到本书的原版,且有能力阅读英文的话(我相信这是一个务实的程序员的必备技能),请直接去读原文。因为这样的话,我的译文根本不值得一读。

作为务实的程序员,原作者在写作本书时实践了他们的理念:用 markdown 创作,基于版本控制工具维护,利用自动化脚本生成最终的版面。很惭愧,受当前的中文出版条件所限,我只在初译阶段,遵循了这些。排版阶段还无法写出自动化脚本整合版面,也因此无法维护原书丰富的索引。对此我甚为遗憾。

最后,愿每个写代码的人都能成为务实的程序员。

December 03, 2019

5 岁小朋友的游戏历程

云豆 5 岁半了,早在他三岁的时候,我就刻意培养他玩游戏的能力。我觉得这是促进智力发展的最佳途径。

一开始是给他玩一些非常简单手机游戏,当时他还不到三岁,即使是那种给猫玩的简单游戏,似乎他也无法明白其中的逻辑。我感觉我儿子的大脑发育较慢,谈不上聪明,至少不比同龄小朋友聪明。我在三岁时未经刻意学习已经可以认不少字,并能记事了;而云豆这个时候还不能用语言流利的表达。但我想我有耐心慢慢陪伴他长大,观察人类习得基本技能的过程,面临的挑战(成人已经忘记,觉得理所当然的东西),也是件极为有趣的事。

云豆第一个感受到乐趣,乐此不疲的游戏,是 ios 上一款叫做有趣的食物的 app 。它为幼龄儿童考虑的相当周到,大多只需要点点点就能继续下去,需要非常有限的逻辑。在三岁左右的年龄段,我尝试了很多游戏 app ,以点击为主,大多都达不到让小孩理解并独立玩下去的程度。

比较神奇的是,云豆自己开始在爷爷奶奶的 ipad 上自己通过广告下载游戏了。他比较喜欢简单跑酷类的(但我给他试过此类游戏的鼻祖古墓逃亡,却玩不下去),还有一个神奇的游戏叫 tap tap dash ,他玩了几年,最近把所有关卡都解锁了(有几千关),最后的关卡快到了匪夷所思的程度,需要大量机械性地背板才能完成。

我当时自己特别喜欢 mr jump ,经常玩给他看,他也是很喜欢,但一直无法自己上手。直到 4 岁多才能自己通过第一关;后面的关卡都能玩一些,都没有一个能打过。


我试过让云豆学习用鼠标,但难度很大。或许是到了这一辈,除了工作,大家都很少用鼠标了,触摸屏才是首选交互。似乎在 10 年前,如此大的小朋友在 PC 上玩植物大战僵尸都还挺溜的。即使在 ipad 上,我也没能教会三岁小朋友理解 PvZ 的游戏逻辑。

因为在家里我也不太用电脑,我很早就放弃了教小朋友玩 PC 上的游戏。最好的游戏设备还是客厅中的 switch 。

最初他(不到三岁)唯一能接受的游戏是 1-2-switch 里的摇汽水,怎么都不玩不腻。但 1-2-switch 里大多数游戏都太抽象了,小孩无法学会,远远比不上后来的马里奥派对。等大一点他才学会了像挤牛奶等简单的游戏。

我很想让云豆早点学会怎么使用游戏手柄。我发现使用手机的技能并不是天生具备的。我们这一代玩家从雅达利的摇杆,到任天堂 FC 的十字键加两个按钮过来,其实是一个慢慢习惯的历程。现在的手柄需要动用双手大部分手指,实在是太复杂了。像我父母这辈的老人就很难习惯。

一开始我是用你剪我裁训练云豆的。只需要用摇杆在平面做左右的操作。他费了很大的气力才能够把小黄人停在期望的位置。这个过程在三岁初大约花了几个月时间,玩了几十次。不知道是年龄增长的缘故,还是熟能生巧,反正慢慢掌握了。

之后我尝试过马里奥赛车,他兴趣不大。不过赛车支持体感操作,比小摇杆要简单一点。

云豆真正爱上并能独自玩耍的游戏是星之卡比:新星同盟。不得不说这个游戏设计的太棒了,简直是为小朋友定制。即使你什么都不懂,也能一直飘在空中飞到关底。在云豆刚满四岁的时候,我连着陪他玩了一个月的卡比。一开始他不太理解怎么玩,但教学部分却能跟着做,并引以为趣。每到不知道怎么过去的地方就甩手柄给我。但渐渐的就有打怪、避免受伤、找出隐藏要素、打 boss 这些概念了。

小孩子最为有趣的地方就是一旦他学会了,就不厌其烦地从头到尾一遍遍的玩下去。后来我就可以放手不管,他能自己一遍遍通关,并逐个找到隐藏要素。当然,并不是找出来的,而是背出来的。期间,有几个邻居大一点的小朋友来家里玩,也能很开心的一起游戏。

马里奥派对发行的晚一点。我试着教他玩里面一些比较难的小游戏,尤其是一些需要用摇杆在平面移动的,云豆的操作还很有问题,最后就是不太愿意玩。游戏逻辑性比较强的也比较难理解。记得稍微逼过一次(玩不过去就不让玩别的游戏),还因为不会玩而痛哭流涕。

大约快 5 岁的时候,耀西的手工世界成了云豆的最爱。这个游戏比卡比多了一个摇杆瞄准射击,需要一点时间学习,但基本上还是一个平台跳跃游戏,有很大的共通性。最了不起的设计和卡比一样,有个简单的翅膀模式,只要不停的按就能飘在空中,甚至飞上去。这对小孩(以及没有游戏经验的人)真是太棒了。

耀西一个颇为讨厌的问题是无法删档重玩,但小朋友就喜欢一遍遍的重玩。从头收集是他源源不断地乐趣。所以我只好不停的建新用户,然后删掉。耀西恐怕被云豆通关了至少 10 遍。一开始他无法独立打 boss ,看我玩了几次后,慢慢就学会了。可以说小孩背版的能力真的是超强。当然他一直念叨的全收集,还是我帮他完成的。耀西最后几关的全收集对成年人来说也是个挑战。

下一个可以独立玩的游戏是蘑菇队长。这个游戏发行虽然早一点,但开始我没有买。后来有朋友介绍说收集元素和耀西颇为类似,我就买了一个试试。但蘑菇队长的操作难度瞬间就提升了。需要学会双摇杆操作,一个控制行走,另一个控制镜头,部分关卡还需要用陀螺仪定位。云豆一开始无法独立游戏,必须我手把手教。他几位喜爱看我通关,他对看人打游戏的乐趣胜于自己玩。但和云玩家不同,看多了还是会自己尝试的,慢慢就自己会玩了。只是作为一个小孩,耐心还是不足。一个地方如果失败了很多次,就不愿意尝试了。我玩游戏则相反,越失败越要玩下去。我认为这是急需培养的地方。

所以,马里奥 U 和马里奥制造 云豆都玩不进去。我想是马里奥的加速跳操作太难是一个原因,另一个原因是死亡惩罚太高,动不动就要重来。同期也尝试过蔚蓝这类平台游戏,云豆多是喜欢看多过尝试的念头。

最近云豆的新宠是路易鬼屋。有之前蘑菇队长等游戏的基础,复杂的手柄操作已不在话下。虽然一开始还是不太愿意自己挑战 boss ,甚至在 boss 出场的时候甩手柄给我我没接的情况下大哭了一场。但在看我通关后,也开始自己独立游戏。尤其是第一次靠自己打败了 boss 后那个开心劲,现在又开始删档重玩了。


前段他迷恋过一个月的健身环,无师自通,差不多通关了。

我还陪他玩过差不多一个月的勇者斗恶龙11s ,云豆非常喜欢,天天让我一起陪玩。只是这种 RPG 需要一定的阅读能力,战斗也需要逻辑理解。他暂时只能做到简单的加血攻击,后期的 boss 根本无法自己进行。最近我的业余时间多在做书的翻译,无法每天陪着,只好用新游戏(路易鬼屋)把他吸引开了。同样的遭遇还有塞尔达旷野之息。恐怕 RPG 类只能等他大一点再享受了。

另外,有个同事家的小朋友同龄,据说自己可以通关王国守卫军。比云豆强。我给他玩了一段时间的 ipad 版,打到一半就玩不过去了。