Home · Book Reports · 2023 · Game Programming Patterns

designates my notes. / designates important. / designates very important.

• Pages numbers from the pdf

Thoughts

I appreciate the humor sprinkled throughout.

Table of Contents

• 00: Introduction
• 01: Design Patterns Revisited
• 02: Sequencing Patterns
• 03: Behavioral Patterns
• 04: Decoupling Patterns
• 05: Optimization Patterns

· Chapter 00 - Introduction

page 14:

• The first key piece is that architecture is about change. Someone has to be modifying the codebase. If no one is touching the code — whether because it’s perfect and complete or so wretched no one will sully their text editor with it — its design is irrelevant. The measure of a design is how easily it accommodates changes.

page 17:

• Whenever you add a layer of abstraction or a place where extensibility is supported, you’re speculating that you will need that flexibility later. You’re adding code and complexity to your game that takes time to develop, debug, and maintain. That effort pays off if you guess right and end up touching that code later. But predicting the future is hard, and when that modularity doesn’t end up being helpful, it quickly becomes actively harmful. After all, it is more code you have to deal with.

· Chapter 01 - Design Patterns Revisited

Command

Flyweight

page 40:

Observer

page 54:

page 57:

page 60:

• Multiple nodes can point to the same observer.

page 61:

• On deleting observers

• More often than not, the observer does know which subjects it’s observing, so it’s usually just a matter of adding a removeObserver() call to its destructor.

• If you don’t want to leave observers hanging when a subject gives up the ghost, that’s easy to fix. Just have the subject send one final “dying breath” notification right before it gets destroyed. That way, any observer can receive that and take whatever action it thinks is appropriate.

page 62:

• Imagine this: you’ve got some UI screen that shows a bunch of stats about the player’s character like their health and stuff. When the player brings up the screen, you instantiate a new object for it. When they close it, you just forget about the object and let the GC (Garbage Collection) clean it up.

• Every time the character takes a punch to the face (or elsewhere, I suppose), it sends a notification. The UI screen observes that and updates the little health bar. Great. Now what happens when the player dismisses the screen, but you don’t unregister the observer?

• The UI isn’t visible anymore, but it won’t get garbage collected since the character’s observer list still has a reference to it. Every time the screen is loaded, we add a new instance of it to that increasingly long list.

• The entire time the player is playing the game, running around, and getting in fights, the character is sending notifications that get received by all of those screens. They aren’t on screen, but they receive notifications and waste CPU cycles updating invisible UI elements. If they do other things like play sounds, you’ll get noticeably wrong behavior.

• This is such a common issue in notification systems that it has a name: the lapsed listener problem.

page 63:

• if your program isn’t working and the bug spans some chain of observers, reasoning about that communication flow is much more difficult. With an explicit coupling, it’s as easy as looking up the method being called. This is child’s play for your average IDE since the coupling is static.

• But if that coupling happens through an observer list, the only way to tell who will get notified is by seeing which observers happen to be in that list at runtime. Instead of being able to statically reason about the communication structure of the program, you have to reason about its imperative, dynamic behavior.

• My guideline for how to cope with this is pretty simple. If you often need to think about both sides of some communication in order to understand a part of the program, don’t use the Observer pattern to express that linkage. Prefer something more explicit.

• When you’re hacking on some big program, you tend to have lumps of it that you work on all together. We have lots of terminology for this like “separation of concerns” and “coherence and cohesion” and “modularity”, but it boils down to “this stuff goes together and doesn’t go with this other stuff”.

page 64:

• If I were designing an observer system today, I’d make it function-based instead of class-based. Even in C++, I would tend toward a system that let you register member function pointers as observers instead of instances of some Observer interface.

page 65:

• Many recent application frameworks now use “data binding”.

• Unlike more radical models, data binding doesn’t try to entirely eliminate imperative code and doesn’t try to architect your entire application around a giant declarative dataflow graph. What it does do is automate the busywork where you’re tweaking a UI element or calculated property to reflect a change to some value.

• Like other declarative systems, data binding is probably a bit too slow and complex to fit inside the core of a game engine. But I would be surprised if I didn’t see it start making inroads into less critical areas of the game like UI.

