Game replay techniques and the importance of floating point determinism

Working our way towards release we're currently going through a heavy bugfixing phase on the Macintosh version of Eets. One particularly interesting bug was causing incorrect level replays and the official solution video (not really videos but ingame replays) to be incorrect. We had a floating point determinism problem

Level completion replays and solution videos in Eets work by replaying user input. It makes a lot of sense to do this as user input is, relatively speaking, low frequency. To achieve the same results by recording the state of the all the objects in the game would make replay files a *lot* larger. (Consequently - The same technique can be used in writing a network game. Often known as the lockstep technique)

To be able to playback recorded user input into the game engine and have it play out exactly the same, the engine must be completely deterministic. A couple of key components needs to be addressed or things go very wrong.

For starters, the engine's random number generators are in fact not random at all. They need to play out the same random appearing numbers after being seeded each time. Secondly the mathematics of gameplay and engine need to be completely deterministic. This is actually not as easy as it sounds.

Next up, the physics engine needs to be designed from the beginning with determinism in mind. In particular iterative solvers are likely culprits for breaking determinism. Finally, the floating point math in all of it, needs to be deterministic. The floating point math situation is pontially one of the most tricky parts. Calls out to function in the operating system and other libraries - you frequently have not control over and they vary from platform to platform.

Once would think floating point math would always yield the same results, but the results actually vary slightly between processor, operating system, compiler and instruction set. Typically it's rounding method differences that are at play in this diverging scenario. (Did you know? - banking software avoids floats or doubles because of the way they handle rounding).

When floating point math was first catered for in silicon; a number of different ways of doing things made it out into the wild. The bulk of the computing public is using x86 type chips these days. In the early days of x86 floating point math was done in software, and understandably it was pretty slow. At some point the x87 co-processors were introduced. They were physically separate processors, and had their own instruction sets. Now the same instruction set exists today within your average Intel and AMD processor. It still gets used in software today but there are even more possibilities thrown into the mix. First came MMX (the multimedia instruction set), then MMX2, SSE, SSE2, and finally SEE3. Not to mention 3DNow and a similarly targeted instructions set. All of these instructions sets and their corresponding silicon implement floating point math in various ways and to varying degrees.

The Institute of Electrical and Electronic Engineers ratified a standard way of doing floating point math. The standard is known as ieee754. Making sure that your floating point math happens in a standardised way goes a long way to reducing the potential for different results.

Since most games engines update through time iteratively a small error early in the piece can create vastly different results down the track.

Mathematical methods like cos, tan and the other trigonometric functions are also common causes for different results on systems. The reason being that they're so called transcendental functions. That is they generate results by evaluating geometric series. Unfortunately this allows for plenty of scope for error.

Some tips on how to locate and improve floating point math determinism problems.

• Use modern ieee754 compliant processor instruction sets SSE and up. Many compilers can be told to automatically use them for floating point math, otherwise you can manually use them via compiler intrinsics or assembly code.


• Make sure you know what level of floating point optimisations are being using by the compiler when compiling. For the Microsoft Compilers look for problematic switches like /fp:fast. For gcc look for -mfpmath=sse and -msse and/or -msee2(x86 specific).


• Check results from Transcendental functions (tan, sin, cos and their ilk). If they're causing problems what in software versions outside of the system library that you have control over.

Bresenham's circle, Open GL and blowing holes in textures

Bresenham's circle algorithm is actually a variation on Bresenham's line drawing algorithm and as such it gets it's name, even though Bresenham didn't really invent the circle part.

Playing with destructable terrain I wanted to be able to blow circular holes in a texture. I succeeded by fetching a texture with Open GL and twiddling the bytes with the circle algorithm to do so.

The code below is in the spirit of what I did. Below is the main meat method on the algorthim, you might call it DrawFilledCircle() or some such.

..

/*

Input Parameters:

Vector2 pos; // The position of the explosion/circle center in texture pixel space.
float radius; // The radius of the explosion/circle in pixels
unsigned char* buf; // The pixel array - pixels are in RGBA format
Texture* texure; // a texture or texture info pointer
Colour colour; // the colour RGBA that you want the circle to be
*/

int width = texture->GetWidth();
int height = texture->GetHeight();

int left = int(pos.x - radius);
int right = int(pos.x + radius);
int top = int(pos.y + radius);
int bottom = int(pos.y - radius);

