Action and strategy games typically feature a variety of objects, many of which share common behaviour:

• Many objects need to test for collisions between their bounding-box and the map.
• All enemies deal damage to the player on contact.
• All bosses should display a special health bar on–screen.
• Some objects have a direction and velocity, some are affected by gravity.
• etc.

How can we implement shared traits of behaviour without duplicating code?

Some Metrics Before We Start

In terms of entity complexity, this article assumes that you are trying to build the next Super Mario World or 2D Zelda clone in C++. I have neither games’ source code, but I can look at my own 2D platformer, Terava:

• 109 final classes of objects (eg. Player, Coin, GiantSpider, Waterfall)
• 24 virtual member functions in the Object root class (eg. update, draw, serialize)
• 27 more virtual member functions defined further down the inheritance tree (eg. onJumpedOn callback defined by the Enemy base class)
• 14 behaviour traits that can be mixed into a class on demand (e.g. Rectangular adds a bounding box, Moving adds x/y velocity properties)

For my first freeware game, Peter Morphose, the values were roughly a third each, so I can see a pattern. If you are working on your own game project, feel free to compare.

The C Way: Using struct, No Inheritance

One way to implement game objects is to use structs with a type flag:

struct GameObject {
    enum { PLAYER, BOMB, COIN, BAD_GUY } type;
    int x, y;
    union { // depending on type
        struct { int velocityX, velocityY; int health; } player;
        struct { int radius; } bomb;
        struct { int velocityX, velocityY; bool chasingPlayer; } badGuy;
    };
};

void updateObject(GameObject& object);

While this approach will earn you points for being old-school, the updateObject function is unlikely to scale beyond a handful of object types.

The Java Way: One Superclass Ought to be Enough for Everyone

Object Oriented Programming 101 would love to come to the rescue. Just make it four classes and add intermediate classes for shared behaviour. Right?

class GameObject {
    ...
    virtual void update() ...
};
class Moving      : public GameObject {
    ...
    void update() { GameObject::update(); ... }
};
class HurtsPlayer : public Moving {
    ...
    void update() { GameObject::update(); ... }
};

class Player : public Moving      { ... };
class Bomb   : public HurtsPlayer { ... };
class Coin   : public GameObject  { ... };
class BadGuy : public HurtsPlayer { ... };

This is a huge step forward in maintainability. It also feels ‘natural’, not least because it is reminiscent of the tree of life in biology.

However, what if a Bomb does not move, which is currently implied by HurtsPlayer? Exchanging the base classes does not help:

There is no way around awkward decisions, duplicated code or bloated intermediate classes with a single inheritance tree.

The C++ Way: Multiple Inheritance

C++ famously supports multiple inheritance. It even provides the mind-bending notion of a “virtual base class”, so that BadGuy only inherits all GameObject members once, not twice (via the intermediate classes):

class GameObject { virtual void update() ... };
class HurtsPlayer : virtual public GameObject { void update(); };
class Moving      : virtual public GameObject { void update(); };

class Player : public Moving { ... };
class Bomb   : public HurtsPlayer { ... };
class Coin   : public GameObject { ... };
class BadGuy : public HurtsPlayer, public Moving { ... };

The inheritance graph now correctly describes each class:

However, how do we implement BadGuy::update? Should it call Moving::update to move, then hurt the player in HurtsPlayer::update, or the other way around? And if GameObject::update is not empty, whose job is it to call it? (We don’t want to call it twice, either.)

The compiler cannot sort this out for us—we’ll have to deal with these issues for each virtual member. So let’s give up on multiple inheritance.

Towards Entity Component Systems

We can solve our issues with dynamic behaviour objects that can be registered at runtime:

class BadGuy : public GameObject {
    ...
    BadGuy()
    {
        registerBehavior(new HurtPlayerBehavior());
        registerBehavior(new MovingBehavior());
    }
}

Now everything is a GameObject, and all data and behaviours are moved into independent components.

