Game Programming Patterns

PROBLEM

Input code calls jump() and fireGun() directly. No rebinding buttons, no AI driving the same actor, no taking a move back.

PATTERN

Turn the call into an object you can keep in a variable, hand to any actor, queue, log — and undo.

• Rebindable input: each button holds a command.
• Player and AI emit the same commands. Demo mode for free.
• Undo / redo: undo() plus a history list.

class Command {
public:
  virtual ~Command() {}
  virtual void execute() = 0;
  virtual void undo() = 0;
};

class MoveUnitCommand : public Command {
public:
  MoveUnitCommand(Unit* unit, int x, int y)
  : unit_(unit), x_(x), y_(y) {}

  virtual void execute() {
    // Remember where it was, so undo can go back.
    xBefore_ = unit_->x();
    yBefore_ = unit_->y();
    unit_->moveTo(x_, y_);
  }

  virtual void undo() {
    unit_->moveTo(xBefore_, yBefore_);
  }

private:
  Unit* unit_;
  int x_, y_, xBefore_, yBefore_;
};

PROBLEM

A forest of thousands of trees. Each has a mesh and bark and leaf textures — and they’re all the same ones.

PATTERN

Every Tree points at one shared TreeModel and keeps only its own position, height and tint.

• On the GPU: instanced rendering. The model once, the instances as a list, one draw call.
• Terrain tiles: a grid of pointers to three Terrain objects instead of an enum and a pile of switches.

class TreeModel {
private:
  Mesh mesh_;
  Texture bark_;
  Texture leaves_;
};

class Tree {
private:
  TreeModel* model_;  // shared by every tree

  Vector position_;   // the rest is this tree's own
  double height_;
  double thickness_;
  Color barkTint_;
  Color leafTint_;
};

// The world is a grid of pointers to flyweights.
Terrain* tiles_[WIDTH][HEIGHT];

int cost = world.getTile(2, 3).getMovementCost();

PROBLEM

An achievement for falling off a bridge. Do we really want unlockFallOffBridge() in the middle of the collision code?

PATTERN

The subject keeps a list of observers. Anyone can add or remove themselves; notify() walks the list.

KEEP IN MIND

• It’s synchronous. A slow observer blocks the subject.
• Lapsed listeners: forget to unregister and zombies keep getting called.
• Who’s listening is only known at runtime. Use it between lumps of code, not inside one.

void Physics::updateEntity(Entity& entity) {
  bool wasOnSurface = entity.isOnSurface();
  entity.accelerate(GRAVITY);
  entity.update();
  if (wasOnSurface && !entity.isOnSurface()) {
    notify(entity, EVENT_START_FALL);
  }
}

class Subject {
public:
  void addObserver(Observer* observer);
  void removeObserver(Observer* observer);

protected:
  void notify(const Entity& entity, Event event) {
    for (int i = 0; i < numObservers_; i++) {
      observers_[i]->onNotify(entity, event);
    }
  }

private:
  Observer* observers_[MAX_OBSERVERS];
  int numObservers_;
};

PROBLEM

Ghost, Demon, Sorcerer… and then GhostSpawner, DemonSpawner, SorcererSpawner. A second, parallel class hierarchy.

PATTERN

One Spawner holds a prototype monster and stamps out clones. A fast-ghost spawner is just a fast ghost.

VERDICT

Nystrom never found the class pattern the best answer: spawn functions, templates or first-class types do it with less code. Where prototypes do shine is in data →

class Monster {
public:
  virtual Monster* clone() = 0;
};

class Ghost : public Monster {
public:
  Ghost(int health, int speed)
  : health_(health), speed_(speed) {}
  virtual Monster* clone() {
    return new Ghost(health_, speed_);
  }

private:
  int health_;
  int speed_;
};

class Spawner {
public:
  Spawner(Monster* prototype) : prototype_(prototype) {}
  Monster* spawnMonster() { return prototype_->clone(); }
private:
  Monster* prototype_;
};
Spawner* ghostSpawner = new Spawner(new Ghost(15, 3));

THE ANOMALY

Every other chapter shows how to use a pattern. This one shows how not to.

WHY WE REGRET IT

• It’s a global variable in a nice class: harder to reason about, invites coupling, unfriendly to threads.
• It solves two problems when you have one. You wanted easy access to the log; now there can only ever be one log, and every call site says so.
• Lazy initialisation takes control away: the audio system loads on the first sound, mid-fight.

class FileSystem {
public:
  static FileSystem& instance() {
    // Lazy initialize.
    if (instance_ == NULL) {
      instance_ = new FileSystem();
    }
    return *instance_;
  }

private:
  FileSystem() {}
  static FileSystem* instance_;
};

// Fine, until the log file becomes a dumping
// ground and you want one log per domain:
Log::instance().write("Some event.");
// ...in every file that ever logged anything.

