Python has this really neat feature called generators. I’ve found them to be incredibly useful in my code, especially for games. You see, it turns out they’re great for handling animations, scripted sequences, and a whole bunch of stuff.
I’m going to talk primarily about generators in Python here, but generators exist in many other languages such as C# and Javascript, and I believe Unity3D also makes use of them for animations and such.
Coroutines
If you’re not familiar with the concept of a coroutine, excuse me while I blow your mind somewhat. When one calls a regular function, otherwise known as a subroutine, something like this happens:
function_a () { function_b (x,y,z) {
[ ] ... .----> ...
state function_b (x,y,z) ----' foo = 5
held ... call ...
} }
1) The state of calling routine is recorded and execution jumps into the called subroutine with any arguments it was called with.
function_a () { function_b (x,y,z) {
[ ] ... | ... [ ]
function_b (x,y,z) exec. | foo = 5 state
... v ... held
} }
2) Execution continues until the subroutine returns. During the subroutine’s execution it may have its own state, using local variable for example
function_a () { function_b (x,y,z) { \ /
[ ] ... return ... - -
resume function_b (x,y,z) <---. foo = 5 / \
state ... '---- ... state
} } lost
3) The called subroutine’s state, i.e. its arguments and local variables, are discarded and execution jumps back to the point where the subroutine was called from, possibly with a return value if it returned something. The state of the calling routine is restored.
Coroutines are different. Program execution can jump between coroutines without their state being discarded. An example might go something like this:
coroutine_a () { coroutine_b (x,y,z) {
[ ] ... .----> ...
state coroutine_b (x,y,z) ----' coroutine_a ()
held ... call ...
coroutine_b (x,y,z) ...
} }
1) The state of calling routine is recorded and execution jumps into the called coroutine with any arguments it was called with, same as before.
coroutine_a () { coroutine_b (x,y,z) {
[ ] ... exec. | ... [ ]
coroutine_b (x,y,z) v coroutine_a () state
... ... held
coroutine_b (x,y,z) ...
} }
2) Execution of the coroutine continues. The routine has its own state.
coroutine_a () { coroutine_b (x,y,z) {
[ ] ... call ... [ ]
coroutine_b (x,y,z) <--------- coroutine_a () state still
... ... held
coroutine_b (x,y,z) ...
} }
3) The coroutine hands execution back to the calling routine, however its state is NOT discarded - it is preserved in the same way the calling routine’s state was.
coroutine_a () { coroutine_b (x,y,z) {
[ ] ... call ... [ ]
state coroutine_b (x,y,z) .----> coroutine_a () resume
held ... | ... state
coroutine_b (x,y,z) -----' ...
} }
coroutine_a () { coroutine_b (x,y,z) {
[ ] ... ... [ ]
coroutine_b (x,y,z) coroutine_a ()
... exec. | ...
coroutine_b (x,y,z) v ...
} }
4) The calling routine once again invokes the subroutine. The subroutine recovers its state, and continues execution from the point it got to last.
Execution can quite happily ping-pong indefinitely between two coroutines in a way which may be quite alien if you’re used to thinking in terms of subroutines and their call stacks. Curious, no?
Python Generators
Python generators allow you to do something a bit like this. A generator
behaves like a regular Python function, but preserves its state when it
passes execution back to the calling function using a special yield
statement.
A trivial example of a Python generator might be something like this:
>>> def integers():
... i = 0
... while True:
... yield i
... i += 1
...
We define the generator the same as we would define a regular function. The
key difference is the inclusion of the yield statement which indicates to
the compiler that this is a generator function. integers can now be called
to create a new generator. Each time we iterate the generator with its next
method, it executes up the the next yield statement and passes the value of
i back to us.
>>> g = integers()
>>> g.next()
0
>>> g.next()
1
>>> g.next()
2
The state of the generator, and therefore the value of i, is preserved
between calls.
The ping-ponging described in the previous section could be accomplished in Python with something like this:
>>> def myfunc(): >>> def mygen():
... g = mygen() ... while True:
... while True: ... print "now"
... print "how" ... yield
... g.next() ... print "cow"
... print "brown" ... yield
... g.next() ...
...
When myfunc is invoked, the function and generator will happily pass
execution to and from each other forever - no stack overflows involved:
>>> myfunc()
how
now
brown
cow
how
now
brown
cow
.
.
.
Now of course, there’s nothing particularly special about how this generator
object behaves. One could easily create a Python object which, when iterated
over, behaved the same way; returning "now" and "cow" alternately. What
would the implementation of such an object look like, then? Well, how about
this:
>>> class NowCow(object):
...
... def __init__(self):
... self.cow = False
...
... def next(self):
... if self.cow:
... self.cow = False
... return "Cow"
... else:
... self.cow = True
... return "Now"
...
What we’ve created here is a state machine. The object preserves the cow/now
state between calls to next, by using a boolean, and this state is checked
on each call to determine how the object should behave. This is fine, and for
many problems this is a great solution. Where generators come into their own
is for defining a linear sequence of states in a concise and natural way.
This leads me to how you can use them to great advantage in games.
Generators for Scripted Sequences
Let’s say that you’re putting the finishing touches on your next masterpiece
of a game. It’s time to add in the main menu screen, and you want it to be a
magnificent sight to behold. You’d like the main menu buttons to fly in one
by one and come in to land in the centre of the screen. But you also have your
game loop to consider; your main loop invokes your do_menu function 60 times
per second. On each call, the function has to update the positions of your
button sprites and return so that the program can perform its rendering and
other duties and complete the frame.
1 2 3
+-----------+ +-----------+ +-----------+
[ ] ----> | | [ ] | | [ ] |
| | | <----- [ ] | [ ] |
| | | | | /|\ |
+-----------+ +-----------+ +----|------+
screen [ ]
The code to achieve this is going to have do something different each frame, depending on what state the animated sequence is in. A state machine for this, in pseudo-code, might look something like this:
state = 1
function do_menu {
if state == 1 {
move button 1's position
if button 1 is in place
state = 2
}
else if state == 2 {
move button 2's position
if button 2 is in place
state = 3
}
else if state == 3 {
move button 3's position
if button 3 is in place
state = 4
}
...
}
The more complicated this scripted sequence gets, the more states we are going to have to declare. As I’m sure you can imagine, this can very quickly get ugly and difficult to maintain.
Instead, let’s consider how this could be achieved using a generator instead:
generator menu {
while button 1 not in place
move button 1
yield
while button 2 not in place
move button 2
yield
while button 3 not in place
move button 3
yield
}
This generator can be iterated every frame, in the same way that our do_menu
function could be called. But the expressiveness of the generator syntax lets
us declare the linear sequence of events in a more procedural way. The flow of
events in the animation reads more naturally from top to bottom, the same way
as any other program flow would be declared, without having to define lots of
individually handled states. Each time we yield, we allow the game loop to
render another frame.
I find this expressiveness pretty neat for games. In fact Fiona has created an entire 2D library for Python called Myrmidon which uses a generator for each game object. This allows the entire lifecycle of each sprite to be laid out in this procedural way. It takes inspiration from an old game-making tool we used to use called Fenix/DIV. Here’s an example of a Myrmidon game object that fades in, pauses, follows the player for a while, then fades out:
class Ghost(MyrmidonProcess):
def execute(self):
# appear
for i in range(60):
self.alpha = i/60.0
yield
# pause
for i in range(30):
yield
# follow the player
for i in range(500):
self.rotation = MyrmidonGame.angle_between(
(self.x,self.y), (player.x,player.y))
self.move_forward(2.0)
yield
# disappear
for i in range(60):
self.alpha = 1.0-i/60.0
yield
Generators can be nested, too. That is, you can have a generator yield while it is iterating another generator. This makes them really useful for games which rely heavily on scripted story-based content, such as RPGs or adventure games. Rather than relying on a separate scripting language such as Lua or some kind of home-grown scripting DSL, we can take advantage of Python’s expressiveness and write scripts in the language itself! Consider this scripted sequence written as a generator:
def love_scene():
for i in fade_in(): yield
for i in character_walk_to(alice,(12,16)): yield
for i in character_say(alice, "Hey there Bob"): yield
for i in character_turn(bob, west): yield
for i in character_say(bob, "Oh hi Alice"): yield
for i in character_walk_to(bob,(12,17)): yield
for i in character_say(alice, "I love you Bob!"): yield
for i in character_say(bob, "I love you too, Alice!"): yield
for i in fade_out(): yield
The commands fade_in, character_walk_to, character_say and so on are
themselves generators which each perform an action over a number of game
cycles. By looping over them and yielding on each iteration, we can have the
main script wait until the command has finished. There is in fact a PEP
suggesting a yield from syntax for Python which would eliminate some of
the boilerplate here, but at the time of writing it hasn’t quite made it into
the language yet.
Performance Considerations
Naturally there is some overhead associated with using a generator over a regular function. Based on some quick benchmarks, it would seem that iterating a generator executes more or less as quickly as a calling the equivalent function. There is overhead involved in constructing the generator, though; you’re looking at around 5x the time it takes to construct a do-nothing class instance. That said, if you’ve already chosen to use Python to write games then it might be fair to assume that performance isn’t your highest priority anyway. Particularly if you’re prototyping, you’ll probably be aiming to make things as easy as possible for yourself - in which case, go for the generators!
Conclusion
Generators are an interesting tool which allow linear sequences of events to be declared in a natural, procedural way. In many cases they eliminate the need for complex state machines, and are especially useful for games. Next time you’re stringing together a state machine just to make your main menu look nicer, or inventing a scripting language just to add cutscenes to your game, consider using this powerful language feature instead.