Intent

Speed searches by position in a Model Database.

Motivation

Almost all games need to search a Model Database quickly by location or region.

A few examples of spatial searches:

• the renderer (see View Pattern) needs to cull objects which can not be seen;
• a trigger (see Trigger) needs to determine if the player has passed over it;
• the UI needs to determine what object was clicked on by the mouse;
• the physics needs to detect collisions;
• a time bomb needs to determine what to damage.

Implementation

There are many implementations of spatial indices, each optimized for the particular kind of game. Without excellent implementations of these indices, whole categories of games could not exist.

Some common examples:

• Binary Space Partition Trees;
• X and Y Hashes with threaded collision resolution;
• Portals which link isolated spatial indices.

Indices must remain synchronized with the associated Model Database. It is common to see the spatial index implemented within the framework of a Model Database.

Spatial indices are often considered a View pattern optimization and become strongly associated with View code. Because the index is usually read-only by the View, but read-write by the Model, it should probably belong more to Model code than to View code.

Related Patterns

A Spatial Index is synchronized by a Model Database.

A Gateway is often used to simplify the synchronization.

Also Known As

Index Synchronization, Choke Point, Ethereal Void

Intent

Isolate database changes for index and/or client/server synchronization.

Motivation

It is critical that all Spatial Indices remain synchronized with their associated Model Database. Similarly, a client must remain synchronized with a server. Since several things can cause a change to a Model Database, it is best to isolate all changes to two calls: push and pop (a.k.a. insert / remove). This creates two states: "in world" and "out of world" which is also known as "in ethereal void".

This pattern gets its name from the way that all insertions and deletions are limited to one place like a physical gateway where all people must move through it to get in or out which allows you to control flow.

Implementation

A pop() method brings a model object out of the "void" and into the Model Database and its associated spatial index. A push() method removes the object from the database and index and into the void.

There are three basic operations:

• when an object moves, it pushes itself into the void, updates its position, then pops itself back into the world;
• when an object is created, it is created in the void then popped into the world;
• when an object is destroyed, it is pushed into the void first, then destroyed.

Some games have different world or index states. For example:

• an object may be allowed to be placed inside of another object (a container);
• an object may be attached to another object (a weapon, armor, etc.).

In these cases, there may be more than one implementation of pop(). For example:

• popIntoWorld( int x, int y); // pop into world
• popIntoContainer( Model &container ); // pop into container
• popOnto( Model &parent, Matrix4X4 &orient ); // pop onto another model

The push / pop choke point may also be used to synchronize a client to a server by transmitting all database changes from server to client.

It should also be noted that having one gateway of change allows multiple changes to be made simultaneously with minimal synchronization effect. For example, push(); move(); changeSize(); pop(); prevents an unnecessary update from happening around the changeSize() call.

Related Patterns

A Gateway simplifies the synchronization of a Spatial Index with a Model Database.

Gateways are often implemented inside of Model Database code.

Thanks To

Herman Miller, Tony Zurovec

Also Known As

Configuration, Global Info, Type Data, Prototype Info

Intent

Store information which is common to Model types.

Motivation

There is often a great deal of common information concerning types of objects. Artwork, basic statistics, etc. To avoid duplication, and to simplify editing, these are separated into a database.

Implementation

A Type Database is conceptually static data associated with a model sub-class. However, the type database is rarely implemented this way; instead, it is often an independent relational database indexed by "type number" and referenced by such in a model instance.

Examples of fields which might exist in a type record:

• prototype state (e.g. max hit points, strength, range, cost, etc.);
• size, extents, initial orientations;
• type categorization (e.g. offense, defense, mobile, fixed, human, alien, etc.);
• execution scripts (see Usecode);
• artwork (e.g. meshes, texture-map, sprites; these are frequently stored by reference to yet another database);
• sound effect handles or references;
• appearance maps (see Appearance Map).

Type lookup may be done directly to the type database. For example, a view object might reference getType (typeBeingSorted)->getSize() to find an extent in a sort loop.

Alternately, type lookups may be delegated to an object. For example: modelBeingSorted->getSize(). The delegated method allows a sub-class to override in strange cases. For example:

int Spaceship::getSize() {
    int size = getType()->size;
    if (shieldsUp) size *= 2;
    return size;
}

Type databases often contain tweaky constants which are adjusted for game play reasons near the end of a project. Also, these constants may be editable by the players or mission builders. Consequently, type data is often loaded dynamically from text files or similar human readable input.

Art importation is often closely associated with the type importation. It is common to see a compile-time tool(s) which handles both.