This approach completely circumvents the language facilities for inheritance. There are three downsides to this design:

• Interaction among behaviour traits is non–trivial.
• Casting to a superclass does not come for free. If a Storm object wants to push the player to the right, it cannot simply call player->setVelocityX(6). Instead, it needs to look up the player’s MovingBehavior and talk to it.
• Harder to make fast: In a naïve implementation, each behaviour is allocated separately, and referencing non-local memory is more expensive than accessing the base class.

(Of course, there is also one big upside: Behaviours can be added and removed dynamically!)

If that sounds like your cup of tea, check out Entity Component Systems. Personally, I feel this is way too complex for most 2D games, especially in C++. And I prefer to wire up as much of my game logic as possible during compile-time.

So without further ado, here’s the method that works for me:

Static C++ Template Mix-Ins

Let’s take a step back and look at the single–inheritance approach from above. It looks clean and efficient. The only problem is that we have to decide on a base class for every intermediate class.

Except we don’t! We can choose our base class using templates:

class GameObject { virtual void update() ... };

template<typename Base>
class Moving : public Base {
  void update() { Base::update(); /* movement here */ }
};

template<typename Base>
class HurtsPlayer : public Base {
  void update() { Base::update(); /* check for player collision */ }
};

class Player : public Moving<GameObject> { ... };
class Bomb   : public HurtsPlayer<GameObject> { ... };
class Coin   : public GameObject { ... };
class BadGuy : public HurtsPlayer<Moving<GameObject>> { ... };

This solution has it all:

• The behaviour introduced by Moving and HurtsPlayer is defined in exactly one place.
• No extra code, no runtime mechanisms.
• Every game object is exactly one C++ object, no indirections attached.
• The priority of behaviours is defined by the order of inheritance.
• Minimal virtual function calls. BadGuy::update can statically call HurtsPlayer::update, which statically calls Moving::update, which statically calls GameObject::update. The compiler can decide to inline all of it.
• Mix-in base class can add getters and setters to the object itself, and they can be inlined as well.

It also illustrates nicely how you can think of class templates as compile–time functions that return a new class. You “call” Moving<T>, and it constructs the desired class for you.

There are three potential issues with using templates:

1. Templates have a reputation of inflating binaries.

If one class inherits from A<B<C<D<...>>>> and another from B<A<D<C<...>>>>, etc., then there will be code in the binary for each permutation.

The solution is simple: try to keep the order the same every time. Merge sets of commonly shared behaviour into intermediate classes and give them intuitive names.

2. If A<...>::f() is a very long method, the binary will contain one copy each for A<B>::f, A<C>::f and so on.

Solution: Move the function out of the template class:

void moveObject(Obj& o, int& velX, int& velY); // defined in Moving.cpp

template<class Base>
class Moving : public Base {
    int velocityX, velocityY;
    ...
public:    
    void update() {
        Base::update();
        moveObject(*this, velocityX, velocityY);
    }
}

Since we are dealing with templates, this also means we can move the code from our header into a .cpp file to reduce compile times:

3. Moving is not one single class anymore.

You cannot dynamic_cast any GameObject into Moving to access its member functions anymore.

We can overcome this problem by combining our approach with multiple inheritance:

class MovingBase {
    int vx, vy;
protected:
    void move();
public:
    /* common member functions */
    void setVelocityX(int) ...
    void setVelocityY(int) ...
};

template<class Base>
class Moving : public Base, public MovingBase {
    ...
public:    
    void update() {
        Base::update();
        move();
    }
};

Alternatively, MovingBase can be made an interface with only virtual methods, and each instantiation of Moving<> then implements the interface.

(Or even better yet, just don’t set the velocity on arbitrary objects – instead add a public virtual function impulse(vx, vy) on the root class, with an empty default implementation. Moving<> then overrides this method to update its velocity.)

Summary