// check to see the circle will even touch the texture
if (!((left < width && right > 0) && (bottom < height && top > 0)))
{
return;
}

int max_x = std::min(right, width);
int max_y = std::min(top, height);

int r = (int)radius;
int x = 0;
int y = r;

float p = 1 - r;

while (x < y)
{
if (p < 0)
{
x += 1;
p = p + 2 * x + 1;
}
else
{
x += 1;
y -= 1;
p = p + 2 * (x - y) + 1;
}
CircleLineFill(buf, width, -x + pos.x, y + pos.y, x*2, colour, max_x, max_y);
CircleLineFill(buf, width, -x + pos.x, -y + pos.y, x*2, colour, max_x, max_y);
CircleLineFill(buf, width, -y + pos.x, x + pos.y, y*2, colour, max_x, max_y);
CircleLineFill(buf, width, -y + pos.x, -x + pos.y, y*2, colour, max_x, max_y);
}

The next method is CircleLineFill. This is a slight variation of the normal algorithm that draws just the outline of a circle, it doesn't fill the circle. This method fills the entire circle, leaving the edges of the intersection with a black edge.


void CircleLineFill((unsigned char* buf, int width, int x, int y, int length, Colour col, int max_x, int max_y))
{
if ((y < 0 || y >= max_y) ||
(x + length < 0) ||
(x >= max_x ))
return;

int right = std::min(x + length - 1, max_x);
int left = std::max(0, x + 1);

Colour* pixel = NULL;
if (x >= 0)
{
pixel = (Colour*)((char*)buf + (y * width * sizeof(Colour) + sizeof(Colour)*x));
if (pixel->a != 0)
{
*pixel = Colour(0, 0, 0, 255);
}
}
int dwords = right - left;
if (dwords > 0)
{
pixel = (Colour*)((char*)buf + (y * width * sizeof(Colour) + sizeof(Colour)*(left)));
memset(pixel, col.c, (dwords*sizeof(Colour)));
}
if (right > 0 && right < max_x)
{
pixel = (Colour*)((char*)buf + (y * width * sizeof(Colour) + sizeof(Colour)*(right)));
if (pixel->a != 0)
{
*pixel = Colour(0, 0, 0, 255);
}
}
}



OSX: Carbon Event Loop not firing - Application unresponsive

In the development of Eets I've been using Apple's Carbon API. As some of my peers have correctly pointed out Carbon is slowly being deprecated, at least publically (outside of Apple). I'm pretty sure I've read somewhere that the Carbon API is still being heavy used to support the features underneath (for example in the Cocoa API). So this will likely be the last time I get to use it on any serious. I've already noticed that Googling for Carbon problems doesn't return a boatload of results. So I figure it's a pretty naive way of telling that Carbon it's really where the action is these days.

