Game Programming Patterns by Robert Nystrom
November 2, 2014
Publisher: Genever Benning
ISBN: 978-0990582908

"Game Programming Patterns" provides a systematic description of selected patterns from the Gang of Four book and how they apply to game programming as well as other patterns grouped into four categories: Sequencing Patterns, Behavioral Patterns, Decoupling Patterns, and Optimization Patterns. Keep in mind that each time you use a pattern, you will likely implement it differently.

Notes

Engineering challenges encountered in game programming:

  • Time and sequencing are a core part of a game's architecture.
  • Development cycles are highly compressed.
  • Multiple programmers need to be able to rapidly build and iterate without interfering with each other.
  • Many pieces of software have to interact with each other.
  • Performance is critical.

A good design is about how easily we can accommodate changes. Implementing changes is easier when pieces of software are decoupled, i.e. when one piece can be understood and changed without touching another piece. Maintaining a good architecture requires time, effort, and discipline. It's a trade-off: Do I really need this abstraction? Will I ever use this extensibility point? Keeping things simple may be a helpful guidance in finding the trade off. Try to write code that is easy to understand. Note that writing simple code does not necessarily mean it would take less time to create it.

Game development requires iteration and experimentation. It means that development speed is critical. Prototyping comes handy when we only need to test some idea. It's important to throw away the prototype or re-write it once we are done with testing.

Elegant solutions are usually general: a small bit of logic that covers a wide range of cases.

The following Gang of Four patterns are presented:

Command Pattern

  • Encapsulates a request as an object.
  • An object-oriented replacement for callbacks.
  • Decouples the producer of commands from the consumer.
  • Commands can be placed in a stream by the producer and sent over the network.
  • The Command pattern is a way of emulating closures in languages that don't have them.
  • When you have an interface with a single method that doesn't return anything, there's a good chance it's the Command pattern.

Examples

  • Configuring input and passing in an object we want to control (an actor). In this case, we abstract the command from the actor it modifies i.e., we can apply the command to any actor we pass.
  • Undo and redo operations. In this case, we bind the command to the actor i.e., our command applies to a specific object.

 

Flyweight Pattern

  • The Flyweight pattern can be useful when you need a lot of objects that share the same chunk of data.
  • Each object has the instance-specific state (the extrinsic state) as well as references to shared data (the intrinsic state).
  • Flyweight objects are almost always immutable.
  • This pattern has actual hardware support in DirectX and OpenGL called instanced rendering. It operates on two streams of data. The first stream contains common data (meshes, textures, etc.). The second stream is a list of instances and their parameters.
  • The Flyweight pattern is about efficiency. It saves memory as well as time to push data over the bus to the GPU.
  • One use of the Flyweight pattern is managing a tiled terrain with multiple tile types.
  • The Flyweight pattern can be used with the State pattern to reuse the same state instance in multiple state machines.

 

Observer Pattern

The subject

  • holds a list of observers that are interested in this subject
  • announces that something happened by sending notifications to all observers from the list; sending a notification is just a method call

The observer

  • adds itself to the subject's observer list
  • handles incoming notifications

Adding and removing observers without involving dynamic memory allocations

Another approach is to use a linked list of observers rather than the list located in the subject. The subject holds a pointer to the head of the linked list as well as methods to add and remove observers. The observer itself holds a pointer to the next observer. The subject walks the linked list of observers and sends notifications. 

Destroying subjects and observers

Problem

  • When you delete an observer, the subject will have a dangling pointer to deallocated memory.
  • When you delete a subject, the observer will still "think" it is going to receive notifications.

Solution

  • The observer needs to unregister itself from any subjects before it gets deleted.
  • The subject needs to inform all observers before it gets deleted. This allows observers to unregister themselves from the subject.

The lapsed listener problem

  • Occurs when a "destroyed" subject retains a reference to an observer (a listener) which prevents the subject to be garbage collected. A solution is to always unregister the observer from the subject when we no longer need to listen to it.

