Managing game object hierarchy in an entity component system

I thought I’d do a post on this, since there is little concrete information on the web about how to implement parent-child relationships in an ECS. I’ve been struggling with this for a while, and have finally developed something that appears reasonable (at least for the scenarios I think need to accomplish).

This will be a boring post with no pictures.

Ideally you want to be able to express several kinds of hierarchies (visual, inventory, teams, etc…). I’m mainly going to focus on visual hierarchy for this article, however. It’s the most complex and prevalent.

Some notes about transform hierarchy:

• When I change the values in the parent’s transform, those need to result in the child’s final transform getting updated
• We don’t ever want to get out-of-sync (e.g. draw a child in the wrong position)
• Items at the root don’t need a local transform
• I’d like to minimize memory usage (i.e. not store transforms if I don’t have to)

The first thing that is clear is that we have a distinction between local transform and what I’ll call final transform (the one we use for rendering). The value for final transform is equal to (local transform) * (parent’s final transform).

Do local and final transform belong together on a single component? That would make sense if all visual entities require both kinds of transforms. But entities at the root (which is most entities) don’t need a local transform – what would it be local to? I suppose we could have an identity matrix as the parent transform for entities without visual parents. This was an appealing idea at first because it implied a level of consistency between all entities. The obvious downside is that we are now storing a bunch of unneeded extra information for top level entities (which, again, is probably most entities).

Having top level entities without a local transform felt a little “dirty” to me, like a kind of code smell. I think this was because I was thinking that outside code then needs to be smart about whether it pushes values into local or final transforms. Any changes made to final transform will just be overwritten when the final transform is calculated from the local transform. So it would need to manipulate local transform instead – unless it was a top level entity without a local transform.

But more thinking and reading led me to believe that this isn’t a problem. “Outside code” is kind of a generic catch-all term. But what code is it that sets position, orientation, scale, etc? There’s the physics code – but as far as I can think, in my case it should always be operating on top level elements (and the “final transform”). Same for code that might be responsible for spawning items in the world. If my game allows equipping weapons or items (and needs to visually attach them to a player model) then that code would automatically be aware that it is attaching stuff to an existing entity. Thus it would know to use local transform. In short, I’m hard-pressed to come up with a scenario where code would have to make a choice between local or final transform.

The one exception is the editor – I want to be able to manipulate top level and child entities in the same manner. In this case, I manipulate to the final transform, and then look for a local transform and use the inverse of the parent’s final transform to update the local transform.

In any case, it now seemed fine to separate transform into Transform and LocalTransform.

Dirty state and updates

Ideally, I’d like not to have to update the final transforms every frame. Updating the transforms involves following the parent hierarchy up, which does not access memory in a cache-friendly manner.  This means I need to implement some kind of dirty state.

• if the LocalTransform is dirty, the Transform also needs to be dirtied
• if the Transform is dirtied, all child Transforms are also dirty

So we basically have a two stage “dirty bit propagation” requirement. Breaking it down like this makes it fairly straightforward to implement with a pair of systems. First, a system iterates through all LocalTransforms. If it finds one that is dirty, it looks for a Transform component on the same entity as the LocalTransform. It then marks this Transform as dirty.

Next, a second system iterates through all Transforms. If it finds a dirty one, it then looks for a TransformChildren component on that same entity. TransformChildren contains a list of entity ids for entities who have LocalTransforms that specify the current entity as the parent. It looks up Transform components on those entities and sets their dirty bit. It then needs to continue this recursively down the visual hierarchy. If my Transforms were sorted in visual hierarchy (i.e. like a binary tree), I could avoid the recursive propagation.

Finally, there is a system that resolves dirty transforms. This is where the logic lies that computes the values in Transform from the values in LocalTransform and the parent’s Transform.

All of these systems are fairly straightforward and not much code.

Update order

The systems described above run in the order they are described. Of course, it is possible that some system that runs shortly after will then modify a Transform somewhere that causes other child transforms not to be up-to-date. Subsequent systems may then consume these incorrect Transforms. This could also happen with a system that runs before. I don’t think that’s really avoidable though, unless I always keep all transforms up-to-date immediately (which would be a performance problem and would cause code dependencies that I’d rather not have).

TransformChildren

I kind of hastily introduced the TransformChildren component above. For every LocalTransform on an entity, the parent entity needs to have a TransformChildren that has the child entity in its child list. Any changes to one need to be reflected in the other, so you need to be careful about who modifies these components, and ensure both are updated in some atomic fashion. Similarly, for inventory, I have Inventory (on the parent) and InventoryParent (on the child – this specifies the parent to whom’s inventory it belongs).

Ideally I wouldn’t even need TransformChildren (or Inventory). This is essentially duplicated state. The needed information is contain wholly in the child entities’ components. But getting whe needed is not convenient. In fact, the only place TransformChildren is really needed is in the system that propagates dirty transforms. If I didn’t need this dirty state propagation, I could probably do without TransformChildren. So that’s something I might look into.

This is all still fairly theoretical at the moment, I need more game scenarios implemented to see how things fall out.