Thoughts Serializer

Multithreaded Game Scripting with Stackless Python

Charilaos Kalogirou

The very basic problem that a creator of a game engine faces when it comes to scripting the game engine is: what will be the language that will be used. Of cource there is the option of creating a custom language for the purpose, but today with the plethora of scripting languages available it doesn’t really make sense to go through all the development process of a custom scripting language. No matter how big the development team will be, it will never be possible to match the man-months that have gone into an existing scripting language.

I will try to introduce the scripting language Python and more specifically a special version of it, the Stackless Python, as I used it in the implementation of the Sylphis3D Game Engine. For a basic introduction to game programming with python I suggest you try this book : Game Programming with Python. Stackless is a modified version of the mainstream version based on the work of Christian Tismer. The main feature that makes Stackless so attractive for use as a scripting language is the support for tasklets. Tasklets make it possible to create “micro-threads”, allowing the programmer to switch among several execution threads that only exist in the python environment and have no dependencies on the underlying OS threads. Some would call these threads”green-threads”. These threads has very small footprint on memory and CPU. You can actually create hundreds of threads with almost no overhead. Every tasklet has only a few bytes of memory overhead. And the scheduling of threads takes O(1) time with a simple Round-Robin scheduling algorithm. If we where talking about native threads we would have almost 1MB of memory per thread and high cost scheduling to do things we don’t need. To all that add that the engine would behave very differently on different operating systems. Even on different versions of the same operating system.

Game Engine, the game’s operating system

In most current game engines there is a fundamental flaw in the way the game engine and game code are viewed. The game engine is not viewed like a concrete system capable of providing the low level facilities that a game needs. Instead it is viewed at best as a library. It is viewed as a collection of functions that basically encapsulates driving the low-level hardware. This tends to make the game code aware of the underlying procedures of the game engine.

Instead the game engine should be the operating system of the game, and the game entities should be like the processes running in it. The engine designer should have that in mind when creating any aspect of the engine. It is starting to be obvious that to accomplish this, the game code should run at a different “level�? than the actual game engine, so that the game engine can have complete control over the execution of the game code. In real operating systems this accomplished with support from the hardware. In our case this different “level�?, is simulated by running the game code in a virtual machine, hence the scripting language.

In trying to create such a design for the game engine, we have to consider what the analog of a real operating system process will be in the game engine. In a game engine, a process will be an “actor�?. The “actor�? will be the fundamental game creation block. The design tries to make everything an “actor�?. The player is an actor, the objects in the game are actors and even the game world and the game itself is an actor. These actors are autonomous entities actually running in the game engine. The actor must be totally encapsulated and never has to directly worry about other actors.

Multithreaded design

The nature of a game is multithreaded, because the game tries to simulate a world populated by objects that do various tasks in parallel. It is obvious that this must be simulated since we don’t have as many processors as objects in a game! Most engines simulate multi-threading by iteratively calling an update function of the actors in the world. The actor updates its state according to the time passed and returns to the engine. Game engines with no scripting capabilities use this method, and it is as a legacy mindset used even by newer engines in the scripting environment. Most engines with scripting just go a little further, implementing the update() methods in the scripting language. This doesn’t really give us much. Since the game code runs in a virtual machine, each actor should instead run in it’s own context. In Sylphis every actor can have at least one thread, just as an operating system’s process does.

In a multithreaded design the actor’s code is linear in execution and easier to write. For example let’s consider the game code that closes a door. In a classic game engine (Quake I/II/III, Unreal, etc) the code looks something like this : 

void update(t_actor *actor,double timedelta){
    if(actor->state == CLOSING){
        CVector3 pos = actor->origin;
        pos = pos + actor->velocity * timedelta;
        if(pos == restpos){
            actor->state = CLOSED;
            return;
        }
        actor->origin = pos;
    }
}
Although the above example is far from the complexity of true code that would contain all the states etc, it is still ugly. Below we can see the code that does the same thing using threads and written in python. 
def close(self):
    self.setVelocity(self.mMoveVelocity)
    self.sleep(self.mCloseMoveTime)
    self.setVelocity(CVector3.ZERO)
