今年上半年的时候，就想把我们游戏引擎中场景层次结构管理模块的设计记录一下。每次想写的时候都在做小调整。直到最近，算法和数据结构才稳定下来。今天做一个记录。
游戏里的场景对象，通常以树结构保存。这是因为，每个对象的空间状态，通常都受上一级的某个对象影响。
从管理角度讲，每个对象最好都能知道它可以影响其它哪些对象；且必须知道它被哪个对象影响。所以，这会用到一个典型的树结构。尤其在做编辑器时，树结构还会直接呈现在编辑界面上。不过，我认为在运行时，从父对象遍历到子对象的需求并不是必要的，需要时可以额外记录。从数据上考虑，父亲记住孩子和孩子记住父亲，是重复了同一种关系信息。如果不需要记住孩子的兄弟次序，那么在核心数据结构中，我们只需要让孩子记住父亲就足够了。
去掉冗余信息可以简化数据结构、减少维护成本、避免犯错误。尤其对于 ECS 架构，我希望所有对象都是平坦的，在场景对象组件上，一个 parent id 可以最少的构造出场景的层次结构出来。
最近我们在开发引擎时遇到一个和操作系统有关的问题，想了个巧妙地方法解决。我感觉挺有意思，值得记录一下。
在 ios 上，如果你的程序没能及时处理系统发过来的消息（比如触摸消息等），系统有机会判定你的程序出了问题，可能主动把进程杀掉。
完全自己编写的应用程序，固然可以把处理消息循环放在最高优先级。即使有大量耗时操作，也可以通过合理的安排代码，不让消息处理延后。但作为引擎，很难阻止使用者阻塞住主线程做一些耗时的操作。所以，通常我们会把窗口消息循环和业务逻辑分离，放到两个不同的线程中。这样，消息处理线程总能及时的处理系统消息。
在 windows 上，允许程序在任何一个线程做窗口消息循环。但在 ios （以及 Mac）上似乎不行。窗口消息循环必须在主线程中运行。
最近我们开发中的游戏引擎在修理资源管理模块中的 bug 时，我提出了一些想法，希望可以简化资源对象的生命期管理。
其实这个模块已经被重构过几次了。我想理一下它的发展轨迹。
最开始，我们不想太考虑资源的生命期问题，全部都不释放。当然，谁都明白，这种策略只适合做 demo ，不可能用在产品中。
因为我们整个引擎的框架是用 lua 搭建，那么，最直接的想法就是利用 lua 自带的 gc 来回收那些不被引用的资源对象。我不太喜欢这个简单粗暴的方法。因为首先， gc 不会太及时，其次 gc 方法触发的时机很难控制，容易干扰正常的运行流程。图形显示模块是时间敏感的，如果因为资源释放占用了 cpu 的话，很容易变成肉眼可查的卡顿。
另一个促使我们认真考虑资源管理模块的设计的原因是，当我们从 demo 过渡到现实世界的大游戏场景时，过多的资源量触发了 bgfx 的一个内部限制：如果你在一个渲染帧内调用了过多资源 api （例如创建新的 buffer texture 等），会超出 bgfx 的多线程渲染内部的一个消息管道上限，直接让程序崩溃。
所以我们不得不比计划提前实现资源的异步加载模块，它属于资源管理模块的一部分，所以也就顺理成章的考虑整个资源管理模块的设计。
我们上周在游戏引擎上面的工作中遇到一些 bug ，涉及到过去的一些设计问题。维持讨论了几天解决该问题的方案。今天终于把最终方案确定了下来，值得做一个记录。
bug 出在游戏资源文件的转换上面。
游戏里用到的资源通常需要一个导入资源库的过程，例如你的原始贴图是一个 png 文件，但是引擎需要的是对应运行平台的压缩格式，windows 上是 dxt ，手机上是 ktx 等等。这个过程，在 Unity 等商业引擎中，是放在资源导入流程中。
我们的引擎把这个转换过程放在虚拟文件系统这个层次。这个设计决策是因为，我感觉统一导入资源是个痛点，用的人通常需要等待导入过程。Unity 用了 cache server 来解决这个痛点，但我认为 cache server 也存在一些设计问题 ，这个会在后面再展开一次。
我更希望转换过程是惰性的，直到最终运行需要的资源才需要转换。
经常有小（我 20 岁左右的）朋友问我，作为一个程序员该怎样提高自己。每个人的经历不同，所处环境不错，其实这个问题很难具体回答。不如好好写一篇总结，以后就不必每封 email 都重新写一次了。
纵观我近 30 年的编程生涯，在每个时期，我看到的东西都不同。想必再过 10 年还会有变迁。我只能写写当下眼界所及之处。
这几天一直在忙着在 bgfx 上增加 ASTC 格式的法线贴图支持 。
法线贴图上的法线向量虽然有三个分量，但是它们是归一化的。而且，切线空间上的法线贴图的第三个向量 Z 总是正值，所以我们只需要用两个分量就可以保存下法线信息，在运行时再计算出第三个向量。
不过这种方法有一个问题，贴图采样的时候，由于是线性插值，所以计算出来的第三个向量可以和实际差的较远。通常的解决方法是保存球形投影的 X Y 分量，减少 Z 的偏差。具体可以看看 Nvidia 的这篇 Real-Time Normal Map DXT Compression 。
显卡硬件一开始并不支持的双通道压缩贴图，所以最早使用这个算法的 Id 是用 dxt5 模拟的，使用 Dxt5 的 RGB 中的 G 保存一个通道，再用 A 保存另一个通道。后来的 EAC_RG11 则直接支持了双通道压缩贴图。
ASTC 虽然没有特别支持双通道贴图，但是它的 encoder 可以把信息权重放在两个通道上，这样就可以在同样的 bpp 下，让双通道信息的误差更小。
bgfx 自带的贴图压缩工具没有支持这样的压缩参数，我最近的工作就是完善它。
我们公司的一些 Unity 项目，当 cache server 的数据上涨到几百 G 后，经常遇到问题。最近一次是 nodejs 内存使用太多导致进程挂掉。
我不太想的明白，一个几乎不需要在内存中保留什么状态的服务，为啥会吃掉那么多内存。简单看了一下 cache server 的官方实现 感觉实现的挺糟糕的。它的业务很简单，还不如按协议自己实现一个。
场景层次结构的管理 (6)
Cloud :
对，我搞错了时间复杂度。...
场景层次结构的管理 (6)
resty :
拓扑排序的时间复杂度O(n + m)就足够了m是边数，对于一个树来说，...
场景层次结构的管理 (6)
:
如何判断兄弟节点之间的层级问题呢...
场景层次结构的管理 (6)
蜗牛 :
写得好！...
关于地图编辑器的一些想法 (43)
hehe :
测试...
那些日子（十八） (15)
tango :
看了您的行事风格，真是像一位武侠小说中的侠客。交友很广，认识行业朋友好...
法线贴图的压缩格式比较 (5)
灵卦 :
第五...
程序员应该怎样提高自己 (31)
山顶的微风 :
可以对文中有不同的意见嘛，但不能以此攻击人！@呵呵 ...
