Tuesday, May 20, 2014

Pong, a.k.a. Retro Game I, available in the App Store!

Right after finishing Pong, I started the experiment of porting it to iOS, mainly to learn more about RoboVM. After a bit of research and asking questions on the RoboVM Google group, I got the game running on my iPhone 5 and wondered if Apple would accept it into the App Store. After a bit more research and asking questions on said Google group, I finally had a valid and signed IPA, sent it to Apple and crossed my fingers. Much to my surprise, on May 16th the light turned green and Pong (rebranded as Retro Game I) was available on the App Store:

https://itunes.apple.com/us/app/retro-game-i/id876950489

For a while I thought this was the first JavaFX app on the App Store. That turned out not to be the case (https://itunes.apple.com/de/app/ultramixer-remote/id669471908 was first), but as far as I know it still is the first open source one ;)

Even though the iOS port has some issues, this has been a fun, exciting and successful experiment!

For those of you wanting to try out JavaFX on iOS for yourself, I'll spend the remainder of this post recapping the steps I took to port the game to iOS and publish it to the App Store.

Source code

The complete project (source code, configuration files and assets) is available on GitHub:

https://github.com/svanimpe/pong/

Make sure you get the ios branch, and run it on JDK 7. See this post if you're new to Git and/or Maven. It explains how to get the code from GitHub and run it in NetBeans.

Prerequisites

You will need a Mac with Xcode installed and a JavaFX project to start from. I'll be using the RoboVM Maven plugin, so you'll need to use Maven for your project. My initial POM contained the following:

<groupId>svanimpe</groupId>
<artifactId>pong</artifactId>
<version>1.0-SNAPSHOT</version>
<packaging>jar</packaging>

<name>Pong</name>
<url>https://github.com/svanimpe/pong</url>

<properties>
    <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
    <maven.compiler.source>1.7</maven.compiler.source>
    <maven.compiler.target>1.7</maven.compiler.target>
    <mainClass>svanimpe.pong.ui.Pong</mainClass>
</properties>

<dependencies>
    <dependency>
        <groupId>com.oracle</groupId>
        <artifactId>javafx</artifactId>
        <version>2.2</version>
        <scope>system</scope>
        <systemPath>${java.home}/lib/jfxrt.jar</systemPath>
    </dependency>
</dependencies>

I also added -Xbootclasspath/a:"${env.JAVA_HOME}/jre/lib/jfxrt.jar" to all my NetBeans actions in nbactions.xmlto add jfxrt.jar to the boot classpath. You can do the same in your POM if you don't use NetBeans, but since I will use nbactions.xml again later on, I did it this way. Just make sure java.home refers to JRE 7, not 8. With this you should be able to run your JavaFX Maven project. Try it out and fix any issues before you continue.

Prepare for RoboVM

RoboVM does not support Java 8 so make sure you're not using any Java 8 language features or API. RoboVM uses a backport of OpenJFX 8 so don't use anything from JavaFX 2 that has been removed in JavaFX 8. Also, audio is not yet supported on iOS. There probably are other unsupported features as well, but audio is the only one I needed to remove from Pong to get it running on iOS.

Configure RoboVM

RoboVM uses robovm.properties and robovm.xml as configuration files, as well as Info.plist.xml which contains information about your application bundle. My files contain the following:

robovm.properties:

app.version=1.0
app.id=svanimpe.pong
app.mainclass=svanimpe.pong.ui.iOSLauncher
app.executable=Pong
app.build=1
app.name=Retro Game I

robovm.xml:

<?xml version="1.0" encoding="UTF-8"?>
<config>
    <executableName>${app.executable}</executableName>
    <mainClass>${app.mainclass}</mainClass>
    <os>ios</os>
    <arch>thumbv7</arch>
    <resources>
        <resource>
            <directory>resources</directory>
        </resource>
    </resources>
    <target>ios</target>
    <iosInfoPList>Info.plist.xml</iosInfoPList>
</config>

Of note here is the resources folder which contains the required icons, launch images, etc. See Apple's information on App Related Resources to figure out what files you need.

Info.plist.xml:

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
    <dict>
        <key>CFBundleDevelopmentRegion</key>
        <string>en</string>
        <key>CFBundleDisplayName</key>
        <string>${app.name}</string>
        <key>CFBundleExecutable</key>
        <string>${app.executable}</string>
        <key>CFBundleIdentifier</key>
        <string>${app.id}</string>
        <key>CFBundleInfoDictionaryVersion</key>
        <string>6.0</string>
        <key>CFBundleName</key>
        <string>${app.name}</string>
        <key>CFBundlePackageType</key>
        <string>APPL</string>
        <key>CFBundleShortVersionString</key>
        <string>${app.version}</string>
        <key>CFBundleSignature</key>
        <string>????</string>
        <key>CFBundleVersion</key>
        <string>${app.build}</string>
        <key>NSHumanReadableCopyright</key>
        <string>Copyright © 2014 Steven Van Impe. All rights reserved.</string>
        <key>LSRequiresIPhoneOS</key>
        <true/>
        <key>UIDeviceFamily</key>
        <array>
            <integer>1</integer>
        </array>
        <key>UIRequiredDeviceCapabilities</key>
        <array>
            <string>armv7</string>
            <string>opengles-2</string>
        </array>
        <key>UISupportedInterfaceOrientations</key>
        <array>
            <string>UIInterfaceOrientationLandscapeRight</string>
        </array>
    </dict>
</plist>

See Apple's Information Property List Key Reference for more information on what the different keys mean.

The last part of the configuration is to add RoboVM to your dependencies:

<dependency>
    <groupId>org.robovm</groupId>
    <artifactId>robovm-rt</artifactId>
    <version>0.0.12</version>
</dependency>
<dependency>
    <groupId>org.robovm</groupId>
    <artifactId>robovm-cocoatouch</artifactId>
    <version>0.0.12</version>
</dependency>

and configure the plugin:

<plugin>
    <groupId>org.robovm</groupId>
    <artifactId>robovm-maven-plugin</artifactId>
    <version>0.0.12.1</version>
    <configuration>
        <propertiesFile>robovm.properties</propertiesFile>
        <configFile>robovm.xml</configFile>
        <includeJFX>true</includeJFX>
    </configuration>
</plugin>

Launcher class

The final piece of the puzzle is the launcher class. This is an implementation of a UIApplicationDelegate required by iOS:

public class iOSLauncher extends UIApplicationDelegateAdapter
{
    @Override
    public boolean didFinishLaunching(UIApplication application,
                                      NSDictionary launchOptions)
    {
        Thread fxThread = new Thread(new Runnable()
        {
            @Override
            public void run()
            {
                Application.launch(Pong.class);
            }
        });
        fxThread.setDaemon(true);
        fxThread.start();
        return true;
    }
    
    public static void main(String... args)
    {
        System.setProperty("glass.platform", "ios");
        System.setProperty("prism.text", "native");
        
        NSAutoreleasePool pool = new NSAutoreleasePool();
        UIApplication.main(args, null, iOSLauncher.class);
        pool.drain();
    }
}

This class is completely reusable. Simply replace Pong.class with your JavaFX Application subclass.

Running on a simulator

After all this you should be able to run your app on the simulator with the Maven goals robovm:iphone-sim and robovm:ipad-sim. If you prefer the convenience of NetBeans, add the following actions to your nbactions.xml:

<action>
    <actionName>CUSTOM-device</actionName>
    <displayName>Run on device</displayName>
    <goals>
        <goal>robovm:ios-device</goal>
    </goals>
</action>
<action>
    <actionName>CUSTOM-iphone</actionName>
    <displayName>Run on iPhone simulator</displayName>
    <goals>
        <goal>robovm:iphone-sim</goal>
    </goals>
</action>
<action>
    <actionName>CUSTOM-ipad</actionName>
    <displayName>Run on iPad simulator</displayName>
    <goals>
        <goal>robovm:ipad-sim</goal>
    </goals>
</action>
<action>
    <actionName>CUSTOM-ipa</actionName>
    <displayName>Build IPA</displayName>
    <goals>
        <goal>robovm:create-ipa</goal>
    </goals>
</action>

These include the actions to run your app on a device and to build an IPA, which we'll need in the following sections.

Running on a device

If you want to run your app on a device, you'll need:

  • an iOS developer account.
  • to provision your device for development.

Follow Apple's steps on how to run your app on a connected device then connect the device and run the Maven goal robovm:ios-device or use the custom NetBeans action from the previous section.

Submit to the App Store

First go to iTunes Connect and create a new App Record. It should be in the status 'Waiting For Upload'. Then, similar to what you did in the previous section, create a signing identity and provisioning profile for distribution. It's easy enough through Xcode. Apple has more on this in the App Distribution Guide.

Next, configure the RoboVM Maven plugin to use your distribution (not development) signing identity and provisioning profile. My configuration is as follows:


<plugin>
    <groupId>org.robovm</groupId>
    <artifactId>robovm-maven-plugin</artifactId>
    <version>0.0.12.1</version>
    <configuration>
        <propertiesFile>robovm.properties</propertiesFile>
        <configFile>robovm.xml</configFile>
        <includeJFX>true</includeJFX>
        <iosSignIdentity>iPhone Distribution</iosSignIdentity>
        <iosProvisioningProfile>F40BF4FD-D09A-4548-8667-EE6E819D3755</iosProvisioningProfile>
    </configuration>
</plugin>

The iosProvisioningProfile key refers to the UUID of your provisioning profile. To find this value, go to the Apple Developer Member Center, download your distribution provisioning profile and open the downloaded file in TextEdit (or cat it on the command line).

With your signing identity and profile set up, you should be able to generate an IPA with the Maven goal robovm:create-ipa or using the custom NetBeans action. Finally, use Application Loader (it comes with Xcode) to submit your IPA. If your IPA contains all the required assets, and it's signed correctly, you should be fine. All that's left now is to sit back and wait a few days for your app to be reviewed.

Good luck!

Classic game programming: Pong

I originally started this blog to share a silly little game called Jumpman I wrote as an example of the State design pattern. Jumpman was pretty popular with my students and it made me realize that games might be a great way for me to get my students to roll up their sleeves, study my code and make games of their own.

I got back into game programming with the previous posts on game loops and I'd like to continue by releasing the first finished game: Pong.


Topics

The topics covered in this game are:
  • A game loop with variable time steps (as explained in the previous posts).
  • Game objects.
  • Keyboard controls.
  • Collision detection and 'faked physics'.
  • A simple AI to control the opponent paddle.
  • Multiple screens and switching between them.
  • Sound effects.
  • Scaling the screen while respecting the aspect ratio, using letter- and pillarboxing.
The code should contain enough comments to allow you to figure out what it does. Go read it!

Source code

The source code is available on GitHub:


Make sure you get the master branch, and run it on JDK 8. See this post if you're new to Git and/or Maven. It explains how to get the code from GitHub and run it in NetBeans.

Known issues

The game has some issues, the most important one resulting in jerky animations. See this issue on GitHub for a workaround.

Friday, May 16, 2014

Installing and running example projects

In this post I will explain how to install and run the newer example projects on this blog. This applies to all examples published since January 2014.

Software requirements

I'll assume you're using NetBeans 8. You can use another IDE, or no IDE at all, but the steps will be different.

Java EE 7 projects require the GlassFish 4 application server. It can be downloaded together with NetBeans.

Regular Java or JavaFX projects require JDK 8. Java EE projects are intended to be run on JDK 7. Your mileage may vary on JDK 8.

If you're using JDK 7 and JDK 8 concurrently, make sure to run NetBeans itself on JDK 7 by configuring jdk_home in netbeans.conf. Then add JDK 8 as an extra platform in Tools > Java Platforms. Don't forget to select the correct Java platform for each project you open or create.

The other tools you'll need are Git and Maven. NetBeans includes both.

Git and GitHub

Git is a version control system. Put very simply, it manages and tracks changes to the source code and allows multiple people to work on the same project. GitHub is used as a central repository. That's where the code is stored so that's where you'll download it from.

Every example project includes a link to a GitHub repository page. The repository page for Pong, for example, is at https://github.com/svanimpe/pong. The easiest way to get the project into NetBeans is by cloning it. For this, you'll need the HTTPS clone URL which can be found on the repository page. For Pong this URL is https://github.com/svanimpe/pong.git.

Cloning
To clone a project, use Tools > Git > Clone. Use the clone URL you found on the repository page, select the branches you want, make sure to scan for NetBeans projects and open them afterwards. You should now have your own copy of the project. You might have to take some additional steps to get the project running. These are covered below.

Branches
A project might have different branches. These can be viewed as different versions of the project. The master branch is the main version of the project. Other branches usually contain experimental work or platform-specific versions of the project. When using branches, it is helpful to open the repository browser (Team > Repository Browser) and to turn on versioning labels (View > Show Versioning Labels). To load a specific branch, right-click it in the repository browser and choose Checkout Revision. NetBeans will now show this version of the project.

Maven

Maven is a build tool, amongst other things. It provides a standardized way to structure a project, declare its dependencies, configure the steps needed to compile it, build it, package it, run tests, ... You don't need to know anything about Maven to use the example projects, but you might have to take a few steps to get a project running after cloning it:
  • If your fresh clone shows issues (as indicated by a yellow triangle), you might be missing some of the project's dependencies. Right-click the project, choose Resolve Project Problems and click Resolve. This will download the project's dependecies.
  • Right-click the project and choose Properties. Navigate to Build > Compile and set the correct Java platform.
That's it

You should now be able to run the project. Have fun!

Projects that require additional setup will mention this in their README file (which is shown on their repository page).

Friday, May 2, 2014

Game loops and applying them to JavaFX (2/2)

It's been a while, but it's finally here: part 2! In this part I will attempt to apply the general explanations in part 1 to JavaFX. Make sure you've read part 1 first.


Demo application

The application I built to test all of this out is available on GitHub: https://github.com/svanimpe/fx-game-loop



You can use this application to visually compare the different loops. This application uses Box2D (JBox2D) as a physics engine. Reading the "Hello Box2D" section in the Box2D manual should be sufficient to understand the code. The application is extensible so you can easily add new games/animations or game loop implementations and try them out.

Note that I am by no means a JavaFX, Box2D or game programming expert, so if you spot something that could or should be improved, let me know or send me a pull request!


Understanding JavaFX

Before we can talk about game loops, we need to discuss pulses. A pulse is a special event scheduled by JavaFX whenever animations are running or the scene otherwise needs updating. During a pulse:
  • animations are advanced.
  • CSS is applied.
  • layout is done.
  • the scene is synchronized with the render thread.
Pulses run at most 60 times per second, less if they take longer than 1/60th of a second. This means JavaFX already has target frame rate of 60FPS built-in. Less work for our game loop!

The easiest way to hook into the pulse system is to start an AnimationTimer. Objects of this class have a handle method. This method is called during every pulse and is passed the current time in nanoseconds. We'll use this handle method to implement our game loop.

To learn more about pulses, go watch the following talks on Parleys:

Variable time steps

The first implementation I'll discuss is that of a game loop using variable time steps. This is an implementation of "Variable time steps - variable frame rate with a target frame rate and a maximum time step" from part 1.

First note that I moved the implementation into a separate class VariableSteps and used callbacks to tell the loop what to do at certain points:

private final Consumer<Float> updater;
private final Runnable renderer;
private final Consumer<Integer> fpsReporter;

public VariableSteps(Consumer<Float> updater,
                     Runnable renderer,
                     Consumer<Integer> fpsReporter)
{
    this.updater = updater;
    this.renderer = renderer;
    this.fpsReporter = fpsReporter;
}

The updater will be called to update the physics state based on the amount of time passed. Next, the renderer will be called to update the properties of the nodes on screen based on their updated physics state. Finally, the fpsReporter will be called twice per second to update the FPS status on screen.

Class VariableSteps inherits from class GameLoop, which holds a maximumStep property common to all game loops in the demo application. Class GameLoop inherits from AnimationTimer so all our game loops are AnimationTimer subclasses and will override the handle method. For the variable time steps implementation, this is done as follows:

private long previousTime = 0;
private float secondsElapsedSinceLastFpsUpdate = 0f;
private int framesSinceLastFpsUpdate = 0;

@Override
public void handle(long currentTime)
{
    if (previousTime == 0) {
        previousTime = currentTime;
        return;
    }

    float secondsElapsed = (currentTime - previousTime) / 1e9f;
    float secondsElapsedCapped = Math.min(secondsElapsed, getMaximumStep());
    previousTime = currentTime;

    updater.accept(secondsElapsedCapped);
    renderer.run();

    secondsElapsedSinceLastFpsUpdate += secondsElapsed;
    framesSinceLastFpsUpdate++;
    if (secondsElapsedSinceLastFpsUpdate >= 0.5f) {
        int fps = Math.round(framesSinceLastFpsUpdate /
                             secondsElapsedSinceLastFpsUpdate);
        fpsReporter.accept(fps);
        secondsElapsedSinceLastFpsUpdate = 0;
        framesSinceLastFpsUpdate = 0;
    }
}

This implementation can be split up into four parts:
  1. If this is the first frame, simply record the current time.
  2. Calculate the amount of time passed since the previous frame (also converting nanoseconds to seconds) and adjust this to the maximum time step.
  3. Call the updater and renderer callbacks.
  4. Calculate FPS and report it to the fpsReporter callback.
I also override the stop method from AnimationTimer so the loops can be restarted:

@Override
public void stop()
{
    previousTime = 0;
    secondsElapsedSinceLastFpsUpdate = 0f;
    framesSinceLastFpsUpdate = 0;
    super.stop();
}

Note that some of the choices I made here were intended to keep the code clean and readable, and to suit the demo application. For example:
  • If you don't implement your game loop as a separate class, or implement it as an inner class, you might not need callbacks.
  • If you don't need to be able to restart the game loop, you don't need to override the stop method.
  • If you don't need to track FPS, you can ofcourse delete that part of the code.

Fixed time steps

Next up are fixed time steps. This is an implementation of "Fixed time steps using an accumulator and a maximum delta time" from part 1.

Class FixedSteps has two additional attributes compared to class VariableSteps:

private static final float timeStep = 0.0166f;
private float accumulatedTime = 0;

These attributes are used in both the handle and stop methods:

@Override
public void handle(long currentTime)
{
    if (previousTime == 0) {
        previousTime = currentTime;
        return;
    }

    float secondsElapsed = (currentTime - previousTime) / 1e9f;
    float secondsElapsedCapped = Math.min(secondsElapsed, getMaximumStep());
    accumulatedTime += secondsElapsedCapped;
    previousTime = currentTime;

    while (accumulatedTime >= timeStep) {
        updater.accept(timeStep);
        accumulatedTime -= timeStep;
    }
    renderer.run();

    secondsElapsedSinceLastFpsUpdate += secondsElapsed;
    framesSinceLastFpsUpdate++;
    if (secondsElapsedSinceLastFpsUpdate >= 0.5f) {
        int fps = Math.round(framesSinceLastFpsUpdate /
                             secondsElapsedSinceLastFpsUpdate);
        fpsReporter.accept(fps);
        secondsElapsedSinceLastFpsUpdate = 0;
        framesSinceLastFpsUpdate = 0;
    }
}

@Override
public void stop()
{
    previousTime = 0;
    accumulatedTime = 0;
    secondsElapsedSinceLastFpsUpdate = 0f;
    framesSinceLastFpsUpdate = 0;
    super.stop();
}

As you can see, this is a pretty straightforward implementation of the pseudo-code in part 1. Things start to get interesting when we add interpolation, which is what I'll discuss next.


Fixed time steps with interpolation

This is an implementation of "Fixed time steps using an accumulator, a maximum delta time and interpolation" from part 1.

At first sight, implementing interpolation seemed like quite a challenge. In order to interpolate, we need to maintain two separate states to interpolate between, namely the current state and the next state. This seemed like a lot of work, until I made the following observation: combining JavaFX with a physics engine automatically results in two separate states. On the one hand there is the state of the JavaFX nodes (translateX, translateY, ..) while on the other, there's the state of the physics bodies. Having realized that, I tried to come up with a clever implementation of interpolation that would not require any additional state on top of what we already have.

First we introduce an additional callback to handle interpolation:

private final Consumer<Float> updater;
private final Runnable renderer;
private final Consumer<Float> interpolater;
private final Consumer<Integer> fpsReporter;

public FixedStepsWithInterpolation(Consumer<Float> updater,
                                   Runnable renderer,
                                   Consumer<Float> interpolater,
                                   Consumer<Integer> fpsReporter)
{
    this.updater = updater;
    this.renderer = renderer;
    this.interpolater = interpolater;
    this.fpsReporter = fpsReporter;
}

This interpolater will be called with the current alpha value to interpolate between the current state and the next state as discussed in part 1. Next, the implementation I came up with goes as follows:

@Override
public void handle(long currentTime)
{
    if (previousTime == 0) {
        previousTime = currentTime;
        return;
    }

    float secondsElapsed = (currentTime - previousTime) / 1e9f;
    float secondsElapsedCapped = Math.min(secondsElapsed, getMaximumStep());
    accumulatedTime += secondsElapsedCapped;
    previousTime = currentTime;

    if (accumulatedTime < timeStep) {
        float remainderOfTimeStepSincePreviousInterpolation = 
            timeStep - (accumulatedTime - secondsElapsed);
        float alphaInRemainderOfTimeStep =
            secondsElapsed / remainderOfTimeStepSincePreviousInterpolation;
        interpolater.accept(alphaInRemainderOfTimeStep);
        return;
    }

    while (accumulatedTime >= 2 * timeStep) {
        updater.accept(timeStep);
        accumulatedTime -= timeStep;
    }
    renderer.run();
    updater.accept(timeStep);
    accumulatedTime -= timeStep;
    float alpha = accumulatedTime / timeStep;
    interpolater.accept(alpha);

    secondsElapsedSinceLastFpsUpdate += secondsElapsed;
    framesSinceLastFpsUpdate++;
    if (secondsElapsedSinceLastFpsUpdate >= 0.5f) {
        int fps = Math.round(framesSinceLastFpsUpdate /
                             secondsElapsedSinceLastFpsUpdate);
        fpsReporter.accept(fps);
        secondsElapsedSinceLastFpsUpdate = 0;
        framesSinceLastFpsUpdate = 0;
    }
}

It's easier to understand this code if you skip the special case where the accumulator is less than the time step and start reading at the while loop. The algorithm then goes as follows:
  1. Keep calling the updater as long as there are two or more time steps remaining in the accumulator. After this is done, there is one complete time step left in the accumulator, and possibly a remainder as well.
  2. Call the renderer. This updates the state of the nodes based on the current physics state, which will soon be the previous physics state, because there is still one time step left in the accumulator. For an example of 'rendering', see the method updatePosition below.
  3. Do the final time step. At this point, the physics state is one step ahead of the state on screen. Calculate the alpha value based on the time remaining in the accumulator.
  4. Call the interpolater with this alpha value. This will interpolate all game objects between their current state (the state of the node, based on the previous physics state) and their next state (the current physics state, as a result of the final time step). For an example of interpolation, see the method interpolatePosition below.
Rendering and interpolation examples taken from the class Ball:

public void updatePosition()
{
    if (!body.isAwake()) {
        return;
    }
    setTranslateX(body.getPosition().x * SCALE);
    setTranslateY((HEIGHT - body.getPosition().y) * SCALE);
}

public void interpolatePosition(float alpha)
{
    if (!body.isAwake()) {
        return;
    }
    setTranslateX(alpha * body.getPosition().x * SCALE +
                  (1 - alpha) * getTranslateX());
    setTranslateY(alpha * (HEIGHT - body.getPosition().y) * SCALE +
                  (1- alpha) * getTranslateY());
}

These methods transform the world coordinates (the x and y positions of the physics body) into screen coordinates (based on the SCALE and HEIGHT settings of the game) and update the translateX and translateY properties of the node used to represent a Ball on screen.

Finally, there's a special case where the accumulator is less than the time step. In this case we need to re-interpolate between the same two states we used for the previous interpolation. But this is impossible, as one of those states (the state of the node, based on the previous physics state) got overwritten during the previous interpolation. By summoning the vast power of mathematics however, we can adjust the alpha value to interpolate not between the previous physics state (which we don't have anymore) and the current physics state, but between the previous interpolation (which is now the state of the node) and the current physics state. Doing it this way avoids having to store multiple physics states.


