云风的 BLOG

所以我认为，遍历应该是对外的 API 、而结构控制则应该是内部的 API 。也就是说，作为一个模块，对外不用显露其实现用到的数据结构，而只关心怎样取得模块内部的状态。这时，合适的遍历接口足以。典型的文件系统的接口就是这样做的：我们可以用 / 连接目录和文件名变成一个完整的路径名，用它打开一个文件；而不必一级级取得目录对象，再从中获得文件对象。

相较于结构控制的 API （增加、删除、移动节点这些），更重要的是树的持久化。因为最终用户关心的是最终的数据，以及怎样使用这些数据，而不大关心数据的构建过程。常见的做法是把树状结构的数据呈现为一个 XML 文件，或是生成一张 Lua 表，然后一次加载它，得以在内存中重建树结构。持久化数据的格式不重要，你可以根据性能需要优化它，也可以因为健壮性而采用易读的文本。在大多数应用需求里，一旦树被重建为编辑产生它时构建的样子，就不会再修改它了。无论多简单的结构，把构建过程直接用代码的形式写在源文件中，是最不值得做的事情。早期的 GUI 程序或许还会一行行调用 API 把窗口以及布局搭建起来，而现代 GUI 框架几乎都为界面布局定义一套 DSL ，鼓励设计人员独立描述它们了。

我认为，即使是动态性要求很高的场合，最好也定义出数据格式，便于和使用了树结构的模块交互。比如在 GUI 程序中，我们不建议把一个按钮被按下的行为注入到那个按钮对象中，而是从外部捕获按钮被按下的消息，忽视掉界面的层次结构而直接处理这些消息。为了做到这一点，我们可以定义出类似 HTML 的语言来定位界面上的按钮。

少量修改已经事先创建好的对象的需求也是普遍存在的。往往对象的结构很复杂，但可以调整的部分却很少。有一些支持对象的语言中，直接提供了蓝图对象的概念。比如早期网络游戏常用的 LPC ，让程序员实现一个对象，再给出方法复制它。

我最近读到 狂刃 的图形引擎也用了类似的方法。它在编辑器中编辑出需要的怪物/粒子等对象，然后持久化到文件中。运行时，加载这些数据构造出编辑得到的对象，再根据需要的数量 clone 它们。

对于那些需要对象中需要少量修改的部分，按蓝图复制出一个复制体，再根据需要修改即可。这是图形引擎常见的需求，比如动画节点当前播放的帧号就是一个随时间变化的节点属性，需要在运行期修改的。

我想再谈一点实现上的细节以及优化。

采用了树结构组织起来的数据体，往往就意味着复杂且零碎的数据片段。因为每个结点下都可能有很多子节点，而子节点上保存的对象类型也可能不同，最终是大量不同尺寸内存片的组合体。但实际上，整棵树的绝大部分是不变的。

如果我们在编辑器里编辑出一个复杂的怪物，以它为蓝图在运行期 clone 出多份的话，会发现，这些克隆体之间的共有数据远多过易变量。所以我觉得，把这些易变量和不变量分开储存可能是个更好的方案。易变量（比如每个节点的当前空间状态等）可以平坦化储存，不变量虽然在逻辑层次上是一棵树，但在编辑完成时就决定了它是怎样的，完全可以持久化为连续的数据，并还原到连续内存中，且作为一个对象来管理。作为公有的蓝图，也不必真的复制为多个克隆体，而只需要指针引用即可。

在我最近的另一个项目中，我用 C + Lua 实现了类似的结构，发现代码没有我一开始想的那么复杂。Lua 和 C 的层次还是能分的很清楚。一些需要靠字符串索引储存的数据，我放到 Lua 表中，而 C 中的数据结构则专注于树结构的表述。这样不会在 Lua 中保存太多零碎的 table ，在 C 结构中保有高效的树结构索引能力，又可以把比较麻烦的字符串管理扔给 Lua GC 。而且在很多情况下，对于字符串常量，Lua 语言比 C 语言要高效的多。