Original link: https://blog.codingnow.com/2022/07/group_mount.html
Some time ago we added object grouping to the engine . The motivation for this feature is to have a mechanism to quickly filter out the set of code to process when the number of objects in the entire game world far exceeds the number of objects that need to be processed (displayed) at the same time.
In the process of using it, I found other uses for this feature one after another.
In a game project in the past, there was such a requirement: the game needs to generate an avatar for the player, and this avatar is composed of many parts. There are player portraits, names, levels, icons for cosmetic purposes, and more. This avatar may be displayed in many places on the screen at the same time.
If the scene is a simple tree structure, then every place where an avatar appears is a subtree that makes up the avatar element. In this way, multiple identical subtrees may appear in the scene. Although we can construct this subtree with a common interface, once the player’s attributes change, we need to modify the same subtree that appears in all scenes. This requires maintaining an additional list for each player, referencing where all the avatars appear in the scene tree. This undoubtedly increases the complexity of the data structure.
A natural thought is that the scene is no longer a tree, but a directed acyclic graph. Player avatars can appear in multiple places in the scene, but there is only one subtree. The root node of this subtree can have multiple parents. In this way, when we need to modify, we only need to change one place.
In Ejoy2D, I implemented this mechanism. But it always feels a little awkward, because the underlying data structure has become complicated.
Currently we are developing a game with a new engine and encountered the same problem. We’re working on a game like Factory Alien with lots of little details. Small components are hooked up to many scene elements (factories, robotic grippers, transport drones, etc.). Players can see these little things flowing through the game. For example, the mechanical claw grabs an iron plate and puts it into the target container. Players can see this process on the scene; the increase or decrease of the iron plate can also be seen in the open space outside the factory.
We started by constructing a new object and hooking it to the corresponding hook point. Remove these widgets once they are no longer needed.
It wasn’t much of a problem at first. But when there are thousands of these widgets on the scene, building delete objects becomes a performance hotspot. After all, at the beginning of the design, we thought that the creation and deletion of objects should not be frequent operations, and there was no optimization for them. Of course, we can optimize the construction and deletion process of objects. But these small components themselves may also be composed of multiple underlying objects, and constructing new objects is a heavyweight operation.
In our game, there are hundreds of these little elements that move in the scene. I think a better approach is to create only one instance of the same thing (such as a gear), and this instance can be hooked to multiple hook points.
The first thing that came to my mind was the directed acyclic graph method that I used in the past, but I rejected it in my heart. Then, I thought of the grouping function that I recently implemented. The currently implemented grouping, tagging the same group of objects is a fairly cheap operation, and the time complexity is only related to the number of elements that need to be tagged. If we create small components such as gears and iron plates independently, instead of placing them in the scene, but assigning a group id separately; then the cost of finding the same group id is only related to the number of objects with the same id. In most cases, this number is 1. This operation is also O(1).
All that remains is to add a virtual node to the scene object type. In addition to the scene component that the scene object should have, it only has a reference to the group id. When you need to render this virtual node, you only need to find all the objects in the corresponding group (usually only one object) according to the group id. The world matrix of these objects is calculated once when they are created, and can be regarded as a flattened set of objects. All objects in this set are multiplied by the virtual node’s world matrix to render in the correct position.
Summary: The game world is a forest of trees. Only one of the trees is to be rendered for the current scene. This render tree can have several virtual leaf nodes that reference other trees in the forest. For non-render trees, all nodes on each tree are grouped together. These nodes are grouped flatly in the same set.
This article is reprinted from: https://blog.codingnow.com/2022/07/group_mount.html
This site is for inclusion only, and the copyright belongs to the original author.