Results

I was very happy to see the expected behaviour reproduced in the demo application:
  • Physics issues quickly appear when using variable time steps.
  • A lot less physics issues appear when using fixed time steps. The issues that remain seem to be normal and a matter of accuracy vs. speed when configuring the physics engine.
  • The spiral of death is easily reproduced by simulating a large number of objects without using a maximum step.
  • Using a maximum time step causes the game to slow down instead of spiraling to death whenever the machine can't keep up.
  • Interpolation does seem to smoothen out the animation. Try setting the demo application to fixed steps without interpolation, choose a low number of objects so the animation can run at full speed and turn off the maximum step. Look for glitches when a ball is stepped twice in one frame, instead of the usual one step per frame. Then turn on interpolation and see if these glitches disappear.
Please let me know what results you observe and contact me if you think anything can or should be improved!

Sunday, January 12, 2014

Game loops and applying them to JavaFX (1/2)

After spending almost an entire year doing nothing but JavaEE, I decided it was time to have some fun and got back to one of the items on my to-do list: write a series of classic game programming examples using Java and JavaFX. The first such example should be online in the near future, but for now, I'd like to share some thoughts on an important topic for beginning game programmers (that includes myself): the game loop.

Note: part 2 is now available!

The basic loop

If you've done any GUI programming at all, you'll know that GUI frameworks are event-driven. This means that the framework doesn't do very much, it simply waits for an event to occur, processes it, then waits for the next one. Games on the other hand tend to use a loop as a heartbeat that moves time forward.

