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:

• deWiTTERS Game Loop, by Koen Witters at Koonsolo
• Fix Your Timestep!, by Glenn Fiedler at GafferOnGames

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:

The first screenshot of Infiniworld!

Welcome back, fellow web traveler.  Here is, as I promised you in my previous post, the very first screenshot of Infiniworld.

Two entities (white) in the world (gray). One of them can be moved around by the player.

Game features:

• Spawn your very own blocky creatures with a single key stroke (Enter/Return) !
• Take control of your creatures and tell them where to go (WASD keys to move) !
• A stunningly fluid 60 FPS refresh rate on any recent machine !
• Save your battery life: the game sleeps when it has nothing to do !
• Spy on yourself by logging everything you do into a file, and learn about what’s going on under the hood !

Game does not feature:

• Physics engine.
• Any kind of landscape.
• Boobies and explosions (Actually they are in game, but only allegorically, just use your imagination).
• Things to do.

Download and play this first interactive version of Infiniworld !

GitHub link: https://github.com/Niriel/Infiniworld/tree/v0.0.2

If you are a git user:

git clone git@github.com:Niriel/Infiniworld.git

If you just want a zip:

• Go there : https://github.com/Niriel/Infiniworld/
• Click on the big “Downloads” button on the right of the screen.
• A window appears. Under “Download Packages”, click on v0.0.2.
• That’s it, you have the zip !

Run the game.

Enter the src directory and type “python solo.py”.

Implementation.

How does it all work ?  you ask.  Here is how:

• Model classes:  WorldModel, EntityModel.
• View classes: PygameView, AreaView, EntityView.
• Controller classes: PygameController, PlayerController, GameLoopController.

Models.

The world is extremely simple for now.  There is no landscape, no map, no tiles.  It contains nothing but some entities.  I call “entity” anything that exists in the game world and can move: creatures, fireballs…

Entities are represented by an EntityModel class and have  a position stored as a two-dimensional vector (see geometry.Vector).  Each EntityModel has a unique entity_id.  Every event regarding a given entity will carry that entity_id. Today, the role of the EntityModel is to change its position when it is asked to do so.  Since there is no landscape and no physics engine, it always accept any order it receives.  That means that any MoveEntityRequest results in a EntityMovedEvent.

For now, the only responsibilities of WorldModel are to create and destroy EntityModel instances, and keep a list of them.

Views.

The PygameView is the root of everything that is displayed on the screen.  It opens the window and draws everything that needs to be drawn when it receives a RenderFrameEvent.

The AreaView displays a part of the world: landscape, entities.  There is no landscape so it just displays entities for now.  Each time AreaView receives an EntityCreatedEvent, it instantiates an EntityView object for representing it.

EntityView objects listen to the EntityMovedEvents to remain in sync with the EntityModel objects.

These views uses pygame.sprite for showing themselves on the screen.  The sprites of the EntityViews objects are blitted onto the sprite of the AreaView object, which is blitted onto the display by PygameView.  On the screenshot, the display is black, the AreaView is gray and the EntityViews are white.

Controllers.

The PygameController translates the pygame events (which are SDL events) into Infiniworld events.  For example, it translates the fact that Escape key is pressed into a QuitEvent.

The PlayerController contains an entity_id: the entity being controlled by the player.  When the PlayerController receives a PlayerMovedEvent from the PygameController, it responds by posting a MoveEntityRequest with the proper entity_id.

The last controller is the GameLoopController.  The current implementation is pretty naive and simple.  It posts a ProcessInputsEvent and a RenderFrameEvent 60 times per second.  ProcessInputEvent wakes up the PygameController and RenderFrameEvent wakes up the PygameView.  Note that the GameLoopController does not use any pygame function, so it does not call pygame.time.clock for running at 60 FPS.  Instead, it uses the time module from the standard library.  The game loop stops when the GameLoopController receives a QuitEvent.

What next ?

The goal of this demo was to have something interactive as quickly as I could.  It works: I can create entities and move them around.  But it’s not pretty: the entities are teleported, it is not fluid at all.  It would be nice to have a physics engine.  However, a physics engine should manage collisions, and I do not have much to collide against for now.  I need a landscape.  So I think that the next step is to implement tiles, maps, areas, etc..

The WorldModel will hold many AreaModel instances in memory: dungeons floors, cities, overworld, etc..  The EntityModel needs to be extended to accomodate the fact that there are now several areas.  The AreaView should show one area only.  Entities should be able to move from one area to another.  Lots of work to do !

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

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.

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.

• sjbrown’s Writing Games Tutorial
• Game Architecture: Model-View-Controller, by Koonsolo

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.

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!