Game loops – Not to be taken lightly

Not too far back, I started developing games. Back then I decided to hit the books for a while before getting upfront with the actual programming and one of my questions was about game loops. While googling the web I came across this article (a must read for anyone not familiar with different game loops) and must say that I was a bit surprised how a rather simple thing as a loop turned into something a bit more complex, but for the better!

I must begin to thank Koen Witters for his post about game loops as it helped me a lot. However, it still took me some time to wrap my head around the constant game speed independent of variable FPS loop, and decided to write this in order to work out some of the questions I had.

This is a modified version of the suggested game loop by Koen Witters:

typedef T_TIMEINFO struct {
    int updates_per_second;
    int frequency;
    int skip_ticks;
    int max_frameskip;
    int next_game_tick;
    int loops;
    float interpolation;
} TIMEINFO;

TIMEINFO t;
ZeroMemory( &t, sizeof( TIMEINFO ) );

t.updates_per_second = 25;
t.frequency          = get_frequency();
t.skip_ticks         = t.frequency / t.updates_per_second;
t.max_frameskip      = 5;
t.next_game_tick     = get_time();

while( true ) 
{
    t.loops = 0;

    while( get_time() > t.next_game_tick && 
        t.loops < t.max_frameskip ) 
    {
        update_game();

        t.next_game_tick += t.skip_ticks;
        t.loops++;
    }

    t.interpolation = float( get_time() + t.skip_ticks – 
        t.next_game_tick ) / float( t.skip_ticks );

    update_render( t.interpolation );
}

The variables here have been moved into a struct to make them more easily managed and accessible. Also, time is treated as an incremental value and only through the frequency can you find a relation to actual seconds. This is important since high-resolution timers come with a variable frequency (Hz) while the GetTickCount() function returns a discreet number of milliseconds (1000 Hz).

So without further due I present to you this diagram of the above running game loop:

Let’s start with the scheduling as it’s essential to any game loop.

Each game_update (red dot) occur after deadline (black dot) and thus there is always a difference between game_update and deadline denoted here by overdue. This relatively small value can be used in various ways e.g. in a multiplayer game to check that game state is synchronized among participants, as the overdue value is simply a metric of how far game_update is behind. Note that this value is only accumulated if game_update requires more time than skip_ticks and if so, another game_update is scheduled immediately after.

I bet you went – “Eh? What the… the timer is all backwards!?” when you first looked at the above code. It sure isn’t trivial but it’s essential. You have to think about it as two separate time lines; one continuous and one sampled. While we can plan ahead exact moments in time it’s unlikely that we’ll be that punctuational. If we’d assume we’re always late and plan our next deadline always skip_ticks after last deadline we not only prevent drifting, we also make up for any subtle interrupt game_update might cause. In practice we will either schedule game_update a little before or little after actual skip_ticks but as long as this overdue error remains small, it’s perfectly fine.

It’s possible that game_update might stall (be interrupted) and take very long to finish due to some unexpected behavior. When this occurs the next deadline might be scheduled within the overdue error and immediately run game_update until either caught up with real time or max_frameskip force game_render. A max_frameskip is good, it will give the impression that your game is actually still running, slow, but running. However, getting behind and accumulating an overdue is very bad and you should be aware of problems that might arise from this.

And that’s it! Now all the remaining time between each game_update is spent on game_render. The game_render have to implement prediction and interpolation if you want to smooth results. This is fairly simple and Witters covers that which you need to know in his article. This interpolation value is conveniently always between 0.0 and 1.0 depending on the intermediate step of the current iteration. So the only thing you need to be concern about is how to represent a progression between each fixed game_update.

Ad free Windows Live Messenger

It's actually very simple. Windows Live Messenger get's all it's ad information from a host called rad.msn.com (remote advertisement?) and since it's possible to tell Windows to look up invalid IP addresses through the host file, one can quickly get rid of the ads in Messenger.