The Observer pattern

  • synchronous
  • no memory allocation for notifications
  • no queuing
  • backed in C# by the event keyword
  • although the subject communicates with the observers, it is not coupled to them

 

Prototype Pattern

  • an object spawns other objects (prototypes)
  • an object clones the class of the prototype as well as its state

Examples:

  • A "Monster Spawner" which spawns prototypes of monsters:

Monster* ghostPrototype = new Ghost(15, 3);
Spawner* ghostSpawner = new Spawner(ghostPrototype);

  • A better solution is to use a spawn function rather than separate spawner classes:

Monster* spawnGhost()
{
    return new Ghost();
}

  • A spawner using C++ templates:

Spawner* ghostSpawner = new SpawnerFor<Ghost>();

  • An example of defining types and creating objects in JavaScript - a prototype-based language (though JavaScript does not have a core prototype-based language operation of cloning).
  • An example in JSON of using prototypes and delegation for reusing data. 

 

Singleton

  • restricts a class to one instance
  • provides a global point to access the instance
  • creates the instance at runtime using lazy initialization i.e. the instance is created only when the singleton is first accessed
  • singletons can be subclassed

Downsides

  • a singleton is basically a global variable; it is global state encapsulated in a class
  • encourages coupling
  • not concurrency-friendly (a consequence of being a global variable); it may lead to deadlocks, race conditions, etc.
  • does not provide full control over the timing of initialization
  • does not provide control over memory allocation

Alternatives

  • pass objects as parameters (you can use dependency injection)
  • get objects from the base class
  • get objects from a global object such as Game which represents the entire game state
  • get objects from a Service Locator - a class whose sole reason is to give global access to objects
  • to ensure single instantiation, use a static class or a static flag (isInitialized) to check at runtime if only one instance of the class is constructed
  • very often methods of a "manager"-like class can be included in the managed class itself

One limitation of a class with static members is automatic initialization - static members are initialized before main() is called.

Code examples of singleton implementation:

  • "classic" C++
  • C++11 (thread-safe initialization)
  • no lazy initialization; in this case, it's better to just use static functions instead

Term: cross-cutting concern - a piece of code scattered throughout a codebase such as logging

 

State Pattern

  • goal: to encapsulate all of the behavior and data for one state in a single class
  • each state can encapsulate and manage its own state-specific data

Step-by-step

  • define an interface for the state
  • for each state, create a class that implements the interface
  • create the state object (two ways):
    • if the state object does not have any instance-specific data use a single static instance (the Flyweight pattern)
    • if the state object has any instance-specific data create the instance when you transition to it
  • if needed you can initialize the state object and do clean up using methods such as enter() and exit()
  • delegate to the state object i.e., call the state methods that implement the interface
  • assign a different state object to a "current state" variable in order to change state

Finite State Machines (FSMs) 

  • the simplest machines in automata theory
  • FSMs can be in a fixed set of states
  • FSMs can only be in one state at a time
  • FSMs receives a sequence of inputs or events
  • each state has a set of transitions, each associated with an input and pointing to a state
  • FSMs are not Turing-complete; it means FSMs are not suitable for complex problems such as AI which uses behavior trees and planning systems
  • FSMs have no concept of history i.e., the previous state is lost; solution: pushdown automata

Concurrent State Machines 

  • the main class contains multiple references, each to a different state
  • useful when the states are unrelated

Hierarchical State Machines (HSMs)

  • based on an idea that a substate can have a superstate
  • when an event arrives and it's not handled but the substate, the event propagates to the superstate
  • HSMs can utilize class inheritance to implement the hierarchy; another implementation involves a stack of states
  • useful when the states are interdependent

Pushdown Automata

  • pushdown automaton utilizes a stack data structure to store the state and then recall it later
  • FSM vs. pushdown automaton: FSM has a single pointer to a state, a pushdown automaton has a stack of pointers with push and pop operations