A type database is usually read-only after game initialization, but may be read-write in editor mode.

Type Databases occasionally implement Factories to generate specific Model or Controller objects on demand by either type number or type name. This is especially common in edit modes.

Related Patterns

Type Database is read-only by Model, View, and Controller.

Type Database may store global data for Appearance Map.

Type Database may act as a Factory for Model or Controller objects.

Also Known As

Renderer, Painter, Viewer

Intent

Render the visible Models given a P.O.V.

Motivation

Renderers are often the most custom part of any game; they often define the game's technology and determine the envelope of design. Thus, not surprisingly, extreme optimizations are common often at the expense of organization or maintainability.

Implementation

The View reads the Model Database via a Spatial Index but does not modify either. Thus, typically:

• Model is read-only by View;
• Spatial Index is read-only by View;
• View is invisible to Model and Spatial Index.

The communication between a Spatial Index and a View is often the determining factor in game performance and deserves great attention. Not uncommonly, the spatial index and the view are so intimately related that the index is considered View code. However, one may argue that a spatial index more properly belongs in the model domain due to its read-write status (see Spatial Index – Implementation).

Most View implementations translate a model "state" into an "appearance". For example, a model instance "orc1" is de-referenced and is found to be type==ORC_TYPE and frame==10. The View then finds an artwork pointer via type and frame and draws.

The translation from "state" to "appearance" often has exceptions which clot the render code (see Render Delegation and Appearance Map).

There are frequently more than one View implementation per game. For example, there may be a custom rear-view mirror in a driving game, or an overhead-view mini-map in a strategy game. However, there is usually one View implementation which predominates.

Related Patterns

Views renders Models that it looked-up in the Model Database via a Spatial Index.

Views often derive artwork pointers from a Type Database.

Views may choose to defer customized drawing via Render Delegation.

Views may translate a model's state to its appearance via an Appearance Map.

Also Known As

Overloaded draw

Intent

Pass-off special render cases to Model code.

Motivation

Generic View code often becomes clotted with special cases, especially near the end of a project. Render Delegation gets the special cases out of the View code and into Model subclasses.

Implementation

An example clot in View code:

if (typeToDraw==DARTH_VADERS_SHIP)
	drawSpecialShieldEffect();

To encapsulate these kinds of special cases, the View delegates the draw back to the Model. For example: objectToDraw->draw(x,y)

It is common for the view to do the transformation and sorting work and pass screen coordinates to the draw method of a model.

The view may choose to delegate only in certain special cases, often based on type data. For example:

if (getType(type)->delegateDraw)
    object->draw(x,y);
else
    drawSprite (getType(type)->sprite[frame], x, y);

One major drawback of Render Delegation is that the Model code must include all of the render interface, which may be substantial.

Applicability

Use Render Delegation when:

• you want to ensure reusability / encapsulation of the renderer;
• the View code becomes clotted with special cases;
• every model tends to have a different implementations of render.

Don't use Render Delegation when:

• there are only a few special cases and the cost (compile time, encapsulation) of including render interfaces in Model code is very high.

Related Patterns

Render Delegation passes draw commands from View to Model.

Render Delegation may be part of an Appearance Map.

Also Known As

State to Appearance Translation, Frame Mapping

Intent

Isolate Model state from Model appearance to minimize impact on controllers when art changes.

Motivation

Controllers are often complicated little state machines which interact with Models in very specific ways. It is common for this interaction to change the appearance of the Model, especially in animation controllers. Since art may change frequently (example: more frames are added to an animation) it makes sense to separate the state from the appearance.

Implementation

Without an appearance map, a controller is likely to change the "frame" of an animation directly. For example:

if (state == WALKING) {
    model.frame = WALK_START_FRAME + WALK_NUM_FRAMES * (WALK_DURATION / dt);
}

In this case, if the animation is changed, the three constants WALK_XXX need to be updated and the game recompiled for the change to take effect.

An appearance map eliminates these constants and replaces them with a lookup. Typically, a table is loaded at game initialize time which encodes the translation from state and delta time ("state") to frame ("appearance").

A game with a built-in editor will probably allow this table to either be edited directly or at least to be re-imported on command.

Related Patterns

Appearance Maps translate Model state into an appearance for the View.

Thanks To

Jim Greer

Also Known As

Process, Mini-process

Intent

Update a Model's state based on circumstance.

Motivation

Controllers implement the rules of a game. They determine how objects behave given a circumstance, and isolate these rules from the objects themselves. This makes both the controllers and models more reusable and maintainable.

Implementation

