分组功能在挂接系统上的使用

前段时间我们给引擎增加了对象分组的功能 。做这个特性的动机是当整个游戏世界中的对象数量远超同时需要处理（显示）的对象数量时，有一个快速筛选出待处理代码集合的机制。

在使用过程中，我陆续发现了这个特性的其它用途。

过去的某个游戏项目中，曾经遇到这么一个需求：游戏中需要为玩家生成一个头像，这个头像是由很多部分构成的。有玩家的肖像、名字、等级、修饰用的图标等等。这个头像可能同时在屏幕的很多位置显示。

如果场景是一个简单的树结构，那么，每个出现头像的地方，都是一个构成头像元素的子树。这样，场景中就可能出现完全一样的多份子树。固然我们可以用一个通用接口构造这个子树出来，但是，一旦这个玩家的属性发生变化，就需要针对所有场景中出现的同类子树进行修改。这需要为每个玩家额外维护一个列表，引用所有头像在场景树中出现的位置。这无疑增加了数据结构的复杂性。

一个自然的想法是，场景不再是一颗树，而是一个有向无环图。玩家头像在场景中可以出现在多处，但子树只有一份。这颗子树的根节点可以有多个父亲。这样，需要修改时，我们只需要改动一处。

在 Ejoy2D 中，我实现了这个机制。但总觉得有些别扭，因为底层的数据结构还是变得复杂了。

目前我们正在用新引擎开发游戏，遇到了同样的问题。我们在做一个类似异星工厂的游戏，里面有许多小细节。在许多场景元素（工厂、机械爪、运输无人机等等）中会挂接一些小元件。玩家可以看到这些小东西在游戏中的流动。比如，机械爪抓起一个铁板，放入目标容器中，玩家可以在场景上看到这个过程；工厂外的空地上也能看到铁板的增减。

我们一开始用构建新的对象，挂接到对应的挂接点上的方法来实现。一旦不需要这些小元件后，再将其删除。

一开始并没有太大问题。但当场景上这些小元件数以千计时，构建删除对象变成了性能热点。毕竟，设计之初，我们认为对象的创建和删除不应该是频繁的操作，并没有为之做什么优化。固然、我们可以优化对象的构建删除过程。但这些小元件本身还可能是由多个底层对象组合而成的，构建全新的对象怎么说都是个重量级的操作。

就我们这个游戏来说，场景中动则数以百计这些小元件。我觉得更好的方法是同一种东西（比如一个齿轮）只创建一个实例，而这个实例可以挂接到多个挂接点上。

我第一时间想到的是过去用过的有向无环图的方式，但内心是拒绝的。继而，我想到了最近实现的分组功能。目前实现的分组，对同一组对象打上 Tag 是一个相当廉价的操作，时间复杂度只和需要打 Tag 的元素个数有关。如果，我们让齿轮、铁板这些小元件独立创建出来，不放在场景中，而是单独分配一个分组 id ；那么找出同一个 group id 的成本也只和同一 id 的对象个数有关。大多数情况下，这个个数是 1 。该操作也是 O(1) 的。

剩下的工作只是增加一种虚拟节点的场景对象类型。它除了有场景对象该有的场景组件外，只有一个 group id 的引用。当需要渲染这个虚拟节点时，只需要根据 group id 找到对应分组的所有对象（通常只有一个对象），这些对象的世界矩阵是创建时一次计算好的，可以视为被摊平的对象集合，把这个集合中所有对象乘上虚拟节点的世界矩阵，就可以在正确的位置渲染。

总结：游戏世界是由多棵树构成的森林。只有其中一棵树是当前场景待渲染的。这个渲染树上可以有若干虚拟叶节点，它引用了森林中的其它树。对于非渲染树，每棵树上的所有节点被归于同一个分组。这些节点按分组平坦的放在同一个集合中。