May 26, 2020

lua hash 函数的一点讨论

最近一段时间,lua 的邮件列表中有好几个主题讨论 hash 表的设计。我读下来受益匪浅。比如 前两周的这个主题 中,有同学主张去掉 lua hash table 中的链表指针,而改成固定步长的冲突链表。具体这里就不展开了,有兴趣的同学可以自己看。

这两天的讨论是围绕 lua 的 hash 函数的,暂时还没有固定链接,我把我的理解和思考记录下来,不一定正确,如有行家发现错误,请不吝赐教。

unsigned int
luaS_hash (const char *str, size_t l, unsigned int seed, size_t step) {
  unsigned int h = seed ^ cast_uint(l);
  for (; l >= step; l -= step)
    h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1]));
  return h;
}

来看这样一个 hash 函数:

阅读全文 "lua hash 函数的一点讨论" »

May 19, 2020

记一次生不如死的经历

前几天晚上 21 点洗澡的时候感觉左腹部疼痛。因为前一天有过一次腹泻,便以为是吹空调着凉还没有好。继续蹲在马桶上又拉了一次肚子,但和之前不同,并没有减少痛苦的感觉,反而加重了。

我转而怀疑是吃错了什么东西引起的肠胃问题,但是努力回忆也想不出什么来。只觉得如果能把腹中的东西排空应该就好了。想了一下就抠了一下喉咙,趴在马桶上将肚子里没消化完的食物吐了出来。可是依然不见好转。

这个时候已经是坐立不安了,找不到一个姿势可以让自己好受一点。

我自觉还是对疼痛忍耐指数挺高的,攀岩的时候手指肚上拉下一块皮也不觉得有什么,可以继续爬;有次拔智齿的时候甚至没打麻药,牙科医生都赞我是看过的病人里最能忍痛的。可这次真的有点受不了。

阅读全文 "记一次生不如死的经历" »

May 08, 2020

《程序员修炼之道》中的一段废稿

我在翻译《程序员修练之道》第二版时,一开始拿到的版本并不是现在出版的这个。所以在中途更换过一个版本,即最后英文版的最终版。前后两个版本都不是原始 markdown ,而是 pdf 格式的。试过几个 diff 软件都无法很好的比对,只好花了不少时间人肉校对了一遍。

虽然两个版本先后只差了几个月,但是增加,调整的段落非常之多,可见作者维护的非常频繁。我当时特别想一观他们的内部写作仓库。记忆比较深刻的是有一大段谈团队的文字被删掉了。不知道原因。但我觉得挺可惜的,这是我很喜欢的一个段落。为了忠于原著,我也从中译版里删除。

下面记录一下这段废稿:

阅读全文 "《程序员修炼之道》中的一段废稿" »

April 30, 2020

游戏引擎中预制件的设计

Unity 推广了预制件 Prefab 这个概念,在此之前,Unreal Engine 里有个类似的东西叫做蓝图 Blueprint 。当然它们不完全是一种东西。我现在自己设计游戏引擎,更喜欢 Unity 中的 Prefab ,但我认为 Blueprint 这个名字其实更贴切一些。

当我们说制作一个 Prefab 的时候,其实制作的是一个预制件的模板。引擎运行时对应的那些数据,其实按照这个模板生产出来的。所以,工具制作出来的 Prefab 其实是一个 template ,所以,它本质上就是一张蓝图。但因为 Unity 深入人心,所以我还是打算基于把这个东西叫预制件。

对于 ECS 系统来说,预制件是一组数据,通常保存在文件中,可以以该资源文件的内容为模板,来构造一组 Entity。注意:预制件作为资源文件时,和贴图、模型数据等这些资源文件是不同的。贴图之类的资源,映射到内存后,就是一个数据块或一个引擎中的 handle ,可以被共享使用。但预制件本身只是一个模板,它用于生产数据,本身不是数据。从这个角度讲,如果把预制件文件当作资源纳入资源管理模块统一管理的话,预制件资源对应的是一个 function (生成器)而不是 table (数据集)。

阅读全文 "游戏引擎中预制件的设计" »

April 15, 2020

资源模块的重构

这篇是对 游戏引擎中的资源生命期管理问题 的延续。

