Blog Archives

Apocalypse Bunny, lessons learned.

Working on Apocalypse Bunny was quite fun.  The ambition was low, which makes the goal reachable and the progress quick.  Also I got to touch many pieces of the software so there was no time to be bored.  I even had to do some pixel art \o/.

Sure there’s no sound, and yes the world map doesn’t make sense, and of course the gameplay is limited.  Don’t care.

It’s time to go back to Infiniworld, the big project.  I learned some valuable lessons thanks to Apocalypse Bunny.

Let’s split our code in packages and modules as early as we can.

I know the zen of Python: “Flat is better than nested”, and I agree.  Python is not java, and theses periods don’t come for free.  The thing is that we do not need to have a flat code to have a flat interface.  To the user, it does not matter that the constant infiniworld.NATURE_GRASS is actually a shortcut for infiniworld.models.tiles.NATURE_GRASS.

The more files we have, the less code they contain.  The less code they contain, the less reasons we have to modify them.  The less we modify, the less we break.  It also helps us keeping our list of import statements short, which helps keeping track of dependencies.

I started by keeping all my modules in the root package but they grew very big.  I got entangled in that mess and had to reorganize all the code in smaller pieces.  That’s not a problem at all for Python, and not a problem for the user either if we make our __init__.py files properly, but that’s a problem for git or every version control system: I lost all my history.  Git accepts that we move or rename a file, but it cannot handle the fact that one file became five or ten.  There’s a big discontinuity in the tree now :(.

So if you know in advance that you will have to split your module, don’t write a module but write a package instead.

We need to make room for the special effects.

Until Apocalypse Bunny, all the EntityViews used to corresponding to an EntityModel.  Apocalypse Bunny changed that with what I called “special effects”.  The expanding circle drawn when we blast a psy-wave does NOT exist in the model, this is a purely visual artifact created only by the view.  Same goes for the blood left on the floor when a creature dies, it’s only visual special effects.

A special effect has a position, a rendering method, a sprite, and listens to events like any other EntityView, but it does not have any corresponding entity in the model.  It is so similar to an EntityView that I actually inherited the special effect classes from EntityView.  I will reconsider the names here because that’s going to be confusing.

Because of the similarities, we want to process special effects like we process the views corresponding to real entities.  So we want to put them in the same list/dictionary/set/group than the ‘real’ ones.  But because of the difference, we need a special identifier that no real entity is using.  I decided that since the entity models were having positive integers as identifiers, I would use negative integers for the special effects.  And thanks to this tiny trick, I got all the special effect code working for free with absolutely no effort at all.

Disappearing entities break everything.

When a fox dies, or when a carrot is picked up, their entity disappears.  That crashes the entire game.  Imagine: the carrots are picked up when we collide with them.  It means that the physics engine is in the middle of its iteration doing collision response when we pick up the carrot and it disappears: RuntimeError: dictionary changed size during iteration.

So you think: “okay, let’s not destroy the carrot entity now, instead let’s schedule it from destruction by posting a DestroyEntityRequest which will be processed when the physics has finished running”.  Think again, because you end up with the following possibility: you touch the carrot, and your friend touch the carrot, so you both pick it up and then it’s scheduled for destruction twice.  It may not crash (although I did ask the event manager to crash when something is unregistered twice) but it’s buggy: only one of you should get the carrot.

So we need:  to remove the dead entity immediately, but also to keep it around, alive.  At the same time.  Schrödinger would have loved this.

Imagine if the wave function had collapsed the other way :(.

Solution: add a boolean variable on our entity saying “I (don’t) exist”. Since the entity stays in memory the dictionaries don’t splode. And since we can tell that the entity doesn’t exist, we can skip it in the physics step. We must really get rid of the entity at some point though, so after setting this variable to False, we post a DestroyEntityRequest.  Neat!

Now, the same is true for appearing entities, except that I do not see any reason to create new entities during a physics iteration. Yet. I’ll think about it tonight.

Not all entities are tangible.

Carrots are supposed to represent small things on the floor.  They should not be obstacles, they should not be pushable.  Sure they won’t block the bunny since the bunny picks them up when she touches them, but they should not be an obstacle for the foxes either.  So we want an entity that detects collisions (so that they detect that a bunny touched them) but does not trigger any collision response code from the physics.

Easy: just add a “I’m (not) solid” boolean variable on the entity body and use it well.  Neat, again!

I tried for fun to make the bunny non solid: she crosses the walls and everything, awesome!  Now we can have ghosts \o/.

We need to pause the physics.

The physics engine should not run all the time: we may be on the title screen, or paused, or maybe there is not even a world yet.  It was not easy to add a pause function to my game loop because of the way I wrote it, so a lot of code has changed in there.  Surprisingly, the code got cleaner ô_O.

Partition space for entities.

My collision code for entity vs entity was brute force: test every entity against every other.  This O(n2) algorithm is of course very poor, but I didn’t know how poor, so I chose not to optimize it early.  Well, after having seen how the performance was crashing once I was reaching 50 entities (I’m talking about 5 FPS here), I HAD to optimize.  I did not use any quadtree or cool stuff like that yet, I just cut my map in chunks of 8×8 tiles and query entities by chunks.  8 is a quite random number, I could probably reduce it to 4, 2 or maybe 1, but that creates more chunks containing nothing and therefore more overhead when updating or searching the chunk map.  I need to test to find a good value.  In any case, as soon as we don’t look at the entire map, we’re fine.

That’s all…

At least all I can think of right now.

The engine source files changed quite a lot ; there is no point in merging the two branches.  I will branch out of Apocalypse Bunny and remove the code related to this specific game (it’s all in the bunny package!) to have my new codebase for infiniworld.  I’ll be doing some refactoring in the next days.  Then, new fun stuff!

A wild game loop appears!

Figure 1: Game loop, I choose you!

I told you in my previous posts that the physics would update at 20 Hz while we would render frames at 60 Hz.  It is now implemented and available in the v0.0.6.b of Infiniworld.

There were two things to do:

  • make the game loop smarter,
  • make the view able to interpolate.

Frame interpolation.

If we update the frames three times faster than we update the physics, then we end up rendering three times the same scene with all the entities in the same positions, making our game look like it is rendered at 20 FPS instead of 60.  Nobody wants that.  To avoid this, we can modify the AreaView so that it can perform some interpolation between two physics states.

It felt immediately obvious to me that I should interpolate between the last known physics step and the next one.  Of course the next one hasn’t occurred yet, so I should predict it.  I can predict it for example by using a simple Euler integration: this is computationally cheap and noone is likely to notice any error on a time span of a twentieth of a second.  Then I realize it cannot work because it does not predict the collisions at all.  I need to run the full physics engine in order to have my predicted future. But that does not work either: I cannot predict what the user will do.  I can predict what the Entities will do by running their AI, but the player is a mystery.  And then, what ?  At the next time step I have to recompute the same physics step again, this time with the right player input.  This means that I run the physics twice for every step, and half of these computations give a wrong result because the player cannot be easily predicted.  It sounds like a bad idea doesn’t it?

When we try to guess the future we are not really interpolating, we are extrapolating.  And this, for the reasons given in the previous paragraph, will not work well.  What we should do is interpolating between two known physics steps in the past.  This has the strange consequence that the scene we render on the screen does not show the present state, but a state from a very close past.  This made me feel strange at the beginning, until I realized that we are talking about a delay of a sixtieth of a second, which nobody will notice.

I chose to apply a linear interpolation: we can compute it very fast and it looks good enough.  In short, it means that our entities are smoothly moving in straight lines between the positions given by the physics engine.  I could do some splines or fancy things, using more physics steps, but that would not look nicer.

Figure 2: We render frames using positions interpolated from the last two known physics steps.

The EntityView objects need to store three positions now: the position at the last physics state, the position before that, and an interpolated position.  The latter comes from this very simple line of code:

# Snippet from pygame_.EntityView.interpolatePosition
self.int_pos = (self.old_pos * (1 - ratio) + self.new_pos * ratio)

Each RenderFrameEvent now comes with a ratio.  We use this ratio to interpolate the position of all the EntityView sprites.  Then we draw the scene using these interpolated positions.

Note that only the view does this: the model does not know anything about this interpolation.  Not a single line of code is changed in the model and its physics engine.  We respect our Model-View-Controller pattern.

A smarter game loop.

In order to feed the AreaView with a ratio for its interpolation, the game loop has to compute this ratio. But that’s not the only thing the game loop should do. It should:

  • read the inputs from the keyboard/mouse/joypad/touchscreen but also from the network if we play online ;
  • run the physics ;
  • render the frames with the proper interpolation ratio.

But that’s not it, it also should

  • run the physics at a rate that does not depend on the speed of the machine, which means catching up if the rendering takes so much time we are getting late ;
  • have the highest FPS we can achieve, while still limiting it to what makes sense with the refresh rates of out monitors, independently from the physics ;
  • save some battery and keep the CPU cool by sleeping as much as we can.

I am giving you here links to two very famous and well written articles about game loops:

They present various game loops and their behaviors on fast and slow hardwares.  That’s a good read for people who develop on PC and have to worry about guys like me who change their computer once every five years (and buy each time a cheapos one).  The loop I came up with looks pretty much like what they present at the ends of their articles: everything is independent from everything else, the physics is able to catch up when it’s getting late but even in that case it renders frames once in a while (better have horribly slow game than no game at all).  What I added is the possibility for the CPU to take a rest, and some protection against time jumps that the Network Time Protocol can cause on some machines.

There is a weird thing on the tubes…  I was wondering whether my game loop should sleep or not and many people seemed to find perfectly normal to have the game loop eat ALL the CPU (that’s just one source, I read that in several places).  Even Fiedler and Witters do that.  Why ?  I’ve seen screenshots of Minecraft with absurd frame rates (see Figure 3). Do these people know that their monitor is limited at something like 60 Hz ?

Figure 3: Some dude running Minecraft at 556 FPS. Testosterone much?

At the old times of CRT monitors, 100 Hz was not a luxury, it was a need-to-have if you didn’t want to be staring at a stroboscope all day.  Believe me, I can see a refresh rate smaller than 100 Hz on a CRT.  But we have LCD/TFT/Plasma/dunnowhat monitors now where 60 Hz is perfectly healthy.  Why would you render 10 frames to only display one ?  Maybe it makes sense when you use accelerated graphics cards, but that’s still dumb.  It’s going to make your fans turn at full speed which is never pleasant to the ears and prevent you from playing in summer.  And if you are one of these weirdos who like playing with a laptop on battery in the train (or worse, a Pandora!) you are pretty much doomed.

Now, sleeping is not super reliable, we can wake up if a signal is sent to our process, or we may sleep a bit longer than we hoped.  But I designed a game loop robust enough to handle change in speed, so let’s just do it!  I’ll put the CPU to sleep.

Here you can read the code of my game loop: https://github.com/Niriel/Infiniworld/blob/v0.0.6.b/src/loop.py.

Conclusion.

Figure 1 shows the new game loop in action: This picture is totally representative of what Infiniworld will look like in the end{.} Dear font nerd Pokémon fan: I know I didn’t use the right character font, that’s because I pixel-arted the text in the picture myself ; now, go glitch yourself a Mew. Dear rest of the Universe, let this video blow your mind:

Step 2: interactivity.

In the previous article I explained how I implemented the event management. Now, our software bricks can talk to each other. Let’s get them to talk ! Well… let’s get them, first.  We need bricks.  The good ones.

Too often I started similar projects, focusing on an aspect such as the procedural landscape generation. It worked ! But I got stuck. I ended up with an ASCII dump of something representing a world, but I couldn’t do anything with it.  There was no game built to explore that world.  This time I want to start making the game interactive in the first place: we need to be able to explore before having something to explore.

I chose pygame for managing the input and the output.  The input being the player’s fingers on a keyboard/mouse/joypad, and output being the screen and loud speakers reaching the player’s eyes and ears.  Because I apply some kind of Model-View-Controller (I always say “some kind” because everyone has his own MVC), I will wrap the input in a Controller, and the output in a View.

We will have a PygameController and a PygameView class.  I don’t want to use anything related to pygame in the Model classes, to make sure that when I decide to use a different rendering engine I only have to rewrite the input and output without touching the game logic at all.  There will probably many other pygame-related views, probably one view per character to be displayed, for example.  These views will be managed by the main PygameView.  It would be wise to group everything pygame-related in one single package so that it can be replaced.  Other views, like a console view for the server, would be kept in another package.

And, finally, we’ll need a game loop.  I’ll go for the simplest game loop ever, but in a near future I shall write a whole entry on the subject.

Let’s get to work ! Very soon, the first screenshot !  I bet you can’t wait :).

The event management is in place.

Hello hello !

As promised I worked on what I called “Event Management”, the bare bones of my lousy implementation of the Model-View-Controller pattern.  It’s uploaded on GitHub :

https://github.com/Niriel/Infiniworld/tree/v0.0.1

The important module is evtman.py, “evtman” standing for “Event Management”.  It contains three classes:

  • Event
  • Listener
  • EventManager
Event Manager, events and Listeners.

The Listeners communicate only with Events that transit through an Event Manager.

The classes Event and Listener are abstract, and are meant to be subclassed. The Event class looks a bit complicated, but that’s because it automatizes things in order to make its subclasses extremely easy to define. For example :

>>> class CharacterMovedEvent(Event):
...     name = "Character Moved Event"
...     attributes = ('character_id', 'position_from', 'position_to')
...
>>> event = CharacterMovedEvent('Bunny', (0, 0), (32, 0))
>>> print event.character_id
Bunny
>>> print event.position_to
(32, 0)
>>> print repr(event)
CharacterMovedEvent(character_id='Bunny', position_from=(0, 0), position_to=(32, 0))
>>> print str(event)
Character Moved Event
    character_id = 'Bunny'
    position_from = (0, 0)
    position_to = (32, 0)

See ? Very easy. Now that I think of it, the name attribute should go away because it’s pretty useless; I put it there to have a clean human-readable name but the class name is enough.  I made sure that repr would not lead to insanely long lines by capping at 50 characters per attribute.  Very useful when events carry a complete dungeon map in a huge list/dictionary/tuple/whatever.

It is also very easy to subclass Listeners:

class CharacterView(Listener):
    def __init__(self, character_id):
        self._character_id = character_id
        self._x = self._y = 0
    def onCharacterMovedEvent(self, event):
        if event.character_id == self._character_id:
            # 32 pixels per meter, and the display starts at
            # the bottom while my Y axis goes up.
            self._x = event.position_to[0] * 32
            self._y = 480 - event.position_to[1] * 32

That’s it, you have your View.  It should be a pygame Sprite, the zoom level (32) and the window size (480) should not be hardcoded here, but that’s not more complicated than that.

And to use it is very simple:

def example():
    class CharacterMovedEvent(Event):
        attributes = ('character_id', 'position_from', 'position_to')
    class CharacterView(Listener):
        def __init__(self, character_id):
            self._character_id = character_id
            self._x = self._y = 0
        def __str__(self):
            return "%s: pos = (%i, %i)" % (self._character_id,
                                           self._x, self._y)
        def onCharacterMovedEvent(self, event):
            if event.character_id == self._character_id:
                self._x = event.position_to[0] * 32
                self._y = 480 - event.position_to[1] * 32
    #
    bunny_view = CharacterView('bunny')
    hamster_view = CharacterView('hamster')
    event_manager = EventManager()
    event_manager.register(bunny_view)
    event_manager.register(hamster_view)
    #
    event = CharacterMovedEvent('bunny', (0, 0), (1, 2))
    event_manager.post(event)
    event_manager.pump()
    #
    print bunny_view
    print hamster_view

And the result is:

bunny: pos = (32, 416)
hamster: pos = (0, 0)

There is one thing missing, though: some Listeners may want to post events. For example, the CharacterModel is a Listener which should be able to post the CharacterMovedEvent. This is achieved by giving the event manager to the listener. Add this to the previous code:

    class CharacterModel(Listener):
        def __init__(self, event_manager, character_id):
            Listener.__init__(self)
            self._event_manager = event_manager
            self._character_id = character_id
            self._x = self._y = 0
        def moveTo(self, new_x, new_y):
            old_x = self._x
            old_y = self._y
            self._x = new_x
            self._y = new_y
            event = CharacterMovedEvent(self._character_id, (old_x, old_y), (new_x, new_y))
            self._event_manager.post(event)

    hamster_model = CharacterModel(event_manager, 'hamster')
    event_manager.register(hamster_model)
    hamster_model.moveTo(3, 3)
    event_manager.pump()
    print hamster

Result:

    hamster: pos = (96, 384)

In this example, the model doesn’t listen to anything, but in a real situation it would.


Hero Quest, the toughest monster of all.

HamsterView moving on the tile map and destroying Orcs as a response to a GoBerserkEvent.

That’s all there is to it ! It just works.

Just don’t forget to unregister the Listeners you don’t use any longer:

event_manager.unregister(hamster_view)

Sure the event_manager keeps only Weak References to the Listeners, so they automatically disappear from its lists. But if they disappear right in the middle of an iteration, that may explode. If you see such an explosion, it means you forgot to properly unregister.

A last word: you can post as many events as you want. They will all be processed, in the order you posted them, when you call the pump method of the event manager. Some event handlers will post events, even register new Listener. That is perfectly okay, the event manager is happy with that, the pump will go on until the event queue is empty.

EDIT:

  • I got rid of the ‘name’ variable of events.  It was 100 % useless.
  • I introduced a SingleListener class, which is for Listeners that are interested in ONE event manager only.  And to be fair, that’s the case most of the time.

 

Who controls the controllers?

The Model-View-Controller pattern is quite a wonderful thing.  I had some troubles accepting it because I was born at a time when the most powerful computer in the world had 8 Mb of RAM and a CPU beating at 80 MHz.  I still feel a squeeze in my heart when I write an if statement inside a for loop, so I found it hard to accept replacing function calls with messages broadcast all over the place to components that don’t care.  To me, it’s like taking all the axones away from a nervous system and ask the hormones to replace them in their job:  a tremendous waste of memory and CPU.  But memory and CPU are cheap now, and my ambitions are relatively modest from a performance point of view.  So I gave in and am now a happy man.

I won’t spend much time describing it because others have done it quite nicely before me.  I really urge you to read the following articles if you don’t really know what it’s about.

The idea is to separate the

  • game logic –or Models– (physics engine, position of the characters, tiles in the map)
  • from the way it is presented –by Views– (sprites on the screen, debugging console, a bit of network code that sends the info to the client who is the one doing the actual rendering)
  • and from the way it is controlled –by Controllers– (keyboard, mouse, clock, network sending info from a client or a server).

This makes developing our game a bit like playing with Lego bricks: adding or removing a brick does not interfere with anything.  Models Views and Controllers send Events to an Event Manager which takes care of forwarding them to other Models Views and Controllers.

So who controls the Controllers ? The Event Manager does. It also manages the Views and the Models.

Dr. Manhattan

And HE watches the Event Manager.

For example, the server does not need to display anything, only the client does.  So you just delete all the graphic Views from the server code.  You can plug a console View that shows the server load if you want.  An other example: if you want to replace my PyGame 2D view by some 3D OpenGL magic, go for it.  The game logic does not care one bit.  This is all very well described in the two articles I linked up there.

However, I would like to add a few things in this post.

Brown’s implementation does not scale very well.  It works perfectly of course and has the immense advantage of being very easy to understand, which is exactly why Brown chose this implementation for writing his tutorial.  But when you look at it, 1) every Event is sent to every Listener (Model View or Controllers) ; 2) from there, a bunch of if statements will decide how the Listener will react, if it reacts at all because in many occasions the Listener doesn’t even care about that type of Event.  Stone me for optimizing early, but it could be interesting to have the Listener specify which kind of events they are interested in (solving problem 1), and give to the Event Manager a direct handle to the code that should react to it, instead of filtering with ifs (solving problem 2).

