The Basics of Game Loop Implementation – part 1

Intro

Games at their core have what’s called a “game loop”‘: a looping construct which advances the game a little bit at a time. The main issue with the game loop is how to make it so that it “paces” itself: i.e. that it will advance the game at the same (average) rate no matter what the speed of the loop is on a given machine configuration.

Game loop pacing is an issue for multiple reasons:

– the most immediate one is that given a game (and its game loop) written in a certain language for a target platform, there can be many different hardware configurations on which that game can be ran. Because of the potential difference in target platform’s hardware configuration the code inside the game loop can vary in the frequency with which it is executed. If the game loop does not compensate for this, the user experience when playing the game can vary from one where the game seems to run too fast, to one where it’s moving in “slow motion” and is not responsive.

– also related to game loop “pacing” is the fact that such pacing can be implemented in different ways: either the game loop is left to run as fast as possible and an interpolation must be done between the game advancement and the time the game loop takes to make a full loop (variable step game loop), or the game loop paces itself to a target number of steps per given time period (fixed step game loop). There’s also the option of mixing those two approaches in the same game loop: have some of the game advancing code run in a fixed step game loop and other parts run in a variable step game loop.

– finally, depending on how the target platform implements graphical capabilities, there may already exist a looping mechanism, with an option to hook into it, thus not needing to actually write the game loop by hand. Furthermore, if such a loop is already present, it may or may not have an imposed limit on the maximum number of loops it will do in a given time period (i.e. max steps or frames per second), other than the one that comes from reaching the hardware’s limits. To illustrate this point, here’s some examples: Open GL (both the “full blown” desktop computer version as well as its ES reduced version) expose a callback function which it will call as fast as possible (i.e as fast as it can can render the graphics). An example of a game loop that integrates with Open GL’s callback will be presented in the 2nd part of this article (coded in C). Another example would be JavaScript’s “requestAnimationFrame” mechanism (which is implemented slightly differently on the various browsers). It operates similar to Open GL’s callback, with the added difference that most browsers impose a limit on the frequency with which requestAnimationFrame can be invoked, usually it’s capped at 60 calls per second (meaning that no matter how fast your game loop is executing, the graphics will not be updated more than 60 times each second). The 3rd part of this article contains an example on how to code a game loop in JavaScript using “requestAnimationFrame”.

In order to implement any of the above mentioned game loops, it is advised to follow certain guide lines when organizing the game loop related code:

– There should be a separation at least between the code that deals with graphics rendering and the code that deals with game state advancement. It is desirable to have at least this level of separation in the gaming code because, as it will be discussed later, for most scenarios the state updating code needs to be ran at a different pace than the graphics rendering code.

– There should also be a separation of concerns at the code level, such that different logically grouped parts of the game functionality are implemented in code following that separation: i.e.: the game loop code itself should only deal with high level game loop issues like pacing the game loop. Then, for each step of the loop, it should delegate to other code entities the various jobs of updating the game state and rendering the graphics. A simplistic way to achieve this is to have isolated code representing various “game entities” which are notified by the game loop when the next loop step is to be executed (and, depending on the type of the game loop, how much time since the last loop has passed).

Next, simple examples of the above mentioned types of game loops will be given, implemented using the following platforms (languages): JavaScript (in browser), C (using OpenGL), Java (using Swing). The reason why multiple development languages/platforms have been employed for these examples is that, while fixed and variable step game loop implementations are pretty much platform agnostic (can be done in any of those languages), multiple languages/platforms were needed to also showcase the various types of existing (platform level) loops we can hook in to.

Basic Variable Step Game Loop

One of the simplest to implement game loops is the variable step game loop. If we adhere to the principle that the game loop code should only deal with the game loop and its pacing, and other game aspects should have separate code entities for their implementation, then the variable step game loop simply needs to run as long as the game is still going (hasn’t reached a “game over” or “win/lose” situation) and simply measure how much time has passed between each of its steps, then delegate the per-step game actions to other parts of the code, also passing to them that time difference (delta time) between steps. Then, it’s up to the game entities code to use the delta time in order to make the necessary computations and see how much the game state should advance such that it will give a consistent game experience on various machines.

The code example for this is a very simple technical demo for the variable step game loop. It can be git-cloned from here:

https://gitlab.com/shivansite/JGameLoopStudy.git
(the Variable game loop code is in the “com.shivandragon.jGameLoopStudy.basicVariableStepGameLoop” package)

Here are some screen shots of the running app:

What this thing does is display 4 counters, each going from 1 to 10 (and then looping back to 1). The functional demand is that each counter must be incremented once per second.

The example is coded in Java, and uses Java’s Swing library in order to draw to the screen.

Here’s the game loop code (from the “BasicVariableGameLoop” class):

        long deltaTimeMs = 0;
        while(true) {
            long st = System.currentTimeMillis();
            mainWindow.update(deltaTimeMs);
            long et = System.currentTimeMillis();
            deltaTimeMs = et-st;
        }