• This “data binding” would be like the set and get functions in Godot. They observer changes in a variable and can do things like emit signals to, for example, update the UI when a player’s HP changes.

Prototype

page 71:

• With all of these options, I honestly can’t say I’ve found a case where I felt the Prototype design pattern was the best answer. Maybe your experience will be different, but for now let’s put that away and talk about something else: prototypes as a language paradigm

page 79:

• so let’s close this out with an area where I do think prototypes, or more specifically delegation, can be useful. (data)

page 80:

{
  "name": "goblin grunt",
  "minHealth": 20,
  "maxHealth": 30,
  "resists": ["cold", "poison"],
  "weaknesses": ["fire", "light"]
}
{
  "name": "goblin wizard",
  "prototype": "goblin grunt",
  "spells": ["fire ball", "lightning bolt"]
}
{
  "name": "goblin archer",
  "prototype": "goblin grunt",
  "attacks": ["short bow"]
}

Singleton

page 88:

• By controlling access to instances, you control coupling.

This chapter is primarily about AVOIDING overuse of singletons.

page 92:

• If you can, just move all of that behavior into the class it helps.

State

page 103:

• One problem our Heroine class has is some combinations of those Boolean fields aren’t valid: isJumping_ and isDucking_ should never both be true, for example. When you have a handful of flags where only one is true at a time, that’s a hint that what you really want is an enum. In this case, that enum is exactly the set of states for our FSM, so let’s define that:

enum State
{
  STATE_STANDING,
  STATE_JUMPING,
  STATE_DUCKING,
  STATE_DIVING
};

• Instead of a bunch of flags, Heroine will just have one state_ field.

page 105:

• First, we define an interface for the state. Every bit of behavior that is state-dependent — every place we had a switch before — becomes a virtual method in that interface. For us, that’s handleInput() and update():

class HeroineState
{
public:
  virtual ~HeroineState() {}
  virtual void handleInput(Heroine& heroine, Input input) {}
  virtual void update(Heroine& heroine) {}
};

• For each state, we define a class that implements the interface. Its methods define the heroine’s behavior when in that state. In other words, take each case from the earlier switch statements and move them into their state’s class. For example:

class DuckingState : public HeroineState
{
public:
  DuckingState()
  : chargeTime_(0)
  {}
  virtual void handleInput(Heroine& heroine, Input input) {
    if (input == RELEASE_DOWN)
    {
      // Change to standing state...
      heroine.setGraphics(IMAGE_STAND);
    }
  }
  virtual void update(Heroine& heroine) {
    chargeTime_++;
    if (chargeTime_ > MAX_CHARGE)
    {
      heroine.superBomb();
    }
  }
private:
  int chargeTime_;
};

page 106:

• Note that we also moved chargeTime_ out of Heroine and into the DuckingState class. This is great — that piece of data is only meaningful while in that state, and now our object model reflects that explicitly.

• Next, we give the Heroine a pointer to her current state, lose each big switch, and delegate to the state instead:

class Heroine
{
public:
  virtual void handleInput(Input input)
  {
    state_->handleInput(*this, input);
  }
  virtual void update()
  {
    state_->update(*this);
  }
  // Other methods...
private:
  HeroineState* state_;
};

• In order to “change state”, we just need to assign state_ to point to a different HeroineState object. That’s the State pattern in its entirety.

• This looks like the Strategy and Type Object patterns. In all three, you have a main object that delegates to another subordinate one. The difference is intent.

• With Strategy, the goal is to decouple the main class from some portion of its behavior.

• With Type Object, the goal is to make a number of objects behave similarly by sharing a reference to the same type object.

• With State, the goal is for the main object to change its behavior by changing the object it delegates to.

page 116:

• Here’s an example: Earlier, we let our fearless heroine arm herself to the teeth. When she fires her gun, we need a new state that plays the firing animation and spawns the bullet and any visual effects. So we slap together a FiringState and make all of the states that she can fire from transition into that when the fire button is pressed.

• Since this behavior is duplicated across several states, it may also be a good place to use a hierarchical state machine to reuse that code.

• The tricky part is what state she transitions to after firing. She can pop off a round while standing, running, jumping, and ducking. When the firing sequence is complete, she should transition back to what she was doing before.