An example of a simple FSM (it does not use State Pattern)

  • states are represented by enum values i.e., the state is just a single field
  • FSM is a switch/case statement
  • all code for each state is kept together in individual case blocks

Strategy vs. Type Object vs. State patterns:

  • Strategy decouples the main object from a portion of its behavior through delegating to another object.
  • Type Object makes a number of objects behave similarly by sharing a reference to the same type object.
  • State allows the main object to change its behavior by changing the object (the state object) it delegates to.

 

Sequencing Patterns

  • Double Buffer - Cause a series of sequential operations to appear instantaneous or simultaneous. 
  • Game Loop - Decouple the progression of game time from user input and processor speed.
  • Update Method - Simulate a collection of independent objects by telling each to process one frame of behavior at a time.

 

Double Buffer

  • A buffered class encapsulates two buffers: a next buffer and a current buffer.
  • Information is always read from the current buffer and written to the next buffer.
  • When the changes are complete, the buffers are swapped.
  • Double buffering can be useful in scenarios other than graphics. It solves a more general problem of accessing state while it's being modified.
  • You need to consider how the buffers are swapped (pointer swapping vs. copying data between buffers) and the granularity of the buffers (monolithic vs. a collection)

An example of double buffering in graphics:

  • A raw buffer class Framebuffer; methods: Clear, SetPixel.
  • A Scene class - a wrapper for Framebuffer; contains instances of a next buffer and a current buffer; methods: Draw, Swap (private, called in Draw), GetBuffer (always returns the current buffer).

An example of double buffering in AI: All actors appear to update simultaneously. The key is to fist perform updates and then swap the states. 

 

Game Loop

A game loop has two key pieces: non-blocking user input and adapting to the passage of time.

A rudimentary game loop (fixed time step with no synchronization):

while (true)
{
    processInput(); // process user input without blocking
    update(); // update the game state, usually AI and physics
    render();
}

A fixed time step with synchronization:

while (true)
{
    processInput(); // process user input without blocking
    update(); // update the game state, usually AI and physics
    render();

    sleep(); // wait for the next frame
}

A variable (fluid) time step:

(!!!) It makes gameplay non-deterministic and unstable.

double lastTime = getCurrentTime();
while (true)
{
    double current = getCurrentTime();
    double elapsed = current - lastTime; // determine how much real time passed since the last game update

    processInput(); 

    update(elapsed);
    render();

    lastTime = current;
}

A variable time step for rendering. A fixed time step for physics and AI:

double previous = getCurrentTime();
double lag = 0.0;

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

    // Lag indicates how far the game's clock is behind to the real world.
    lag + = elapsed; // update lag based on how much real time passed

    processInput();

    // Catch up using a series of fixed time steps.
    // This allows us to update the game at a fixed interval.
    // STEP is the granularity used to update AI and physics.
    while (lag > = STEP)
    {
        update();
        lag -= STEP;
    }

    // Take into account the residual lag that indicates
    // how far into the next frame we are.
    // The renderer knows each game object and its current velocity.
    render(lag / STEP); // lag is normalized to be between 0 and 1
}

In mobile games, you usually want to set an upper limit on the frame rate. If the game loop is done processing before that slice of time is spent, it will just sleep for the rest.

 

Update Method

  • The game world maintains a collection of objects. Each object implements an update method that simulates one frame of the object’s behavior. Each frame, the game updates every object in the collection.
  • Each entity in the game should encapsulate its own behaviour.
  • The game loop maintains a collection of objects and calls their Update methods.
  • Each object stores its state to resume where it left off each frame (the State pattern may be useful).
  • The order in which the objects are updated is significant. Double buffering eliminates this dependency if not desirable.
  • Be careful modifying the object list (i.e., when adding or removing objects) while updating.
  • Following an advice "Favor 'object composition' over 'class inheritance'", the Update method should be on the entity's components rather than on the entity itself.
  • Update Method vs. Component patterns: In the same way that the Update Method pattern lets you decouple game entities from each other in the game world, the Component pattern lets you decouple parts of a single entity from each other.
  • The more inactive objects you tend to have, the more useful it is to have a separate collection that avoids them during your core game loop.

 

