Programming Tips for Game AI

Have you ever noticed how certain AI engines are easier to extend, and allow better debugging of the behaviors? Popular software patterns can be of great help when designing your architecture.

Implementing Modular Behaviors

If you need to start a new system, then it’s important to make sure your basic building blocks. Here’s one way to approach the problem in C++.

• A Low-Level Task Class

• A Scheduler for Tasks

• Observing the Scheduler

• Observers for Individual Tasks

Fast delegates are a C++ version of closures, which are basically functions bound to an execution environment. Delegates, in practice, are used as a lightweight implementation of interfaces, or as an elegant replacement for member function pointers. If you cringe at the thought of writing an interface around simple functionality, or get frustrated […]

Game logic is highly concurrent; not only does each entity in the world have its own main script, but there are typically many event handlers and latent behaviors that can run at the same time also. Luckily, there are many software engineering techniques to deal with this — in particular custom task schedulers.
This article […]

High-level logic is typically full of indirection, so performance suffers when it’s used heavily. This is the case in game AI when you start adding more behaviors; a constant overhead for virtual calls quickly takes its toll. After optimizing the typical bottlenecks (i.e. collision queries, animation, path-finding), the best thing you can do is optimize the virtual calls in your logic framework.

At GDC ‘07 there was a talk about behavior trees. It’s the type of AI that Halo 2 uses, as described by described by Damian Isla at GDC ‘05. The first part of this year’s talk was by Lauren McHugh who’s working on the AI for Spore — EA’s delayed mega-hit for […]

When you start adding more behaviors to your actors, you’ll find yourself creating many tasks with custom memory. For example, there would be some specific C++ code for PlayAnimation, FollowPath or UseObject.
To preserve some layering in your engine, your AI library cannot depend directly on game-specific behaviors. So all game behaviors must […]

Everything that happens in a virtual world is called an event. It’s represented as a data-structure that contains all the information needed to specify what, why, and who the event happened to. For actors to behave realistically, they must react and potentially adapt to every such piece of information.
An event loop is […]

Using the most basic type of memory pooling can improve the performance of your AI engine dramatically. However, your memory usage may not be optimal at first if you have one big memory pool.
Problems arise when pooling AI tasks because of the following:

All tasks are different and they have various sizes in […]

With many task hierarchies running in parallel, it can be impossible or undesirable to store everything in memory. It may be faster to allocate all the memory upfront for small trees, but in practice a lazy approach is better. However, because many tasks need their own custom memory (of different type and size), this policy causes lots of small memory allocations.

A scheduler is a great way to centralize the management of tasks. However, to get the most benefit out of it, you’ll probably need a combination of a couple tricks: a work queue and the command pattern. These give your AI engine the following benefits:

All the AI processing is handled in a […]

A major advantage of creating modular behaviors is reusability. So it’s important to reduce the cost of reusing these behaviors to a strict minimum, particularly in terms of memory usage. If two identical behaviors are running on two different actors, you can often do better than twice the memory consumption.
To get this […]

Most high-level languages support functions that can suspend their computation and later resume where they left off, commonly known as coroutines. However, despite being the standard language of choice for game developers, C++ doesn’t provide much in that department. Luckily, there are many ways to implement simplified coroutines — which is good […]

This post about the efficiency of fast delegates has been superseded by this article. It’s hard to make a fast delegate as efficient as an equivalent virtual interface (though it’s possible). The main benefit of fast delegates is their effectiveness at keeping software architectures simple, which indirectly can improve efficiency.
From the perspective of […]

Conceptually, making hierarchical AI is as simple as giving certain tasks other child tasks. This can be done using the composite pattern. Essentially, a composite task is just another task that can store pointers to its children.
Here’s how it can be done in C++:

class CompositeTask : public Task
{
public:
void […]

Having a way to monitor all tasks in a scheduler is particularly useful from a software architecture perspective. But behaviors most often are only interested in specific tasks rather than every one. Having an individual task observer is a great way to accomplish this.
These observers are most often used by composite tasks […]

There are many advantages to having a scheduler for managing tasks, notably allowing the AI to reason about other behaviors, as well as improved debugging and logging. The observer pattern is a good way to provide a generic hook for such features.
Observers are simple objects that get called when a specific things happens […]

Once you have a basic Task class to work with, you’ll be able to make behaviors by combining them together. However, you’ll quickly find it’s much easier to have all the tasks for an actor managed centrally. That’s what the scheduler is for.
Now, the implementation of this class can support as many […]

From a design perspective, it’s useful to think about concepts like behaviors for actors. But on the programming side you’ll need something more concrete. What’s the simplest primitive you’ll need in the source code to implement all the behaviors you have in mind? Usually, it’s a piece of code that can […]