Each of the 4 counters represent one instance of the “BasicVariableGameEntity”. The game loop “update” loop delegates to each of the “update” methods found in this class. The implementation of the counter’s update logic is very simple and straight forward: with each call, add the time of the current game loop to a global variable. If this accumulated time passes 1 second, draw the next counter bitmap (and wrap around to “1” when you get past “10”):

    public void update(long deltaTimeMs) {
        accumulatedDeltaTimeMs+=deltaTimeMs;
        int animImageIncremIdx = (int) (accumulatedDeltaTimeMs/(1000f));

        if(animImageIncremIdx > 0) {
            currentAnimationImageIdx = currentAnimationImageIdx + animImageIncremIdx;
            currentAnimationImageIdx = currentAnimationImageIdx%10;//wrap animation around
            accumulatedDeltaTimeMs = accumulatedDeltaTimeMs-animImageIncremIdx*1000;
        }
        debugger.debug(tag, currentAnimationImageIdx);
    }

Here are some advantages and disadvantages of this implementation:

– It will run as fast as possible. On my laptop, it runs at about 400 updates per second:

This is not necessarily good. For this particular and very basic example, one update per second would suffice (as the game state only changes each second). For a regular game, with actual animations and user input, an update rate of about 60 per second would be enough for a good playing experience. Having a lot more updates than that only uses hardware resources unnecessarily, draining the battery of mobile devices, heating up hardware components etc.

– This game loop will pace itself. This means that, on average, the game will run with the same “speed” (the counters will actually count each second) on most hardware configurations: even if the graphics were to become more complex, and take more time each step, this will only translate in a decrease of the game update rate, the actual “speed” of the game will remain constant (counters will still change their value each second). You can see a simulation of this by letting the application run for a while, and noticing what happens when the counters get to “7”. The “BasicVariableGameEntity” class is implemented such that when it gets to display the sprite for “7” it will sleep for 50 milliseconds. What this translates to in player experience is that when the counters reach 7, a drop in update rate happens (on my machine it drops from 400+ updates to about 20) and maybe some of the subsequent counter values (such as “8”, “9”) will not be displayed, but it will instead “jump” over them.

– The way this implementation deals with variations in game loop step time is not however ideal. You can get into a situation where so many updates take too long to process that the graphics updates will happen at a very decreased rate (the display may update itself one every 10 seconds, for example). This game loop’s simplistic implementation, especially the fact that game state updates are not separated from graphics updates (which would allow them to run at different rates), translates into poor handling of such extreme scenarios. The next example will show how to deal with this issue.

Mixed Step Game Loop

Next, will showcase the “Mixed step” game loop. “Mixed step” refers to the fact that this kind of game loop keeps two kinds of steps : one that advances at a fixed rate (25 updates per second here) and one that runs as fast as possible (variable step). Moreover it’s the fixed steps that have priority, meaning that, on average, we first make sure that fixed steps get to actually be executed once every 25th part of a second before letting the variable step have a turn as well. We’ll detail how this works by having a look at the code, which is found in the “com.shivandragon.jGameLoopStudy.basicMixedStepGameLoop” package.

First, the game loop is implemented as follows:

        long accumulatedTimeMs = 0;
        while(true) {
            long startTime = System.currentTimeMillis();

            mainWindow.updateGraphics();
            while(accumulatedTimeMs >= FIXED_STEP_IDEAL_DURATION_MS) {
                mainWindow.updateState();
                accumulatedTimeMs -= FIXED_STEP_IDEAL_DURATION_MS;
            }

            long endTime = System.currentTimeMillis();
            accumulatedTimeMs += endTime - startTime;
        }

The idea is this: we want the game to advance at the same rate no matter what the hardware performance of the platform is. When we say “game advancement” we refer to the rate with which the game state is updated, not the graphics. For this particular example, where we want to have counters that increment each second, the game state refers to advancing the counter value exactly one time per second. The graphics update refers to actually drawing the sprite corresponding to the current game state (i.e. if current game state says the counter should be at “7” draw the sprite that shows a counter with the value “7”). Now, depending on what graphics are drawn at a particular moment, or the overall performance of the hardware, we may run into situations where the graphics drawing take too long. In order to compensate for this, once such a long time running drawing happens, on the next game loop we’ll update the game state faster (more times) until the overall game advancement rate “catches up” with the average value we want.

Let’s see how all this is implemented in the above code snippet:

– On each game loop, we first measure the current time. When the loop ends we measure the current time once more and then calculate the duration of this particular game loop step and keep it in a global variable
– Next the loop will do a graphics rendering (mainWindow.updateGraphics()). This is the “variable step” part. It will be called as fast as possible, with one limiting condition:
– when the rendering for this game loop step is done, we look at how much time has accumulated so far. From this we deduce how far behind the fixed step execution is. As an actual example of this, imagine that we want to have 25 fixed steps per second. That means that once 1/25 = 40 milliseconds have past since the last fixed step, we need to do another fixed step. Now, imagine that the variable step (the graphics rendering part) actually took 95 milliseconds on the previous game loop step. This means that our accumulatedTimeMs=95, and we need to do 2 fixed steps (2×40 ms) in order to catch up, leaving an accumulatedTimeMs reminder of 95 – (2 x 40) = 15 milliseconds to keep for the next step in the loop.

