Cross platform RTS synchronization and floating point indeterminism

If you are about to create an RTS with thousands of units simultaneously on the map (in my game BOID I support 1400), you probably have only one option regarding how to design your networking engine and how to implement the synchronization between players machines.

In this legendary Gamasutra article “1500 Archers on a 28.8 Network”: the method for achieving this option is described in detail. If you are not familiar with this article, it would be a very good idea to read it. I'll just repeat the foundation that this approach is based on:

"Rather than passing the status of each unit in the game, the expectation was to run the exact same simulation on each machine. "

Your PC is a deterministic machine. If it's not influenced by external effects i.e. user input, network input, random number generator… it will run the same code exactly the same each time. This fact makes RTS games possible. When creating an RTS we just write the code the way it will not depend on any external effects. We don’t use multithreading, use random number generators with same seeds and even user input is processed on the same engine steps.

For an RTS this means that when you play it in multiplayer on different machines, the AI will make the same decisions on both machines - when a unit gets hit, the damage calculated on both machines will be just the same and when the path for a unit is calculated it will be just the same path on both computers. Once again - if you want to know in details how it gets done, please read 1500 Archers.

Hundreds of units in BOID

This approach seems tricky at first glance, but from my experience it makes things even simpler. The only thing that you actually "synchronise" is user input and everything else just works. And if you want to create an RTS with hundreds of units - you have no other options. This is the only way that allows you to make all of your units behave the same on different machines.

Unfortunately, everything is not so bright when you decide to make your game cross-platform.

When I designed BOID, I designed it first as an RTS for tablets, and later switched to PC. As such, the controls are very simple and all the aspects of the game should work great on touchscreen tablets, and probably on game consoles. I decided to make it possible to play multiplayer crossplatform. PC vs. Mac, iOS vs. Android, iOS vs PC - you choose.

It seemed to me like a great idea and a great addition for the competitive part of the game. iOS users will love to play against Android, we can finally decide who's better - PC or Mac - and it will be really interesting to see platform based ratings and know how players skills differ from platform to platform.

But when you decide to implement this simultaneous simulated game cross-platform approach, one tricky little problem crosses your way. Floating point indeterminism.

Floating point indeterminism

What does it mean? Different processors calculate floating point numbers in different ways.

If two users play multiplayer, some number on the first machine could be calculated as 0.0000001, but on the other machine it could be 0.000000999. This is not a big difference and doesn't matter much in most cases.

But what does it mean for a simultaneously simulated RTS game? Your unit could follow a different path or take less damage or even die only on one machine. And because off the butterfly effect you could soon have a totally different situation for different players. (Actually no - you'll have just a checksum error on this step and the game will exit).

Why does it happen and why all the processors don't calculate the same way?

I like how Shawn Hargreaves puts it:

"This is madness! Why don’t we make all hardware work the same?

Well, we could, if we didn’t care about performance. We could say “hey Mr. Hardware Guy, forget about your crazy fused multiply-add instructions and just give us a basic IEEE implementation”, and “hey Compiler Dude, please don’t bother trying to optimize our code”. That way our programs would run consistently slowly everywhere :-)"

Even if you take only x86 processors there could be difference between Intel and AMD or between different processors generations. For x86 architecture you could probably avoid this using some compiler directives (though I use C# and it's not an option for me).

But what if you are going to support also ARM and game consoles with their architectures? And you want to make it possible to play x86 vs ARM? There is no way to achieve this with floating point calculations.

Is there an other way? It's not only gamedev, a lot of different areas requires consistent numbers computations. For example finance. So of course there are some approaches and there are libraries that process floating point numbers in a deterministic manner.

But in most cases they are created for high precision, so they are generally much slower comparing to raw floats. But since it's a gamedev and you are going to make a lot of real time calculations, and performance is very critical for you, you need a solution that is really fast. Better if it has the same performance as built in number types.

Solution

After some research I decided to go with fixed point numbers. I've found an open source implementation and tuned it to fit my needs.

How they work:

You store your number in an integer type (64 bit for better precision).  You choose an amount of bits to shift. I choose 12. So you have 52 bits for the integer part of your number and 12 bits for the fractional part.

For example the value ”one” would be stored as 1 shifted 12 bits to the left

And all the calculations are made using integers so they are deterministic. 2x2 is always 4 right?

What’s good about this approach is that it's very easy to implement the basic arithmetic operations. That is to say, multiplication of two fixed point numbers A and B would be calculated as

C.data = (A.data * B.data) >> ShiftAmount;

Of course you would encapsulate this in operator overrides so in your regular code you just write

c = a * b;

For trigonometric functions like sin/cos, the implementation I've found uses lookup tables, so it's not precise, and square root is calculated in a loop, which is really slow.

Using fixed point math and simultaneous simulation approach should be enough to implement cross platform multiplayer RTS. In theory.

Putting it into practice

In practice everything gets much more complicated.

Instead of using float type you should use your newly created fixedNumber. This means that you cannot use any third-party library. You can’t use third party physics, path finding, anything - even some basic stuff like data structures (i.e. QuadTree).

And in most cases you can’t just globally replace float with your new fancy fixedNumber. Some code will work oddly because of low precision. Some code will just not work. Some parts will be very slow because of looped calculations.

But when it's done, that's it. Fixed point math and simultaneous simulation is enough to synchronise your RTS between different platforms and avoid floating point indeterminism.

There are also some hidden benefits in this approach. Since you need to rework/rewrite all the third party code that you were using, you can dramatically level up your programming skills.

In BOID, I use my own data structures: quad tree, query grid, my own physics engine, ray casting, my own path finding based on navigation mesh that I generate using ray casting.

Path finding graph in BOID map editor

Some parts of the code are written from scratch, while some are based on opensource libraries and reworked and optimized to fixed point math.

What I'm really happy with is that it actually works. It synchronises well and I’ve only caught a few checksum errors – and even then it was a mistake in my code, not the fault of the approach.

Now I have a deterministic cross platform physics engine, and a lot of other cross platform deterministic tools. And I can say I understand all the internals of the tools that I use now and that I used previously.

This gives me much better control. I see new ways for optimization, and almost any third-party library that I'm going to use in future, I'll use as a white box.

I hope you enjoyed this article and it was useful for some of you, if you'd like to see it in action, please do pick up a copy of my game BOID on Steam when it launches on January 8th.