Template mix-ins have worked great for me. As a real-world example, here is the list of base classes for a typical bad guy in my game, the Skeleton. The inheritance tree uses a healthy mixture of single inheritance for core classes and mix–ins for smaller traits.

// - Object is the base class for game objects.
class Object {...};
// - Living<> adds the health property and a virtual `onDeath()`
//   callback for convenience. It might as well be a mix–in.
class Living     : public Object {...};
// - Directed<> adds a direction (left/right) that can be changed in the
//   level editor.
// - VirtuallyRectangular<> introduces a virtual size for display (only
//   for hit checks in the level editor, not collisions).
// - SkelLiving is an object that loads a skeletal animation.
class SkelLiving : public Mixins::VirtuallyRectangular<
                             Mixins::Directed<Living>> {...};
// - Rectangular<> adds a rectangular hit box to the object.
// - Actor provides a common base class for most enemies and the player.
class Actor      : public Mixins::Rectangular<SkelLiving> {...};
// - MakeMovingSticky<> adds movement with special handling for slopes.
//   (To avoid actors jittering down a slope, they are made ‘sticky’.)
// - Humanoid adds helper methods that trigger common animations in the
//   skeletal animation system for humans.
class Humanoid   : public Mixins::MovingSticky<Actor> {...};
// - MakeEnemy<> introduces checks for collisions with the player.
// - Skeleton adds its own specific logic, such as falling apart when
//   the player jumps on it.
class Skeleton   : public Mixins::Enemy<Bases::Humanoid> {...};

Each of these classes and mix–ins only introduce a few lines of code, which in turn are trivial to debug or review. No code is repeated anywhere, everything is DRY.

Update & Related Reading

This entry has been discussed a bit on reddit and commenters generally favour splitting objects up over using mix-ins, for two reasons.

Improve Performance / Data–Oriented Design

If you often access your objects’ data, you should try to rearrange your data to increase cache locality. For instance, if you regularly need to modify each object’s position, you could move all positions into a separate pool and minimize cache misses during iteration. This blog post has some examples.

I use a particle engine in my game, and I imagine particle engines are the perfect candidate for a data-oriented design.

However, I don’t see how I could make it work for actual game objects. The majority of my game logic consists of if statements that usually involve more than one kind of object attribute.

Improve Flexibility / Component–Based Design

Many commenters prefer Entity Component Systems (ECS) for their flexibility. This slideset by Scott Bilas has data from a much bigger game than mine, these PowerPoint slides by Marcin Chady make a similar point.

One advantage of an ECS is that you can change each object’s behaviour at runtime. (That’s not the only advantage — they can also make it easier to implement a data-oriented design.)

In my game, which is based on the template mix-ins presented above, I have also run into situations where objects change their behaviour.

I’d like to present my workaround. I can’t replace an object’s mix-in base classes at runtime, so I instead I replace the object. To ensure that objects can reference each other even when they ‘become’ another object, I have written a redirectable smart pointer.

Fictitious example: Say the platypus is an enemy that walks or swims, depending on its position on the map. Instead of writing a single Platypus class that handles both ‘states’, we define the WalkingPlatypus and a SwimmingPlatypus classes, each with different mix-in base classes. Now a platypus can change into the other ‘state’ using code like this:

void WalkingPlatypus::update() {
  ...
  if (inWater()) {
    SwimmingPlatypus *newThis =
      new SwimmingPlatypus(this->x(), this->y());
    redirectPointers(newThis);
    this->removeObject();
  }
}

And if a HomingMissile object is chasing a RunningPlatypus that starts to swim, the missile’s object reference (redirectable smart pointer) will be updated to point to the new SwimmingPlatypus instance, thanks to the call to redirectPointers(). The missile would keep chasing the poor platypus, because it is still logically the same object.

The whole mechanism takes a page of code to set up, but it ensures that compile-time mix-ins don’t turn into a dead end when behaviours need to be adjusted at runtime.

If you are a fellow C++ game developer, what do you think of this solution? If you are using another language, what’s its best solution to the problem?