The simplest possible game loop looks something like:

while (!gameOver)
{
    processEvents();
    updateWorld();
    renderFrame();
}

As you can probably tell, this loops handles any input that needs handling, moves the state of the game world one step forward in time, then renders this new state on screen.

This implementation of the game loop isn't very useful. It simply runs the loop as fast as possible. The result of this is that the faster your machine is, the faster time will move forward in the game. You could end up with a game character walking in slow motion on one machine, while running at the speed of light on another. This approach to a game loop is often called a CPU dependent game loop, for obvious reasons. It could work in situations where the speed of the machine is fixed and known, but that's usually not the case.

In what follows we'll explore several possibilities to improve upon this basic approach. Note that while the code examples will be in Java, they are intended only as illustrations and do not cover every single detail or edge case, so they should be viewed as pseudo-code only.

Variable time steps

Think about this for a while: instead of using a fixed time step (as we did in the basic approach), why not simply measure how much time has passed since the previous iteration of the loop, and use that time difference to update the game world? By synchronising the game time with the real time, the game time will progress at a constant speed, no matter the speed of the machine.

Variable time steps - variable frame rate


A first implementation of this idea could look like:


long previousTime = System.nanoTime();

while (!gameOver)
{
    long currentTime = System.nanoTime();
    long elapsedNanos = currentTime - previousTime;
    double deltaTime = elapsedNanos / 1_000_000_000.0; /* to seconds */

    processEvents();
    updateWorld(deltaTime);
    renderFrame();

    previousTime = currentTime;
}