If you run the example, you’ll notice that this time the window displays two update rate values: UPS (updates per second, refering to the local game state update rate) and FPS (frames per second, refering to the rate with which the grapics are updated):

As before, the code is “rigged” so that when one of the counters is displaying “7”, it will simulate a delay of 50 ms for the graphics rendering. What will happen this time is that this will mostly influence the graphics update rate (FPS value), which will drop sharply for a while, while the game state update rate (UPS) will drop a lot less (or possibly not at all) and will catch up as soon as it can (namely, when the counters gets to “8” and the graphics updates are no longer “slow”, then more game state updates will be executed for a while, until the average game state update rate is back to 25/second, aka accumulatedTimeMs is less then 1/25 = 40 milliseconds).

This implementation of the game loop is better then the previous example:

– firstly, the game state update rate is independent of the graphics update rate. Thus it is less influenced by how fast the graphics can be drawn, making the game advancement rate stick more closely to the desired (average) value.
– also, now we can easily change the state update rate as desired, without influencing how fast the graphics will be drawn. For example: for this particular example, a game state update rate of 25 per second is too high. We can lower it to 5 per second (since the actual game state only needs to change once every second) thus saving some CPU usage for the calculation of the game state.
– the downside here is that even though the game update steps are capped to a given (constant) value, the graphics rendering steps will run as fast as they can, aka they will “fill all the time gaps” left by the fixed game state update steps. Again this is not ideal, as more resources than necessary are consumed because of it.

The next part of the article will showcase various game loop implementations using C and OpenGL. We’ll see how to tap into the existing loop OpenGL gives us, as well as how to better control the game loop’s advancement rate in order to have a more economical usage of hardware resources.

The Code Example

The code can be git-cloned from here:

https://gitlab.com/shivansite/JGameLoopStudy.git

In order to actually run the application, the content of both “src” and “res” folders need to be added to the class path (if using Eclipse, make sure both these folders are declared as “source folders”).

The “Basic Variable Step Game Loop” example should be run using the “com.shivandragon.jGameLoopStudy.basicVariableStepGameLoop.BasicVariableGameLoop” main class.

The “Basic Mixed Step Game Loop” example should be run using the “com.shivandragon.jGameLoopStudy.basicMixedStepGameLoop.BasicMixedGameLoop” main class.

It should be noted that, in order to simplify the code, and focus only on the game loop implementation part, the way in which the Java Swing library is used in these examples to make graphics renderings is not the recommended one.

Swing offers the “paintComponent” method which normally should be overridden with the desired draw calls, letting Swing call it whenever it deems necessary. These examples avoid this and simply call “getGraphics().drawXXX” each time the game loop deems it necessary to make a graphics update. While for the two above-mentioned examples there’s no visible problem, you can see how this can lead to bad graphics artifacts by running the “com.shivandragon.jGameLoopStudy.inputMixedStepGameLoop.InputMixedGameWindow” main class. This example also contains user input handling. If a left-button mouse click is performed anywhere inside the application window, the counter will be moved at that position. In order to handle the redrawing of this, the “repaint()” method in called on the JPanel. This leads to image “flickering”. This could be fixed by refactoring the code to properly use the Swing library, but it’s beyond the scope of this article. However, in the words of every math textbook I’ve had in primary school: “this is left as a potential exercise for the reader” :)

Advertisements
This entry was posted in Examples, Game Dev and tagged , , , , , , , . Bookmark the permalink.

7 Responses to The Basics of Game Loop Implementation – part 1

  1. Pingback: The Basics of Game Loop Implementation – part 2 | Shivan's Blog

  2. Pingback: The Basics of Game Loop Implementation – part 3 | Shivan's Blog

  3. Pingback: Using a Queue for User Input Evens | Shivan's Blog

  4. Pingback: Using a Queue for User Input Events | Shivan's Blog

  5. VBA4all says:

    Thanks for this very nice article on A*.

    One question though:

    Why when you start h = 12 ? How did you work that out?

  6. shivand says:

    Hi. In short: it’s because I’ve set the “size” (width or height) of a cell to 3. I chose to set it to 3 and not 1 or some other value because I’ve noticed that with other values I sometimes got wrong results due to rounding (precision loss) errors when calculations were made to obtain a path.

    So, in my example, the start position has a g score of 0 and a h score (heuristic estimation of distance from start to finish) of 12, so the start position’s f score is 0 + 12 = 12.

    h is 12 because the start position is 4 squares away from the destination position “as the crow flies” (ignoring obstacles). So using Pythagoras and keeping in mind that each cell has a size of 3, we get 3 * 4 = 12.

  7. It’ѕ hardd to fіnd educatedd people fⲟr thiѕ topic, ƅut you sem lіke you
    knoѡ what үou’гe talking about! Thanks

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s