2 Comments

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.

Advertisements

2 comments on “Managing game object hierarchy in an entity component system

  1. Sounds promising. I’m keen to hear how it goes “in the field”, and if any of your assumptions didn’t work out.

    • One follow up I have is that I’ve been able to get rid of TransformChildren, so I just have LocalTransform which exists on the child. This avoids duplicated state that risked getting out of sync. I still do calculate something very similar to what existed in TransformChildren though (since it is necessary for efficiently propagating dirty state down the hierarchy). The difference is that this data no longers exists in a component, but only within the system that needs it. And only that system is responsible for calculating it, so there’s no risk it gets out of sync.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Space Quest Historian

Let's Play's, Podcasts, and General Adventure Game Goodness

Harebrained Schemes

Developer's blog for IceFall Games

kosmonaut games

Development blog of "Bounty Road"

Halogenica

Turn up the rez!

bitsquid: development blog

Developer's blog for IceFall Games

Game Development by Sean

Developer's blog for IceFall Games

Lost Garden

Developer's blog for IceFall Games

Memories

Developer's blog for IceFall Games

Casey's Blog

Developer's blog for IceFall Games

Blog

Developer's blog for IceFall Games

Rendering Evolution

Developer's blog for IceFall Games

Simon schreibt.

Developer's blog for IceFall Games

Dev & Techno-phage

Do Computers Dream of Electric Developper?

- Woolfe -

Developer's blog for IceFall Games

Ferrara Fabio

Game & Application Developer, 3D Animator, Composer.

Clone of Duty: Stonehenge

First Person Shooter coming soon to the XBOX 360

Low Tide Productions

Games and other artsy stuff...

BadCorporateLogo

Just another WordPress.com site

Sipty's Writing

Take a look inside the mind of a game developer.

Jonas Kyratzes

Writer, game designer, filmmaker.

%d bloggers like this: