One thing to be careful about when programming games is relying on the rules of algebra. Simple laws like the Associative Law and Distributive Law don't always work when using floating point numbers. I'll give some Python code to demonstrate, but these problems are with floats, not with Python.

  • Distributive Law. We've been taught that a * (b + c) == (a * b) + (a * c).
    a, b, c = 0.111, 0.201, 0.305
    s1 = a * (b + c)
    s2 = (a * b) + (a * c)
    print '%.08f - %.08f = %.08f' % (s1, s2, s1 - s2)
    print '  equal? %s' % (s1 == s2)
    

    These are the results:

    0.05616600 - 0.05616600 = -0.00000000
      equal? False
    

    The difference looks like 0, but it's not. The two sums are not equal. To see the problem, change the format specifier %.08f to %g.

  • Associative Law. We've been taught that a + (b + c) == (a + b) + c. When some of those are negative and some are positive (and occasionally even when they're all positive), the results won't be the same.
  • Additive Inverse. We've been taught that a + b - b == a.
    a = 1e-30
    b = 1e+30
    print a, a + b - b, (a + b - b) == a
    

    The result is that (a + b - b) != a. You can look at this example as a special case of the Associative Law.

To some of you these problems will seem obvious and not a big deal for most applications. Why do I bring it up in this blog? Loss of precision can open up exploits in multiplayer games. Let's consider a game in which you can trade with someone else, and the total amount of money is represented as a float. If player A has a large amount of money a, he may be able to send a very small amount x to B (who has b) without it affecting his own amount. We can have a + b < (a - x) + (b + x), which means this exploit creates new money out of nowhere.

If you're using floating point numbers, be sure to use double precision. Alternatively, use integers or fixed point arithmetic to avoid some of these issues. If you do a lot of math in your game, be sure to learn about numerical programming. There are a lot more issues than the simple ones I describe here.

Labels:

4 comments:

Robert 'Groby' Blum wrote at December 29, 2006 8:19 AM

I'm sure you're aware that using doubles instead of floats does not solve the problem at all. It does merely postpone it a bit in the additive case. Multiplication still suffers the same problems as soon as non-integers come into play.

Given that doubles also cost quite a bit of memory, I'd consider fixed-point over double whenever numerical inaccuracies matter. They have the added bonus that it's easy to predict a maximum error, while floats don't really allow that.

Or, to put it more succinctly - math sucks ;)

Amit wrote at December 29, 2006 8:55 AM

Yes, I tend to avoid doubles too, but they do postpone the problem in many situations, sometimes enough that it doesn't matter anymore. I still like fixed point better. :-)

Whether the memory cost of doubles will affect you depends on how many you have. For 3d models I tend to use floats (with object-local coordinates instead of world coordinates), because there's a lot of vertex data, but for a lot of things, like the amount of money the player has, doubles aren't a problem. Maybe I should have said, if it's a scalar, use a double, and if it's an array, think about which one is better.

Amit wrote at June 26, 2007 3:50 PM

Also check out this article.

Anonymous wrote at January 10, 2009 10:19 PM

doubles won't help.

The problem is that you're trying to use the == operator with floating point types.

STOP THAT STUPID SHIT.

instead of (f1 == f2), do

(abs(f1 - f2) < epsilon)

Duh.