Book Summary: Game Programming Patterns – Behavioural Patterns

This is the fourth post of the Game Programming Patterns book summary series. The first and second posts are about some selected patterns from the Gang of Four book. The third one covers the Sequencing Patterns. This post outlines the Behavioural Patterns section.

Book Summary: Game Programming Patterns

Behavioural Patterns

These patterns can be used to define what an entity in the game world can do.

Bytecode

When I try to summarise Bytecode, I feel like there is too many useful information that I can’t just not mention them here, so it turns out to be three times longer than the other chapters.

Sometimes, we need to model a large number of complex behaviours. We might need something that resembles a pseudo-code. This pseudo-code can be used not only by the game programmer, but also by the game designer, the outside contractor content creators, or even a modder. This pattern is particularly useful if the person designing the behaviour (the game programmer) is not necessarily the one who programs (the tools programmer).

The DIY implementation:

Create an API. Define which of our game library functions are available to be called from the interpreted codes.
Create an interpreter. Map our game library functions into the actual bytes. We can do this by a simple switch in C#.
Create a virtual machine. We can use stack-based or register-based machine. Don’t forget to sandbox our VM. Define hard limits on execution time, stack size, and the number of executions.

Keep in mind:

We need to have a tool to author the Bytecode. We can:
- Use an existing scripting language. We just have to define the API without needing to create our own interpreter and VM. For example, we can pick:
  - Lua (moon, Portuguese) with Moonsharp.
  - An existing visual scripting tool.
- Choose the DIY way. If we don’t like the complexity of Lua, we can make our own simpler syntax.
Debugging is hard if we don’t author the debug tool. If we pick an existing scripting language, an available debugger would be a plus.

Design decisions:

How do we generate our byte code?
- Compile a text-based script. It’s unfriendly to the non-programmers. We also need to make our own syntax, parser, and handle syntax errors. The good thing is text files are easier to port to other platforms, just remember to use the correct encoding for the files.
- Provide a GUI to the designer. It’s unfriendly to the programmers ~~because GUI work means having to think about the user using the user interface~~. But we get to prevent errors at creation time because we design the UI to give only checked options to the user. However, porting takes relatively more work. The GUI is its own program. It must be ported into the working platform which generates code for the target platform.
How does our VM work? We divide them by how instructions access the memory.
- Stack-based. The byte codes can only see the top stack to find arguments so the number of pop/push calls are relatively larger than the register-based machine. But, the implementation is simpler because our VM only have to handle one data at a time.
  - Pushdown automata. We can simply use a single stack to walk through the interpreted byte code instructions. This implementation is not Turing complete, though.
  - Turing machine. Add another stack to save what the first stack has been popping so we can simulate moving forwards and backwards through the instructions ‘tape’.
- Register-based. Add an address/register info to each byte codes. The information allows random access of the stack’s content. We can jump to instructions or read arguments while having less number of instructions. However, the size of our byte code has to grow to accommodate the additional info. It’s also more complicated to implement the VM because it has to process more data at a time.
What kinds of instructions does the VM accommodate?
- External primitives. They are direct calls to our game APIs.
- Internal primitives. Store data internally in the VM and reuse them.
- Control flow. If else while end instructions.
- Abstractions. Add an ability to save data in the VM with a structure, e.g. lists, tuples. We can also define an internal function calls with their own return calls.
If we can store values in the VM, how are those values represented?
- Single data type. We can make our data all strings or all floats, for example.
- Tagged variant. The data has a tag and a value. We can use an enum to interpret the type tags.
- Untagged union. Bytecodes can represent any type; another Bytecode is needed to interpret them. This is how statically typed language works–type is defined at compile time. It’s compact and fast but unsafe. The compiled byte code can be modified to jump/read/write maliciously so we need to verify them before running them.
- Interface. It’s like the untagged union but with polymorphism. First, we define an interface. The interface handles how the bytes codes can be read as a type–with a getValue()function or converted into a certain type–with a parse<Type>()function. Then, create some implementation classes for the types we want. E.g. a Byte class is responsible to create Byte objects and convert them into Integer objects, or an Integer class to read integers that can be converted into Enum objects. This way, it’s open-ended so we can add more types. But every getValue()call is virtual method call so it might be inefficient.

Subclass Sandbox