PROBLEM

A platformer heroine with isJumping_ and isDucking_. Every fix opens a new bug: air jumps, standing up in mid-air, jumping out of a dive.

PATTERN

A finite state machine: a fixed set of states, one at a time, inputs, and transitions between them.

• Simplest: an enum and a switch on it.
• The State pattern: one class per state, the heroine delegates to the current one.
• enter() and exit() actions; static or per-machine states.

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

class DuckingState : public HeroineState {
public:
  DuckingState() : chargeTime_(0) {}

  virtual void handleInput(Heroine& heroine, Input input) {
    if (input == RELEASE_DOWN) {
      // Change to standing state...
    }
  }

  virtual void update(Heroine& heroine) {
    chargeTime_++;
    if (chargeTime_ > MAX_CHARGE) heroine.superBomb();
  }

private:
  int chargeTime_;  // only means anything while ducking
};

// Heroine just delegates:
//   state_->handleInput(*this, input);

PROBLEM

The display reads the framebuffer while we’re still writing to it. Half a face, then the old one: tearing.

PATTERN

Two stages in one theatre: play scene one on A while the stagehands set up scene two on the dark B, then switch the lights.

• Read from current, write to next, swap() when done.
• Not just pixels: any state that’s read while it’s being changed — even by the code changing it.
• The swap must be atomic and quick. You pay with two copies in memory.

class Scene {
public:
  Scene() : current_(&buffers_[0]), next_(&buffers_[1]) {}

  void draw() {
    next_->clear();
    next_->draw(1, 1);
    // ...
    swap();
  }

  Framebuffer& getBuffer() { return *current_; }

private:
  void swap() {
    // Just switch the pointers.
    Framebuffer* temp = current_;
    current_ = next_;
    next_ = temp;
  }

  Framebuffer  buffers_[2];
  Framebuffer* current_;
  Framebuffer* next_;
};

PROBLEM

An event loop waits for input. A game can’t: the monster keeps chomping on your hero while you think. And it must run at the same speed on every machine.

PATTERN

Process input without blocking, update, render — and track the passage of time.

• As fast as it can: speed depends on the machine.
• Variable time step: keeps up, but non-deterministic and unstable.
• Fixed update, variable render: catch up in fixed steps, render when you can, interpolate the leftover.

double previous = getCurrentTime();
double lag = 0.0;
while (true) {
  double current = getCurrentTime();
  double elapsed = current - previous;
  previous = current;
  lag += elapsed;

  processInput();

  while (lag >= MS_PER_UPDATE) {
    update();
    lag -= MS_PER_UPDATE;
  }

  render(lag / MS_PER_UPDATE);
}

If you’re in a browser or an engine, the platform owns the loop and calls you back — the pattern is still there.

PROBLEM

A skeleton guard patrolling, two statues firing lightning: each one’s counters and flags end up as loose variables mushed together in the main loop.

PATTERN

The world keeps a collection of objects. Each has an update() that does one frame of its behaviour. Each frame, call them all.

KEEP IN MIND

• Slicing behaviour into frames means storing where you left off — State helps.
• Not truly concurrent: update order matters.
• Careful adding or removing objects while you walk the list →

class Skeleton : public Entity {
public:
  Skeleton() : patrollingLeft_(false) {}

  virtual void update() {
    if (patrollingLeft_) {
      setX(x() - 1);
      if (x() == 0) patrollingLeft_ = false;
    } else {
      setX(x() + 1);
      if (x() == 100) patrollingLeft_ = true;
    }
  }

private:
  bool patrollingLeft_;  // was a local in the loop
};

void World::gameLoop() {
  while (true) {
    // Handle user input...
    for (int i = 0; i < numEntities_; i++) {
      entities_[i]->update();
    }
    // Physics and rendering...
  }
}

PROBLEM

Spells for a wizard fighting game. Designers want to tweak them without a recompile, you want to patch them after ship, modders want to write their own — without crashing anyone.

PATTERN

An instruction set, encoded as a sequence of bytes. A virtual machine runs them one at a time, passing values on a stack.

• The Interpreter pattern’s tree of objects is flexible but slow. Bytecode is dense and linear, like machine code — but sandboxed.
• It grows like vines: keep it on a short leash.
• You’ll need an authoring tool — and you’ll miss your debugger.

class VM {
public:
  void interpret(char bytecode[], int size) {
    for (int i = 0; i < size; i++) {
      char instruction = bytecode[i];
      switch (instruction) {
        case INST_LITERAL: {
          // The value is the next byte in the stream.
          int value = bytecode[++i];
          push(value);
          break;
        }
        case INST_SET_HEALTH: {
          int amount = pop();
          int wizard = pop();
          setHealth(wizard, amount);
          break;
        }
        // ... GET_HEALTH, ADD, DIVIDE
      }
    }
  }
};