The benefits are obvious. In the python example one can tell what the code does in a glance. There is no need for state keeping. The state is encapsulated in the current code that is executing. When the door calls the close() method, the door is in closing state, and when it returns it will be in the closed state.

Why multithreaded design was avoided

Multithreaded environments can be a headache. Experienced programmers know that and try to avoid threads, while on the other hand inexperienced programmers find them quite attractive and usually make applications a mess. It all boils down to synchronization. Synchronization of threads can be very hard to get right and is wet ground for a great number bugs to grow. Add to that, that race conditions and thread-related bugs can be extremely hard to hunt down, since the condiitons to reproduce them may be unknown. The efficiency of threads is also a concern. The scripting engine for a game must be fast. The game world contains many actors that need to be updated at least every frame. You don’t want a scheduler to take up half of your CPU trying to decide which – of many, many actors – to run next. Also, if you have to spawn and delete bullet actors in the game (coming from a fast machine gun), you should start looking for thread pools and other techniques since spawning each bullet thread can take too long.

To sum it up: below is the list of reasons that multithreaded environments where overlooked by game developers :

Overcoming multithreaded design pitfalls

As we said before, Stackless Python and tasklets can solve the scheduling overhead, memory costs and slow thread creation. Now we have a better foundation to work on, but the remaining problems like synchronization remain. We have to find ways to maintain the benefits of the multithreaded environment while removing more of these problems.

What makes the multithreading synchronization problems and race conditions serious is preemptivity. Preemptive multithreading introduces a non-determinism in the code execution that requires the programmer to cover his back while doing anything. You can be interrupted at anytime at any part of code. Preemptive multithreading might be great for interactivity on the desktop, but gives nothing to game code. It turns out that not only there is no need for it, but also it does not fit in a game environment. To make that clear we will take a closer at what a game engine does:

The game engine simulates a world different from the world the computer is running in. This other world has its own time that ticks away in discrete steps, either constant or variable. Time in the game world is frozen while the game code executes all the logic for a time step. So why would one want to preempt an actor running some calculations? There is no rush to allow another actor to run, since time does not pass! Worse, it would be wrong! Actors with more complex behaviors will progress slower in the game world, since they require more CPU cycles! The actor’s code executes in our world while the actor runs in the game world.

The obvious solution is non-preemptive multithreading. This also solves many synchronization problems. A non-preemptive environment rarely needs locks and can be deterministic. In a non-preemptive environment a semaphore is just a variable, and there is no need to lock between reading a variable and updating it.

Handling events

The next big issue of game code is passing and handling events. Most work in a game concerns passing events to each relevant actor for processing. So the engine must support facilities to provide efficient and flexible event passing. The Python language alone is very helpful, based on the dynamic nature of the language. The event framework can be very relaxed and simply provide the basic functionality to pass objects around. In Sylphis, when the game engine spawns an actor, it scans the methods of the actor for a handleEvent() method. If the actor has this method implemented, the engine creates an event handling thread that calls the handleEvent() method passing the event object, which can be anything. This creates an asynchronous event passing system.

Using Python in this implementation allows us to implement certain constructs that further beautify the game code. Consider the case we discussed above with the door. Suppose now that we want the door to respond to collisions while closing and stop the move so that it will not crash the colliding actor. The basic idea for handling such cases is to implement a callback function that is called by the engine when a collision happens and then change to the appropriate state. This can be quite straightforward if we see collisions as language exceptions. The micro-thread implementation allows the engine to raise exceptions on threads. So we process the events in handleEvent() and if we have an interesting collision, raise the collision object as an exception to the main actor thread or any other appropriate thread. Below is a modified close() example with the enhanced functionality of stopping when colliding. 

def close(self):
    try:
        self.setVelocity(self.mMoveVelocity)
        self.sleep(self.mCloseMoveTime)
    except CCollition, col:
        print "Oups.. sorry", col.name
    self.setVelocity(CVector3.ZERO)
