C Coroutines for Game Entity State Management

State management is one of the more difficult aspects of game programming. Entities in your game must behave differently depending on their internal state, and may depend on the state of other objects as well.

There are several approaches to solving this problem – the naive approach being lots and lots of conditionals. Finite state machines approach the problem by objectifying state and state transitions. More recently, with the growing popularity of higher level languages like Lua, Python, and C#, coroutines have become a popular choice for mitigating the complexities of managing state.

I have implemented coroutines in C, and it’s turning out great. Here’s how to do it!

First, let’s look at a more traditional approach to state management – the ‘finite state machine.’ Each game entity might keep a state object that implements an interface like this:

class IState
{
	virtual void Enter() = 0;
	virtual void Update() = 0;
	virtual void Exit() = 0;
}

This rather simple approach should be familiar. It’s been my experience that managing state this way has a tendency toward ‘state explosion.’ Consider the following pseudocode:

// WalkTo state
void WalkTo::Update()
{
	while (!IsAtDoor())
	{
		WalkToDoor();
	}
 
	OpenDoor();
 
	actor->ChangeState(new WaitForDoor());
}
 
// WaitForDoor
void WaitForDoor::Update()
{
	while (!IsDoorOpen())
	{
		Idle();
	}
 
	actor->;ChangeState(new EnterDoor());
}
 
// EnterDoor
void EnterDoor::Update()
{
	EnterDoor();
}

Here, we want an actor to walk to a door, open it, wait for it to open, then walk through. To accomplish this, we have to write three states for the actor plus two (not shown) for the door. You can see how easily this can get more complicated.

Ideally, we want to be able to write something like this:

void Actor::WalkThroughDoor()
{
	while (!IsAtDoor())
	{
		WalkToDoor();
		Sleep();
	}
 
	OpenDoor();
 
	while (!IsDoorOpen())
	{
		Idle();
		Sleep();
	}
 
	EnterDoor();
}

If you have been working in Unity3D or UnrealScript, this might look pretty familiar. Both of these environments provide some kind of coroutine system, as does Lua, Python, and other higher-level languages.

If, however, we are writing our game in C or C++, we’re out of luck. Neither of these languages comes with built in support for coroutines. We could use threads, but synchronization would be a serious problem, and the number of coroutines you could have in your game (which potentially could be quite a lot) would be limited to the number of threads the OS supports. You could also use the dark magic that lurks in setjmp.h, but it is notoriously difficult to use across different platforms.

The solution I will present takes advantage of a somewhat controversial feature of the C switch statement: if a block in a switch is not terminated with a break statement, the flow of control will simply continue executing code in the next block. This anomaly, and the fact that it’s legal to jump into the middle of a loop in C were the basis of Tom Duff’s famous serial copy optimization, known as “Duff’s Device.”

An extremely detailed breakdown of this coroutine implementation by Simon Tatham can be found here. The implementation I arrived at is almost exactly the same as Simon’s, and looks like this:

#include 
 
#define COROUTINE_STATIC_BEGIN static int srcLine = 0; switch(srcLine) { case 0:;
#define COROUTINE_STATIC_END(value) } return (value)
#define COROUTINE_STATIC_END_VOID } return
#define COROUTINE_STATIC_YIELD(value) \
	do {\
		srcLine = __LINE__;\
		return (value); case __LINE__:;\
	} while (value)
 
#define COROUTINE_CONTEXT_PARAM void** contextParam
#define COROUTINE_CONTEXT_BEGIN struct ContextTag { int line; int sleepTimer; int sleepTime
#define COROUTINE_CONTEXT_END(x) }* x = *contextParam
#define COROUTINE_BEGIN(x) if (!x) { x = *contextParam = malloc(sizeof(*x)); x->line = 0;} \
								if (x) switch (x->line) { case 0:;
#define COROUTINE_END(value) } free(*contextParam); *contextParam = 0; return(value)
#define COROUTINE_END_VOID } free(*contextParam); *contextParam = 0; return
#define COROUTINE_YIELD(value) \
	do {\
		((struct ContextTag*) *contextParam)->line = __LINE__;\
		return(value); case __LINE__:;\
	} while (0)
#define COROUTINE_YIELD_VOID \
	do {\
		((struct ContextTag*) *contextParam)->line = __LINE__;\
		return; case __LINE__:;\
	} while (0)
#define COROUTINE_SLEEP(time) \
	((struct ContextTag*) *contextParam)->sleepTimer = 0; \
	((struct ContextTag*) *contextParam)->sleepTime = time;\
	do {\
		((struct ContextTag*) *contextParam)->sleepTimer += game.deltaTime;\
		COROUTINE_YIELD_VOID;\
	} while (((struct ContextTag*) *contextParam)->sleepTimer < ((struct ContextTag*) *contextParam)-&gt;sleepTime)
#define COROUTINE_STOP(value) do { free(*contextParam); *contextParam = 0; return (value); } while (0)
#define COROUTINE_STOP_VOID do { free(*contextParam); *contextParam = 0; return; } while (0)
#define COROUTINE_CONTEXT void*
 
#define COROUTINE_ABORT(context) do { free (context); context = 0; } while (0)

These macros set up the switch statement and the labels which act as the reentrance points of the coroutine. The macros come in two versions: regular and static. Static functions are those which don’t need any values saved between calls or that the data is function static. The regular version assumes that you have some data that needs to persist between calls. The context macors create a small heap-allocated object that stores your data.

One caveat with is code is that while it’s perfectly valid C and C++, you have to turn off Edit and Compile when compiling in Visual Studio. Studio does something strange with the __LINE__ macro when Edit and Compile is turned on.

With these macros, you can write code like this:

int myCoroutine(COROUTINE_CONTEXT_PARAM)
{
	COROUTINE_CONTEXT_BEGIN;
	int i;
	COROUTINE_CONTEXT_END(ctx);
 
	COROUTINE_BEGIN(ctx);
	for (ctx->i = 0; ctx->i < 10; ctx->i++)
	{
		printf("%d\n", ctx->i);
 		COROUTINE_YIELD_VOID;
 	}
 
	// Sleep for 30 ticks
	COROUTINE_SLEEP(30);
 
	printf("finished sleeping\n0");
 
	COROUTINE_END_VOID;
 }
 
 int callingFunc()
 {
	COROUTINE_CONTEXT context;
	context = 0;
 
 	do
 	{
 		myCoroutine(context);
	} while (context);
 }

Now, this might not be as pretty as, say, Unity3D’s C# coroutines or UnrealScript’s state blocks, but functionally it’s about the same. Using this coroutine implementation has sweeping implications on your C or C++ game code. Every actor in your game can behave as if it has its own thread, without the headaches of synchronization.

Try it out!

One Reply to “C Coroutines for Game Entity State Management”

  1. Hi Will, this is a neat way to do coroutines. I’m a little confused by the void * casting. It doesn’t seem to compile in c++, but I know the idioms for void casts in c++ is different than c. Thanks for posting this!

Comments are closed.