In this approach the game world is no longer updated with fixed time steps, but with time steps that depend on the actual time that has passed since the previous iteration of the loop. If one machine is able to run this loop 100 times per second, that machine will update the world 100 times with time steps averaging 10ms. If another machine is only able to run the loop 50 times per second, that machine will update the world 50 times per second with time steps averaging 20ms. The result is the same on both machines: after 1 second of real time, the game time has advanced by 1 second as well.

This approach may seem great at first: not only does the game progress at a constant speed independent of the underlying hardware, the loop actually adjusts the frame rate to the underlying hardware as well as to the current load. The loop runs as fast as possible, but when the load increases (for example: if there are lots of objects that need to be updated), the time steps will increase as well, lowering the frame rate. If the load decreases, the time steps will decrease as well, raising the frame rate.

Variable frame rates are not without their issues however, especially when physics are involved:
  • Low frame rates result in large time steps. Large time steps can cause objects to 'jump' between points, instead of moving smoothly between them. This in turn could result in collisions going undetected, allowing your game objects to pass through one another.
  • High frame rates result in small time steps. As you probably know, floating point numbers only have limited precision, so floating point calculations often involve some sort of rounding error. If the time steps get too small, an unnecessary amount of calculations is performed. This could result in rounding errors accumulating to a point where your game objects end up in the wrong place.
