Thoughts Serializer

Computer graphics, Games, Personal

Multithreaded Game Scripting with Stackless Python

62 Comments »

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 :

  • Scheduling overhead
  • Memory cost per thread
  • Inefficient thread creation
  • Synchronization problems
  • More bug prune
  • Difficult to debug

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 action can be the effect of an event, or the effect of another action.
  • An actor can have several actions.
  • An action is a concrete and discrete procedure that the actor can follow.
  • An actor can be taking an action or not. There is no middle state.
  • One can monitor the actions an actor is taking.
  • It is possible to make an actor follow an action.

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


CDoor

  • Open
  • Close
  • Lock
  • Unlock
  • Toggle

CSpeaker

  • Play
  • Pause
  • Stop
  • Rewind

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++.

62 Responses

Interesting article. I haven’t looked at the game engine yet, but it sounds promising.

You are absolutely right about “green threads” and non-preemtive multitasking makes programming much simpler. I’m developing a mobile phone game right now under Symbian, which is an operating system with a multitasking system very much based around “active objects”, which is the same idea. (It still supports threads, but their use is discouraged unless you really really need them.) Not having to synchronize and always think about parallellism issues is a relief.

There is one thing that I’m thinking about though, and that’s the problem that green threads by their design can only utilize one CPU in a multiprocessor or multicore architecture. The trend is moving towards several CPU:s so our programming models need to reflect that. To use more than one CPU, you’ll still have to use operating system threads.

  • Maybe it will be possible to spread out the execution of green-threads to more that one system thread. The problem will be preemptivity. We will have to think of ways to maintain the simplicity of non-preemptivity. I can think of ways to do that allready, so must ve possible. But for now I think the additional CPUs have to be used for physics, sound, procedural geometry, etc and let the game code run on one CPU.

  • Hi.

    What you describe sounds very similar to how I have designed my game engine. The concept of autonomous entities driven by events or actions is very powerful, but as you say can be very difficult to (firstly) design and (secondly) debug.

    Effectively we’re talking about ‘Event Driven Software’, something which has been used widely outside of games for some time.

    http://en.wikipedia.org/wiki/Event-driven_programming

    I have found though that many game coders I meet are unwilling to step outside the ‘Update()’ methodology as they have in many cases used it for many years and see no value in doing things differently.

    My experiences so far have been largely positive – ‘building’ a game from entity ‘building blocks’ feels more like making a model aeroplane than writing software. The difficulty is in designing the plane in the first place, and when something goes wrong debugging can be extremely painful. I feel that before I scale-up my projects I will need much better debug tools than I presently have.

  • It’s a neat idea with the try/except, though it goes a bit against the rule that try/except aren’t here to make flow-control, but rather for real exceptions. See Paul Graham or the Pragmatic Programmer on the topic. I’m not convinced this will not come back to hunt you once employed in a larger context. I’d be nice to check, but then you don’t realease sources…

    Btw, it seems like green-threads and more elaborate continouations/closure makes its way into the main python branch, so you might enjoy the full CPython and have the stackless benefits, well, somewhere in the future :D

  • Just a quick point!

    I think your close function will NOT work all the time correctly unless you make sure it collides with something when it closes (or you make sure that the position update and complete actor loop are run for each frame).

    Why? Well say you have a computer running a bit slowly. You set the velocity and wait the time to cover the distance the door needs to close. On a slow computer when the wait finishes to door may have travelled further than the distance it needs to close!

    Perhaps it would be better to instead of setting the velocity use a function self.SetTranslateRotate(dx,dy,dz,rx,ry,rz,NumberOfFrames) then you could guarantee the finishing position at Now+NumberOfFrames….

  • Hi Rob!

    The world update is decoupled from the frame update. The world is updated in constant steps of 1/60 sec. There is no difference in slow or fast computers.

    You are partly right though. The only problem you have is always under 1/60 sec. For example if you have to wait for 1.5 secs and the step time is 1 sec. You will wake in 2 secs. The problem is solved by adding a :

      self.setPosition(self.closedPosition)
    

    at the end. It was not included in the example code for simplicity. The actual code from Sylphis of the slideing door is this :

    def Action_open(self, other):
        self.killActionThreads('close')
        self.setPortalOpen(True)
        self.body.setVelocity(self.vel)
        time = self.calcMoveTime(self.openPos)
        self.sleep(time)
        self.body.setVelocity(CVector3.ZERO)
        self.body.setPosition(self.openPos)
    
  • it might be worthwile to contemplate a

    self.body.translate( self.openPos, self.closedPos, speed )

    that only comes back once the move has finished, or was interrupted and you do your thing with cathching that event.

  • You say the world update is decoupled from the frame update, and that the world is updated in constant steps of 1/60 sec. Could you elaborate? Is that 1/60 sec. real-time or CPU/engine time? I can’t imagine that it’s real time: if my computer — fast or slow — is bogged down, how can you guarantee that the world (or any process on the PC, for that matter) will be updated every 1/60 sec.? Isn’t that like saying I can guarantee that a “download emails” thread would finish in exactly x amount of time?

    If it’s “engine” time, then does that mean that a bogged down PC would result in slow-motion in the game? I’m thinking about games that “skip a beat” whenever something really intense happens outside the game’s process: when that background task lets go of the CPU, the player’s movement has covered 400 ft. in one frame (well, one redraw). This, I assume, is based on the Update() methodology relying on the system clock, which isn’t present in the approach you’re talking about.

  • 1/60sec is ofcource game time. If you have a slow computer the FPS will be lower but objects will cover bigger distances each frame. It is normal, I don’t understand why you are stuck?

  • I guess the part I’m really stuck on is, “The world is updated in constant steps of 1/60 sec. There is no difference in slow or fast computers.”

    In an Update() paradigm, the world is updated and the screen redrawn on every frame; one doesn’t happen without the other — they’re coupled. When you said the frame update and world update were decoupled, I took that to mean a world updating loop separate from the screen redraw loop. So if the world updates every 1/60 sec., how often is the screen redrawn, and how are those two loops decoupled in code? As an event-driven programmer just getting into game design, that sounds to me like two separate threads — one for the world runner and one for the render runner.

  • No, no threads.. it is much simpler. You update the game time for as much time as the last frame took to render, but in updates of 1/60 sec length.

  • Harry, Thanks for your reply!

    I was thinking that as you were using a physics engine you could use self.setForce(vecForce) You could store the door mass as a hidden variable Therefore applying f=ma :: a=m/f you could work out what to change the velocity by per tick (60th second)

    Rearranging suvat s= distance to close door u=0 v=? a= m/f t=?

    we get t=SQR(2s/a)

    we want to make the door deccelerate after it’s gone half-way (2s/2), so sleep for SQL(s/a) then reverse the force and sleep for SQL(s/a) the door should now be shut and the velocity 0.

  • Whoops SQL =SQR = Square-root!

  • Hi Harry,

    that’s a really nice article. It shows how Stackless is used in games (and there are a couple more) and simulation engines (for the latter, I use it myself). This was exactly what I had in mind when I designed Stackless: Making expensive concepts cheap and usable, change the programming paradigm from complicated to natural, get rid of callback functions and explicit state engines.

    State should almost be where it is, naturally: Your state is your program counter.

    A handler of something is not a reactive pattern. Instead it is a littlemain program that has the feeling like it is the main application. And it is the main application, because it takes care of what it is interested in and defers everything else by issuing calls.

    It would be nice to talk about this a little on the stackless mailing list. You might also consider the use of channels as a very effective synchronization/communication feature.

    cheers – chris

  • Hi Chris!

    First of all thank you for Stackless! :) I’m glad you liked the article.

    I wanted to post about the article at the stackless mailing list to talk about it but the website seems down. Is there a problem? Harry

  • Hi Harry,

    Saw your article after Chris posted it on the Stackless mailing list. I got quite the dejavu from reading is as we were struggling with similar things back in 2000 and then we found Stackless Python and haven’t looked back since.

    We have now been running our MMORPG EVE Online (http://www.eve-online.com) for 2 years with no problems due to Stackless or Python. We have had up to 13.422 concurrent players so performance is defenetly not an issue.

    Good luck with the Sylphis Engine. Hilmar

  • I love the idea of microthreading because, like Unreal, you can write ‘latent’ event handlers, which places more of the burden of state machine management on the language instead of the application. But… I’m concerned about a recent comment in the stackless archives saying that blocking functions like sleep() will block other microthreads. So, my question is… what is the proper implementation of your ‘self.sleep(time)’ statement? Documentation seems to be sparse… what’s the best place to find out more?

  • Harry -

    Fascinating article. I have become convinced that Python has a great future for games and many other things. I have been working on the “Game OS” problem from a different perspective – how to handle online games in a standard, meaningful and secure manner. Our SecurePlay (http://www.secureplay.com) approach builds on “basic game transactions” as bulding blocks for exchaning game actions and state. Thinking about games from a security perspective is quite interesting problem in that you have different information known by different players (and the game itself) yet still work together in the same game world.

    One of the things that you have nailed, I think, is the separation of the “game play engine” from the “game presentation engine”. It is poor terminology and poor design to combine the two and it is a major source of game problems (I would tend to argue that many cheating problems are the result of asking a graphics engine to handle game play).

    I would be happy to talk with you further about this on- or off-line.

    Steve

    Steven B. Davis CEO IT GlobalSecure Inc. http://www.secureplay.com/

  • John DeWeese: So, my question is… what is the proper implementation of your ’self.sleep(time)’ statement?

    When you want a tasklet to sleep, just remove it from the list of active tasklets. Have a function called periodically that checks the sleeping tasklets and when their time to awaken arrives, add them back into the list of active tasklets.

    Here is some example code that works: http://www.stackless.com/Members/rmtew/StacklessMud/wikipage_view

  • Great article! I had been talking about similar models with another programmer and he pointed me to this site. Fantastic stuff. 2 questions for now.

    Hilmar: quite impressive that EVE uses it, you havent run into performance problems with so many players in the world? I just question how a model such as this would work in an RTS (the games i work on) with thousands of units in the world that need to update.

    My second question is somewhat related how does the code work with physics, lets say a 3rd party physics engine. I would imagine there would need to be some sort of synchronization because the physics engine can and will change the the physical location of the actors. Thoughts as to how this would be handled?

  • Thanks Todd, I’m glad you find the article interesting!

    Can you be more specific about the physics engine integration? That exactly is that you need clarification?

  • Ya great article, i’ve passed it on to all my fellow programmers at work as i’m trying to explain and show the benefits of a scripting lang such as Stackless or LUA.

    i’ve started a thread over at game dev: http://www.gamedev.net/community/forums/topic.asp?topic_id=344771

    but basically it has to do with your comment from August 12 about system threads and avoiding synchronization. with the next gen of console cpus and desktop cpus going multicore developers will probably have upwards of 6-8 hardware threads. along with SDKs such as Novodex coming into play that work on hardware physics processing unit, it would seem that at some point the processing of physics, and by physics i mean, collision and simulation of the objects (meshes, boxes, etc) will be in their own thread. at the same time the game logic will be running in a seperate thread. it would seem that both threads are coupled to one another… maybe the logic thread is more dependant on the physics sim thread, as an example what to do objects collide. i can imagine a system where the logic polls the phsyics threads at specific intervals or the physics thread sends messages such as objectA collided with objectB along with the necessary info to process the resolution.

  • In most situations the physics thread and the game-logic thread meet at collitions. I don’t there are big problems in syncronizing physics and game logic.

    In Sylphis3D for example actors bind functions on physics events such as collition. And in general if the actor uses physicalized objects in the game world it is expected not to alter the state of the physicalized object many times, so sync penalties will be rare. Even then the lock will be per object (better object island) so threads can keep going…

  • I agree thats the place where both modules will meet most. You say that the actor is expected not to alter the state of the physical representation all that often, but in the example code above, the actor is setting its velocity which would directly affect its physical represenation. It would also seem that in a game the user will be altering the physical state of the object quite frequently i.e. apply forces such as accelaration thru controller input.

  • Yes it sets the velocity once per state change. Make it more clear :

    Tha game code affects the physics world by applying forces, some times velocities (setting the position is posible but not sugested). That is when you need a lock. Physics engines work in groups of objects, called islands. This islands consists of objects that relate in some way (touching, having a common joint, etc). When locking you lock an island. The physics thread can continue processing other islands.

    For the example of the player that is indeed the actor that affects physics most(every frame that the user gives input), the lock will be only on that actor for most of the time unless he touches something. The physics thread will be free to process the stack of falling object utilizing the other processor…

  • I’ve come here from /. and this is a great start on game as OS concept.

    With all three consoles coming out with latest Power architecture (see V2.02 for latest public one), there will be some form or another of virtualization support (hypervisor mode in IBM lingo) in each console (at least as a potential).

    This means that each game console could allow games to run on the HW as a virtualized OS with more control available to game developers (or game engine developers). Whether any of the consoles would allow such freedom, I have no idea.

    For those into open source world, trying to create such a world with, say, Xen or IBM’s open source research hypervisor might be a great start. Any takers?

    (Email directly to me, danny at cellbex.com, if you are interested. Thanks)

  • Just wondering if a complete game application has been finished with your engine. Are the performance considerations and architectural methods you descreibe implemented in a complete game? The reason I ask, is that some of your examples are a little skewed – the close dorr example is a bit miscontrued. An actor in many of those engines is a class (and in some cases a struct) with methods that apply the actions the python ojbject does. Thus you could make the other engines code look almost exactly the same as the python example ie: void Actor::Update() { setVelocity(mMoveVelocity); sleep(mCloseMoveTime); setVelocity(CVector3(ZERO)); } However, I agree with your assessment of the way game systems can be created. Although this is more of a holy grail than a true applicable design. Most games these days need to be designed specifically with the features needed – creating a generic game engine is just too costly these days, unless its a well proven off-the-sholf system like Renderware or Unreal engine. And most often these are heavily rewritten to meet the game needs.

    I hope there is a generic game engine solution that can do everything games need, but in practice I think it is a little too niave to think this is achievable.. as hardware complexitity increases, so does software diversity – thus catering for wider and wider software implementations is going to be difficult, if not impossible.

  • The actor::update() function you wrote (i suppose it is C++) will have to run in a thread of its own to work. Otherwise the whole game will sleep. I think you missed the main point of the article, so I suggest you read it again.

    No full game was created to publishing point with Sylphis3D, but I don’t think that devalues the design, because it is not related to the design. Sylphis3D was used in many “prototype” games and the programmers always find the actor system described above very helpfull and productive. After all you can always fallback to regular game programming in Sylphis3D if you like, even if I wouldn’t suggest it.

  • I’ve loved this idea since I have seen it employed in UnrealScript, but your exception utilization is really concerning to me. Having collision be modeled as exceptions seems very dangerous. What if I have the following code:

    def Action_OnOpen(self, other): sleep(5) # wait 5 seconds and then someMonster.blowUp() # kill off a specific monster

    Clearly this code says I want a monster to blow up a five seconds as soon as the door is opened. What if the door get stuck on something? Will a collision exception be raised during the sleep resulting in the monster never being blown up? This seems extremely error prone.

  • To get collition events as exceptions you must set it up like that. If you do so and then don’t utilize try/except it is a bug!

  • I just want to check how the sleep() function works. Your close funtion gets run once per tick so when it reaches the sleep function it breaks and returns to Stateless to run the next process in the stack until the function has run three times (for 3 ticks) right? I am just wondering how you implement this sleep function or is this something that comes with stateless? And does it mean your class has to keep track of how many ticks has passed somehow?

    It sounds a bit like yeild() in a generator. I don’t use python too much so I may be wrong of course.

    This looks like it could be really useful for things like DAG trees and maybe implementing some sort of SIMD engine?

  • Very interesting. I have seen a stackless multithreaded object-oriented scripting language in a game engine before, way back in a 1992 DOS game called ZZT. The language was extremely primitive and the multithreading was preemptive, so you had to handle your own locking. But the multithreading model made it so simple that anyone could pick it up and understand it. In fact, even though the game engine hasn’t been developed in over 10 years (the source code was lost), people are still making games for it. Granted, these are very simple games in many ways, but people like using the model you describe to write games.

    In ZZT, the game model is much more rudimentary than in your game engine. A single game screen (called a board) is a 25 row by 60 column grid of tiles. There are empty tiles, walls, the player, various hard-coded enemies, and some other exotic types. But the most powerful type of tile is the programmable object, which is much like the actors in your engine. Each ZZT object, however, has exactly one instance running, always visible on the screen (it became common to hide objects by making them look like walls and such). Objects can pass messages back and forth and receive messages from their environment (e.g. when the player moves up to an object, it receives the “touch” message). Events and method calls are the same thing: an incoming message simply moves the object’s execution pointer to a corresponding label in the object’s code, unless the object is locked.

    As you can see, it had plenty of room for improvement; too much was hard-coded into the game engine. But I’ve never seen a better approach to managing interaction between actors in a time-based environment.

    Many limitations kept ZZT from becoming a serious game platform. The stunning 60×25 ASCII character graphics never impressed anyone. The game’s creator, Tim Sweeney, later went on to found Epic Megagames and eventually create the Unreal engine, leaving the ZZT executable to the public domain. The PASCAL source code was supposedly lost in a hard drive crash, which is probably for the best.

  • “To get collition events as exceptions you must set it up like that. If you do so and then don’t utilize try/except it is a bug!”

    So the mere presence of the exception handler enables receiving the collision event? How is this accomplished? Is there some way in python to get the stack of exception handlers? I’m not really sure how this would work…

  • The way Harry had set it up in the example:

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

    Is the collision handler, whatever code detected the collision would throw that CCollition exception class. the ‘except’ clause handles it. in his example there isnt much interms of collision resolution, but you can imagine passing that collision object to a something like self.resolveCollision(col)

    hope that helps :D

    self.setVelocity(CVector3.ZERO)
    
  • Harry said that you won’t get the event unless you setup code to catch the collision. I was asking how is this implemented? If there some code in the engine some where that reads something like this:

    event onCollision(args) { if (executing code has a collision exception handler on the stack) { executing code -> throw new CCollisionException } }

    How is that implemented??

  • Old ideas die young…

    I was reading an interesting article about Stackless, and implementation of python than implementas micro-tasks or tasklets, more to the point it’s about Sylphis3D Game Engine use of it. Anyway, reading the comments I find it amazing how may people d…

  • First of all Nice atricle, I liked the Ide alot. Seems like a good and solid design.

    The exception handling does it work like C++. with try, except and finally? finally is microsoft spesific.. but

    BTW: Is the source of the Sylphis engine available?

  • Interesting article. The one thing that I think is a bad idea is your use of Exceptions to effectively pass messages. This breaks the key rule of Exceptions:

    Exceptions are for exceptional events, not for normal events that might occur as part of running your program.

    This rule is there for a good reason. Exceptions in python are very quick to set up with a try, in terms of run-time, but very slow when it comes to actually raising. It’s costly to raise an exception. For this reason, I think it’s not a great idea to use exceptions for passing messages about game state…. (Others languages have similar costs for exceptions too.)

  • Hi Alex thanks for taking the time to post here!

    On the subject of rules… I say that rules are ment to be broken!

    As I see it, when I write game code a collition can be an exceptional event. There are times that you expect a collition, but there are also times that a collition is indeed exceptional. When it is exceptional you gain both in readability and in speed! Note that you choose when you want events as exceptions. Raise is indeed slow but look at this for example :

    try:
        value = d[key]
    except KeyError:
        value = default
    

    And the equivalent without exceptions :

    if key in d:
        value = d[key]
    else:
        value = default
    

    The code using exceptions IS faster when you expect to find the ‘key’ in ‘d’! So reconsider the above example with the CDoor actor. Most of the times the door will close since it is more common not to collide with anything, so it will be faster with exceptions, than manualy checking for collitions!

  • [...] This post was triggered by a comment by Alex Hunsley on the Multithreaded Game Scripting post. [...]

  • [...] The scripts loads and runs the map, and invokes a function that runs in parallel with the game engine, that will time the process for 50 second of game world time. Microthreads in action!!! [...]

  • [...] The hard part to parallelize would be the game code. The code that the entities run. This part has many critical sections since many entities affect others. How hard it would be to parallelize this depends on the engine and how it was designed. For Sylphis this will be easier since the game core is already thread aware (in a sense)…. [...]

  • [...] Kristján Jónsson from CCP Games did a presentation about their use of Stackless python in their MMORPG game. The use of Stackless in EVE Online is very close to the use of Stackless in Sylphis so I recomment it as a good reading along with my post about stackless. The presentation can be downloaded from this link… [...]

  • Stackless technology revolutionizes performance, taking it to another level of magnitude. I can see this technology being very popular in any algorithm that needs to manage a vast array of items, objects or actors such as the EVE game, or the next generation web-based operating system. Eve is most facinating to me due to the thousands of stations, ships and incredible amount of data accessable from even a basic computer with dialup connection. With the advent of converging PC technology with mobile phones and cellular internet, online games/databases/applications with almost incalculatable amounts of data can be optimized using stackless. In a way stackless lets you build your own mini-OS on an OS, unlocking the true potential of multithreading. The trick is now to optimize/engineer the code for multiprocessor platforms of tomorrow. It would be nice to have the main OS handle multithreading instead of the developer, what about it Bill? :)

  • I was doing more thinking about using Stackless for AI programming. Take the game design and impliment it AI. I imagine that there would be a visual recognition interface that can encapsulate physical objects and pass that to a system that creates that actor and fills in the attributes of those objects in a streaming fashion. Methods can be called for physics interactions with other actors, etc. As actors are added in a rapid fashion could cause a problem for most conventional code, Stackless has the advantage of managing many thousand actors at the same time and the interactions between them on conventional hardware of today. The sweet thing also is those actors could then be serialized to take a snapshot of the current state of the machine and store it in memory. If the AI was to interact with those objects again it could unserialize it and resume interaction in real time, after finishing the interaction, reserialize the actor, effectively cleaning it’s memory realtime, making space for new actors. The machine could understand past by activating it’s serialized “snapshots” and using a simulated difference engine to identify trends over time.

    Our perception engine renders reality in our own created 3D world in our mind where we interact with it. A book is not a book, the spoon does not exist. Our biological host machine simply is an actor, and the 3D construct in our minds is where all the decision making takes place. By providing AI a 3D construct of their own, we could start to bridge the divide between the consciousness of man and machine. With computers as advanced as today, it makes not sense why they cannot drive my car, or relate to me in a meaningful way. I think that stackless gives us the tools to manage the complexity and the game design a starting point. We just need one of you geniuses to impliment the code!

  • Interesting, but definitely not new (as with most software technologies). In addition to “microthreads” that we’re using (in a custom VM), I believe Naughty Dog code most, if not all, of their games with this type of system. Their custom (compiled) scheme like langauge called GOAL helps them accomplish this task – I think there may have been a Game Developer magazine article on this exact sort of thing a few years back. It is, however, a nice thing to implement using Stackless. Good luck with it all.

  • Markus…

    It was quite useful reading, found some interesting details about this topic. Thanks….

  • [...] Others have covered Stackless Python better than I could, so I’ll point you to them. There is a great overview of Stackless Python for games on Thoughts Serializer. From there it’s a quick jump to Introduction to Concurrent Programming using Stackless Python. And, of course, there is always the Stackless website. [...]

  • [...] Harry Kalogirou presents a length article Multithreaded Game Scripting with Stackless Python which goes deeper into tech side, but is worth checking for any programmer. [...]

  • [...] Multithreaded Game Scripting with SHow to do good bloom for HDR renderHDRR screenshotsHDR lighting… possibilities…Programmable GPUs and the programmiFirst there was DOOM 3, then Quake Google photo management = Picasa 2Attacked by the spammersWashing the car after 4 monthsMultithreading Game Engines for Mul [...]

  • Hello! I want to know, where you have a section for advertising at a forum? Or it is not present? I have not found it. P.S. Are you see storm in Europe? It’s a horror…

  • I think, that is interesting for all.

  • [...] One thing that this game taught me is the concept of Actors, which seem to be getting a lot of attention these days (Erlang Actors/Scala Actors or this or this or this) [...]

  • [...] I readily bought into the first two reasons; it was the third reason I didn’t much buy. After all, I’m a programmer and I program all the time — there’s nothing wrong with Java as a high-level language. But as I delved deeper into information about scripting engines, I stumbled across this blog entry; although nearly three years old, the information seems to be relatively fresh. Now I want to use Stackless Python. [...]

  • [...] The article, Multithreaded Game Scripting with Stackless Python is an extremely detailed article that discusses using Stackless Python to provide a game scripting framework that allows game designers to write actor/entity code in a more intuitive independent process oriented approach, as opposed to the standard time-slice update() every frame approach. I’ve been trying to come up with a way to integrate this functionality into jME (Java Monkey Engine), and am taking a look at the new Java 6 Scripting Engines to see if any of the available languages support coroutines (the basic elements of cooperative multithreading). The big idea is NOT to provide a true multithreaded framework, in the sense that these software only threads will be run in a single-threaded simulated cooperative threaded environment. [...]

  • [...] Multithreaded Game Scripting with Stackless Python: This seems to be a very interesting for Python programming (and maybe GeeXLab can take adavantage of it): ”Stackless Python 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.” [...]

  • [...] Microthreaded Game Programming with Stackless Python [...]