PROBLEM

A hundred superpowers, each written by someone different, each poking at audio, particles, physics, the renderer’s private layers. Duplicate code everywhere, coupling everywhere.

PATTERN

The base class offers protected provided operations and one abstract sandbox method. Subclasses only use what they’re given.

• Coupling moves into one place: the base class.
• A shallow, wide hierarchy — a point of leverage.
• Watch for the brittle base class; split helpers out (getSoundPlayer()) when it bloats.

class Superpower {
protected:
  virtual void activate() = 0;  // the sandbox method

  void move(double x, double y, double z);
  void playSound(SoundId sound, double volume);
  void spawnParticles(ParticleType type, int count);
  double getHeroZ();
};

class SkyLaunch : public Superpower {
protected:
  virtual void activate() {
    // Spring into the air.
    playSound(SOUND_SPROING, 1.0f);
    spawnParticles(PARTICLE_DUST, 10);
    move(0, 0, 20);
  }
};

// Every power: inherit, override activate(),
// build it out of the provided operations.

PROBLEM

Dragon : Monster, Troll : Monster, hundreds more. A designer emails: troll health 48 → 52. Check out, edit, recompile, check in, reply. Repeat.

PATTERN

Two classes and no inheritance: Monster and Breed. Every monster points at its breed; breeds come from data.

• A breed can construct its monsters (newMonster()) and control their memory.
• Breeds can inherit from a parent breed — at lookup, or copied down at load.
• Data is easy; behaviour per type is harder (pick from a fixed set, or Bytecode).

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

  Monster* newMonster() { return new Monster(*this); }
  int getHealth() { return health_; }
  const char* getAttack() { return attack_; }

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

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

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

{
  "Troll":        { "health": 25, "attack": "The troll hits you!" },
  "Troll Archer": { "parent": "Troll", "health": 0,
                    "attack": "The troll archer fires an arrow!" }
}

PROBLEM

Bjørn, a Danish baker in a platformer: input, physics, animation, rendering and sound in one 5,000-line class. Changing anything means knowing everything:

if (collidingWithFloor() && getRenderState() != INVISIBLE) playSound(HIT_FLOOR);

PATTERN

Slice the class along domain lines into components. The entity becomes a container that holds them, and the state they share.

• Swap one component: DemoInputComponent and the computer plays.
• Components talk through the container’s state, direct references, or messages.

class GameObject {
public:
  int velocity;
  int x, y;

  GameObject(InputComponent* input,
             PhysicsComponent* physics,
             GraphicsComponent* graphics)
  : input_(input), physics_(physics), graphics_(graphics) {}

  void update(World& world, Graphics& graphics) {
    input_->update(*this);
    physics_->update(*this, world);
    graphics_->update(*this, graphics);
  }

private:
  InputComponent* input_;
  PhysicsComponent* physics_;
  GraphicsComponent* graphics_;
};

GameObject* createBjorn() {
  return new GameObject(new PlayerInputComponent(),
                        new BjornPhysicsComponent(),
                        new BjornGraphicsComponent());
}

PROBLEM

Audio::playSound() sprinkled everywhere. It blocks while the sound loads; two enemies hit in one frame play the same wail twice as loud; and it runs on whichever thread called it.

PATTERN

Sending enqueues a request and returns at once. The receiver pulls requests later, when it suits it — push on one end, pull on the other, a buffer in between.

• A ring buffer: an array whose head and tail wrap around.
• The receiver can merge, delay or drop requests.
• Careful: the world changes before the event is handled, and loops of events don’t crash — they slosh.

void Audio::playSound(SoundId id, int volume) {
  // Merge with a pending request for the same sound.
  for (int i = head_; i != tail_;
       i = (i + 1) % MAX_PENDING) {
    if (pending_[i].id == id) {
      pending_[i].volume = max(volume, pending_[i].volume);
      return;
    }
  }

  assert((tail_ + 1) % MAX_PENDING != head_);

  pending_[tail_].id = id;
  pending_[tail_].volume = volume;
  tail_ = (tail_ + 1) % MAX_PENDING;
}

void Audio::update() {
  if (head_ == tail_) return;

  ResourceId resource = loadSound(pending_[head_].id);
  int channel = findOpenChannel();
  if (channel == -1) return;
  startSound(resource, channel, pending_[head_].volume);

  head_ = (head_ + 1) % MAX_PENDING;
}

PROBLEM

Physics, AI and UI all play sounds. AudioSystem::instance() at every call site ties each one to the concrete class and to how to reach it.

PATTERN

A phone book. Callers look the service up by its interface; the locator hides who provides it and how it was found.

• Null service: nothing registered? You get one that does nothing, not a crash.
• Decorated service: wrap the real one in LoggedAudio to log every call.
• Still global: use it sparingly. Pass the object in first.