Instead of throwing variable frame rates out the window, let's see if we can address some of these issues.

Variable time steps - variable frame rate with a target frame rate


The first issue we'll address is small time steps as a result of high frame rates. The solution for this is quite simple: impose an upper bound on the frame rate by making the loop wait until a minimum amount of time has passed.

This approach looks something like:

final double targetDelta = 0.0166; /* 16.6ms ~ 60fps */
long previousTime = System.nanoTime();

while (!gameOver)
{
    long currentTime = System.nanoTime();
    double deltaTime = (currentTime - previousTime) / 1_000_000_000.0; 

    processEvents();
    updateWorld(deltaTime);
    renderFrame();

    previousTime = currentTime;

    double frameTime = (System.nanoTime() - currentTime) / 1_000_000_000.0;
    if (frameTime < targetDelta) {
        /* wait targetDelta - frameTime seconds */
    }
}

As you can see, we measure the time it took to update the world and if necessary, make the loop wait a while before starting the next iteration. The resulting loop is said to have a target frame rate of 60fps. Because every iteration takes at least 16.6ms, the time steps will never be smaller than 16.6ms.

Variable time steps - variable frame rate with a target frame rate and a maximum time step


The technique we used to address small time steps unfortunately cannot be applied to large time steps as well: while we can tell the loop to wait a while, we can't tell it to 'hurry up' because our frame rate is getting too low. If the hardware can't keep up with our demand, the performance will degrade. There isn't much to be done about that. But we do have a choice as to how the game degrades:

  • We stick to the previous implementation and let the frame rate drop. As a result, the game time keeps progressing at a constant speed but the time steps will grow larger, possibly making the game unplayable due to increased latency and physics issues.
  • We impose an upper bound on the time steps. As a result, we are effectively slowing down time in the game because the time steps used to update the game will be smaller than the actual time that has passed. Whether or not this makes the game any more playable at low frame rates than with the previous approach is hard to say.

