Game Programming Patterns / Behavioral Patterns

Type Object

×

This book is a work in progress!

If you see a mistake, find something unclear, or have a suggestion, please file a ticket. To know when new chapters are up, join the mailing list:

Thank you!

— Bob (@munificentbob)

Intent

Allow the flexible creation of new “classes” by creating a single class, each instance of which represents a different type of object.

Motivation

Imagine we’re working on a fantasy role-playing game. Our task is to write the code for the hordes of vicious monsters that seek to slay our brave hero. Monsters have a bunch of different attributes: health, attacks, graphics, sounds, etc., but for example purposes we’ll just worry about the first two.

Each monster in the game has a value for its current health. It starts out full, and each time the monster is wounded, it diminishes. Monsters also have an attack string. When the monster attacks our hero, that text will be shown to the user somehow. (We don’t care how here.)

The designers tell us that monsters come in a variety of different breeds, like “dragon” or “troll.” Each breed describes a kind of monster that exists in the game, and there can be multiple monsters of the same breed running around in the dungeon at the same time.

The breed determines a monster’s starting health: dragons start off with more than trolls, making them harder to kill. It also determines the attack string: all monsters of the same breed attack the same way.

The typical OOP answer

Given that game design, we fire up our text editor and start coding. According to the design, a dragon is a kind of monster, a troll is another kind, and so on with the other breeds. Thinking object-oriented, that leads us to a Monster base class:

class Monster
{
public:
  virtual ~Monster() {}
  virtual const char* getAttack() = 0;

protected:
  Monster(int startingHealth)
  : health_(startingHealth)
  {}

private:
  int health_; // Current health.
};

The public getAttack() function lets the combat code get the string that should be displayed when the monster attacks the hero. Each derived breed class will override this to provide a different message.

The constructor is protected and takes the starting health for the monster. We’ll have derived classes for each breed that provide their own public constructors that call this one, passing in the starting health that is appropriate for that breed.

Now let’s see a couple of breed subclasses:

class Dragon : public Monster
{
public:
  Dragon() : Monster(230) {}
  const char* getAttack() {
    return "The dragon breathes fire!";
  }
};

class Troll : public Monster
{
public:
  Troll() : Monster(48) {}
  virtual const char* getAttack() {
    return "The troll clubs you!";
  }
};

Each class derived from Monster passes in the starting health, and overrides getAttack() to return the attack string for that breed. Everything works as expected, and before long we’ve got our hero running around slaying a variety of beasties. We keep slinging code, and before we know it, we’ve got dozens of monster subclasses, from acidic slimes to zombie goats.

Then, strangely, things start to bog down. Our designers ultimately want to have hundreds of breeds, and we find ourselves spending all of our time writing these little seven line subclasses and recompiling. It gets worse: the designers want to start tuning the breeds we’ve already coded. Our formerly productive work day degenerates to:

  1. Get email from designer asking to change health of troll from 48 to 52.

  2. Check out and change Troll.h.

  3. Recompile game.

  4. Check in change.

  5. Reply to email.

  6. Repeat.

We spend the day frustrated because we’ve turned into data monkeys. Our designers are frustrated because it takes them forever just to get a simple number tuned. What we need is the ability to change breed stats without having to recompile the whole game every time. Even better, we’d like designers to be able to create and tune breeds without any programmer intervention at all.

A class for a class

At a very high level, the problem we’re trying to solve is pretty simple. We have a bunch of different monsters in the game, and we want to share certain attributes between them. A horde of monsters are beating on the hero, and we want some of them to use the same text for their attack. We define that by saying that all of those monsters are the same “breed,” and that the breed determines the attack string.

We decided to implement this concept using inheritance, since it lines up with our intuition of classes: A dragon is a monster, and each dragon in the game is an instance of this dragon “class.” Defining each breed as a subclass of an abstract base Monster class, and having each monster in the game be an instance of that derived breed class mirrors that. We end up with a class hierarchy like this:

Each instance of a monster in the game will be of one of the derived monster types. The more breeds we have, the bigger the class hierarchy. That’s the problem of course: adding new breeds means adding new code, and each breed has to be compiled in as its own type.

