Cowboy Programming Game Development and General Hacking by the Old West

January 5, 2007

Evolve Your Hierarchy

Filed under: Game Development,Inner Product — Mick West @ 11:35 am

Refactoring Game Entities with Components

Up until fairly recent years, game programmers have consistently used a deep class hierarchy to represent game entities. The tide is beginning to shift from this use of deep hierarchies to a variety of methods that compose a game entity object as an aggregation of components. This article explains what this means, and explores some of the benefits and practical considerations of such an approach. I will describe my personal experience in implementing this system on a large code base, including how to sell the idea to other programmers and management.

GAME ENTITIES

Different games have different requirements as to what is needed in a game entity, but in most games the concept of a game entity is quite similar. A game entity is some object that exists in the game world, usually the object is visible to the player, and usually it can move around.

Some example entities:

  • Missile
  • Car
  • Tank
  • Grenade
  • Gun
  • Hero
  • Pedestrian
  • Alien
  • Jetpack
  • Med-kit
  • Rock

Entities can usually do various things. Here are some of the things you might want the entities to do

  • Run a script
  • Move
  • React as a rigid body
  • Emit Particles
  • Play located audio
  • Be packed up by the player
  • Be worn by the player
  • Explode
  • React to magnets
  • Be targeted by the player
  • Follow a path
  • Animate

TRADITIONAL DEEP HIERARCHIES


The traditional way of representing a set of game entities like this is to perform an object-oriented decomposition of the set of entities we want to represent. This usually starts out with good intentions, but is frequently modified as the game development progresses – particularly if a game engine is re-used for a different game. We usually end up with something like figure 1, but with a far greater number of nodes in the class hierarchy.

As development progresses, we usually need to add various points of functionality to the entities. The objects must either encapsulate the functionality themselves, or be derived from an object that includes that functionality. Often, the functionality is added to the class hierarchy at some level near the root, such as the CEntity class. This has the benefit of the functionality being available to all derived classes, but has the downside of the associated overhead also being carried by those classes.

Even fairly simple objects such as rocks or grenades can end up with a large amount of additional functionality (and associated member variables, and possibly unnecessary execution of member functions). Often, the traditional game object hierarchy ends up creating the type of object known as “the blob”. The blob is a classic “anti-pattern” which manifests as a huge single class (or a specific branch of a class hierarchy) with a large amount of complex interwoven functionality.

While the blob anti-pattern often shows up near the root of the object hierarchy, it will also show up in leaf nodes. The most likely candidate for this is the class representing the player character. Since the game is usually programmed around a single character, then the object representing that character often has a very large amount of functionality. Frequently this is implemented as a large number of member functions in a class such as CPlayer.

The result of implementing functionality near the root of the hierarchy is an overburdening of the leaf objects with unneeded functionality. However, the opposite method of implementing the functionality in the leaf nodes can also have unfortunate consequence. Functionality now becomes compartmentalized, so that only the objects specifically programmed for that particular functionality can use it. Programmers often duplicate code to mirror functionality already implemented in a different object. Eventually messy re-factoring is required by re-structuring the class hierarchy to move and combine functionality.

Take for example the functionality of having an object react under physics as a rigid body. Not every object needs to be able to do this. As you can see in figure 1, we just have the CRock and the CGrenade classes derived from CRigid. What happens when we want to apply this functionality to the vehicles? You have to move the CRigid class further up the hierarchy, making it more and more like the root-heavy blob pattern we saw before, with all the functionality bunched in a narrow chain of classes from which most other entity classes are derived.

AN AGGREGATION OF COMPONENTS

The component approach, which is gaining more acceptance in current game development, is one of separating the functionality into individual components that are mostly independent of one another. The traditional object hierarchy is dispensed with, and an object is now created as an aggregation (a collection) of independent components.

Each object now only has the functionality that it needs. Any distinct new functionality is implemented by adding a component.

A system of forming an object from aggregating components can be implemented in one of three ways, which may be viewed as separate stages in moving from a blob object hierarchy to a composite object.

OBJECT AS ORGANIZED BLOB

A common way of re-factoring a blob object is to break out the functionality of that object into sub-objects, which are then referenced by the first object. Eventually the parent blob object can mostly be replaced by a series of pointers to other objects, and the blob object’s member functions become interface functions for the functions of those sub-objects.