最近对我们游戏引擎的资源模块做了一次重构,大概花了一周的时间,其中核心模块的代码实现花了 2 天。比之前的方案简洁很多。新方案的设计是基于以下原则来实现的:

  1. 引擎应该围绕数据来设计。ECS 更是数据驱动的模型。
  2. 数据全部都用一致的数据结构来表达,方便统一处理。因为我们采用 lua 做开发,所以,一切数据都是 lua table 。我们的引擎与其说是基于 lua 开发,不如说是基于 lua 的数据结构开发。即使某些模块因为性能因素用 C/C++ 实现,操纵的还是 lua table 。读写 lua table 的性能和读写 C struct / array 相比,并无显著的劣势。
  3. 在使用上尽量不区分外部不可修改的静态数据和运行期动态修改的数据。
  4. 惰性加载,延迟异步加载,替代资源,这些尽可能的隐藏起来,不必对外透露细节。尽可能的减少外部干预。
  5. lua 虽然有 metatable 这个神器,可以帮助我们抹平不同数据、不同策略之间的差异。但不要过多依赖语言特性。

阅读全文 "资源模块的重构" »

April 10, 2020

场景层次结构的排序

这篇是对 场景层次结构的管理 的再思考。

最近在重构引擎的场景管理模块。主要动机之一,还是觉得现在已经实现的东西(由于需求不断增加)太复杂了,以至于老在修补其中的 bug 。

经过了几天的思考后,我决定把场景管理中的一部分挪出来,单独作为一个模块。那就是对层次结构的排序。

具体是这样的:

阅读全文 "场景层次结构的排序" »

April 04, 2020

《程序员修炼之道》20 周年版已付梓

我翻译的 The Pragmatic Programmer 20th Anniversary Edition 已经摆上了书店的货架。今天收到了出版社快递来的几本样书。纸张挺精良的,对得起这本著作。听朋友说,京东上的预定也陆续到货了。我非常期待各位学友的反馈。

去年几乎是一口气翻译完的。倾注了颇多心血。一边翻译一边和身边的朋友分享,几乎每个读过的人都很喜欢。我希望每个程序员都能读一读这本书。即使你已经读过第一版,也绝对不能放过这个新版。我在翻译过程中一直在做新老版本的对照,能明显感到与时俱进的内容。而且即使是没怎么修订的章节,这次因为读得非常细致,也有很多新的领悟。

限于水平,这次的翻译一定会有差错。希望发现错误的朋友能不吝指教。我会尽力在重刷的时候修正过来。

另外,这次的译本同时拿到了 kindle 上出版的版权(挺不容易的)。kindle 电子版应该会在 2-3 月内上线。不太喜欢囤实体书的同学可以再等等。

勘误见这里: https://github.com/cloudwu/tpp_feedback/

March 12, 2020

矩阵 decompose 的一点优化

我们的游戏引擎中,有个重要的功能是将一个矩阵分解成 S 缩放,R 旋转,T 位移三个分量。这里 T 直接取矩阵的第四行即可,代价比较高的是 S 和 R 的分解,其中 R 又取决于 S 的提取。

但是,游戏中大量的矩阵中是不包含缩放的,即 S 分量大多是 (1,1,1) 。一旦不用缩放,又可以简化 R 提取的操作。所以我打算对传统算法做一点优化。在提取 S 的时候多加一次判断,看值是否接近 1 。

计算 S 的方法是将矩阵的前三行当作三个 vector 3 分别取 length 。length 其实是取 dot 然后计算 sqrt。由于大多数情况预测 dot 值很可能为 1 ,那么当 dot 接近 1 的时候,就不必再开方了。

阅读全文 "矩阵 decompose 的一点优化" »

March 11, 2020

不变量及运算优化

去年的时候,我们对正在开发中的游戏引擎做了一点 profile 工作。后来发现,在场景中对象很多的时候,有一处运算占据了 10% 以上的 cpu 时间。当时我的判断是,这处地方值得优化,但并不是工作重点,所以就搁置了。

问题的具体描述是这样的:

我们的引擎每帧会将场景中的对象依次提交到一个渲染队列中,每个可渲染物件,除了自身的网格、材质外,还有它自身的包围盒(通常是 AABB),以及它在世界空间中的矩阵。