This works, but it isn’t the only option. We could also architect our code so that each monster has a breed. Instead of subclassing Monster for each breed, we have a single Monster class and a single Breed class:

That’s it. Two classes. Notice that there’s no inheritance at all. With this system, each monster in the game is simply an instance of class Monster. The Breed class contains the information that’s shared between all monsters of the same breed: starting health and the attack string.

To associate monsters with breeds, we give each Monster instance a reference to a Breed object containing the information for that breed. To get the attack string, a monster just calls a method on its breed. The Breed class essentially defines a monster’s “type.” Each breed instance is an object that represents a different conceptual type, hence the name of the pattern: Type Object.

What’s especially powerful about this pattern is that now we can define new types of things without complicating the codebase at all: we’ve essentially lifted a portion of the type system out of the hard-coded class hierarchy into data we can define at runtime.

We can create hundreds of different breeds just by instantiating more instances of Breed with different values. If we create breeds by initializing them from data read from some configuration file, we have the ability to define new types of monsters completely in data. So easy a designer could do it!

The Pattern

Define a type object class and a typed object class. Each instance of the type object class represents a different logical type. Instances of the typed object class store a reference to the type object that describes their type.

Instance-specific data is stored in the typed object instance, and data or behavior that should be shared across all instances of the same conceptual type is stored in the type object. Objects referencing the same type object will function as if they were the same type. This lets us share data and behavior across a set of similar objects, much like subclassing lets us do, but without having a fixed set of hard-coded subclasses.

When to Use It

This pattern is useful anytime you need to define a variety of different “kinds” of things, but baking the kinds into your language’s type system is too rigid. In particular, it’s useful when either of these are true:

Keep in Mind

The type objects have to be tracked manually

One advantage of using something like C++’s type system is that the compiler handles all of the bookkeeping for the classes automatically. The data that defines each class (primarily the vtables that control which overridden functions gets called) is automatically compiled into the static memory segment of the executable and just works.

With the Type Object pattern, we are now responsible for managing not only our monsters in memory, but also their types: we have to make sure all of the breed objects are instantiated and kept in memory as long as our monsters need them. Whenever we create a new monster, it’s up to us to ensure that it’s correctly initialized with a reference to a valid breed.

We’ve freed ourselves from some of the limitations of the compiler, but the cost is we have to re-implement some of what it used to be doing for us.

It’s harder to define behavior for each type

With subclassing, you can override a method and do whatever you want to: calculate values procedurally, call other code, etc. The sky is the limit. We could define a monster subclass whose attack string changed based on the phase of the moon if we wanted to. (Handy for werewolves, I suppose.)

When we use the Type Object pattern instead, we replace an overridden method with a member variable. Instead of having monster subclasses that override a method to calculate an attack string using different code, we have a breed object that stores an attack string in a different variable.

This makes it very easy to use type objects to define type-specific data, but hard to define type-specific behavior. If, for example, different breeds of monster needed to use different AI algorithms, using this pattern becomes more challenging.

There are a couple of ways we can get around this limitation. A simple solution is to have a fixed set of pre-defined behaviors, and then use data in the type object to simply select one of them. For example, let’s say our monster AI will always be either “stand still”, “chase hero”, or “whimper and cower in fear” (hey, they can’t all be mighty dragons). We can define functions to implement each of those behaviors. Then we can associate an AI algorithm with a breed by simply having it store a pointer to the appropriate function.

Another more powerful solution is to actually support defining behavior completely in data. The Interpreter, and Bytecode patterns both let us build objects that represent behavior. If we read in a data file and use that to create a data structure for one of these patterns, we’ve moved the behavior’s definition completely out of code and into content.

Sample Code

For our first pass at an implementation, let’s start simple and build the basic system described in the “Motivation” section. We’ll start with the Breed class:

class Breed
{
public:
  Breed(int health, const char* attack)
  : health_(health),
    attack_(attack)
  {}