The above code feels natural. The collision is an exception in the door’s movement and it is modeled like one. You can actually explain the above code to non-programmers on your team and be optimistic that they will understand it. They may even be able to add their own safe, interesting code tweaks. This is due to the fact that the code is laid out as people think of the game actions, and doesn’t mess with complex state machines even for the simplest task.

Actions

The work that goes into setting up a game world, usually involves the associations of actors with event dependencies. For example we would like to set up a door that when opened produces an alarm. This should be easily set up from inside the game world editor and should be easy for the artists to understand and use. Most game engines today support things like this through the use of special trigger actors that trigger other actors when an event occurs. Although this works most of the time, it is not very flexible since at the end there is generally a single trigger signal for a specific event. Every actor has to make good use of it, often by coding for special cases. A door will probably open on a trigger event or close if it was open. But what happens when we want to trigger the door to do something different, like unlock? Then we have to start writing special case code to support it, and the door is just a simple example. Suppose we need to make the player’s AI teammate say “Good job�? when the door is unlocked. It is clear that a system that allows all that at the world editor’s level is necessary.

The actors must be designed around the action concept. Below, we will see various actions that actors have.

CDoor

CSpeaker

It would be nice if we could express this conceptual level in the game programming. Programming the above actions in typical state machines and common langauages is like trying to implement UML class diagrams in C. It can be done, but it is not going to be as smooth as it would be with an object-oriented language. So what we need is a language that will support action-oriented programming. It turns out that Python can support this model through the use of threads and the dynamic capabilities of the language.

Let’s examine in more detail what we are trying to design, in the highest level. An actor can have a number of actions, which are basically implemented as methods, of the actor class. These methods, is a good thing to have a special name so that it can be distinguished from normal class methods. For example an action method for when a door is opened is named like this: 

def ActionOnOpen(self, other):
    pass
Now the world editor should give the artist the ability to connect actions. For example the artist might connect the action OnOpen of a door with the OnTurnOn of a light. The engine will then dynamically intercept the calls to the method Action_OnOpen() of the door actor and also call the Action_OnTurnOn() method of the light actor. This interception is possible with the dynamic nature of the Python language. When the game engine spawns an actor in the game world looks at the _action connection table that the world editor provides and replaces the appropriate methods with an interceptor method that calls the original method and the target action method on the target actor.

Is has to be clear that these methods are no dummy methods that are just used for signaling. These methods can be the methods that do actual work. To clarify that lets remember the close() method we of the door we described earlier in the document. That method can be turned into a action just by renaming it and adding the additional parameter. 

def Action_close(self, other):
    try:
        self.setVelocity(self.mMoveVelocity)
        self.sleep(self.mCloseMoveTime)
    except CCollition, col:
        print "Oups.. sorry", col.name
self.setVelocity(CVector3.ZERO)

What we have now is an action method that can be connected to other actors to make them act on the event of the door closing. The action can be connected in the other direction also, to make the door close when something happens to another actor. Connecting the OnDie() of the player to the close() of the door will make the door close when the player dies, while connecting the close() of the door to the OnDie() of the player will make the player die when the door closes.

With this system the actors gain the ability of broadcasting action about anything. Also the actor can listen for actions of other actors. All that without changing the actor’s code. All setup in the world editor and linked dynamically at initialization of the actors.

Actor hibernation and migration

Using micro-threads implemented in Stackless Python allow us to save the state of an actor without any hassle. Stackless has the ability to pickle (serialize) tasklet objects like normal objects. This means that you can suspend a running thread and get a string representation of it, with all the running state included like a normal object. That string can be saved on disk and later on the tasklet can be re-animated. So the use of a multithreading model in the scripting of the engine, does not remove any of the easy save/load benefits of running in a virtual machine.

With a bit more care we can also implement actor migration. For example we can have a distributed system running the game world. This can be common in a massively multiplayer online game where the number of players and game objects are enormous. In a smaller scale this can be a peer-to-peer multiplayer game. In the above cases it might be useful to be able to migrate an actor from one machine to an other. Using Stackless this can be possible without the actor having the slightest idea that it was moved. Unfortunately special care must be taken when the actor uses python objects implemented in C++.