Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Just like it was demonstrated with games like dungeon siege and KSP, a large enough level will start to have glitches because of how floating point works. You can't add 1e-20 to 1e20 without losing accuracy.

If I choose to limit the size of my level, how do I calculate the minimum speed my object can move at until it begins to be choppy ?

share|improve this question

2 Answers 2

A 32-bit float has a 23 bit mantissa.

That means each number is represented as 1.xxx xxxx xxx xxx xxx xxx xxx x times some power of 2, where each x is a binary digit (either 0 or 1)

So in the range from 2^i and 2^(i+1), you can represent any number to within an accuracy of ±2^(i - 24)

As an example, for i = 0, the smallest number in this range is (2^0) * 1 = 1. The next smallest number is (2^0) * (1 + 2^-23). If you wanted to represent 1 + 2^-24, you'll have to round up or down, for an error of 2^-24 either way.

In this range:           You get accuracy within:
-----------------------------------------------
0.25 - 0.5               2^-26 = 1.49011611938477E-08
0.5 - 1                  2^-25 = 2.98023223876953E-08
1 - 2                    2^-24 = 5.96046447753906E-08
2 - 4                    2^-23 = 1.19209289550781E-07
4 - 8                    2^-22 = 2.38418579101562E-07
8 - 16                   2^-21 = 4.76837158203125E-07
16 - 32                  2^-20 = 9.5367431640625E-07
32 - 64                  2^-19 = 1.9073486328125E-06
64 - 128                 2^-18 = 0.000003814697265625
128 - 256                2^-17 = 0.00000762939453125
256 - 512                2^-16 = 0.0000152587890625
512 - 1024               2^-15 = 0.000030517578125
1024 - 2048              2^-14 = 0.00006103515625
2048 - 4096              2^-13 = 0.0001220703125
4096 - 8192              2^-12 = 0.000244140625
8192 - 16384             2^-11 = 0.00048828125
16384 - 32768            2^-10 = 0.0009765625
32768 - 65536            2^-9 = 0.001953125
65536 - 131072           2^-8 = 0.00390625
131072 - 262144          2^-7 = 0.0078125
262144 - 524288          2^-6 = 0.015625
524288 - 1048576         2^-5 = 0.03125
1048576 - 2097152        2^-4 = 0.0625
2097152 - 4194304        2^-3 = 0.125
4194304 - 8388608        2^-2 = 0.25
8388608 - 16777216       2^-1 = 0.5
16777216 - 33554432      2^0 = 1

So if your units are metres, you'll lose millimetre precision around 16 km from the origin.

Exactly how much inaccuracy your game can tolerate will depend on details of your gameplay, physics simulation, entity size/draw distances, rendering resolution, etc. so it's tricky to set an exact cutoff. It may be your rendering looks fine 50 km from the origin, but your bullets are teleporting through walls, or a sensitive gameplay script goes haywire. Or you may find the game plays fine, but everything has a barely-perceptible vibration from inaccuracies in the camera transform.

If you know the level of accuracy you need (say, a span of 0.01 units maps to about 1 px at your typical viewing/interaction distance, and any smaller offset is invisible), you can use the table above to find where you lose that accuracy, and step back a few orders of magnitude for safety.

But if you're thinking about huge distances at all, it may be better to sidestep all of this by recentering your world as the player moves around. You choose a conservatively small square or cube-shaped region around the origin. Whenever the player moves outside this region, translate them, and everything in the world, back by half the width of this region, keeping the player inside. Since everything moves together, your player won't see a change. Inaccuracies can still happen in distant parts of the world, but they're generally much less noticeable there than happening right under your feet, and you're guaranteed to always have high precision available near the player.

share|improve this answer
    
Recentering is definitely the way to go! –  Floris May 24 at 4:47
    
What about using fixed point coordinates? Maybe with 64 bit integers if necessary? –  API-Beast May 24 at 6:35
    
the question is, how big that re-centered region can be ? if for example in my game I want to shoot at a high distance with a strong zoom, do I absolutely need to use double or is float enough? isn't it better to recenter according to a quad tree or some tile algorithm ? –  jokoon May 24 at 7:30
    
It will depend on the numerical stability of the algorithms employed by your rendering and physics systems - so for a given codebase/engine, the only way to know for sure is try a test scene. We can use the table to estimate maximum accuracy (eg. A camera 16 km away from an object will tend to see at least millimetre-sized errors, so your zoom should be wide enough to keep those smaller than a pixel - if the zoom needs to be tighter for your game then doubles or some clever math may be required), but a chain of lossy operations can run into problems well before this hypothetical limit. –  DMGregory May 24 at 11:45

You can avoid it altogether by multiplication.
Instead of working with floats, just multiply them by 10^(x), store them, and when needed multiply again by 10^(-x).
From that it depends on what type of int you want to use.

share|improve this answer
    
This doesn't avoid the problem. A fixed-point format still has finite precision and range - the greater the range, the lower the precision (based on where you put that fixed decimal point) - so the decision of "how big can I make a level without visible rounding errors" still applies. –  DMGregory May 24 at 3:44
2  
Moreover, base-10 is not very practical. Fixed-point numbers work a lot better when you split the integer in terms of bits (consider unsigned 26.6 -- the fractional component is the lower 6-bits (1.0/64.0 * x&63) and the integral part is simply x>>6). That is much simpler to implement than raising something to a power of ten. –  Andon M. Coleman May 24 at 4:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.