Game logic is highly concurrent; not only does each entity in the world have its own main script, but there are typically many event handlers and latent behaviors that can run at the same time also. Luckily, there are many software engineering techniques to deal with this — in particular custom task schedulers.
This article has multiple purposes. First, it introduces the idea of a round-robin scheduler as a solution for this kind of multi-tasking — explaining what you need for it to work in your own game using executable pseudo-code. Second, it gives you a little background into this kind of concurrency for the Python programming language, notably stackless or the greenlet modules, showing how you can implement one using the other.
Cooperative Scheduling
There are many ways to implement multi-tasking. One of them is to use cooperative scheduling, as used by the infamous Windows 3.1 operating system. The idea is to let each script or task terminate of its own accord when it’s ready to do so, only then proceeding to the next task.
In practice, this works out very well in games, for the following reasons:
You control of the implementation of each of the tasks to prevent any of them from hogging resources,
You can easily tune the granularity at which the processing happens for each task, and
You have the option of building custom schedulers easily to make sure you maximize hardware usage.
That third point is what this article focuses on, showing you how you can build a simple scheduler to manage these tasks. But first, a little background…
A History of Multi-Tasking in Python
Since Python version 2.2, it’s been possible to implement a simple form of task concurrency using generators. Generators are essentially an implementation of the iterator pattern; each loop the code performs some computation and returns a value. While it’s supported out of the box, the down side of this approach is that it doesn’t allow nested functions and you can’t jump from one generator to another: you must always return a value to the caller.
from __future__ import generators
Stackless Python was the the first major project to provide general tasklets that allowed you to jump arbitrarily from one script to another without any restrictions. Under the hood, Stackless is implemented as a fork of the main Python codebase with non-trivial changes to the interpreter to make sure no data is stored on the C-stack — whence the name Stackless. The down sides of this implementation is that it requires a custom executable, and it only exposes a high-level scheduler from which you can re-implement low-level coroutines on top (these are more convenient when you need fine control over the sequencing of your scripts).
# This module is typically built in to the interpreter. import stackless
The newcomer on the scene is the greenlet module, which rather amazingly does the same thing that Stackless does, but as an optional module separate from the Python interpreter! This presumably uses some non-standard manipulation of the C-stack to save and restore it as necessary — like the protothread library. This explains why the library is called py.magic! The only disadvantage of this solution can be a blessing too: you must build custom schedulers yourself.
# This library is external to the main interpreter! from py.magic import greenlet
The ideal solution would be to use a scheduler interface primarily, breaking down into coroutines when more control is necessary. This article will show you how to rebuild the stackless scheduler on top of the greenlet module, thereby no longer requiring you to use the custom executables for running Python scripts.
Round Robin Algorithm
One of the most widely used scheduling algorithms is round-robin, which balances execution opportunities as fairly as possible while still being simple to implement. Basically, all the tasks to be scheduled are stored in a linked list. When the current tasks decides to yield control, the next in the list is picked.
This is basically how Stackless Python works. Sample usage looks somewhat like this:
# Main entry point for our coroutines. def think(name): """Do some processing and yield control each frame.""" for i in range(1,10): stackless.schedule() print name
NOT LOGGED IN
Comments
Comment on this article. | Show full forum thread.package that contains deque is called collectionS
The lack of corroutines, and a good way yo make a scheduler, was one of the reasons we had for switching to Lua.
Anyways I think I'd still stick to Lua if you are scripting a C/C++ engine, its just simpler to integrate. But if your going all out Python this is definately useful.
About the history:
It was Stackless Python that appeared first (1999), way before
generators were considered for CPython. They were added as some
kind of reaction to Stackless' existence.
About Greenlets:
Note that Greenlets are a spin-off from Stackless, using the same
stack slicing technique (with enhancements) that Stackless tried
to avoid and used only as a fall-back. For that reason, tasklet switching
is 10 times faster in Stackless. No stack access, but it does co-operative
switching. More efficient, but much harder to implement.
Stackless has the same magic, it just tries to do better.
I agree that not replacing the interpreter is an advantage, and
I'm thinking about how to do that for Stackless, too.
About PyPy:
The comment about an official way of implementing Stackless on
top of Greenlets is somewhat missing the point.
With careful reading, you should realize, that using Greenlets in
PyPy is just the fall back, the emulation layer to be able to run
Stackless tests on untranslated PyPy.
The real translated PyPy does not use Greenlets at all, but implements
everything natively. Greenlets have the advantage to provide easy
testing, and that's all about it.
cheers - chris