Controllers relate to Models and Views as follows:

• Models are read-writeable by Controllers;
• Controllers are created and destroyed by Models, but are otherwise invisible;
• Views are invisible to Controllers and vice-versa.

Controllers are often associated with only one model instance. For example: animation, AI, pathfinding. In these cases the controller instance is usually created and destroyed synchronously with the associated model.

Some Controllers inherently have more than one associated Model. For example: multi-body physics, target tracking (heat seeking missiles, etc.). These controllers often maintain Model references which must be notified / garbage collected when the referenced object dies. This is called the "model death problem". The creation and deletion of these multi-owner controllers is usually done by some primary owner.

Controllers are often implemented as "processes" in a mini cooperative multi-tasking kernel (see Mini-kernel), but may also be implemented as "hard wired updates" in the main loop, especially for large multi-model controllers like physics.

Some simple Controllers are stateless. For example, a homing missile controller may just compute the direction to the target and apply force as necessary. Most controllers, however, are state-aware. For example, an animation tracks progress through the animation and changes states accordingly; e.g. if (frame > 10) state = STOP_WALKING.

State-aware controllers often become significantly complicated with large switch statements (see Controller State Machine).

Related Patterns

Mini-kernels aggregate Controllers, giving each controller some time to work.

Controllers modify Model's states.

Views may translate Model state with an Appearance Map.

Complicated state-aware controllers may use a Controller State Machine.

Also Known As

Controller Database, Process List, Controller List, Game OS

Intent

Provide each Controller with a chance to execute once per game frame.

Motivation

Without a mini-kernel, Model objects are typically updated by a set of hard-wired controller functions called from the main loop. For example:

