云风的 BLOG

游戏场景中的物件都处于一个树结构的某个层次节点上。之所以是一个树状的层次结构，是因为物件本身的某些属性的值是由层次结构中的父节点中的属性决定的。

典型的需求是物件的空间位置，通常在节点本身记录的是一个相对父节点局部空间的矩阵。但渲染模块处理物件，则需要计算这个物件在世界空间的位置，即世界矩阵。

还有一些类似的东西，例如，我们可以给一个节点设置一个材质，如果子节点未设置别的材质的话，则希望继承父亲的材质。

总的来说，每个节点的属性并非只记录在节点身上，还可能受父亲和祖先的影响。

标准的树结构是在每个对象中都保存一个父节点的引用，以及一组孩子的引用。但我不喜欢这样的数据结构。

首先，但这有明显的数据冗余，A 如果是 B 的父亲的话，这个关系同时记录在 A 的孩子引用中，也记录在 B 的父亲引用中。数据冗余会增加复杂度，滋生 bug 。bug 容易导致冗余数据的不一致。

其次，遍历树结构比遍历线性平坦结构需要更复杂的迭代器，也就是说，迭代过程的状态更复杂。尤其对于我们的 ECS 框架来说，保持迭代过程的简洁非常重要。

最后，一旦树结构中出现环，会让一些非常严重的 bug 滞后表现出来。而检查树结构的错误状态的成本也是比较高的。

我们一开始设计场景管理模块时就摒弃了这种传统的数据结构。我认为，场景对象只需要保留父节点 id 就足够了。内存中即有完整的场景层次结构。大多数物件并不关心自己的孩子有哪些，如果业务层真的需要遍历自己的孩子，完全可以额外再记录下来。

但这样设计的缺点也是明显的：在不做额外处理时，场景中的物件是无序的。

如果我们需要读取的场景物件的某个属性依赖父节点的状态，那么就需要上溯完整的祖先链。例如，计算物件的世界矩阵，就需要将自身的局部矩阵乘上父节点的局部矩阵，以及所有祖辈的矩阵，直到根节点。

对于处理整个场景来说，很多矩阵乘法都是多余的。

如果是用传统的树结构，因为遍历是有序的，遍历过程总能保证祖辈节点比后代先处理到，所以就可以减少重复的矩阵乘法。

那么，在现有的平坦结构（每个节点只保存父节点的引用）下，有没有办法也做到有序遍历呢？

我之前的做法是在遍历前做一次拓扑排序。并对拓扑排序结构做若干缓存处理，让引擎做拓扑结构不发生大的变化时，重整次序的代价尽量的小。

但这次重构，我发现了一个更简单的算法，可以在一个简单的数据结构之上实现出来。

如果我们给每个场景物件都赋予一个独立的 id ，其中，根节点的 id 为 0。那么，我们要的其实是一个用物件 id 构成的有序队列。所有场景物件都在在这个队列中，且，每个物件的父亲都处于队列中自身的前面。

满足这个条件的队列远不止一个，对树进行深度遍历得到的序列，以及对树进行广度遍历得到的序列都满足这样的约束条件，甚至在遍历孩子时打乱兄弟之间的次序也没有关系。可见，维持这样的次序是很宽松的，所以我们一定能找到很轻量的算法来保持队列的次序。

假设我们的系统一开始，这个有序队列是空的，然后，我们 监听了所有对物件的父节点引用的修改事件 。这个事件是一个二元组，即谁的父节点变成什么。当新节点创建时，即为 一个新的 id 和旧有 id 的二元组。如果我们想删除一个场景节点，则是将某个节点的父节点引用设置为空。

可想而知，场景的构建过程，就是处理一个个这样的消息逐步完成的。

为了后续处理方便，我再设置了一个索引表，记录下队列中每个节点 id 在队列中的位置，以及每个 id 的父 id 是什么。

接下来就可以处理消息了。处理这个二元组消息分这样几种情况：

1. 如果是新节点引用旧节点，即创建了一个新 id 指向已有的 id 。那么，我们只需要把新 id 放在队列尾。因为已有 id 一定在它的前面。

2. 如果新节点引用另一个新节点，即父子对都还不存在于队列中。那么，我们只需要把两个新节点都放在队列尾，父亲在前，孩子在后。同时，把父节点的父亲设置为根 id 0 。

3. 如果是一个已有节点引用另一个节点（如果不存在则将这个新的父亲先家到队列尾），这就意味着，节点需要更换父亲，这样我们的队列次序可能被破坏了。需要调整队列，保持有序。

这是最复杂的情况。这时，应该查询一下父子两个节点在队列中的位置。假设子节点位置为 P ，父节点位置为 Q 。

如果 P > Q ，那么子节点依然在父节点的后面，什么都不需要做。

如果 P < Q ，那么，我们需要调整 P 和 Q 之间这一段，保持队列有序。这时，我们可以新建一个临时队列 T ，把 Q P 先放进去。然后遍历 P 和 Q 之间这一段，比较每个节点，若节点的父亲在 T 中，则把该节点加在 T 的最后；否则把这个节点向前挪，顶到 P Q 区间的前段。遍历完毕后，就可以把 T 补在 P Q 区间的后段。

关于删除节点，即把对应节点的父引用设为空。我们在遍历时，可以同时检查父节点是否为空，如果是，则将自己置空。这样就可以在遍历完毕后，找到删节点的所有子节点一并删除了。

我把以上的算法及数据结构单独放在一个 lua 模块中，这个模块仅仅管理这样的 id 构成的队列。因为算法逻辑较为复杂，我用 C 语言编写反而比 lua 实现更顺畅（性能也更好）。但数据结构则完全采用 lua table （表示那个有序队列）而不使用任何 userdata 。

这样，就可以灵活的被其它模块使用。