Behavioral Patterns

  • Bytecode - Give behavior the flexibility of data by encoding it as instructions for a virtual machine.
  • Subclass Sandbox - Define behavior in a subclass using a set of operations provided by its base class; let derived classes implement themselves using derived protected (and likely non-virtual) methods.
  • Type Object - Allow the flexible creation of new "classes" by creating a single class, each instance of which represents a different type of object.


Bytecode

  • The Interpreter pattern is related to the Bytecode pattern. The book points several downsides of the Interpreter pattern.
  • Users author game's behaviour in some kind of high-level language that is then translated by a compiler to bytecode.
  • Bytecode is executed by a virtual machine.

Advises:

  • Decide on API you want to support. 
  • Turn the API into a set of elementary instructions.
  • Use a stack machine to handle instructions' parameters.
  • Expand your instruction set to allow composition through expressions.
  • Build an authoring tool for designers (preferably GUI).

 

Subclass Sandbox

A base class defines an abstract sandbox method and several provided operations. Marking them protected makes it clear that they are for use by derived classes. Each derived sandboxed subclass implements the sandbox method using the provided operations.

  • Create a base class with an abstract protected sandbox method and other protected methods that provide operations.
  • Create your classes and inherit them from the base class.
  • Implement the sandbox method by calling the protected methods of the base class.
  • This way your derived classes are only coupled to the base class rather than classes providing the operations.
  • You may want to create helper classes that encapsulate related operations. Instances of these classes can be returned by the base class's protected methods.

 

Type Object

Define a type object class and a typed object class. Each type object instance represents a different logical type. Each typed object stores a reference to the type object that describes its type.

  • Define a type object Type.
  • Define a typed object Thing and pass an instance of Type to Thing's constructor. Alternatively, you can use the Factory Method pattern to instantiate Type.
  • Delegate Thing's type-specific methods the Type's method.
  • You may want to implement inheritance mechanism (such as "copy-down" delegation) in your type object.
  • You need to decide if the type object is encapsulated or exposed.

 

Decoupling Patterns

  • Component - Allow a single entity to span multiple domains without coupling the domains to each other.
  • Event Queue - Decouple when a message or event is sent from when it is processed.
  • Service Locator - Provide a global point of access to a service without coupling users to the concrete class that implements it; Make objects globally available.

 

Component

A single entity spans multiple domains. To keep the domains isolated, the code for each is placed in its own component class. The entity is reduced to a simple container of components.

  • Keep state that needs to be shared between components in a container class. It gives the components an easy way to communicate without being coupled to each other.
  • Alternatively, the components can refer each other directly (it implies tight coupling between components) or send messages (components communicate with each other indirectly by routing the messages through the container object).
  • Create interfaces for your components. Make the container class accept these interfaces in its ctor.
  • Instantiate your container class by passing instances of concrete component classes.

 

Event Queue

A queue stores a series of notifications or requests in first-in, first-out order. Sending a notification enqueues the request and returns. The request processor then processes items from the queue at a later time. Requests can be handled directly or routed to interested parties. This decouples the sender from the receiver both statically and in time.

 

Service Locator

A service class defines an abstract interface to a set of operations. A concrete service provider implements this interface. A separate service locator provides access to the service by finding an appropriate provider while hiding both the provider’s concrete type and the process used to locate it.

Examples of services that may be accessed using Service Locator are logging and memory management.

Define a service as an interface.

Implement the service interface as a concrete service provider.

Create a service locator that ties the service and the service provider together.

 

Optimization Patterns

  • Data Locality
  • Dirty Flag
  • Object Pool - keeps track of already created objects; a technique for avoiding memory fragmentation
  • Spatial Partition

Other patterns

  • Factory - encapsulates construction of objects.
  • Component and Type Object patterns model different kinds of entities without representing them as classes.