void updateWorld() {
for( int i=0; i<numTanks; i++ ) {
    if( tanks[i] ) {
        updateTankPhysics( tanks[i] );
        updateTankAI( tanks[i] );
    }
}
for( i=0; i<numSoldiers; i++ ) {
    ... etc ...
}

This style of updating requires that any new controller be hardwired into the update calls, which reduces encapsulation and increases maintenance.

An operating-system-like method is needed where controllers can be created and removed dynamically as needed.

Implementation

A base controller class is created which is the super-class of all controllers. A list of controller pointers is maintained. Each game frame, the mini-kernel (called from the main loop) gives each controller a chance to execute by calling a virtual "update" method. This is a cooperative multi-tasking system.

For example:

class BaseController {
    virtual void update() = 0;
}

class MissileController : BaseController {
    Model &missle, ⌖
    virtual void update() {
        missile.pos += missile.vel;
        missile.vel += (target.pos – missile.pos).norm() * missAcc;
    }
}

void miniKernelDoAllControllers() {
    foreach controller in list { controller.update(); }
}

Note that all controllers update calls are non-blocking; they are expected to do some actions quickly and return control back to the mini-kernel.

It is often necessary to ensure that some controllers always run before others. For example, user interface may need to run before animation or physics to ensure that mouse clicks are interpreted with respect to the correct frame of reference. This can implemented with a priority number for each controller; the mini-kernel either sorts the controller pointers once per frame by priority or ensures that the list remains in sorted order.

The mini-kernel may be implemented to handle some common controller bookkeeping. For example, the kernel might update a counter in each controller so that the controller can determine its age quickly. Or, the kernel might monitor per controller sleep fields to simplify timing much like the sleep() function in Unix or Win32 [RICH94].

Controllers are frequently "attached" to Model objects though some sort of dependency system. This dependency ensures that the controller is garbage collected along with the associated model when it dies. This may involve some cooperation on the part of the mini-kernel.

Related Patterns

Mini-kernels are aggregations of Controllers.

Thanks To

Tony Zurovec

Intent

Track an old and new state for multi-Model Controllers.

Motivation

Some Controller systems (for example, collision physics) need to track the state of several objects simultaneously and it must be ensured that they always read the same time step state for each Model instance.

If double buffering is not used, then as the physics system traverses the Models, it will become "confused" when it reads a state which has already been updated, thus using a new state instead of an old state.

This is analogous to a variable swap. int temp = a; a = b; b = temp; Without the temp variable, a = b; b = a; would cause a==b always.

Implementation

The necessary state information is typically isolated into a separate structure. For example:

struct PhysicsState {
    Vec3 pos,vel,angles,angVel,forceAccum,torqueAccum
};

Two instances of this class are combined into either the controller or model, often in a two element array. A global or local variable is used to flip between the two states using an accessor method.

For example:

class Model {
    PhysicsState states[2];
    PhysicsState getOldState() { return state[ globalFrame   &1]; }
    PhysicsState getNewState() { return state[(globalFrame+1)&1]; }
};

Related Patterns

Controller

Thanks To

Chris Hecker [HECK]

Also Known As

Eggs

Intent

Provide a simple mechanism for building geometric game puzzles.

Motivation

Many games, especially adventure games, have a variety of puzzles oriented around movement of the player character. For example: switches, traps, secret doors, mines, guards, etc.

A simple mechanism is needed which allows the game designer to create these puzzles without resorting to specifying coordinates or other programatic solutions.

Implementation

A trigger "dummy object" is created which automatically instanciates a controller when it is inserted into the world database. This controller checks for some "trigger condition" (for example, if the player character is within a certain distance) each game turn and causes something to happen when the condition is satisfied. Thus, a trigger is analogous to an "if statement" which runs each game frame.

One versatile and clever implementation of triggers is "detect, broadcast, respond". For example, imagine a game puzzle which involved darts flying out of a wall when the player character steps in a certain area. To implement this, a "detect trigger" is placed in the appropriate place and its bounds are set accordingly. Furthermore, the game designer specifies a "broadcast message" which is to be issued when the condition is satisfied. In this case, suppose the message is: "shoot darts". When the game runs and the condition is satisfied (the player character steps into the bounds of the trap), the "broadcast" is implemented by searching the local area for other triggers and passing the "shoot darts" message to each. Some of these triggers may respond to the message, other ignore it. In the "darts" example, two shooting "response triggers" would be placed into the world and would have been instructed to activate (shoot darts) when they received the "shoot darts" message.

Although somewhat limited, a simple trigger system can be surprisingly rich in behavior and is very easy for game designers to learn and use (certainly much simpler and more flexible than custom code or script to do the equivalent). They are also useful for games which allow end users to build their own levels due to their great simplicity.

The properties of triggers (bounds, messages, actions, etc) are usually specifyable in edit mode, and may be visible in debug / edit mode.

Some advanced trigger systems may include "predicates" such as "only if flag X" or other such conditions. In the extreme, a scripting language (see Usecode) may be used to specify the "detect" and "response" criteria.

Related Patterns

Trigger are a special kind of Controller, associated with a special kind of Model object.

Triggers can work to augment or even replace Usecode scripts.

Thanks To

Gary Scott Smith, Herman Miller, Tony Zurovec

Intent

Track a complicated state process with a controller.

Motivation

Many Controllers are very complicated state machines which involve convoluted state transitions as circumstances progress and in response to events. Animation is the canonical example – both time and user input effect the state transitions of animations, often with many special cases and subtle complications.

Implementation

A Controller subclass is created which contains the list of all state variables. For example, and animation might have: currectFrame, currentAnim, lastFrameTime, etc.

The process virtual of the controller contains a switch on some primary state. For example:

void Animation::doProcess() {
    switch( animState ) {
        case RUNNING_STARTING:
        case RUNNING:
        case RUNNING_STOPPING:
        ...

Each state updates and checks for transition conditions. For example, RUNNIG may check to see if it is at the end of the cycle, if so, restart it. It might also check to see if the mouse button is still down, if not, change to RUNNING_STOPPING.

State machines can become very complicated and difficult to maintain using this technique. One alternative is to use function pointers and setjmp/longjmp. See [ZS1] for a sample implementation of this technique.

Related Patterns

Contoller, State [GoF2]

Also Known As

Scripts, Imbedded Languages

Intent

Create a simple and safe imbedded language with which game designers and (potentially) end-users can build game logic.

Motivation

Many game problems are inherently algorithmic. However, it is often desirable to allow designers and customers to create this logic without recompiling the game. Script languages are Interpreters [GoF3] which are designed to simplify the implementation of game specific puzzles or features.

Implementation

A language is designed with a small library appropriate for the game. A parser is typically implemented which translates this code into virtual machine code which is then loaded into the game and interpreted. Alternatively, the game may choose to implement the parser directly into the game and avoid the compilation step; this is called "immediate execution".

It is a common problem with Usecode implementations that they become very unwieldy. They have a tendency to grow and grow in scope until the problems they are solving might as well have been implemented in the native language (C, for example). If Usecode is used, it is best to keep a very limited scope on its implementation. When more sophisticated logic or libraries are needed, revert the native language (a common solution is to use dynamiccly linked libraries with standard interfaces for this).

Related Patterns

Controller, Interpreter [GoF3]

Thanks To

Richard Garriott. Name evolved at Origin from "usable" objects and their associated scripts in the Ultima series.