我们有一套资源系统,场景中的对象会引用资源系统中的对象,这些资源对象是一个不变量,会被多个场景对象所引用。而资源对象又可以是一个树结构,比如一个模型就可以由若干子模型所构成。提交到最终渲染队列中的是不可再拆分的子模型的信息。

也就是说,在场景管理的层次,对象的数量是远少于提交到渲染队列中的对象数量的。这就是为什么我们渲染每次重建渲染队列,而没有将每帧提交给渲染队列的列表持久化为一个链表并作增减维护的原因。

问题出在提交给渲染队列的每个物件的包围盒上。

阅读全文 "不变量及运算优化" »

February 12, 2020

git shallow clone 的一个问题

最近在家办公,遇到的第一个问题就是家里网络极不稳定,无法 git clone 那些庞大的仓库。我知道 git 现在支持浅拷贝,用 --depth 1 就可以取出某个分支的 HEAD 指向的拷贝所依赖的所有文件。

但是,光用 git clone url --depth 1 还不能解决我的所有问题。因为需要传输的文件还是太大,不稳定的网络无法坚持到我顺利下载完成就断开了。而 git clone 得下载过程似乎不能续传,我只好另辟蹊径。

过去翻 git 文档时,曾经了解过有一个 git bundle 这个指令可以对需要传输的内容打包,然后大多数依赖接受数据的 git 指令都可以直接接收用 git bundle 打好的包,而不必通过网络传输。事实上,git clone 的过程就是在远程打好包,然后传输到本地,再解开的。

阅读全文 "git shallow clone 的一个问题" »

February 05, 2020

skynet 版的 cache server 改进

去年我实现的 Unity cache server 的替代品 已经逐渐在公司内部取代 Unity 官方的版本。反应还不错,性能,可维护性以及稳定性都超过官方版本。

最近疫情严重,公司安排所有人员在家办公,今天是开工第三天。前两天比较混乱,毕竟在家办公的决定是在假期中间做出的,并没有预先准备,我们的这个 cacheserver 也在第一天受到了极大的考验,暴露出一个问题,好在只是内存用量预警,并没有出任何差错。我花了一天多的时间排查和解决问题,感觉这是一个极好的案例,值得记录一下。

阅读全文 "skynet 版的 cache server 改进" »

January 19, 2020

不适合采用 System 的一种情况

ECS 框架中,System 通常是对某种 Component 的集中处理。大部分情况下,一次性对大量对象中的简单的数据结构做简单的处理,比每次对一个对象的复杂数据结构(通常是简单数据结构的组合)做复杂处理,依次处理所有的对象要更好。

凡事总有例外。我们最近就发现有一类情况不适合这样做。那就是骨骼动画的骨骼计算。

骨骼计算会分为若干步骤,有骨骼数据的展开,骨骼姿态的混合,IK 计算等等。一开始,我们遵循着 ECS 的设计原则,把这些步骤分到不同 System 种。例如并非所有的对象都需要做 IK 计算,这样 IK System 就只用遍历一个子集;同样,也并非所有的动画都需要做多个姿态的混合,等等。

阅读全文 "不适合采用 System 的一种情况" »

January 13, 2020

ECS 中的概念缺失

经过长时间的思考和实践,最近一个多月,我们的 ECS 框架做了较大的调整。其中一部分工作已经在前一篇消息发布订阅机制中介绍,另一部分工作其实开展的更早,但因为我想多沉淀一段时间再写。到本周基本基本改动完毕,可以总结一下了。

ECS 框架几乎只在游戏开发领域提出,我认为这主要是因为目前只有在游戏领域,周期性的大量对象的状态变换才是主流行为。而在其它人机交互领域,响应外部事件才是主流。这是为何 System 在游戏领域如此重要的原因。

但另一方面,ECS 框架对过去流行的面向对象框架的反思,主要集中在面向数据/数据驱动。这是 Component 概念被如此看重的原因。Component 是行为被拆分出来的对象,重要的是数据本身。对于框架来说,要解决的是更方便的组合、有完善的自省机制,这才能针对数据集本身来编程。因为游戏开发,程序员的工作仅占很少的部分,大部分的工作是策划和美术围绕开发工具给数据添砖加瓦的。

阅读全文 "ECS 中的概念缺失" »

Misc

Categories

Archives

Recent Comments