Original link: https://blog.codingnow.com/2022/06/ecs_group.html
Currently, we use ECS to manage objects in the game engine. When the game scene is large enough, there needs to be a mechanism to quickly filter out the subset of objects that need to be rendered. In other words, if you create 100K entities, but only 1K entities need to be rendered at the same time, although the minimum cost of traversing all renderable objects is O(n), but this n is of the order of 100K or 1K, the difference Still big.
Our ECS system already supports the tag feature, which can use visible tag as the main key to quickly filter visible objects. But when the camera moves, needing to reset these tags may have performance issues. How can resetting these visible tags avoid working at O(n) complexity on the order of 100K?
An easy-to-think solution is to group Entity. For example, in a very large-scale scenario, we can group by blocks. According to the position of the lens, you can quickly determine which groups are concerned and which ones are not.
My first thought was to use multiple worlds to describe the whole scene. Each world is a group that stores Entity by geographic location. But this has obvious problems: some aspects of rendering are unique, such as the generation of Z Buffer in the PreZ stage and the processing of screen space effects in the post-processing stage, which require multiple groups to be processed together.
So, I still tend to add a group id to Entity to distinguish them.
If ECS is regarded as an in-memory database, then our requirement is the query function of where clause. You can quickly filter out the Entity whose group id belongs to a certain collection. The cost of filtering all entities that meet the requirements should be orders of magnitude of such entities, not orders of magnitude of all entities in the world.
Only in this way is it suitable for large-scale scenes, and expanding the scale of the number of scene objects does not affect the rendering performance.
I would like such a grouping function to be non-intrusive relative to the existing ECS features, preferably without modifying existing data structures. When the grouping function is not used (small scene), do not affect the basic function. Based on this, I designed such a data structure:
Each Entity can optionally have one (or more) group index structures. The group id can only be assigned when the Entity is created and cannot be modified. We maintain this index structure by group id during the build process.
The index structure has four fields:
uint64_t uid; uint64_t lastid; uint32_t groupid; uint32_t next;
Among them, uid is a 64-bit self-incrementing id, and each entity is given a unique id when it is created; groupid is the group number to which it belongs; lastid is used to index the uid of the previous object in the same group, and next is used to quickly locate the previous same group object.
This index structure is an ordinary component, which is actually stored in a contiguous array. Because Entity can only be given a unique uid at the moment of creation, and uid is monotonically increasing. Therefore, the uid field of the contents of this index structure is strictly sequentially increasing.
In this index structure, depending on uid / lastid, it can be naturally divided into several groups according to groupid. The next field describes the relative offset of the previous object of the same group in this index structure array.
When Entity is not deleted, next forms a linked list, which can quickly traverse all objects in the same group, and lastid can be used for double verification.
Once the Entity is deleted, we don’t have to update the linked list immediately. On the next traversal, next will point to the wrong location, but with lastid you can quickly fix the linked list (because the location of the correct group of objects is nearby).
Using this index structure, we can quickly traverse the Entity of the same group and tag it. After that, you can use the tag to retrieve it normally. For the big world scene, we divide the group according to the map block, and then use the location of the camera to quickly calculate which groups need to be rendered nearby, and then we can quickly generate visible tags.
In addition to maintaining visible tags, this grouping feature can also be used to quickly delete entities that don’t have to be kept in memory. Just delete and select them according to groupid and delete them in batches.
The above work is reflected in this commit .
This article is reprinted from: https://blog.codingnow.com/2022/06/ecs_group.html
This site is for inclusion only, and the copyright belongs to the original author.