If you prefer the second option, your implementation could look like:

final double targetDelta = 0.0166;
final double maxDelta = 0.05;
long previousTime = System.nanoTime();

while (!gameOver)
{
    long currentTime = System.nanoTime();
    double deltaTime = (currentTime - previousTime) / 1_000_000_000.0; 
    
    if (deltaTime > maxDelta) {
        deltaTime = maxDelta;
    }

    processEvents();
    updateWorld(deltaTime);
    renderFrame();

    previousTime = currentTime;

    double frameTime = (System.nanoTime() - currentTime) / 1_000_000_000.0;
    if (frameTime < targetDelta) {
        /* wait targetDelta - frameTime seconds */
    }
}

Fixed time steps

It turns out our basic loop did have one advantage: fixed time steps. While the variable time step approach in the previous section might work fine for you, there are a few reasons why you should consider opting for a truly fixed time step.

Fixed time steps are the only way to get truly deterministic (and thus reproducible) behavior. As we discussed before, floating point calculations are not without errors. The result of a 16.4ms time step followed by a 16.8ms time step might not be the same as the result of two 16.6ms time steps. Fixed time steps and the resulting determinism makes it possible to:
  • track down bugs by reproducing the exact circumstances in which the bug occurred.
  • synchronise network play.
  • provide instant replays.

