In the previous post, I mentioned that the Untold Engine lacks a way to propagate transformations (position, rotation, scales) from a parent entity to a child entity.
You can see this problem in the video in the previous post; The car moves but the wheels do not rotate. Moreover, the steering sucks.
What I need to do is implement a Scene Graph into the engine. Doing so, allows me to set the F1 car body as the parent node and the wheels as children nodes. The goal is to implement a Scene Graph so that the steering looks like shown below.
The problem is:
How do you implement a Scene Graph in an ECS architecture?
What is a Scene graph
It is a hierarchical data structure that helps manage spatial relationships between objects in a scene. In game engines, they are used to manage hierarchical transformations, where a parent's transformation (position, rotation, scale) affects its children.
One key feature of a scene graph is that objects are arranged in a tree-like structure, where transformations propagate from parent to child. For example, if a robot's arm rotates, its hand and attached tools rotate.
OOP vs ECS differences
In object-oriented programming, implementing a scene graph is straightforward because objects can reference their parents and children. It allows for simple, recursive traversal and updates of hierarchical transformations.
In contrast, in ECS, entities are represented by IDs (like uint64), which are simple numeric values with no built-in structure or relationships. This raises the question, how do you propagate transformations in a hierarchy when all you have are IDs?
I searched for answers online and could not find anything helpful. So, I devised a crazy idea: Traversing the scene graph by levels.
Traversing the scene graph by levels in ECS
A scene graph is a tree with different levels, correct?
- The root node is at level 0
- Children are at level 1
- Grandchildren are at level 2, and so on.
I thought, "What if I could use these levels to simplify traversal?"
For example:
- First, fetch all entities at level 0 and update their transforms.
- Then, fetch all entities at level 1 and update their transforms, applying the transformations of their parents.
- Continue this process for level 2, level 3, and so on.
So, I introduced a component in my engine that tracks entities' parent IDs and their current level in the hierarchy:
struct HierarchyComponent{
var parent: EntityID
var level: Int
}
Whenever a child is assigned a parent, the system calculates and assigns the child's level as the parent's level + 1.
For example, a car entity, wheel entity, and a rim entity start at level 0. If the wheel is attached to the car, the wheel's level is updated to 1. If the rim is linked to the wheel, the rim's level becomes 2.
Traversing and propagating hierarchy transformation works as follows:
- First, process the car (level 0) and calculate its world transform.
- Then, process the wheel (level 1) and combine its local transform with the car's world transform.
- Finally, process the rim (level 2) and combine its local transform with the wheel's transform.
This approach ensures that parent transforms are always processed before their children, eliminating the need for recursive traversal.
Results
To get this working, I needed to modify the F1 model in Blender. I ended up breaking it up into F1 car body, steering, wheels as shown below.
Once the meshes were broken up, I was able to set up hierarchies between meshes using the new Scene Graph. Once I hit play, the steering looked a lot better.
Implementing this idea was simple and I didn't have to deal with recursive functions. I'm sure there are flaws but out of the other crazy ideas I came up with to solve this problem, this one was the cleanest and the easiest to implement.
Let me know what you think? How would you implement it?