In this case, we need to create many classes with similar behaviours but not exactly the same. We want to minimise the coupling of these classes because those similar behaviours call the same classes. To do that, we have a base class provides the protected functions which call the classes so that the subclasses don’t have to. These protected functions can’t be too specifically made for certain subclass so that other subclasses can use them.

Keep in mind that the base class will be coupled to any class with which the sub-classes need to communicate. The Component pattern is a good alternative if the UML representation of the base class starts to look like a sea urchin.

Design decisions:

Which functions are in the base class? Which ones are in sub-classes?
- Too few sub-classes uses the base class’s function? Move the function to the sub-class.
- Sub-class modifies the data of something? Move the function to the base class.
- A forwarding call might feel like redundancy. But, if the other functions in the family are in the base class; for consistency, forwarding is warranted.
In the base class, who owns the functions?
- The base class. A simple implementation for simple cases.
- Other instance that is owned by the base class. This instance turns into something like a Component object of the base class. This is good for decoupling a family of functions from the base class. We can use a Service Locator to get the instance.
How do the base class get the data for the sub-classes to use?
- Two-stage initialisation. Make a static method that is responsible to call the constructor and then an init function–which create a new data object.
- Make one static object. It’s like a Singleton but protected. It’s still can’t play nice with concurrency.
- Use a Service Locator.

The Subclass Sandbox pattern is similar to the Facade pattern in terms of providing an API to minimise coupling. In the Template Method pattern, the roles of the sub-class and the base class are reversed. The Template Method is owned by the base class which is–simply put, an interface but for methods/functions.

Type Object

Type Object pattern is to be used when the number of types is not exactly known, i.e. character types in our game world that might be added later in the updates. The class contains the shared attributes of the possible types. Then, an instance defines a type. The object that needs to be typed saves a reference to the instance. That way, we can add/modify types without compiling new code because types are represented by instances instead of classes.

Keep in mind:

We need to keep track of all the instantiated Type Objects. We need to be able to pick a from that pool of Type Objects when we instantiate the typed object. It’s better to also make sure the Type Objects are always in the CPU cache–use the Data Locality pattern.
While it’s easier to share values, it’s harder to share behaviours.
- Use anything that simulates a first-class function, then have the Type Object store their references. E.g. Command pattern, C# delegates.
- Use Bytecode to define the typed behaviours. In this case, the type is data, so are the behaviours.

Design decisions:

The reference to the Type Object; encapsulated vs. exposed:
- Encapsulated. The complexity of the Type Object design pattern is hidden. From the outside, it’s just an object with a type. We may choose to selectively override Type Objects behaviours. But, we need to write more code to encapsulate the Type Object’s behaviours even if it’s simple forwarding.
- Exposed. It’s good for quick prototyping. It will become hard to maintain because all Type Object’s API is accessible from the typed object and Type Object’s instance is not secure from modification outside the scope of the typed object.
How the typed objects are instantiated:
- Pass Type Object in the typed object constructor. The list of Type Object instances is already handled by another class.
- The Type Object’s class has a Factory Method for typed object instantiation. The list of instantiated Type Objects is maintained by the Type Object’s class itself.
Can a typed object change its type?
- No. Simple code and debugging.
- Yes. Typed objects are allowed to change the internal Type Object reference, hence all the codes using the reference must handle the type-change feature.
Inheritance support:
- No. Simple code but there may be code and data duplication.
- Single inheritance. Forward get/set functions of the inherited values to the parent. If the shared values are designed to be immutable, we can just simply copy them at instantiation. We can have duplication but only at run-time. Single inheritance is still fairly simple to code because we only need to handle get-set forwarding/copying attributes from a single Type Object.
- Multiple inheritance. Data duplication is minimised most effectively but the code must implement get-set forwarding/copying attributes from multiple Type Objects which may have conflicting attributes.

The Prototype pattern may answer the similar problem of having an unknown number of objects share the same attributes. Type Object is similar to Flyweight in terms of data sharing, but Type Object is more about the logical organisation instead of optimisation. It is also similar to the State pattern in its ways of delegation. But the use of the State pattern implies there will be inputs changing the state, while the Type Object pattern is intuitively more unchanging.

That’s all for the Behavioural Patterns section. The next section to be summarised is Decoupling Patterns–that is available here.

A Not-Too-Secret Diary