• If we’re sticking with a vanilla FSM, we’ve already forgotten what state she was in. To keep track of it, we’d have to define a slew of nearly identical states — firing while standing, firing while running, firing while jumping, and so on — just so that each one can have a hardcoded transition that goes back to the right state when it’s done.

• What we’d really like is a way to store the state she was in before firing and then recall it later. Again, automata theory is here to help. The relevant data structure is called a pushdown automaton.

• Where a finite state machine has a single pointer to a state, a pushdown automaton has a stack of them. In an FSM, transitioning to a new state replaces the previous one. A pushdown automaton lets you do that, but it also gives you two additional operations:

1. You can push a new state onto the stack. The “current” state is always the one on top of the stack, so this transitions to the new state. But it leaves the previous state directly under it on the stack instead of discarding it.

2. You can pop the topmost state off the stack. That state is discarded, and the state under it becomes the new current state.

· Chapter 02 - Sequencing Patterns

Double Buffer

page 121:

• Cause a series of sequential operations to appear instantaneous or simultaneous.

Game Loop

page 140:

• Decouple the progression of game time from user input and processor speed.

page 145:

• For me, this is the difference between an “engine” and a “library”. With libraries, you own the main game loop and call into the library. An engine owns the loop and calls into your code.

Update Method

page 160:

• each entity in the game should encapsulate its own behavior

page 168:

• There are some readers whose skin is crawling right now because I’m using inheritance on the main Entity class to define different behaviors. If you don’t happen to see the problem, I’ll provide some context.

• When the game industry emerged from the primordial seas of 6502 assembly code and VBLANKs onto the shores of object-oriented languages, developers went into a software architecture fad frenzy. One of the biggest was using inheritance. Towering, Byzantine class hierarchies were built, big enough to blot out the sun.

• It turns out that was a terrible idea and no one can maintain a giant class hierarchy without it crumbling around them. Even the Gang of Four knew this in 1994 when they wrote:

Favor ‘object composition’ over ‘class inheritance’.

• Between you and me, I think the pendulum has swung a bit too far away from subclassing. I generally avoid it, but being dogmatic about not using inheritance is as bad as being dogmatic about using it. You can use it in moderation without having to be a teetotaler.

• When this realization percolated through the game industry, the solution that emerged was the Component pattern. Using that, update() would be on the entity’s components and not on Entity itself. That lets you avoid creating complicated class hierarchies of entities to define and reuse behavior. Instead, you just mix and match components.

• If I were making a real game, I’d probably do that too. But this chapter isn’t about components. It’s about update() methods, and the simplest way I can show them, with as few moving parts as possible, is by putting that method right on Entity and making a few subclasses.

page 170:

page 172:

• Where to put the update() method?

• If you’re already using the Component pattern, this is a no-brainer. It lets each component update itself independently. In the same way that the Update Method pattern in general lets you decouple game entities from each other in the game world, this lets you decouple parts of a single entity from each other. Rendering, physics, and AI can all take care of themselves.

page 174:

• This pattern, along with Game Loop and Component, is part of a trinity that often forms the nucleus of a game engine.

· Chapter 03 - Behavioral Patterns

Bytecode

page 182:

• We’d call our little emulator a virtual machine (or “VM” for short), and the synthetic binary machine code it runs bytecode. It’s got the flexibility and ease of use of defining things in data, but it has better performance than higher-level representations like the Interpreter pattern.

• In programming language circles, “virtual machine” and “interpreter” are synonymous, and I use them interchangeably here. When I refer to the Gang of Four’s Interpreter pattern, I’ll use “pattern” to make it clear.

Subclass Sandbox

Type Object

page 230:

class Breed
{
public:
    Monster* newMonster() { return new Monster(*this); }
    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_;
};

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_;
};

• There’s another minor difference here. Because the sample code is in C++, we can use a handy little feature: friend classes. We’ve made Monster’s constructor private, which prevents anyone from calling it directly. Friend classes sidestep that restriction so Breed can still access it. This means the only way to create monsters is by going through newMonster().

Monster* monster = new Monster(someBreed);

• After our changes, it’s like this:

Monster* monster = someBreed.newMonster();

page 231:

• 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 only 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.

page 232:

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_; }

• 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!"
  }
}

· Chapter 04 - Decoupling Patterns

Component

page 243:

• Decorations are things in the world the player sees but doesn’t interact with: bushes, debris and other visual detail. Props are like decorations but can be touched: boxes, boulders, and trees. Zones are the opposite of decorations — invisible but interactive.

7.1.2. 249:

class Bjorn
{
public:
  Bjorn()
  : velocity_(0),
    x_(0), y_(0)
  {}
  void update(World& world, Graphics& graphics);
private:
  static const int WALK_ACCELERATION = 1;
  int velocity_;
  int x_, y_;
  Volume volume_;
  Sprite spriteStand_;
  Sprite spriteWalkLeft_;
  Sprite spriteWalkRight_;
};

• Bjorn has an update() method that gets called once per frame by the game:

void Bjorn::update(World& world, Graphics& graphics)
{
  // Apply user input to hero's velocity.
  switch (Controller::getJoystickDirection())
  {
    case DIR_LEFT:
    velocity_ -= WALK_ACCELERATION;
    break;
    case DIR_RIGHT:
    velocity_ += WALK_ACCELERATION;
    break;
  }
  // Modify position by velocity.
  x_ += velocity_;
  world.resolveCollision(volume_, x_, y_, velocity_);
  // Draw the appropriate sprite.
  Sprite* sprite = &spriteStand_;
  if (velocity_ < 0)
  {
    sprite = &spriteWalkLeft_;
  }
  else if (velocity_ > 0)
  {
    sprite = &spriteWalkRight_;
  }
  graphics.draw(*sprite, x_, y_);

page 250:

• Let’s move that logic out into a separate class:

class InputComponent
{
public:
  void update(Bjorn& bjorn)
  {
    switch (Controller::getJoystickDirection())
    {
      case DIR_LEFT:
        bjorn.velocity -= WALK_ACCELERATION;
        break;
      case DIR_RIGHT:
        bjorn.velocity += WALK_ACCELERATION;
        break;
    }
  }
private:
  static const int WALK_ACCELERATION = 1;
};

• The changes to Bjorn are also straightforward:

class Bjorn
{
public:
  int velocity;
  int x, y;
  void update(World& world, Graphics& graphics)
  {
    input_.update(*this);
    
    // Modify position by velocity.
    x += velocity;
    world.resolveCollision(volume_, x, y, velocity);
    
    // Draw the appropriate sprite.
    Sprite* sprite = &spriteStand_;
    if (velocity < 0)
    {
      sprite = &spriteWalkLeft_;
    }
    else if (velocity > 0)
    {
      sprite = &spriteWalkRight_;
    }
    graphics.draw(*sprite, x, y);
  }
  
private:
  InputComponent input_;
  
  Volume volume_;
  
  Sprite spriteStand_;
  Sprite spriteWalkLeft_;
  Sprite spriteWalkRight_;
};

page 251:

• We’ve only started, but already we’ve gotten rid of some coupling — the main Bjorn class no longer has any reference to Controller. This will come in handy later.

• Here’s our new PhysicsComponent:

class PhysicsComponent
{
public:
  void update(Bjorn& bjorn, World& world)
  {
    bjorn.x += bjorn.velocity;
    world.resolveCollision(volume_,
        bjorn.x, bjorn.y, bjorn.velocity);
  }
private:
  Volume volume_;
};

page 252:

• Last but not least, here’s where the rendering code lives now:

class GraphicsComponent
{
public:
  void update(Bjorn& bjorn, Graphics& graphics)
  {
    Sprite* sprite = &spriteStand_;
    if (bjorn.velocity < 0)
    {
      sprite = &spriteWalkLeft_;
    }
    else if (bjorn.velocity > 0)
    {
      sprite = &spriteWalkRight_;
    }
    
    graphics.draw(*sprite, bjorn.x, bjorn.y);
  }
  
private:
  Sprite spriteStand_;
  Sprite spriteWalkLeft_;
  Sprite spriteWalkRight_;
};

• We’ve yanked almost everything out, so what’s left of our humble pastry chef? Not much:

class Bjorn
{
public:
  int velocity;
  int x, y;
  void update(World& world, Graphics& graphics)
  {
    input_.update(*this);
    physics_.update(*this, world);
    graphics_.update(*this, graphics);
  }
private:
  InputComponent input_;
  PhysicsComponent physics_;
  GraphicsComponent graphics_;
};

• This can be further abstracted to allow Bjorn to be constructed with other components, like an AI controlled InputComponent.

page 258:

• The components will have to communicate at some point. You have 3 options:

1. By modifying the container object’s state

2. By referring directly to each other

3. By sending messages

page 260:

• Unsurprisingly, there’s no one best answer here. What you’ll likely end up doing is using a bit of all of them. Shared state is useful for the really basic stuff that you can take for granted that every object has — things like position and size.

• Some domains are distinct but still closely related. Think animation and rendering, user input and AI, or physics and collision. If you have separate components for each half of those pairs, you may find it easiest to just let them know directly about their other half.

• Messaging is useful for “less important” communication. Its fire-and-forget nature is a good fit for things like having an audio component play a sound when a physics component sends a message that the object has collided with something.

Event Queue

page 271:

• When you receive an event, you have to be careful not to assume the current state of the world reflects how the world was when the event was raised. This means queued events tend to be more data heavy than events in synchronous systems. With the latter, the notification can say “something happened” and the receiver can look around for the details. With a queue, those ephemeral details must be captured when the event is sent so they can be used later.

page 272:

1. A sends an event.
2. B receives it and responds by sending an event.
3. That event happens to be one that A cares about, so it receives it. In response, it sends an event…
4. Go to 2.

• When your messaging system is synchronous, you find cycles quickly — they overflow the stack and crash your game. With a queue, the asynchrony unwinds the stack, so the game may keep running even though spurious events are sloshing back and forth in there. A common rule to avoid this is to avoid sending events from within code that’s handling one.

page 280:

• If you queue events:

• An “event” or “notification” describes something that already happened, like “monster died”. You queue it so that other objects can respond to the event, sort of like an asynchronous Observer pattern.

• You are likely to allow multiple listeners. Since the queue contains things that already happened, the sender probably doesn’t care who receives it. From its perspective, the event is in the past and is already forgotten.

• The scope of the queue tends to be broader. Event queues are often used to broadcast events to any and all interested parties. To allow maximum flexibility for which parties can be interested, these queues tend to be more globally visible.

• If you queue messages:

• A “message” or “request” describes an action that we want to happen in the future, like “play sound”. You can think of this as an asynchronous API to a service.

• Another word for “request” is “command”, as in the Command pattern, and queues can be used there too.

• You are more likely to have a single listener. In the example, the queued messages are requests specifically for the audio API to play a sound. If other random parts of the game engine started stealing messages off the queue, it wouldn’t do much good.

page 284:

• this pattern is the asynchronous cousin to the well-known Observer pattern.

Service Locator

• Similar to singleton, useful for abstracting access to things that are needed game-wide (like audio or logging).

· Chapter 05 - Optimization Patterns

Data Locality

• Organizing your data in memory to take advantage of CPU cache.

Dirty Flag

• aka: Dirty bit - for synchronizing or (deferring) calculation.

Object Pool

page 361:

• This looks a lot like the Flyweight pattern. Both maintain a collection of reusable objects. The difference is what “reuse” means. Flyweight objects are reused by sharing the same instance between multiple owners simultaneously. The Flyweight pattern avoids duplicate memory usage by using the same object in multiple contexts.

Spatial Partition

page 365:

• For a set of objects, each has a position in space. Store them in a spatial data structure that organizes the objects by their positions. This data structure lets you efficiently query for objects at or near a location. When an object’s position changes, update the spatial data structure so that it can continue to find the object.

page 380:

• Grid

• Quadtree

• BSP

• k-d tree

• Bounding volume hierarchy

• Each of these spatial data structures basically extends an existing well-known data structure from 1D into more dimensions. Knowing their linear cousins will help you tell if they are a good fit for your problem:

• A grid is a persistent bucket sort.

• BSPs, k-d trees, and bounding volume hierarchies are binary search trees.

• Quadtrees and octrees are tries.