You need administrative privileges for this, and if you are running Vista with UAC enabled you need to make sure you launch both Notepad.exe and Cmd.exe with elevation (Shift right-click them in the start-menu and choose run as administrator).

• First, find you host file, Microsoft Windows (NT/2000/XP/2003/Vista) is located in %SystemRoot%\system32\drivers\etc by default.
• Second, open Notepad.exe as administrator (and with elevation if you use Vista and UAC) choose File > Open... and navigate to the host file (make sure you show all files) and open it. It's called "hosts" without a file extension.
• Now add the following new line at the end of the file: "0.0.0.0 rad.msn.com". Save the file and close Notepad.

It will tell Messenger to look up an invalid IP address for ads, and thus display no ads. You need to flush the DNS cache for this to take immediate effect, and it can be done by opening the command prompt Cmd.exe (as administrator) and type "ipconfig /flushdns". If you wait long enough Messenger should stop displaying ads but the quickest path to salvation is restarting Messenger as well.

Enjoy your Ad free Windows Live Messenger.

World of Warcraft security and protocol analysis

[This post was originally published as part of my developer blog back in late 2006. Back then I was reverse engineering network protocols for educational purposes. I found a flaw in the World of Warcraft encryption scheme that allowed me to tap into the network stream. The results presented here explains how to exploit this weakness as well as how to prevent it. Enjoy.]

When logging onto WoW the client and server computes an identical private key as part of the SRP6 authentication. This key is 40 bytes in length and is used as a session token as well as keystream. In an attempt to locate this key in client memory, I was unsuccessful. But recently I've figured out a way to subvert the encryption.

I've seen a lot of people making packet captures of serve/client traffic and trying to analyze the raw data. But as you might already know, the header of each message is encrypted. This encryption however, is flawed. While subverting the stream is simple in theory, it's a bit tricky to implement in practice.

The problem is that the underlying network layer (TCP) does not provide a reliable way to determine the actual length of application layer data. And since TCP itself is quite a hassle to handle, the process of keeping track of sequence numbers is frustrating. On top of this, the guesses used to crack the encryption becomes even more of a problem when the server bursts data (multiple packets per segment). The game will of course handle this correctly but the tap will not be in-sync.

The idea is based upon a more complex approach where the tap examines every piece of pushed TCP data and for each guess parts of the keystream. As soon as a continuous keystream is found we cycle the entire keystream to synchronize the cipher (in theory, the keystream is too short). This step does not take time, does not involve intense computations and it's a very neat way to being able to tap into the network stream (this works for any computer with a promiscuous network interface in the same collision domain).

Each packet uses a header which stores the actual length of packet. Since the client piggy backs each packet with the PSH flag we can use the TCP/IP headers to calculate the actual length value. This is how we guess the key stream. What's even worse is that the client sends 6 byte encrypted headers while the server uses 4 bytes. This will effectively allow us to cycle the keystream in no more than 20 packets. The problem is that we can guess parts of the plaintext. A quick and dirty solution here is to just pad every other packet or so with 1-3 bytes.

However, if you think about what you gain this system (despite being completely broken) still has some benefits. Even if you have complete control over the TCP stream, you can not just inject data it's more difficult than that. Either the client (will most likely crash) or server will de-sync and terminate the compromised connection but it's not impossible to act as a man-in-the-middle.

While Blizzard clearly states that the creation of third-party applications that enable players to gain an unfair advantage is strictly forbidden. This will not in any way make it possible to gain such an advantage. It will however allow you to read all in-game languages. The benefit of this is that an external application can log your play or more precisely see what you see and even further record your actions and later replay those actions.

While working on this I had an idea that could enable replay capabilities. I never finished reverse engineering the protocol but I knew enough about the game internals to impersonate a server. This effectively allowed me to pretend that the client was playing the game, while in fact you where watching a replay of some previously logged session. You can't interact with this session but you can re-experience any event as if you where playing the game, allowing you to freely move around and examine every angle of the situation.