Fixed time steps using an accumulator


Let's take a stab at re-implementing our game loop using fixed time steps:

final double timeStep = 0.0166;
long previousTime = System.nanoTime();
double accumulatedTime = 0;


while (!gameOver)
{
    long currentTime = System.nanoTime();
    
double deltaTime = (currentTime - previousTime) / 1_000_000_000.0;
    
accumulatedTime += deltaTime;

    processEvents();


    while (
accumulatedTime >= timeStep) {
        updateWorld(timeStep);
        
accumulatedTime -= timeStep;
    }


    renderFrame();


    previousTime = currentTime;
}


The technique here is to slice the amount of time passed into timeStep-sized pieces. If we measured a delta time of 34ms and our time step is 16ms, we simply step the world twice. The remaining 2ms are saved in the accumulator and carried over to the next iteration. By doing this, the game time will progress at a relatively constant speed, yet we have all the benefits of a fixed time step.

There are two issues with this approach however. The first issue is that the number of steps taken in each iteration of the loop can vary. Let's say our time step is set at 16ms, yet most frames take 17-18ms. This 1-2ms difference will slowly build up in the accumulator until it reaches 16ms. At that point the game will move forward 32ms instead of the usual 16ms. This leads to what is knows as temporal aliasing.

The second issue is the so called 'spiral of death' where if one interation takes up a lot of time, the next iteration will have to take additional time steps, causing that iteration to take up even more time, etc. This issue didn't exist with variable time steps because we were updating the world only once, albeit with a large time step.


