11 ms·

> The formula was probably `return new_maxhp * (old_hp / old_maxhp);` ... > Due to floating point rounding errors, convert_hp(1, 55, 55) equals 0.9999999403953

• zelphirkalt 4y ago
  Seems all that could have been avoided by using rationals in general and the condition for living being >0 instead of dying <1. Not sure in what case it makes sense to have dying at smaller than 1. To the user all the numbers are integers, so why not use rationals instead of floats? The more I write code, the more I notice how rarely one truly should want floats in most kinds of programs and how they almost always carry a whole bag of problems with them.
  • DaiPlusPlus 4y ago
    > Seems all that could have been avoided by using rationals in general It's 2023: I'm still surprised that so many new languages/platforms still only provide only basic integer and IEEE-754 types for numerics: Rust, C#, Java, Swift and others still lack built-in, runtime-provided, nor even standard-library-provided rational types, which I assume really should be the preferred type for most business/domain/application values, exactly for things like RTS game unit health, for example. (and Java's lack of operator overloading makes this even more painful). ---- On a related note, can we agree that an application-programming language today should also include signed-and-unsigned "money-safe" decimal types, and IEEE-754 types should be smarter about when NaN can happen - and it should support interval types (and evaluating interval-type-based contract invariants): this would eliminate whole classes of bugs in the first place (too many programmers think single/double is appropriate for storing currency values, ugh).
    • PhilipRoman 4y ago
      Aren't rationals subject to exponential blowup in storage/precision? IMO the best approach for business logic values is picking the smallest meaningful unit and representing it with integers. Precision and storage requirements become very easy to reason about.
      • DaiPlusPlus 4y ago
        > IMO the best approach for business logic values is picking the smallest meaningful unit and representing it with integers. How would you design an RTS unit stats system to avoid this AoE Monk HP bug using only integer types?
        • bruce343434 4y ago
          How much health precision do you need? Make hp an int. Or like a /64 fixed point.
          • account42 4y ago
            Congratulations, you just introduced a new damage threshold / resistance threshold / etc where things effectively do no damage. Fixed point would not have helped here. Integer would only have helped because dividing first would break immediately.
        • falcor84 4y ago
          Well, in this case, if a unit is converted to a different type and back, it would just keep its (absolute) value of HP (in this case 1), no need to scale anything.
          • db48x 4y ago
            You haven’t thought it through yet. In this case, HP _is_ an integer, and so is the MaxHP for the unit type. And yet the bug still occurs! Storing the HP as an integer does not prevent the problem from ever occurring, because fundamentally the user still expects HP to be proportional. That is, suppose a unit is sitting there at full health, and you research a tech that increases that unit’s max hp? Should the unit now be at less than full health, as if it had been in combat? Users probably don’t like that. Suppose it is at full health, and then it gets downgraded to a type with less maximum health. Does it stay at it’s current HP? Users probably won’t like being attacked with supercharged units that have extra HP; they’ll think that the other player was cheating somehow. What if it is damaged and at half health, then gets upgraded. Should it be fully healed? Gain HP equal to the difference between the new and old maximum HP? Or should it gain half of that, so that it stays at half health? Or perhaps HP is too limiting, and the game should do what Dwarf Fortress does. DF knows the approximate surface area of every body part (based on each creature’s body plan, plus individual stats such as strength, fatness, size, etc), and the size of every weapon. Every attack therefore deals damage to a certain area, measured in square inches, and individual body parts will be destroyed once a sufficient percentage of that surface area is damaged by wounds. Or maybe you are designing this game in the 90’s, and you have to worry about squeezing unit updates for 200 units per player into the bandwidth provided by the average modem of the day (probably 28.8kbaud), so you stick to one integer because it’s the simplest think that can possibly work, and the number of bytes per update can be calculated in advance. And then some other schmuck gets stuck with the job of handling unit type changes (but be warned that the schmuck might be yourself in six months).
  • gizmo 4y ago
    You mean fixed point numbers presumably, because at the time using integers that use a variable amount of memory was totally out of the question. Today it’s still terrible for performance because you can’t use caches and simd effectively when numbers can’t be packed directly in arrays.
    • zelphirkalt 4y ago
      Does AoE2 do that? Packing numbers directly into arrays? Or does it rather deal with objects, which are variable size anyway? I am not sure how much high performance work has been done in AoE2. Maybe not that much.
  • CodesInChaos 4y ago
    The big problem with rationals is that it's easy to end up with both nominator and denominator growing without bounds, which IMO is an even bigger pitfall than those of floating-point or fixed-point.
  • ilyt 4y ago
    > Not sure in what case it makes sense to have dying at smaller than 1. To the user all the numbers are integers, so why not use rationals instead of floats? If killing unit takes X attacks, user buys 10% attack damage upgrade, and it still takes X attacks they will be annoyed. If rounding down takes that to x-1 attacks it might be preferable. That being said you're absolutely right. just use HP*100 in calculations and display HP/100 to the user, and when you need to round into specific direction do it explicitly
  • perihelions 4y ago
    Rationals fail in their own spectacular ways. Take a simple approximate exponential decay: x ← (99/100) * x. In exact rational arithmetic, your program will happily calculate integers (99^k) and (100^k) for unboundedly large values of k (there's no reduction – they're all coprime), grinding the program to a halt until it runs out of memory. "Oh, the solution is obvious: you should simply round that to an approximate fraction..." — yes, and that's floating-point arithmetic. Point is, you can't use either with thinking, about numerical representations and their possible failure modes.
    • zelphirkalt 4y ago
      The difference is, that with rationals you do not lose any precision on the way. I doubt, that 99^k is part of AoE2 code. For the simple calculations in AoE2 regarding unit health, rationals will do a fine job. With rationals the rounding does not happen during the precise calculation. It happens explicitly, only once, at the end of the calculation, at the programmer's wish and conscious decision, thereby avoiding the kind of issue we see here. Rationals might not be the solve all problems type, but here they seem very applicable.
      • perihelions 4y ago
        It's a very common pattern, in its more general forms. Sure, you can abstract away the naive re-implementation of exp() loop { x ← a*x } as one function call x(t) = exp(-k*t), so that one looks pointless. But moving-average [0] type expressions loop { x ← a*x + f(t) } are more interesting. You can't generally refactor those into exp() calls, like x(t) = sum[ f(t_i) * exp(-k*(t - t_i)) ], since that introduces a memory leak – you need to hold an explicit list of all the past values of f(t), in order to compute it this way. That's why the pattern [0] is uniquely useful: it's a trick to incrementally accumulate a moving average using just one variable of state. [0] https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average https://en.wikipedia.org/wiki/Moving_average#Exponential_mov... Here's one uncontrived way this pattern might show up: "the NPC has a numeric disposition towards the player, and the player's actions have positive and negative effects on it. These effects have finite duration, and disposition decays back to the neutral value". Another way: you have a large list (like a time series) you want to reduce to a small one by interpolation. Another way: you have some PID-like controller in your program, and to make it behave, you need a cheap filter to clean a jittery input signal. (I'm building these for my Factorio factories right now – it's the only reason this example occurred to me. "x ← (99/100) * x" is a factory control component I had to implement out of int32_t's).
  • tialaramex 4y ago
    The trouble you have is that you really wanted reals and the rationals are not a much better substitute than the floats (which are mostly just one particularly specialised flavour of rational) It doesn't feel immediately like there ought to be a problem, but witness, mathematically almost all of the reals are Normal and unfortunately Normal doesn't mean "normal" it's a technical mathematical word, that for our purposes means roughly "completely batshit". Normal numbers are non-computable, so we definitely don't want to try to use them in software, which is a problem because again, almost all of the reals are Normal.
    • l__l 4y ago
      Huh? This isn't making a lot of sense to me. Why do you say the rationals aren't much better then floats? In situations like this surely we absolutely want to be working in the rationals, and they're a very easy way to do these calculations correctly without having to worry about tolerance bounds for arbitrary-precision float calculations
    • hgsgm 4y ago
      Algebraics plus pi avoid almost all the concern you mention, but still have the same problem for software. All those nasty reals are unreachable by your program. The actual problems with irrationals is that it is extremely hard to measure their size without converting to rational approximation, so you are back to the original problem.
  • still_grokking 4y ago
    > The more I write code, the more I notice how rarely one truly should want floats in most kinds of programs and how they almost always carry a whole bag of problems with them. This! Imho you more or less never want floats under "normal" conditions. Also in most application domains it makes exactly no difference that floats have HW support, as the bottlenecks are there usually elsewhere. And in case you really need real fast floating point math (say for simulations) you would do it anyway on the GPU nowadays. The only langue I know of that is sane in this regard is Pyret: https://www.pyret.org/ https://www.pyret.org/ [CTRL-F: Pyret has numbers] I'm still baffled no other new language thought about something so basic like number ever again. Everybody is just using what the HW provides natively since the year of yore. As a result there is no motivation for HW vendors to update the status quo form the state of the art of the 60's of the last century. Imho having support for rationals and (fixpoint) decimal numbers in std. hardware is long overdue! But it would only happen if there would be serous demand form the runtime / language vendors. Classical chicken egg problem.
    • marcosdumay 4y ago
      Floats are a computer representation of scientific notation, used for scientific computation. Coincidentally, hardware support is extremely important for scientific computation. (A bit less now than in the 90's but still a showstopper.) Hardware support is also extremely important for games, but floats are not a good representation for most of it. IMO, game data should be composed exclusively of integral numbers, but it is natural to want a little bit more of precision some times.
      • still_grokking 4y ago
        > Floats are a computer representation of scientific notation No, they aren't. They are IEEE 754 binary floating point data. Something extremely weird, without precedent outside of computers science. > Coincidentally, hardware support is extremely important for scientific computation. Maybe it was once, but today it isn't. If you need to do any serious number crunching you use nowadays dedicated hardware for that (which isn't part of the main CPU usually). (You could use CPU integrated GPUs or FPGAs for that, sure, but the point is that the FP unit on the CPU is usually way to slow for anything more serious.) > Hardware support is also extremely important for games That's more or less the only valid usage in mainstream left by now. But even there: > but floats are not a good representation for most of it. Exactly! As said, you could and should use ints for most things. For the rest you want actually rationals. Only in some very special circumstances floats are a good enough approximation. But the cases where this is true are mostly related to rendering, as it doesn't matter if some pixels shown for the fraction of a second have a marginally wrong color or are marginally off. But rendering is done on the GPU anyway. So again no reason to use FP features on the CPU. Even games using vector and quaternion math extensively this is just lib code in the engine. So there is no real reason this couldn't be moved to the GPU also, given an adequate architecture of the game engine. Such an approach brings even amazing possibilities for games; just have a look at for example https://store.steampowered.com/app/1468720/Ultimate_Epic_Battle_Simulator_2/ https://store.steampowered.com/app/1468720/Ultimate_Epic_Bat... Want to animate 10 million of individual NPCs? No problem, if you do it on the GPU! So imho the case for FP on the CPU is very shallow. But the need for rationals and decimals is a real thing. That's what the average cooperate developer needs day to day. It's a shame HW is stuck in the past since decades and there is still no promise of progress on the horizon. (Maybe FPGA accelerators build into CPUs will change that at some point. But we still don't have that, even it's overdue.)
  • avgcorrection 4y ago
    > Seems all that could have been avoided by using rationals in general Why can’t they store HP internally as “millihealth” integers, do integer arithmetic (including division), and then divide that by 1000 purely for display?
    • firstlink 4y ago
      This would require competent senior programmers who are way too expensive, and anyways once hired are used for bullshit tasks like project management.
  • fendy3002 4y ago
    In terms of hp without decimal in gaming and related with max hp changing, the best solution should be to rounding down (or nearest zero rounding) the result, and keep minimum hp to 1 when max hp changes. In case for minimum hp unit (1 in this case) to have changed into lower max hp then they'll die too, hence why minimum 1 hp as the result is logical. This is exactly why heroes won't die in Dota2 when toggling off armlet while having 1 hp
  • wruza 4y ago
    Tbh, the only practical non-integers we all need (apart from science-ish pretence and graphics) are .00, .000, .0000 and .000000 decimals (money, qty, percent.00, milliqty). Literally all business and in-game accounting needs get covered by these. Even edge/rounding issues are irrelevant, because everyone is ready to just agree to either way of doing it, and that agreement is much more important than the method itself. This floating bullshit is basically of none, zero, nil practical use outside of academics. Modern CPUs can effectively emulate whole subroutines in microcode, but somehow we got stuck with that useless binary floating point standard for numbers. And on top of that, languages provide them as a default numeric system for all new software.
  • camgunz 4y ago
    I dug into this problem a while ago and came to the conclusion that these are all rounding problems, which you still can't escape with arbitrary precision systems, because memory is finite. You're always making a tradeoff between precision and space, and you have to rely on programmers to make that tradeoff themselves. Enter the typical floating point types that do some of that work already: float/double. These let you not think (as much) about the memory your math might take up, but they still need you to think about rounding, which almost no one does. This is a long winded way of saying that if you set up your arbitrary precision arithmetic library to use 4 bytes and the same rounding mode (the default is round to nearest) as was used here, you'd reproduce the bug. You'd also reproduce the 64-bit bug moving up sizes, and the 128/256/etc bug. You gotta round. The good news, though, is that actually solves it! You can even use floats for money!
  • gabereiser 4y ago
    bool is_alive(const Entity* unit) { return unit->hp > ZERO_FLOAT; } Super easy… Likewise I’m with you, the more I code, the more I see these kinds of things as bad design choices. If you’re going to deal with a type, keep it that type. If you’re going to convert, you need to take care of edge cases like OP. And don’t just add 0.0001f; that’s an exploit waiting to happen by someone with a macro to pickup/drop relics.
• thrdbndndn 4y ago
  Could you explain to a noob why does this happen, exactly? Is it because 55/55 != 1, or 1*1 != 1? I understand float can't store certain integer/finite decimal precisely, but why would a/a not be 1 if both numerator and denominator are the same (imprecise) number?
  • zem 4y ago
    it's because the calculation (1/ 55) is less than the real number 1/55, so when you multiply it by 55 you get a result less than 1. for an easier to follow example, say you can only work with two decimal places, hp was 1, old max hp was 3 and new max hp was also 3. if you do (3 * 1) / 3 you get 3 / 3 = 1 as intended. if instead you do 3 * (1 / 3) you get 3 * 0.33 = 0.99 which is less than 1
    • thrdbndndn 4y ago
      Thanks! I misread the equation and thought it's `old_hp * (new_maxhp / old_maxhp)`.
    • zelphirkalt 4y ago
      This effect becomes more pronounced, when substracting (but probably also adding) small amounts from big amounts, because more bits are needed to store the big number's more significant digits and floats then lose bits for the less significant digits. That is why, if one needs precision, needs to sort numbers first and then start calculating with the smallest numbers first, working ones way up to the bigger numbers.
      • pixelfarmer 4y ago
        Knuth has an entire chapter dedicated to floats, error ranges and such, which includes pretty much that (a+b)+c != a+(b+c) for floats, which in turn breaks tons of things on the math side already. That is such a large issue that it has some serious consequences in the real world, e.g. constructions failing, or I remember the Patriot missile system having problems from that side.
  • 4y ago
• layer8 4y ago
  > So it should have been `(new_maxhp * old_hp) / old_maxhp`. I don't see how that couldn't run into similar problems. I would use `clamp(old_hp * (new_maxhp / old_maxhp), 1, new_maxhp)` (assuming that old_hp >= 1).
  • iforgotpassword 4y ago
    It could, but only at very large values. It's at least the much more robust solution.
  • tpolzer 4y ago
    If you assume that all three numbers are small integers, doing the division last minimizes precision loss (and doesn't have any loss if the accurate result is representable as a float). Otherwise you get loss from the division and then multiply that loss (by >1).
• pclmulqdq 4y ago
  If you have integers that are stored in floating point types and don't need more than [mantissa] bits of precision, you can operate on them like ints and always* get the right result. Nobody would expect that the formula `return new_maxhp * (old_hp / old_maxhp);` would work with ints, but they see floats as magic that allow them to drop their guard about precision and rounding of operations. Unfortunately not. Rationals have a big problem where under multiplication and division they need to be re-normalized periodically, and that re-normalization is slow (running gcd). Under addition and subtraction, rationals are great. *the one big difference is that division rounding is different
• BeetleB 4y ago
  > The old "Multiplying and dividing is associative... for the set of reals Psstt... Dividing is not associative for the reals.
  • kaslai 4y ago
    I think the original intent was referring to the fact that given the same operand, the order of multiplication and division shouldn't matter, e.g. A * X / X should give the same result as A / X * X, but in reality they can give different results when done by a computer due to precision limits, overflow, etc.
    • BeetleB 4y ago
      Ah that makes sense.
• filmor 4y ago
  None of these would be a problem if people would round instead of truncate by default.