An Anatomy of Despair: Aggregation Over Inheritance
June 1st, 2008One of the first decisions that Adrian and I made in our initial work on Despair was to prefer aggregation to inheritance whenever possible. This is not an original idea. If you Google for “aggregation inheritance” or “composition inheritance,” you’ll get a million hits. The C++ development community has been renouncing its irrational exuberance over inheritance for the last few years now. Sutter and Alexandrescu even include “prefer composition to inheritance” as a guideline in C++ Coding Standards.
Nonetheless, every game engine we’d worked on before Despair had a similar deep inheritance hierarchy of the sort that was in vogue in the mid-nineties: a player class might inherit from some kind of combatant class, which would inherit from a mover class, which would inherit from a physical object class, which would inherit from a base game object class.
This architecture has a lot of shortcomings. Let me enumerate a few of them:
First, it’s inflexible. If you want to create a new AI enemy that has some of the capabilities of enemy A and some of the capabilities of enemy B, that’s not a task that fits naturally into a hierarchical object classification. Ideally, you’d like the designers to be able to create a new enemy type without involving you, the programmer, at all. But with a deep object hierarchy, you have to get involved and you have to try to pick the best implementation from several bad options: to have your new enemy class inherit from one object and cut-and-paste the functions you need from the other; to not inherit from either, and to cut-and-paste the functions you need from both; or to tiptoe down the treacherous slippery slope of multiple inheritance and hope that it doesn’t lead to a diamond of death.
Second, a handful of classes in your hierarchy tend to grow without bound over a game’s development. If the player class is part of the object hierarchy, then you can expect this class to include input and control systems, custom animation controls, pickup and inventory systems, targeting assistance, network synchronization–plus any special systems required by the particular game that you’re making. One previous game that we worked on features a 13,000 line player class implementation, and the player class inherited from a 12,000 physical object class. It’s hard to find anything in files that size, and they’re frequent spots for merge conflicts since everyone’s trying to add new stuff to them all the time.
Third, deep inheritance is poor physical structure. If class A inherits from class B which inherits from class C, then the header file for A–A.h–has to #include B.h and C.h. As your hierarchy gets deeper, you’ll find that all of your leaf classes have to include four or five extra headers for their base classes at different levels. For most modern games, as much compile time is spent opening and reading header files as is spent actually compiling code. The more loosely your code is coupled, the faster you can compile. (See Lakos for more details.)
Therefore we resolved to make Despair as component-based as we could, and to keep our inheritance hierarchies as flat as possible. A game object in Despair, for example, is basically a thin wrapper around a UID and a standard vector of game components. Components can be queried for type information and dynamically cast. The game object provides only lifetime management and identifier scoping. It knows nothing about component implementations. It contains no traditional game object state like position, bounds, or visual representation.
This approach has informed other systems as well. Our scene object implementation is similar to the game object implementation, with a single object representing each model that provides lifetime management for a vector of scene nodes. Scene nodes manage their own hierarchies for render state or skeletal transforms.
Another family of systems is built on a flow-graph library for visual editing. Game logic, animation systems, and materials can all be built by non-programmers wiring together graph components in the appropriate tools.
Using composition instead of inheritance has worked very well for us. Our primary concern when we set out in this new direction was that we’d end up with something that had horrible runtime performance. With Fracture almost complete, though, there’s no evidence that our performance is worse than it would have been with a deep inheritance hierarchy. If anything, I’m inclined to suspect that it’s better, since well-encapsulated components have better cache locality than large objects and since the fact that we only update dirty components each frame means that we can decide what does and doesn’t need to be updated at a finer granularity.
If I were starting over again, the only change I’d make with respect to object composition is to make scene objects more opaque and less like game objects. Scene objects have a different problem to solve. We have several hundred game components now, with more going in all the time, and the flexibility of having a thin game object interface that allows querying components for type has paid big dividends. I think that our game object system is close to ideal for iterating rapidly on gameplay. Scene objects are a different kind of problem, though. We haven’t added any new scene node types since the scene library was written, and all scene nodes are implemented in the scene library instead of in higher-level code. At the same time, it would be nice to be able to experiment with different optimizations of updating skeletal hierarchies without breaking higher-level code. All of this argues that following the Law of Demeter and hiding scene object implementation details would have been appropriate for scene objects even if it wasn’t appropriate in the rapid-prototyping environment of game objects.
Beyond the perfect abstract world of software architecture, component based design also created a couple of surprises in the messier world of development process and human interaction. One lesson of working with a composition-based engine is that the learning curve for new programmers is steeper. For programmers who are used to being able to step through a few big nested functions and see the whole game, it can be disorienting to step through the game and discover that there’s just no there there. For example, Despair contains over 500 classes with the word “component” in their names and 100 classes with the word “object” in their names. Our games aren’t defined by C++ objects, they’re defined by relationships between them. To understand those relationships, you need good documentation and communication more than ever.
Another composition lesson is that component-based design takes a lot of the complexity that used to exist in code and pushes it into data. Designers aren’t used to designing objects and constructing inheritance hierarchies. Working with components requires new processes and good people. Cross-pollination is important. Your programmers need to work building objects in your tools, as well as writing code for components, and they need to work hand-in-hand with good technical designers who can provide tool feedback and build on the object primitives available to them. Like a game, your team isn’t defined by its individual components but by the relationships between them.
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.