Fixed time steps using an accumulator and a maximum delta time


Let's start by addressing the spiral of death:

final double timeStep = 0.0166;
final double maxDelta = 0.05;
long previousTime = System.nanoTime();
double accumulatedTime = 0;

while (!gameOver)
{
    long currentTime = System.nanoTime();
    double deltaTime = (currentTime - previousTime) / 1_000_000_000.0;

    if (deltaTime > maxDelta) {
        deltaTime = maxDelta;
    }

    accumulatedTime += deltaTime;

    processEvents();

    while (accumulatedTime >= timeStep) {
        updateWorld(timeStep);
        accumulatedTime -= timeStep;
    }

    renderFrame();

    previousTime = currentTime;
}

As you can see, this is exactly the same as what we did with the variable time steps. The result is the same as well: by limiting delta time to maxDelta, the game time will effectively slow down once delta time gets larger than maxDelta.


Fixed time steps using an accumulator, a maximum delta time and interpolation


Now, how do we take care of temporal aliasing? Temporal anti-aliasing ofcourse, which in this case boils down to a seemingly simple interpolation:

final double timeStep = 0.0166;
final double maxDelta = 0.05;
long previousTime = System.nanoTime();
double accumulatedTime = 0;

while (!gameOver)
{
    long currentTime = System.nanoTime();
    double deltaTime = (currentTime - previousTime) / 1_000_000_000.0;

    if (deltaTime > maxDelta) {
        deltaTime = maxDelta;
    }

    accumulatedTime += deltaTime;

    processEvents();

    while (accumulatedTime >= timeStep) {
        updateWorld(timeStep);
        accumulatedTime -= timeStep;
    }

    interpolateWithAlpha(accumulatedTime / timeStep);

    renderFrame();

    previousTime = currentTime;
}

What the interpolation does is simply guess where all the game objects would have been, had we taken the remaining accumulated time into account. This can be expressed as follows:

interpolatedState = currentState + alpha * (nextState - currentState)

which is equal to:

interpolatedState = (1 - alpha) * currentState + alpha * nextState

For example: if the remaining accumulated time is 25% of a complete time step, this interpolation guesses where the game objects would have been, had we taken an additional 25% of a time step.

While this all looks simple in pseudo-code, implementing interpolation is not as easy as the pseudo-code makes it look. In order to calculate the interpolated state, you need to maintain two separate copies of the game state: the current state as well as the next state.

Also note that because the physics system always needs to calculate one step ahead (we need the next state to do the interpolation), this technique adds additional input latency to your game.


Results

So which implementation should you use? My short answer would be: if you're using a physics engine, you need fixed time steps, period. If not, variable time steps might be easier to implement and work just fine. For a more thorough comparison, see part 2!


References

I learned the most from the following sources, so go and check them out: