« 给 ECS 增加分组功能 | 返回首页 | ECS 系统中 Entity 的生命期管理 »

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

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

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

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

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

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

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

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

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

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

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

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

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


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

Comments

网上2012年左右有一篇文章《程序员的十层楼》,我感觉,我已经看到天空了,肯能是我还没有进楼的外行吧。

哈哈,我闪了,你心里有数就行了。

请不要发和帖子内容无关的留言。如果想私下讨论问题,可以发 email ;如果想公开讨论问题,可以发贴到自己的 blog 或其他公开技术论坛。例如可以自己创建一个 github 账号,提交自己想表达的东西。

我说明一下呀,12代I5大约10M的L2高速缓冲区,但是他可有8个核心,16个线程,基本上一个核心的L2就是1M

10000个表项,存放10000帧的优化的BMP,那么,大约相当于5分钟的高清视频。

最牛掰的,这个解码器,这是脚本,这是可读的,可随时调试的,这不是封装成so或者dll的二进制程序。

理论上,现在I5,CPU的L2高速缓冲大约是1M字节(寄存器虚拟机的API主要是操控和运行在这个上面),也就是大约100万个字符(ASCII),大约相当于2万行Lua程序,10000个关系表项。

我的此贴第一回复,就这么简单的一句话,这句话,恕我直言,全世界能真正理解的程序员,应该不超过3000,你没看错,是全世界。

好像看懂了,一般这种小东西大部分都是用事件分发或者单独的列表管理,但是云风的问题在于创建和删除的性能开销,所以是做了对一个对象反复的渲染,然后多个渲染对应一个object,但确实是有点反直觉。

云风,我觉得你这么熟悉Lua,那么利用这个语言编写一个视频加速解码器,这倒是实实在在的,使用双层的关系表,第一层表代表一个视频的整个帧的序列,比如30秒的小视频,存放900张BMP图到整个表的KEY中,也就是有900个表项KEY,然后,表的值存放一个子表,这个表存的是一个优化后的BMP图的数组。
理论上,根据Lua在游戏引擎C++中的表现,流畅播放1080P的电影,毫无压力。

这样不行云风,要使用迭代器和函数重载,把各种装备和各式各样的人身上的装备,换装以后,生成一个角色对象。

Post a comment

非这个主题相关的留言请到:留言本