GameArchitect

A frustrating feature of previous game engines we’d used was that they tended to overload hierarchy to mean multiple things.

The engine that we used at Cyan, for example, was a pure scene graph.  Every part of the game was represented by one or more nodes in a hierarchy.  But the hierarchy represented logical relationships in some places and kinematic relationships in others.  Throughout the graph, ownership was conflated with update order:  children would be deleted when their parents were deleted and parents always updated before their children.  Kinematic attachment was performed by pruning and grafting trees in the graph, which had the effect of tying the lifetimes of attached objects to the lifetimes of their parents.

The engine used for MechAssault 2 was similar, except that it had separate game object and scene hierarchies.  In both hierarchies, graph relationships defined ownership and update order:  children would be deleted when their parents were deleted and parents were always updated before their children.  In the game object graph, hierarchy also defined logical relationships that varied based on the objects involved.  Triggers, for example, would treat certain of their child objects as inputs to be checked and others as objects to be acted on.  In principle, the entire game object hierarchy updated, then the entire scene hierarchy updated.  In practice, we needed to know the final animated positions of some objects so that we knew where to create effects, so some trees in the scene hierarchy got explicitly updated during the game object update.

All of this was very confusing.  It also meant that changes to the hierarchy motivated by one concern tended to have unforeseen side-effects in other areas.  And it necessitated odd hacks like the MechAssault’s explicit updating of sub-trees in the scene graph. In developing Despair, therefore, we decided to have one data-structure per purpose.  As mentioned previously, we have a well-defined ownership hierarchy among our objects.  For example,

• The streaming manager owns worlds
• Worlds own game objects
• Game objects own game components
• Game components own scene objects (and audio resources, and HUD elements, etc…)
• Scene objects own mesh nodes (and transform nodes, and light nodes, etc…)
• Mesh nodes own vertex groups and index lists

In some cases ownership is shared and in some cases it isn’t, but each object has its level of the hierarchy.  But in addition to the hierarchy that we use for ownership, we also have parallel data structures for

• the object registry used for object look-up
• the dependency graph used for object update
• the physical representation of the world (stored in Havok’s internal hierarchy)
• the renderable representation of the world (stored in our own sphere tree of renderable objects)
• etc.

This has been a big win in terms of clarity and flexibility.  It’s clear when looking at a component what its lifetime will be.  It’s easy to make a component update later in the frame, or not update at all, without having to worry that your change will affect when the object is deleted or whether it’s rendered.  Scene objects and game components are part of the same dependency hierarchy.  Therefore, the component that creates a fire effect can make itself dependent on the scene object for the player’s weapon.  That way the fire effect won’t be created until the weapon has determined its final position for the frame, and the fire effect will be created at the correct location.

The performance implications of orthogonal views are unclear.  One of the frustrations of building a game engine is that you never have the leisure of changing one architectural variable while keeping all others constant.  That means that you can never be sure you’ve made the best decision.  You can only be sure–sometimes–when you’ve made a very bad one.Having orthogonal views of our data was clearly not a decision worthy of regret.  But it’s difficult to be certain whether it’s a net win in terms of performance.  On the negative side, all these different hierarchies are scattered at widely different locations in memory, and on modern hardware memory locality drives performance more than the number of instructions executed does.  But on the other hand, having independent views of the data means that each only needs to process what matters.  Our update pass only updates objects that are actually changing.  Our render pass doesn’t waste any overhead on objects that aren’t renderable.  And when those systems operate, they perform similar operations on sorted lists of similar objects, which is the sort of thing that modern hardware has gotten very good at.  So I think this idiom is a performance win, but the only hard data I have to back that up is that we’re spending less time waiting on cache misses than we were in MechAssault 2.  Given the other differences between Despair and the MechAssault 2 engine and between the Xbox 360 and the original Xbox, that evidence is suggestive but not conclusive.

The one area in which orthogonal views have a clear cost is memory.  As objects add themselves to all our different systems, they may have representations in the registry, in the dependency graph, the scene hierarchy, the physics hierarchy, the render hierarchy, and probably one or two other systems that I’m forgetting.  I’d estimate that this overhead adds up to somewhere between two and three megabytes for a typical level in Fracture.  On a console with 512 megabytes of memory that cost seems justifiable, but it would have been less practical on an Xbox or PlayStation 2 game.