Coroutines as State Machines

Alex J. Champandard on June 13, 2007

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 enough for game AI.

The main challenge to implement coroutines in such a low-level language is to break up the code so that execution can be suspended and resumed at pre-defined locations. It should be easy to resume from the previous execution point without too much hassle.

Using an implementation with one single entry point (like these Tasks with an execute() function) forces the person implementing a custom task to maintain the execution point so the next call can resume where it left off. This can be done either:

  • With simple conditional statements that check what work has been done. They take the form of a chain of if / else statements, or a switch in C++.

  • By using a lookup table to jump to the right location. In this case, each part of the coroutine must specify the next section of code by storing an identifier in the lookup table.

Either way, the coroutine can be understood as a finite state machine. It’s a rather common pattern used when implementing tasks, so it can be a good idea to provide this functionality by default.

A good place to put the state machine management is inside the central scheduler, since it is already responsible for managing tasks. The only thing that needs to change is the Task API; it needs to provide the next task that should be executed on the following update. The scheduler simply stores this as the coroutine’s current position.

class Task
    virtual Task& execute() = 0;

Having each part of the coroutine as a Task object is quite flexible, but it’s not the most efficient approach. Using fast delegates combined with this removes the overhead of having many small objects for a single coroutine. Each part of the coroutine can simply be a delegate that references shared memory.

The only problem with using fast delegates for such a state machine in C++ is recursive declarations — which causes typedefs to not compile. The solution is to introduce a separate helper class:

struct Task;
typedef FastDelegate()> TaskDelegate;

struct Task
    Task(TaskDelegate pp) : p( pp ) {}
    operator TaskDelegate() { return p; }
    TaskDelegate p;

The only remaining issue caused by exposing such a state machine is what to do with the return status codes that tasks normally return. A solution is to have a set of constant tasks that are NullObjects, which the scheduler understands as special return status codes.

Using such mini-state machines makes it particularly easy to build behaviors as combinations of tasks, and things like the typical start(), update(), stop() are optional but always sequenced in the most efficient way (without overheads for empty virtual function calls).

Discussion 0 Comments

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!