This may actually be a reasonable solution if the amount of functionality in your game objects is reasonably small, or if time is limited. You can implement arbitrary object aggregation simply by allowing some of the sub-objects to be absent (by having a NULL pointer to them). Assuming there are not too many sub-objects, then this still allows you the advantage of having lightweight pseudo-composite objects without having to implement a framework for managing the components of that object.

The downside is that this is still essentially a blob. All the functionality is still encapsulated within one large object. It is unlikely you will fully factor the blob into purely sub-objects, so you will still be left with some significant overhead, which will weight down your lightweight objects. You still have the overhead of constantly checking all the NULL pointers to see if they need updating.

OBJECT AS COMPONENT CONTAINER

The next stage is to factor out each of the components (the “sub-objects” in the previous example) into objects that share a common base class, so we can store a list of components inside of an object.

This is an intermediate solution, as we still have the root “object” that represents the game entity. However, it may be a reasonable solution, or indeed the only practical solution, if a large part of the code base requires this notion of a game object as a concrete object.

Your game object then becomes an interface object that acts as a bridge between the legacy code in your game, and the new system of composite objects. As time permits, you will eventually remove the notion of game entity as being a monolithic object, and instead address the object more and more directly via its components. Eventually you may be able to transition to a pure aggregation.

OBJECT AS A PURE AGGREGATION

In this final arrangement, an object is simply the sum of its parts. Figure 2 shows a scheme where each game entity is comprised of a collection of components. There is no “game entity object” as such. Each column in the diagram represents a list of identical components, each row can be though of as representing an objects. The components themselves can be treated as being independent of the objects they make up.

PRACTICAL EXPERIENCE

I first implemented a system of object composition from components when working at Neversoft, on the Tony Hawk series of games. Our game object system had developed over the course of three successive games until we had a game object hierarchy that resembled the blob anti-pattern I described earlier. It suffered from all the same problems: the objects tended to be heavyweight. Objects had unnecessary data and functionality. Sometimes the unnecessary functionality slowed down the game. Functionality was sometimes duplicated in different branches of the tree.

I had heard about this new-fangled “component based objects” system on the sweng-gamedev mailing list, and decided it sounded like a very good idea. I set to re-organizing the code-base and two years later, it was done.

Why so long? Well, firstly we were churning out Tony Hawk games at the rate of one per year, so there was little time between games to devote to re-factoring. Secondly, I miscalculated the scale of the problem. A three-year old code-base contains a lot of code. A lot of that code became somewhat inflexible over the years. Since the code relied on the game objects being game objects, and very particular game objects at that, it proved to be a lot of work to make everything work as components.

EXPECT RESISTANCE

The first problem I encountered was in trying to explain the system to other programmers. If you are not particularly familiar with the idea of object composition and aggregation, then it can strike you as pointless, needlessly complex, and unnecessary extra work. Programmers who have worked with the traditional system of object hierarchies for many years become very used to working that way. They even become very good at working that way, and manage to work around the problems as they arise.

Selling the idea to management is also a difficult. You need to be able to explain in plain words exactly how this is going to help get the game done faster. Something along the lines of:

“Whenever we add new stuff to the game now, it takes a long time to do, and there are lots of bugs. If we do this new component object thing, it will let us add new stuff a lot quicker, and have fewer bugs.”

My approach was to introduce it in a stealth manner. I first discussed the idea with a couple of programmers individually, and eventually convinced them it was a good idea. I then implemented the basic framework for generic components, and implemented one small aspect of game object functionality as a component.

I then presented this to the rest of the programmers. There was some confusion and resistance, but since it was implemented and working there was not much argument.

SLOW PROGRESS

Once the framework was established, the conversion from static hierarchy to object composition happened slowly. It is thankless work, since you spend hours and days re-factoring code into something that seems functionally no different to the code it replaces. In addition, we were doing this while still implementing new features for the next iteration of the game.

At an early point, we hit the problem of re-factoring our largest class, the skater class. Since it contained a vast amount of functionality, it was almost impossible to re-factor a piece at a time. In addition, it could not really be re-factored until the other object systems in the game conformed to the component way of doing things. These in turn could not be cleanly refactored as components unless the skater was also a component.

