I’m sure many of you are familiar with concurrency. I’m going to tell you about a related concept – Asynchrony – that deserves your attention. Let’s start by defining four terms:
Concurrency is about multiple things happening over a period of time. Each piece of work proceeds towards completion without regard for the status of other work.
Parallelism is about multiple things happening at the same time. Each piece of work proceeds towards completion independently of other work, for example, in a separate thread.
Synchronization is about ordering the performing and completion of work. When you have a large set of work to perform but do not know the order in which it will complete, Synchronization is used to prevent things from interfering with each other, and to ensure that work completes in a predictable order.
Asynchrony is about being free to do other work while you wait for a thing to finish. You don’t know how long the thing will take, and it may never finish.
Let’s dive in to a real world example.
Late during development of one of my first industry projects, I was moved from content design to our ‘cinematics team’, in order to help get our cinematics back on schedule. Until that point, the work had been handled by an unlucky effects artist that somehow ended up with the job of writing scripts using C macros – and he was falling behind.
I quickly realized that not only were cinematics more complex than I had realized, but our approach to scripting them was deeply flawed. The cinematic system for this particular engine was built by our lead programmer, and while the code was well-written the design failed to address our basic needs for cinematics.
The core problem we dealt with was timing: Everything in a cinematic took time to happen, and the scripting system did not let us easily wait for those things to occur, or find out how long they would take. We coped by manually timing important events, and then padding those durations out in hopes that it would shield us from variations that occurred when the cinematic actually ran, but player freedom meant that things still went wrong. Later we were given some basic concurrency primitives, like threads, but at its core the scripting language still failed to make timing simple.
I’ll begin with a simple example of what one of those scripts looked like:
1 2 3 4 5 6 7 8 9 10 11 12 13 | BEGIN_THREAD(Camera) CameraLookAt(Position_Player_Start, Interpolation_None, 0), Wait(1000), CameraLookAt(Position_Player_Move_1, Interpolation_Linear, 1000), // ... END_THREAD BEGIN_THREAD(PlayerMovement) CharacterTeleport(Character_Player, Position_Player_Start), Wait(1000), CharacterMoveTo(Character_Player, Position_Player_Move_1), // … END_THREAD |
Over time as our needs changed, the scripting system grew until we had hundreds of different commands, all with their own timing rules. Every script had a handful of these threads, each one running for hundreds of seconds, every command carefully timed to line up. Building these scripts wasn’t hard due to a lack of tools: It was hard because we were given the wrong tools. Adding more tools to our scripting language didn’t fix the problem of the design being fundamentally wrong for our problem.
We spent a lot of time moving characters around, usually one or two at a time. The paths they took were fairly predictable, and they couldn’t do anything else while they ran. Combining this with our timing problems meant that if a character was moving, he couldn’t point or wave or turn around until a little bit after he stopped moving. This didn’t just make the cinematics hard to author – it made them look stilted, too. Moving a couple characters around would look something like this:
1 2 3 4 5 6 7 | /* God only knows where the players are, so let’s teleport them to where we expect them to be and hope that they don’t notice */ CharacterTeleport(Character_Player, Position_Player_Start), CharacterTeleport(Character_HeroicLeader, Position_HeroicLeader_Start), CharacterMoveTo(Character_Player, Position_Player_Destination), CharacterMoveTo(Character_HeroicLeader, Position_HeroicLeader_Destination), Wait(5000) /* Hand-picked value for how long it should take to move from A to B. Let’s hope the artists don’t change the level geometry! */ CharacterAnimate(Character_Player, Animation_Wave); |
The first key observation is that these scripts could benefit from being real, compiled code instead of a custom scripting language – nothing they’re doing is impossible in native C, and you get a debugger and compiler validation, instead of having to reinvent them yourself. For simplicity, I’m going to present my examples in C#. Let’s begin by translating that snippet directly:
1 2 3 4 5 6 7 8 9 10 11 12 13 | Character Player, HeroicLeader; Position Player_Start, Player_Destination, HeroicLeader_Start, HeroicLeader_Destination; Animation Animation_Wave; Player.Teleport(Player_Start); HeroicLeader.Teleport(HeroicLeader_Start); Player.MoveTo(Player_Destination); HeroicLeader.MoveTo(HeroicLeader_Destination); Thread.Sleep(5000); Player.Animate(Animation_Wave); |
This is pretty straightforward to implement if you know a little bit about threading. Some use of library primitives lets us kill the hard-coded sleep and make the behavior clearer:
Player.Teleport(Player_Start); HeroicLeader.Teleport(HeroicLeader_Start); WaitHandle.WaitAll( new [] { Player.MoveTo(Player_Destination), HeroicLeader.MoveTo(HeroicLeader_Destination) }); Player.Animate(Animation_Wave);
We’ve taken some implicit information – like how long a MoveTo command takes, and whether it blocks – and made it explicit by turning it into a value (in this case, a WaitHandle). While this is already an improvement on the script we started with, the idea of having your designers or artists writing threading code probably makes you nervous. Let’s step back and re-evaluate some of our assumptions to see if we can make this less complicated.
We’ve established that we need the ability to have multiple things happen at once, but doing this does not require the use of threads; the only time we ever need a thread is when we want to be performing multiple computations at the same time. In this specific case, what we want is to know when something in the game engine has finished – a character has moved from point A to point B, or an animation has finished playing. This doesn’t require threads or explicit parallelism, because our game engine is already going to be playing animations and moving characters around. What we want here is to be notified when our events of interest have occurred. Since C# has built in support for events, we can try using those instead:
void step1 () { Player.Teleport(Player_Start); HeroicLeader.Teleport(HeroicLeader_Start); var moved = new bool[2]; Player.MoveTo(Player_Destination).OnComplete += () => { moved[0] = true; if (moved[1]) step2(); }; HeroicLeader.MoveTo(HeroicLeader_Destination).OnComplete += () => { moved[1] = true; if (moved[0]) step2(); }; } void step2 () { Player.Animate(Animation_Wave); }
In this example, commands like MoveTo now return an object representing the movement command, with an OnComplete event. We can subscribe to the event in order to find out when the movement completes. We could write some utilities to automate things like registering a callback on multiple events to make this example code a bit smaller, but one problem still persists: We now have to split each ‘thread’ of our cinematic into multiple functions, and carefully wire up the callbacks so that one function always calls the next. If we make a mistake here, playback will just stop, and we won’t have any state to inspect in order to determine what happened.
One thing that would make this easier is support for co-routines. An important trait co-routines possess is that they cooperate: Execution passes explicitly from one co-routine to another, at points of the programmer’s choosing. This has roughly the same advantages for us as pure event-based programming, but it lets us write single, sequential functions instead of having to chain up callbacks. Since our cinematic script’s ‘threads’ have specific places where they want to wait, we can use co-routines to represent them, by having the co-routine give control away when it’s time to wait for an event. As a result, we get synchronization, concurrency, and asynchrony, without the use of parallelism.
In C#, you can implement simple co-routines atop the language’s support for iterator functions. In an iterator function, you have two new statements – yield return and yield break – that allow you to specify points where your iterator should be suspended, and produce a value. With the addition of a simple scheduler to manage your iterators and wire up callbacks when they wait on an event, you’re ready to go. Let’s ignore the inner workings of this system for now and look at the iterator equivalent to the above code:
Player.Teleport(Player_Start); HeroicLeader.Teleport(HeroicLeader_Start); yield return Future.WaitForAll( Player.MoveTo(Player_Destination), HeroicLeader.MoveTo(HeroicLeader_Destination) ); Player.Animate(Animation_Wave);
The code is about the same length, but now we don’t need an operating system thread to run it. In this case, we’ve taken that object representing a movement command from the last example, giving it a name – Future – and written a simple helper method that constructs a single future from a group of futures. When our iterator yields on one of these Futures, the co-routine scheduler can automatically wire up event listeners in order to resume the co-routine once the Future it’s waiting for has completed.
In practice, the code necessary behind the scenes to run a script like the above is actually very simple – not much larger than the equivalent event-based code. Debugging also becomes easier, because the compiler turns your iterators into a simple state machine, and you can inspect the state of those iterators in the debugger, or log it to a file, for easy troubleshooting.
Futures also happen to be simpler to implement than most other synchronization primitives because they are one-shot signals – once they’ve been written to, they’re never written to again. This means that despite us writing our iterators as if they are single-threaded, they can actually interact safely with other threads, as long as they only interact through Futures! This frees you up to construct the innards of your game engine in any way you like, while your cinematic scripts live in a single-threaded paradise.
In this example, we’ve taken advantage of the fact that our cinematics did not require concurrency – they had no need to actually run multiple OS threads in parallel – they just depended on asynchronous events, like characters moving around. This fact allowed us to strip out unnecessary threading and synchronization baggage while still keeping the traits we cared about.
In my next post, I’m going to explain in more detail how you can implement a primitive like Future, and how you can use it to solve real-world problems, even if your language doesn’t offer a feature like iterator functions. I’ll also explain how this approach can make your software more reliable and easier to debug.