class Locator {
public:
  static void initialize() { service_ = &nullService_; }

  static Audio& getAudio() { return *service_; }

  static void provide(Audio* service) {
    if (service == NULL) {
      // Revert to null service.
      service_ = &nullService_;
    } else {
      service_ = service;
    }
  }

private:
  static Audio* service_;
  static NullAudio nullService_;
};

// At startup, somewhere that knows the concrete class:
Locator::provide(new ConsoleAudio());

// Everywhere else:
Locator::getAudio().playSound(VERY_LOUD_BANG);

PROBLEM

CPUs got fast; RAM didn’t. Fetching a byte from main memory can cost hundreds of cycles. An accountant who can do a box in a minute, with a warehouse that takes a day to bring one.

PATTERN

Every read fetches a whole cache line — the pallet the forklift brings anyway. Keep data contiguous, in the order you process it, and use the whole pallet.

• Arrays of components, not pointers to them.
• Active objects packed at the front.
• Hot data apart from cold.

// Before: pointer, pointer, cache miss, cache miss.
for (int i = 0; i < numEntities; i++) {
  entities[i]->ai()->update();
}

// After: one flat array per component type.
AIComponent* aiComponents =
    new AIComponent[MAX_ENTITIES];
PhysicsComponent* physicsComponents =
    new PhysicsComponent[MAX_ENTITIES];

while (!gameOver) {
  for (int i = 0; i < numEntities; i++) {
    aiComponents[i].update();
  }
  for (int i = 0; i < numEntities; i++) {
    physicsComponents[i].update();
  }
  // ...
}

In Nystrom’s test: the same work, fifty times faster.

PROBLEM

A scene graph: a parrot on a pirate in a crow’s nest on a ship. Its world transform is the whole parent chain combined. In one busy frame all four move — recalculating eagerly does ten combines, the parrot four times.

PATTERN

Primary data (local transforms), derived data (world transforms), and one bit: set when the primary changes, checked and cleared when the derived is needed.

• Worth it when primary data changes more often than derived data is used, and can’t be updated incrementally.
• Set the flag on every change. Miss one and you use stale data.

void GraphNode::setTransform(Transform local) {
  local_ = local;
  dirty_ = true;
}

void GraphNode::render(Transform parentWorld, bool dirty) {
  dirty |= dirty_;
  if (dirty) {
    world_ = local_.combine(parentWorld);
    dirty_ = false;
  }

  if (mesh_) renderMesh(mesh_, world_);

  for (int i = 0; i < numChildren_; i++) {
    children_[i]->render(world_, dirty);
  }
}

The dirty parameter carries a parent’s dirtiness down, so moving a node never has to walk its children.

PROBLEM

Every wave of the wand spawns hundreds of sparkles. Allocating that fast is slow — and fragments the heap: fourteen bytes free in two seven-byte holes still can’t fit twelve.

PATTERN

Allocate the whole array up front. Each object knows if it’s in use; create() takes a free one, death hands it back.

• A free list threads through the dead objects’ own memory: constant-time create, no extra bytes.
• When it’s full: size it so it never is, don’t create, kill the least noticeable, or grow.
• Reused objects aren’t cleared — initialise everything.

class Particle {
  // ...
private:
  int framesLeft_;
  union {
    // State when it's in use.
    struct { double x, y, xVel, yVel; } live;
    // State when it's available.
    Particle* next;
  } state_;
};

void ParticlePool::create(double x, double y,
                          double xVel, double yVel,
                          int lifetime) {
  // Make sure the pool isn't full.
  assert(firstAvailable_ != NULL);

  // Remove it from the available list.
  Particle* newParticle = firstAvailable_;
  firstAvailable_ = newParticle->getNext();

  newParticle->init(x, y, xVel, yVel, lifetime);
}

PROBLEM

Real-time strategy: hundreds of units, and each needs to know who it’s close enough to hit. Comparing every pair grows with the square of the army.

PATTERN

On a 1D battle line you’d sort by position. In 2D, lay graph paper over the field: each cell keeps the units inside it, and a unit only checks its own cell and its neighbours.

void Grid::handleCell(int x, int y) {
  Unit* unit = cells_[x][y];
  while (unit != NULL) {
    // Handle other units in this cell.
    handleUnit(unit, unit->next_);

    // Also try half of the neighboring cells,
    // so no pair is checked twice.
    if (x > 0 && y > 0) handleUnit(unit, cells_[x - 1][y - 1]);
    if (x > 0) handleUnit(unit, cells_[x - 1][y]);
    if (y > 0) handleUnit(unit, cells_[x][y - 1]);
    if (x > 0 && y < NUM_CELLS - 1) {
      handleUnit(unit, cells_[x - 1][y + 1]);
    }

    unit = unit->next_;
  }
}