« 用邻接表实现无向图 | 返回首页 | 分组功能在挂接系统上的使用 »

给 ECS 增加分组功能

目前，我们用 ECS 管理游戏引擎中的对象。当游戏场景大到一定程度，就需要有一个机制来快速筛选出需要渲染的对象子集。换句话说，如果你创建了 100K 个 Entity ，但是只有 1K 个 Entity 需要同时渲染，虽然遍历所有可渲染对象的成本最小是 O(n) ，但这个 n 是 100K 这个数量级，还是 1K 这个数量级，区别还是很大的。

我们的 ECS 系统已经支持了 tag 这个特性，可以利用 visible tag 做主 key 快速筛选可见对象。但当镜头移动时，需要重置这些 tag 又可能有性能问题。重置这些 visible tags 怎样才能避免在 100K 这个数量级的 O(n) 复杂度下工作？

一个容易想到的方案是给 Entity 分组。比如在超大规模的场景下，我们可以按区块来分组。根据镜头所在的位置，可以快速的确定哪些 group 是关心的，哪些不必关心。

我首先想到的是用多个 world 来描述整个场景。每个 world 是一个 group ，按地理位置存放 Entity 。但这有明显的问题：渲染的有些环节是唯一的，比如 PreZ 阶段生成 Z Buffer 、后处理阶段处理屏幕空间的效果，这些需要多个分组一起处理。

所以，我还是倾向于给 Entity 加一个 group id 来区分它们。

如果把 ECS 看成是一个内存数据库，那么，我们的需求是 where 字句的查询功能。可以快速的筛选出 group id 属于某个集合的 Entity 。筛选合乎要求的所有 Entity 的成本应该是这类 Entity 的数量级，而不是 world 中所有 Entity 的数量级。

只有这样，才适合做大规模的场景，扩大场景对象数量的规模不影响渲染性能。

我希望这样一个分组功能相对已有的 ECS 特性是非侵入的，它最好不要修改已有的数据结构。在不使用分组功能时（小场景），不要影响基本功能。基于此，我设计了这样一个数据结构：

每个 Entity 可选一个（或多个） group 索引结构。group id 只能在创建 Entity 时赋予，并不可修改。我们在构建过程通过 group id 来维护这个索引结构。

该索引结构有四个字段：

uint64_t uid;
uint64_t lastid;
uint32_t groupid;
uint32_t next;

其中，uid 是 64bit 自增 id ，每个 entity 在创建时被赋予唯一 id ；groupid 是它所属的分组号；lastid 用于索引同组的前一个对象的 uid ，next 则用于快速定位前一个同组对象。

这个索引结构就是一个普通的 component ，实际存放在一个连续的数组中。因为 Entity 只能在创建那一刻赋予唯一 uid ，而 uid 又是单调递增的。所以，这个索引结构的内容的 uid 字段是严格有序递增的。

在这个索引结构中，依靠 uid / lastid 便可以按 groupid 自然分成若干组。而 next 字段描述的是同组的前一个对象在这个索引结构数组中的相对偏移量。

当 Entity 没有删除时，next 形成了链表，可以快速的遍历所有同组对象，而 lastid 可以用于双重校验。

一旦 Entity 删除，我们不必立刻更新这个链表。在下次遍历时，next 会指向错误的位置，但通过 lastid 可以快速修复链表（因为正确的同组对象所在的位置就在附近）。

利用这个索引结构，我们可以快速的遍历出同组的 Entity ，并打上 tag 。之后，就可以利用 tag 来正常检索了。对于大世界场景，我们按地图区块分好 group ，再利用镜头所在位置，快速计算出附近有哪几个 group 需要渲染，就可以快速生成 visible tags 。

除了用于维护 visible tags ，这个分组功能还可以用于快速删除不必保存在内存中的 Entity 。只要根据 groupid 删选出来再批量删除即可。

以上的工作在 这个 commit 中体现。

云风 提交于 June 14, 2022 09:58 AM |

Comments

应该按用途分组吧。如果是可视筛选，那就四叉树或八叉树。如果是基于场景的。比如开房间的游戏，那就按房间来分组吧。分组的目的是快速找到你要的数据。查找时间复杂度至少得是O(logN)。相同的entity应该根据需求有多种查找索引。

Posted by: m | (16) September 21, 2023 11:26 PM

现在计算机工业有一个有意思的变化，那就是当年冯诺依曼提出计算机模型的时候，存储并且能够运行程序的就是计算机，后来N怀特教授（pascal之父，瑞士苏黎世大学终身教授）提出，算法+数据结构这就是程序。 我们今天PC计算机，都是基于冯诺依曼结构的，从微控器到磁盘、光驱、SSD、SPI设备、内存，闪存。 但是，这两年，intel傲腾存储器的出现，SSD大量的应用，机械盘有退出历史舞台的趋势，就像当年的光碟驱动器一样，实际上磁盘（硬盘和光驱）这些技术源自当年IBM研究的磁带机（用于数据备份）。 按照现在的趋势，将来计算机就是简单的CPU+SSD了，没有内存的概念了。 这一点云风需要关注和思考一下，这是硬件结构的革命性变化。

Posted by: rawa459 | (15) July 6, 2022 01:26 PM

为啥不用八叉树空间管理呢.