I'm a little saddened by this. I think it's a well designed and useful API and I've found it quite enjoyable to use but it's clear that slowly C and C++ fall out of favour (yes, yes not without good reasons - I guess I'm just getting old and nostalgic).

In case of the possibility there are some others out there still plugging away with Carbon or at least having a bit of a play, this post is for you!

I had a particularly annoying problem the other night, and it stumped me for longer tham I'd like to admit. It was only some old crusty websites and a mailing list archive that gave me any clues as to what the problem might be. So for the sake of "paying it forward" I just thought I'd mention this problem I had and hope it might help somebody just like me. It was a very unintuitive problem. Most likely because I don't completely understand the way Carbon works with it's disk based resources.

Eets, the title I'm working on, is basically a C++ and Carbon application. I am using CMake to generate the Xcode files. When the products are build, the .app directory and files are cobbled together mostly by hand (or by a script I wrote). I'd used interface builder to setup the basic window and toolbar settings. Somewhere along the line I'd obviously changed something outside of interface builder in the interface nib files.

In my C++ code I've setup the basic Event loops, Events and Event Handlers. My problem began after adding some features and a compile. The main window would open but the whole application would just freeze. The menu wouldn't appear and the application window wouldn't respond to mouse clicks or drags. The window would just sit there and lose focus to any other window in it's way.

I noticed this specifically happened once the code had started up and entered the RunApplicationEventLoop.

I kept thinking I'd setup the Event loop incorrectly or there was a bug in my code. I spent ages trying to work out what I could have done wrong. When I paused the application in the debugger the callstack looked like the one below.


#0 0x900074c8 in mach_msg_trap ()
#1 0x90007018 in mach_msg ()
#2 0x90191708 in __CFRunLoopRun ()
#3 0x90195e94 in CFRunLoopRunSpecific ()
#4 0x927d5f88 in GetWindowList ()
#5 0x927dc6f0 in GetMainEventQueue ()
#6 0x927fe1c8 in GetApplicationTextEncoding ()
#7 0x927fb698 in RunApplicationEventLoop ()
#8 0x0000a264 in main (argc=2141449080, argv=0x38810040)


I eventually worked out what the problem was. It turns out that
RunApplicationEventLoop was freezing, and it was basically not handling events properly. This occurs when the CFBundleExecutable value in Info.plist file of the application bundle doesn't match the application name (set by "PRODUCT_NAME" in the build preferences of Xcode). Deep down within Carbon this apparently stops events from working.

Annoyingly Eets, at the time, wasn't even being built as a bundle so I had to change that. It was time consuming and fiddly to do so - as CMake doesn't really have great support for Xcode application bundles, frameworks etc. It's getting there ... slowly.

After I changed CMake to create an application bundle and setup the Info.plist and .app directory structure, Eets is again working. I didn't change any of the C++ code to fix it. I just setup the .app as apparently required. Well I did learn something, even thought it wasted some time.

I hope this is of use to some Carbon API users out there.

Unity3D: Useful Tricks with Delegates

It's probably fair to say that Unity developers are quite a broad community skills wise. There is mix of first time game developers, seasoned professionals, programmer orientated folks and those of a more artistic nature. For me that's part of the beauty of Unity it has purpose at so many different levels.

I wasn't that clear on a target audience for this post but I figure it's going to be of more use to the less experienced coders amongst us.

As somewhat of an aside, I'd be curious to see the breakdown of Unity developers between those who exclusively use UnityScript (js) and those who predominantly use C#. I'm using a mix, initially I was sticking more with C#, since it's more similar to the language I know best which is C++. Now I find the terseness and succinctness of the UnityScript quite compelling and I've been using it a lot for the last few components I've work on. There's a downside to UnityScript for sure, but this isn't the topic I set out upon.

One thing I kind of miss when using UnityScript in/as a behavior is the ability to create interfaces. When I say interfaces I mean in the object oriented sense. Interfaces are great when you want to interact with a whole bunch of different objects in the same way. To be more explicit lets look at it in the Unity context.

So lets say I've got a GameObject which has an array of other game objects. (see screenshots).

Normally these would be all identical objects, but what if we want to their functionality to vary somewhat from item to item? In object oriented languages this would be the realm of an interface, but in a Unity behavior (even thought it's an object oriented language) we don't directly have the capability of using an interface. So what can we do?

We can use delegates. Delegates applied sparingly can somewhat mimic this nice object orientated characteristic. It's not quite as elegant but it works just fine.

First of all, it's reasonable to ask if you've never come across the term. “What is a delegate?” It's called something slightly different depending on the computing language are talking about. In C and C++ the equivalent functionality you'd term a function pointer. In my mind the simplest description would be that a delegate is essentially a variable that contains a function or a method. You can “call” the variable just a like a function, and you can assign a function to the variable. If it doesn't make sense now, you may want to read a bit further to see it in action. This might make it clearer.

Say for example we have a bunch of GameObjects. Sticking with some sort of familiar tradition lets call them widgets. So we've got a bunch of widget GameObjects, we've attached our widget script and they're all working nicely. Now if we'd like their behavior to vary a little, how are we going to do that?

First of all lets define a widget script with a delegate that gets called in place of the normal functionality. Once we've done that we can attach another script to each widget to further refine it's behavior. The second script will attach to any selected widget GameObject and assign its own function to the delegate in the primary widget script. In this way you can modify the behavior of the original widget method however you wish. Let's look at some example code of this description, I'm of the opinion it will be much easier to understand.

In my example I have a Master GameObject that contains an array of Widgets. The code of the example script is as such. Note the public array of widgets. This is exposed the inspector screen just as we like it. We assigned our selected widgets in the inspector (see screenshot).


/* Master.js */

public var widgets : Widget[];

function Update () {
for (var i = 0; widgets.Length; i++) {
widgets[i].DoSomething();
}
}


Next we create our Widget GameObjects and their associated widget script.

The widget script is kind of like our object orientated interface through which our Master game object interacts with the widgets. As far as the Master GameObject is concerned, all the widgets are identical.


/* Widget.js */

private var doSomethingDelegate = null;

function SetDoSomethingDelegate(func) {
doSomethingDelegate = func;
}

function DoSomething() {
if (doSomethingDelegate) {
doSomethingDelegate();
} else {
/*
Typical do something code ...
*/
}
}

function Update () {
}


For deviation of the widget behavior, let's look at the DoSomethingElse script, which will attach to a widget and this modify it's behavior when DoSomething is called. Note that the DoSomethingElse is assigned in this scripts Awake function. This assures it's ready to go when the action begins.


/* DoSomethingElse.js */
private var widget : Widget = null;

function Awake() {
widget = GetComponent(Widget);
widget.SetDoSomethingDelegate(DoSomethingElse);
}

function DoSomethingElse() {
/*
The brand new wacky functionality that is different to the other widgets
*/
}

function Update () {
}

@script RequireComponent(Widget)


Finally note the “RequireComponent” directive to really make it clear that this script depends on the Widget script being in place.

So as I hope you can see we can now modify a widget's behavior in a myriad of ways using this technique.

What's in the works

As a recently formed independent games studio, we've been asked a number of times what our game plan is (pun intended). Starting the studio in Western Australia after working for some big name developers and publishers in Europe represents quite a change. Not only a simple change in geography but a huge change in proximity to the big market zeitgeist, talent pool and investment/funding opportunities.

Despite having some experience in the industry to fall back on we're under no illusions as to what we can realisticaly achieve in a given timeframe. Not to mention we're all a bit older now than when we first entered the industry. No midnight crunches for us while trying to support families and preserve relationships. Initially we're going to keep things simple.

For me that means the first and most import goal is publishing something. Set attainable goals and achieve them; get the dev cycles going and something on the table. Don't get me wrong, I want to create something special, but even Speilberg didn't create his finest films on his first foray out the door. So something special, but achievable.

We were thinking about how this studio might work months before we left our industry jobs and made the migration to Australia. Looking around at opportunities to achieve our goals we did find a path that we think is a good place to start.

It's always been my feeling that to create something worthwhile, it never hurts to understand what makes something worthwile. This thinking walks hand in hand with the ability to identify greatness in others or another's achievements. It was this thinking and a fortuitous meeting of minds with the developers from Data Realms that laid the path we would choose to take for an initial foray into Indie Game Development.

Data Realms have spent years crafting a beautiful indie game known as Cortex Command. The first time I played it was a hurried affair in a lunch break. My initial exploration didn't do it justice but my interest was perked. A few weeks later with more time on my hands (and with a freshly downloaded build) I was able to spend enough time playing Cortex Command to begin to truely appreciate it. I felt then and still feel now that Cortex Command is one of those creative products that has some sort of destiny. With an idea in mind and a fanboy's appreciation in my heart, that motivated me to bring Cortex Command to the Macintosh. Spiritually, the Macintosh version of Cortex Command is the first title for Kruger Heavy Industries. The fact that it was mostly completed by myself before the company was formed probably only matters to the record keepers on Moby Games.

Later in the piece we were very happy to have elected to be involved with Cortex Command. It did very well at the last Games Developers Conference 2009 in the Indie Games Festival, picking up two awards (Technical Excellence and the Audience Award) (some video coverage available here).


Cortex Command is still actively in development, but is largely code complete - at least as far as the Macintosh porting effort is concerned. It's bugfixing and build making for the most part until release. A day we look forward to greatly. Dan, Prom and the rest from Data Realms are doing a fantastic job.

So, what else is in the works for Kruger Heavy Industries? Fresh from our experience porting Cortex Command we picked up another great game we felt deserved some love on the Macintosh. Currently in active development is the Macintosh version of Eets: Hunger. It's Emotional. It was developed by our friends over at Klei Entertainment. One of their first titles, it's been lavished with much love and attention to detail by the Klei team. We won't tell you too much about Eets right at this moment as we're looking forward to that in a future post. For now we would like you to know we're really looking forward to having Eets playable on the Macintosh and putting that second building block into the foundation of our little studio here in Western Australia.

First Experiences with Unity 3D

I first heard about Unity 3D early last year when some rumblings were made about it in Indie Games Circles. I wasn't really doing much with regards to Indie Games at the time and the company I was working for at time had it's own technology. On top of that Unity 3D was only really available for the Macintosh platform at the time (Windows version was still in Development). With all that in mind it didn't seem like I was going to get a chance to try out Unity 3D any time soon.

Fast forward now to last month. I've just started a new contract for a local mob. We're using Unity 3D, predominately on the Windows platform. So I've finally got the chance to look at Unity 3D properly. My first impressions have been predominately positive.

Unity is probably best described as a Game Engine and Editor “all in one”. It's an IDE, a level editor and properties tweaker. The professional version also has some source control functionality. There is a lot of functionality included in the package an it has the potential to save an enormous amount of development time.

The User Interface

The User Interface is visually appealing, I suppose it would have to be to suit the fashion concious Macintosh crowd. The main interface is broken up in to several areas, the Game View, the Scene View, the Hierarchy View, an Assets View and the Inspector. The game view allows you to review the status of your Game, it's essentially what the game would like. It can be set to run, pause and stop basically allow you to run the game and see what's happening as you build it. If you want to see an animation running in your scene all you have to do is hit play.

The scene view is similar to the Game view but is more orientated towards the actual development process. The scene view will show the scene and level objects in a simple form as well as many of the other implicit objects required for the game logic. The Camera in the scene view is free moving. Models and Game objects can be orientated, placed and scaled all the in the scene view. The interface is quite a lot like 3DS Max in the basic controls.

The hierarchy view (a panel really) is clearly inspired by a Scene Graph. It is essentially a list of objects in the scene, it also displays (via it's heirarchical nature) how these scene objects relate to each other. With it you can quickly find any object in your scene. In the Hierarchy panel, you can select an object, then when you move your mouse pointer over the scene display, pressing “F” will focus the scene view on the select hierarchy object. This without a doubt saves a lot of time. The hierarchy view is also useful for attaching components (behavior modifiers, graphical sugar and script/logic) to your scene objects.

The inspector panel works closely with the hierarchy and asset views. All objects, behaviors and such in your scene have properties associated with them. These properties are exposed by the inspector and can be directly manipulated. Running the game in real time and tweaking values in the inspector allows you to rapidly tune settings for a visual effect or game play behavior.
Finally the last main view or panel is the Project or Asset panel. This is where you can see all the assets in the scene. It's also where you can import new assets into the scene and construct prefab objects (objects that can be used again and again). All assets that have been imported into the assets can be edited from their new locations. Changes are re-imported and applied almost instantly.

Programming

The actual programming side of is done via scripts written in Javascript or C# . Although there is the ability to use plugins in the professional version which are written in C, C++ and or C# - I assume on the Macintosh version we can also use Objective C). The Javascript is really UnityScript I suppose, while sharing many similarities with Javascript there are some notable differences as well, particularly when it comes to the way objects work.

Scripts are typically assigned to game objects where their interfaces are called as the game logic progresses. Scripts assigned to game objects are known as behaviors. The script editor built into Unity 3D is Scite which is a well known simple editor. For more professional programmers who are used to the fully feature code environments such as the likes of Microsoft Visual Studio they may be disappointed. The environment notably lacks any easily accessible debugging, so you'll probably be spending a lot of time doing the old print debugging thing of yesteryear. Thankfully as everything else about the environment makes achieving results easy, this probably isn't as painful as it sounds. At least for small projects.

Under the hood Unity basically creates dynamic libraries with the code that is compiled from the Game scene in development. This is most likely how the Unityscript/Javascript is so fast. Indeed the it becomes apparent that the Javascript i really just a thin veneer over the C# innards and as you start to realise the Unityscript's differences to Javascript it becomes clearer what is going on underneath. Of course it's not Microsoft .Net implementation but rather the C# implementation made available via the Mono project.

Source Control

In the professional version, Unity's own source control functionality is available. It's not brilliant. It's some hodgepodge or Unity 3D UI, with a backend of a Postgres database. Over low latency links it's horrible and generally it lacks features. Strangely it's also one of the most expensive accessories for Unity. I can sort of the see the logic in it, those requiring source control will most likely be the ones cashed up enough to be able to afford it. In effect subsidising the cost of Unity's development and cheap price to Indie Developers and students.

Conclusion

I'm overall feeling positive towards Unity 3D. I've still got a lot to learn but I can see enormous utility in the package for what amounts to (especially for Indies) a lot of bang for you buck. Depending on how my experiences go I may consider using the Engine/Tool myself on a title I've been mooting. I hope to post updates on my experiences as I go.