The solution here was to create a “blob component.” This was a single huge component, which encapsulated much of the functionality of the skater class. A few other blob components were required in other places, and we eventually shoehorned the entire object system into a collection of components. Once this was in place, the blob components could gradually be refactored into more atomic components.

RESULTS

The first results of this re-factoring were barely tangible. But over time the code became cleaner and easier to maintain as functionality was encapsulated in discreet components. Programmers began to create new types of object in less time simply by combining a few components and adding a new one.

We created a system of data-driven object creation, so that entirely new types of object could be created by the designers. This proved invaluable in the speedy creation and configuration of new types of objects.

Eventually the programmers came (at different rates) to embrace the component system, and became very adept at adding new functionality via components. The common interface and the strict encapsulation led to a reduction in bugs, and code that that was easier to read, maintain and re-use.

IMPLEMENTATION DETAILS

Giving each component a common interface means deriving from a base class with virtual functions. This introduces some additional overhead. Do not let this turn you against the idea, as the additional overhead is small, compared to the savings due to simplification of objects.

Since each component has a common interface, it is very easy to add additional debug member functions to each component. That made it a relatively simple matter to add an object inspector that could dump the contents of the components of a composite object in a human readable manner. Later this would evolve into a sophisticated remote debugging tool that was always up to date with all possible types of game object. This is something that would have been very tiresome to implement and maintain with the traditional hierarchy.

Ideally, components should not know about each other. However, in a practical world, there are always going to be dependencies between specific components. Performance issues also dictate that components should be able to quickly access other components. Initially we had all component references going through the component manager, however when this started using up over 5% of our CPU time, we allowed the components to store pointers to one another, and call member functions in other components directly.

The order of composition of the components in an object can be important. In our initial system, we stored the components as a list inside a container object. Each component had an update function, which was called as we iterated over the list of components for each object.

Since the object creation was data driven, it could create problems if the list of components is in an unexpected order. If one object updates physics before animation, and the other updates animation before physics, then they might get out of sync with each other. Dependencies such as this need to be identified, and then enforced in code.

CONCLUSIONS

Moving from blob style object hierarchies to composite objects made from a collection of components was one of the best decisions I made. The initial results were disappointing as it took a long time to re-factor existing code. However, the end results were well worth it, with lightweight, flexible, robust and re-usable code.

Resources

Scott Bilas: GDC 2002 Presentation: A Data-Driven Game Object System
http://scottbilas.com/files/2002/gdc_san_jose/game_objects_slides.pdf

Bjarne Rene: Component Based Object Management. Game Programming Gems 5, 2005, page 25.

Kyle Wilson: Game Object Structure: Inheritence vs Aggregation, 2002, http://gamearchitect.net/Articles/GameObjects1.html

120 Comments »

  1. […] many have proposed a component based system. Before continuing, I recommend reading Evolve Your Hierarchy, a good introduction to the […]

    Pingback by Complex Functionality Using Component Systems | GameDevSoc — December 13, 2011 @ 7:47 am

  2. […] System, a sort of Architectural Pattern to develop game logic (read an excellent introduction here.) Nevertheless, before even starting to think how to apply it in a functional context, I’ve […]

    Pingback by Functional Reactive Programming kick-starter guide « Web life between Python and lambda calculus — December 24, 2011 @ 6:19 am

  3. […] https://cowboyprogramming.com/2007/01/05/evolve-your-heirachy/ http://gameprogrammingpatterns.com/component.html […]

    Pingback by design patterns – MVC-like compartmentalization in games? – Game Development – Stack Exchange | TechRetriever — December 30, 2011 @ 5:06 am

  4. […] recently came across an article, which simply explains what we might want some of our game entities to do, these are summarized […]

    Pingback by Day 8: Add game entities to our iPhone game — January 4, 2012 @ 3:34 am

  5. […] of supporting multiple-inheritance with dynamic type casting in an engine that makes heavy use of component-based design are relatively […]

    Pingback by C++ Metadata – Part II, Inheritance, Dynamic Casting, and Allocation | Game Development Student Journal — January 21, 2012 @ 3:03 am

  6. […] https://cowboyprogramming.com/2007/01/05/evolve-your-heirachy/ […]

    Pingback by 有關Re-Factoryçš„comment « NDark MSN Live Space — January 26, 2012 @ 10:20 pm

  7. […] It’s really easy to use, though it might be confusing at first because it’s a modular game engine that uses entities and components. I suggest you read this article if you don’t have any experience with it: https://cowboyprogramming.com/2007/01/05/evolve-your-heirachy/ […]

    Pingback by Developer Diary: Jetpack game HTML5 – Day 1 - Michiel De Mey's Blog - Programmer, designer and flash juggler — January 31, 2012 @ 9:00 am

  8. […] attempting to framework my fixture item courses comparable to how it is finished in this article. just one method to carry out this tactic is discussed in this StackOverflow […]

    Pingback by Implementing Object Composition | Q&A System — February 7, 2012 @ 3:00 pm

  9. […] It’s really easy to use, though it might be confusing at first because it’s a modular game engine that uses entities and components. I suggest you read this article if you don’t have any experience with it: https://cowboyprogramming.com/2007/01/05/evolve-your-heirachy/ […]

    Pingback by Developer Diary: Jetpack game HTML5 - Day 1 - Michiel De Mey's Blog - Michiel De Mey's Blog - Programmer, designer and flash juggler — February 8, 2012 @ 1:53 pm

  10. […] Um artigo que tenta mostrar as vantagens de usar agregação ao invés de herança: (link) […]

    Pingback by Padrões no desenvolvimento de games | USPGameDev — February 18, 2012 @ 6:21 pm

  11. […] mentioned in an article by Cowboy Programming here it has marginal gains early into a project but reaps high development gains later […]

    Pingback by Game components infrastructure for XNA. | Box Hacker — February 21, 2012 @ 9:06 pm

  12. […] C++ version. I’ll go into more specifics on it later, but for further reading on the concept try here, or even search for “Component Based Architecture”. Share this:TwitterFacebookLike […]

    Pingback by The Core Concept « The Infestation Cometh — February 29, 2012 @ 4:09 pm

  13. […] bug, repetir” cuando se trata de programas inútiles como el mío. Tomemos como ejemplo el modelo de programación de Entidades y Componentes. El artículo que enlazo (nota: si están en esto del desarrollo de juegos deberían darle una […]

    Pingback by DevBlog: C+ « 7c0h — March 2, 2012 @ 5:49 pm

  14. […] https://cowboyprogramming.com/2007/01/05/evolve-your-heirachy/ […]

    Pingback by Game Objects « DTO Software — March 22, 2012 @ 12:35 pm

  15. […] Evolve Your Hierarchy […]

    Pingback by Artemis: the Greek goddess of software architecture | star-fu.tv — April 12, 2012 @ 12:39 am

  16. […] Cow boy programming : Evolve your hierarchy Si vous avez aimé, partagez !   […]

    Pingback by Passez à l’ Entity System ! Partie 1 — April 30, 2012 @ 12:32 pm

  17. […] West. Evolve Your Hierarchy. https://cowboyprogramming.com/2007/01/05/evolve-your-heirachy/, January […]

    Pingback by Game Models – A Different Approach I | npruehs — May 24, 2012 @ 1:24 pm

  18. […] West. Evolve Your Hierarchy. https://cowboyprogramming.com/2007/01/05/evolve-your-heirachy/, January […]

    Pingback by Game Models – A Different Approach (Part 2) | npruehs — May 27, 2012 @ 11:18 am

  19. […] If you are thinking of taking a more modular approach, Mike West discusses this in his post “Evolve Your Hierarchy”. Or alternatively if you are planning on making a larger application and need more structure and […]

    Pingback by Require.js and Inheritance • Tal Woolf | Interactive Developer — June 27, 2012 @ 6:43 am

  20. Have you used or considered Component / Entity System frameworks to build games? Interested in your feedback and experience….

    Yes, I have built a system from scratch in Java, and now use it every day as a built-in feature of Unity. Their embrace of this philosophy has radically simplified development for me. Mick West (co-founder of Neversoft) got me started on the journey wi…

    Trackback by Quora — September 4, 2012 @ 5:57 pm

RSS feed for comments on this post. TrackBack URL

Leave a comment

You must be logged in to post a comment.

Powered by WordPress