Both Brown and Koonsolo apply the traditional MVC pattern which allows the View to know something about the Model.  For example, the DragonSprite View really has a pointer to the DragonCharacter Model.  I don’t think I’ll do that.

The Model sure ignores the View but the View knows about the model.  This asymmetry feels dirty to me.  It’s almost an invitation to modify the Model from the View, which is a bad thing.  But even if you behave, I am still annoyed by having to carry full objects in my Events.  For example, the MonsterAppearedEvent will have to carry the DragonCharacter object so that the DragonSprite be created and points to it.  That complicates the serialization when you need to carry Events over the network and that makes debugging a mess.  First, too many pointers and references: you don’t know who owns who, and if you use WeakRefs in the View to avoid memory leaks you’ll end up with broken pointers.  Second, when you print an event into a log file it doesn’t help you at all because the CharacterMovedEvent does not tell you where the character moved ; indeed the View just has to look into its model to get the info.  Third, it becomes difficult to test the View without testing the Model itself.

Does the Sprite really need to know the whole Model ?  Of course not.  If the Model moves, then the sprite just needs to know the new position, and this position can be stored into the CharactedMovedEvent.

One advantage I can see when one sends the full Model is that the View can initialize itself in one go.  When the View is created, it knows already everything about the model and can display it properly at the right place.  But we can also do it with events.  You can have the CharacterCreatedEvent contain enough info for the View to initialize itself.  And if it’s still not enough, the View can post a CharacterPositionRequest Event and wait for the Model to answer with a CharacterPositionEvent Event.

What I’m going for is not traditional MVC, I’ll use Events all the way.  Which means that there is no real difference between a Model, a View and a Controller, at least not from an implementation point of view.  They’re all Listeners, waiting for events to tickle them and posting events when they feel like it.  However, what I’m not doing, is having all the Models talking to each other through events.  I want to separate Model, View and Controller, I don’t want to separate the model from itself unless there’s a very good reason to do so.  Can’t think of any right now.

So I’ll be working on that.  I’ll tell you when it’s pushed on GitHub!