  int         getHealth() { return health_; }
  const char* getAttack() { return attack_; }

private:
  int         health_; // Starting health.
  const char* attack_;
};

Very simple. It’s basically just a container for two data fields: the starting health and the attack string. Let’s see how monsters use it:

class Monster
{
public:
  Monster(Breed& breed)
  : health_(breed.getHealth()),
    breed_(breed)
  {}

  const char* getAttack() {
    return breed_.getAttack();
  }

private:
  int    health_; // Current health.
  Breed& breed_;
};

When we construct a monster, we give it a reference to a breed object. This defines the monster’s breed instead of the subclasses we were previously using. In the constructor, Monster uses the breed to determine its starting health. To get the attack string, the monster simply forwards the call to its breed.

This very simple chunk of code is the core idea of the pattern. Everything from here on out is bonus.

Making type objects more like types: constructors

With what we have now, we construct a monster directly and are responsible for passing in its breed. This is a bit backwards from how regular objects are instantiated in most OOP languages: we don’t usually allocate a blank chunk of memory and then give it its class. Instead, we call a constructor function on the class itself, and it’s responsible for giving us a new instance.

We can apply this same pattern to our type objects:

class Breed
{
public:
  Monster* newMonster() { return new Monster(*this); }

  // Previous Breed code...
};

And the class that uses them:

class Monster
{
  friend class Breed;

public:
  const char* getAttack() { return breed_.getAttack(); }

private:
  Monster(Breed& breed)
  : health_(breed.getHealth()),
    breed_(breed)
  {}

  int    health_; // Current health.
  Breed& breed_;
};

The key difference is the newMonster() function in Breed. That’s our “constructor” factory method. With our original implementation, creating a monster looked like:

Monster* monster = new Monster(someBreed);

After our changes, it’s like this:

Monster* monster = someBreed.newMonster();

So, why do this? There are two steps to creating an object: allocation and initialization. Monster’s constructor lets us do all of the initialization we need. In our example, that’s only storing the breed, but a full game would be loading graphics, initializing the monster’s AI, and doing other set-up work.

However, that all happens after allocation. We’ve already got a chunk of memory to put our monster into before its constructor is called. In games, we often want to control that aspect of object creation too: we’ll typically use things like custom allocators or the Object Pool pattern to control where in memory our objects end up.

Defining a “constructor” function in Breed gives us a place to put that logic. Instead of simply calling new, the newMonster function can pull the memory from a pool or custom heap before passing control off to Monster for initialization. By putting this logic inside Breed, in the only function that has the ability to create monsters, we ensure that all monsters go through the memory management scheme we want.

Sharing data through inheritance

What we have so far is a perfectly serviceable type object system, but it’s pretty basic. Our game will eventually have hundreds of different breeds, each with dozens of attributes. If a designer wants to tune all of the thirty different breeds of troll to make them a little stronger, she’s got a lot of tedious data entry ahead of her.

What would help is the ability to share attributes across multiple breeds in the same way that breeds let us share attributes across multiple monsters. Just like we did with our original OOP solution, we can solve this using inheritance. Only, this time, instead of using our language’s inheritance mechanism, we’ll implement it ourselves within our type objects.

To keep things simple, we’ll just support single inheritance. In the same way that a class can have a parent base class, we’ll allow a breed to have a parent breed:

class Breed
{
public:
  Breed(Breed* parent, int health, const char* attack)
  : parent_(parent),
    health_(health),
    attack_(attack)
  {}

  int         getHealth();
  const char* getAttack();

private:
  Breed*      parent_;
  int         health_; // Starting health.
  const char* attack_;
};

When we construct a breed, we give it a parent that it inherits from. We can pass in NULL for a base breed that has no ancestors.

To make this useful, a child breed needs to control which attributes are inherited from its parent and which it overrides and specifies itself. For our example system, we’ll say that a breed overrides the monster’s health by having a non-zero value, and overrides the attack by having a non-NULL string. Otherwise, the attribute will be inherited from its parent.

There are two ways we can implement this. One is to handle the delegation dynamically, every time the attribute is requested, like this:

int Breed::getHealth()
{
  // Override.
  if (health_ != 0 || parent_ == NULL) return health_;

  // Inherit.
  return parent_->getHealth();
}

const char* Breed::getAttack()
{
  // Override.
  if (attack_ != NULL || parent_ == NULL) return attack_;

  // Inherit.
  return parent_->getAttack();
}

This has the advantage of doing the right thing if a breed is modified at runtime to no longer override, or no longer inherit some attribute. On the other hand, it takes a bit more memory (it has to retain a pointer to its parent), and it’s slower. It has to walk the inheritance chain each time you look up an attribute.

If we can rely on a breed’s attributes not changing, a faster solution is to apply the inheritance at construction time. This is called "copy-down" delegation because we copy inherited attributes down into the derived type when it’s created. It looks like this:

Breed(Breed* parent, int health, const char* attack)
: health_(health),
  attack_(attack)
{
  // Inherit non-overridden attributes.
  if (parent != NULL)
  {
    if (health == 0) health_ = parent->getHealth();
    if (attack == NULL) attack_ = parent->getAttack();
  }
}

Note that we no longer need a field for the parent breed. Once the constructor is done, we can forget the parent since we’ve already copied all of its attributes in. To access a breed’s attribute, now we just return the field:

int         getHealth() { return health_; }
const char* getAttack() { return attack_; }

Nice and fast!

Let’s say our game engine is set up to create the breeds by loading a JSON file that defines them. It could look like:

{
  "Troll": {
    "health": 25,
    "attack": "The troll hits you!"
  },
  "Troll Archer": {
    "parent": "Troll",
    "health": 0,
    "attack": "The troll archer fires an arrow!"
  },
  "Troll Wizard": {
    "parent": "Troll",
    "health": 0,
    "attack": "The troll wizard casts a spell on you!"
  }
}

We’d have a chunk of code that reads each breed entry and instantiates a new Breed instance with its data. As you can see from the "parent": "Troll" fields above, the Troll Archer and Troll Wizard breeds inherit from the base Troll breed.

Since both of them have zero for their health, they’ll inherit it from the base Troll breed instead. This means now our designer can tune the health in Troll and all three breeds will be updated. As the number of breeds and the number of different attributes each breed has increases, this can be a big time-saver. Now, with a pretty small chunk of code, we have an open-ended system that puts control in our designer’s hands and makes the best use of their time. Meanwhile, we can get back to coding other features.

Design Decisions

The Type Object pattern lets us build a type system as if we were designing our own programming language. The design space is wide open, and we can do all sorts of interesting stuff.

In practice, a few things curtail our fancy. Time and maintainability will discourage us from anything particularly complicated. More importantly, whatever type object system we design, our users (often non-programmers) will need to be able to easily understand it. The simpler we can make it, the more usable it will be. So what we’ll cover here is the well-trodden design space, and we’ll leave the far reaches for the academics and explorers.

Is the Type Object encapsulated or exposed?

In our sample implementation, Monster has a reference to a Breed, but it doesn’t publicly expose it. Outside code can’t get directly at the monster’s breed. From the codebase’s perspective, monsters are essentially typeless, and the fact that they have breeds is an implementation detail.

We can easily change this and allow Monster to return its Breed:

class Monster
{
public:
  Breed& getBreed() { return breed_; }

  // Existing code...
};

Doing this changes the design of Monster. The fact that all Monsters have breeds is now a publicly-visible part of its API. There are benefits with either choice.

How are typed objects created?

With this pattern, each “object” is now a pair of objects: the main object and the type object it uses. So how do we create and bind the two together?

Can the type change?

So far, we’ve presumed that once an object is created and bound to its type object that that binding will never change. The type an object is created with is the type it dies with. This isn’t strictly necessary. We could allow an object to change its type over time.

Let’s look back at our example. When a monster dies, the designers tell us sometimes they want its corpse to become a reanimated zombie. We could implement this by spawning a new monster with a zombie breed when a monster dies, but another option is to simply get the existing monster and change its breed to a zombie one.

What kind of inheritance is supported?

See Also