Posted by: alex | (14) July 1, 2022 03:54 PM

ECS这是三个单词,这大家都知道吧,这是一个资源(实体),角色(人物周边和数值),系统(游戏的逻辑构架)三者分离的设计模型,系统主要是程序员来完成,资源主要是场景策划和建模师,原画师来搞,而角色周边,这个负责的就是大名鼎鼎的数值策划(区别于场景策划).

Posted by: rawa459 | (13) June 29, 2022 09:49 PM

各位大神，问下这种ecs模式在传统的mmo服务端能用上吗？感觉格格不入啊，component变化怎么推送呢？aoi怎么做？

Posted by: phz | (12) June 29, 2022 10:11 AM

楼下说到了数据库，哈哈。 我在2001年有幸参与了第一个跟银行有关的项目，采用的是IBM的DB2之7.1版本，当年有人争论，几种商业版的数据库，那一种是最好的，当时MySQL还是个小玩意，还不Access，那么这个数据库能做到什么呢？说白了，跟现在谷歌的搜索引擎的速度一样，10秒钟内，在几十亿行的表格中找到你需要的各种结果集组合。 现在的问题不是软件是否优秀的问题，是成本问题。 IBM的DB2，一套接近200万美金（包含部分硬件设备）。 那么现在mySQL需要多少钱呢？（性能接近的情况下），只需要2000美元。

Posted by: rawa459 | (11) June 26, 2022 05:20 AM

我在2001年有幸参与了第一个跟银行有关的项目，采用的是IBM的DB2之7.1版本，当年有人争论，几种商业版的数据库，那一种是最好的，当时MySQL还是个小玩意，还不Access，那么这个数据库能做到什么呢？说白了，跟现在谷歌的搜索引擎的速度一样，10秒钟内，在几十亿行的表格中找到你需要的各种结果集组合。 现在的问题不是软件是否优秀的问题，是成本问题。 IBM的DB2，一套接近200万美金（包含部分硬件设备）。

Posted by: rawa459 | (10) June 26, 2022 05:15 AM

感觉这马上就要变成内存数据库了，SQLite memory模式请求出战……

Posted by: Julius | (9) June 24, 2022 01:58 PM

楼下那个人，这都好几天了，也不见你的高论，这要是面对面，这得有多丢人现眼？？是不是很难受？要怪就怪你学艺不精。

Posted by: rawa459 | (8) June 21, 2022 05:15 AM

visible tag ，决定这个标签的，你是不是认为是距离，越远的就不会打上tag，但是如果你面前是一面玻璃和一面反光的墙的时候，这个tag是不是打上，是距离决定不？ 你不是说我胡扯吗？来你来走两步，算了，你这种人，网上上千万人，我知道你也不会回复，会灰溜溜的多起来，看着挺牛逼的，上来就是跟大牛和博士一样，你这个错了，你这个胡扯，自己啥也不说，多有面子，我告诉你，面子不是这样来的，面子是真才实学赢来的，算了，这几天心情不太好，多说两句。

Posted by: rawa459 | (7) June 16, 2022 04:56 AM

是不是害怕说错了，然后彻底暴露你的无知？怕丢人现眼对不？你这种人我见得多了，你不是说胡扯吗？来你来走两步？怎么啥地方都遇到这种人，上来就喷，然后毫无理由，毫无依据，来你来讲讲？？我看看你JJ，别逼我说粗，你个SB

Posted by: rawa459 | (6) June 16, 2022 04:42 AM

哈哈，来你说说哪个地方胡扯了？真是有意思，怎么网上尽是你这种人，来说我胡扯，你来给讲讲？你说别人胡扯，那想必你必有高论，自己又不说？那你这个依据哪里来的？

Posted by: rawa459 | (5) June 16, 2022 04:38 AM

楼下尽是胡扯，适当控制下寄几

Posted by: lichking | (4) June 15, 2022 06:46 PM

并且现在诸如《消失的光芒2》《GAT5》《艾尔登的法环》，这种游戏如果做成MMO，每个玩家有自己的显卡来渲染场景，这个渲染速度和质量，这个不仅仅是放入内存的问题，还要告诉显卡如何去最快最优秀的把玩家应该看到的视频流推出来，给显卡显示。

Posted by: rawa459 | (3) June 15, 2022 05:33 PM

现在唯一能跟U3D抗衡的就是UE5，这就像当年的Clang和C++之争，两者各有所长，都是全世界顶尖的开发环境。

Posted by: rawa459 | (2) June 15, 2022 01:08 PM

场景大，不一定代表（物体或者实体）Entity就一定多，在U3D（Unity 3D）中是使用视界（horizon）来解决你说的这个问题的，horizon之外的东西，使用简单的贴图处理，无论什么Entity，如果在视界之外，都不会得到渲染或者实例化，都是BMP图的一部分而已。 实际上诸如反恐精英（CS）和早期的虚幻2（UE2），视界是非常狭小的，后来出现的方舟（方舟生存进化）和吃鸡（大逃杀）视界才比较广阔一些。 现在U3D可以使用脚本来控制游戏运行中的视界大小，这不就是跟你这个技术有异曲同工之妙吗？

Posted by: rawa459 | (1) June 15, 2022 09:03 AM

Post a comment

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