"This was caused by a floating point rounding error. A unit switching jobs internally becomes a different unit (i.e. a monk with a relic becomes a monk without a relic), and when doing that, HP is scaled proportionally based on the old and new max HP using 32-bit floating point maths."
And there are YouTube videos about this https://www.youtube.com/watch?v=MytWNbpnAVY
> Due to floating point rounding errors, convert_hp(1, 55, 55) equals 0.999999940395355224609375, which is less than 1, which means the unit dies.
Ahh. The old "Multiplying and dividing is associative... for the set of reals, not for the subset that you can actually afford to compute with." So it should have been `(new_maxhp * old_hp) / old_maxhp`. ffmpeg has a whole AVRational class for the same type of problem when converting timestamps accurately between 2 timebases.
Reminds me of the TF2 ammo boxes that give 40 metal on Linux and 41 on Windows https://www.youtube.com/watch?v=QzZoo1yAQag&pp=ygUfdGYyIGhlY...
Apparently the compiler used on Linux chose a less-accurate multiply instruction for 0.2 * 200.
Two wrongs make a right - After being less accurate but rounding up where you don't need to, the Linux binary correctly arrives at 40, and the Windows binary arrives at 41.
For percents (and dollars) I always do everything in cents and divide by 100 at the very end. "20 * 200 / 100" can be done with pure ints, and f32 can represent i16 exactly.
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.
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).
How would you design an RTS unit stats system to avoid this AoE Monk HP bug using only integer types?
Fixed point would not have helped here. Integer would only have helped because dividing first would break immediately.
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).
>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?
if (oldHP == maxOldHP) { newHP = newMaxHP }
else { newHP = max(1,scale(oldHP,oldMaxHP,newMaxHP))
Uhh, last time I checked, that was literally my job, and specifically what I went to school for!
A better solution is to kill the unit when it drops below zero HP, not when it drops below 1.0; scaling will never move the current HP past zero in either direction. Having 0.9999994 HP instead of 1.0 HP would not cause any problems then; the unit is still one hit away from death in either case.
The best solution is probably to store the current HP as a percentage of the max, because then you never have to rescale it in the first place.
Doesn't this solution make the more common calculations more expensive, complicated, and error-prone to make one rare calculation easier? It seems like far more of the operations on the unit's current HP will be "gets damaged by X hp" or "gets healed by X hp", both of which would require the equivalent of the above conversion to establish a result.
Because a sword might do 5HP of damage, not 10% of anyone's damage (whether they've got 50 or 5000HP). Otherwise, hit points are meaningless: 10 attacks with a 10%-damage weapon kills a lowly serf or a mighty dragon.
And because damage reduction might reduce a fixed amount of damage from an attack. Etc.
Then you have the situation where units are displayed as having 0 HP but are still alive.
Top-end players who analyze the engine enough do.
Otherwise, they shrug and say "sometimes 1, sometimes 2 HP"
And even so, we're used to seeing 0/50HP and it meaning "dead" across many games. Seeing 0/50HP and it meaning "just a small amount of HP left" isn't ideal.
Not to mention that weird situations with 5.551115123125783e-17 HP remaining aren't great either (where a player may end up with effectively an "extra" hit point).
But just to humor you: the desire is to have a system where floating point neither surprisingly kills nor gives characters extra hit points. There's a lot of subtlety in this. Schemes where all damage are percents don't preserve the essential pieces of RPG combat systems. Moving the threshold from 1 to 0 HP violates the conventions of the art and doesn't eliminate the problems (you can still end up with hit points epsilon away from 0, instead of 1).
And in D&D, incapacitation happens when a character drops below 0 HP, and death happens once they drop below -10HP. There is no grand convention that all RPG games follow here; each game is making things up as they go. They picked badly when they designed Age of Empires, and that’s ok. It’s not the end of the world. Just know that we can do better if we are paying attention.
And I am serious when I ask “so what?”. Why is it so bad if the game displays 0/55HP? The players all know that fractional HP damage exists, and they can see that their unit is still alive, so what is the problem? They will be at least as amazed that their unit survived as they currently are when they see a unit at 1/55HP.
I am likewise serious about Smaug; there is no way that combat makes any sense if Smaug has a large number of hitpoints or that any weapon at all can damage him. Using hitpoints as an abstraction completely loses all of the flavor of Tolkien’s original descriptions. A better model is one using damage reduction and sensible internal organs; a strike that pierces the heart will kill even a dragon.
Depends on what you do with subnormals and underflow, etc.
> There is no grand convention that all RPG games follow here
Computer RPGs have shown 0/812 for dead for ... forever.
> The players all know that fractional HP damage exists
I think most players will be confused. And for what, to make it "safe" doing floating point operations in the wrong order? (I doubt it's still safe, overall).
> I am likewise serious about Smaug; there is no way that combat makes any sense if Smaug has a large number of hitpoints or that any weapon at all can damage him.
Common mechanisms: an armor class that makes it hard to hit; a fixed amount of damage reduction so that a needle does nothing; a lot of hitpoints.
> and sensible internal organs;
It gets excessively complicated and annoying. Battletech is already excessively complicated, and doesn't go quite as far as you're advocating for here.
Or using fixed-point (which are a relatively simple abstraction over integers): `old_hp * (new_maxhp * old_maxhp)`.
max(1,...Rational types are not super popular and don't get used that much, most (not all) people that end up using them do it very intentionally and consciously and know what they're dealing with -- if they were more ubiquitious, I suspect more trouble would be seen "in practice".
While it's probably true that any digital number format will have edge cases that in fact come up in practice, my personal choice of "Why the heck isn't this more popular, why doesn't every language support it, why isn't it in fact the default representation of a numeric literal" -- is floating point "decimal" types, like ruby (or I think Java?) BigDecimal, rather than rational. I think they mostly work matching programmer's mental models of numbers, and for many/most common uses on 2023 platforms the performance is just fine. (this would not have been true 30 years ago).
What would not have been true 30 years ago? I remember "real" fixed-point type built-in in Turbo Pascal and explicitly documented as suitable for money. Common Lisp has had first class fractions support since the start.
"Real" types were platform-dependent floating-point types, not suitable for monetary calculations whatsoever. and would map to either Single or Double depending on the underlying CPU architecture. Sort of like a C-style "int" that would map to an 8-bit, 16-bit, 24-bit, 32-bit, 36-bit, 60-bit, 64-bit etc integer, depending on the compiler and the compile target.
Turbo Pascal did have an 8-byte, fixed point, "Currency" type suitable for monetary calculations, however using it was very, very slow compared to pure floating point ops - just as the comment you replied to suggested. If that weren't enough, library support (both built-in and 3rd-party) for math and other utility functions was either limited or non-existent.
Turbo Pascal did NOT have an 8-byte fixed point "currency" type suitable for monetary calculations. It did have an int64 type called "comp" though which was handled as a float by the FPU and hence not slower than the types "single" (f32), "double" (f64) or "extended" (f80).
IIRC, "currency" came with Delphi V2.0 (or even later), but then still it wasn't slower than other floats when you did heavy calculations with it as it was also handled by the FPU. Only reads and writes from and to such variables were expensive as there was always a scaling (multiplication by 1e4 and 1e-4) involved — internally it was that int64 "comp" type. (But here I might be wrong, I never really used "currency", I disassembled lots of Delphi binaries with lots of different data types as I wanted to know how the compiler worked. Today however my Delphi knowledge is quite fuzzy).
Why?
Unless you go Haskell where anything can be an operator name, operators are just a minor convenience hack .
A lot of Java/JVM’s design decisions made sense in the mid-1990s, such as not supporting user-defined stack-allocated value-types and only supporting GC-managed objects - as main-memory was fast-enough compared to CPU registers - and many/most Java targets didn’t have any kind of CPU data cache - the idea of using the heap for basically everything wasn’t a bad design… back then. But now it is: high-perf code for the CLR means eliminating unnecessary GC allocation wherever possible - but in the JVM that isn’t possible.
You mean like COBOL?
But, in fact, I don't know of any language that doesn't. They are just not basic types.
———-
Also, in general, it’s not enough to just add loads of distinct numeric types to a language or library; in fact that’s probably the wrong thing to do as it burdens the programmer with having to make (often hair-splitting) decisions ahead-of-time - instead I’d like the language to have me set-up high-level constraints/invariants on a numeric parameter, local, or field and then the compiler chooses the best low-level implementation based on those constraints (and constraint-inference a-la Hindley–Milner would be nice too)
The main applications are: hashes and identifiers, e.g., visitor identifier in clickstream.
A decimal type is definitely necessary, and you can use IEEE decimal floating point for that, too! Other decimal types are very useful. Rationals are a different story: rational numbers are great for addition and subtraction, but if you're going to be doing a lot of multiplication and division, you are going to find yourself also doing a lot of slow gcd calculations to reduce/renormalize the fractions (incidentally, decimal types also need renormalization, but it's a lot cheaper). Most cases where rational types are used today are very careful about not having long chains of these operations.
As to NaNs: those are all considered pretty carefully, and 754-2019 actually reduced the amount of NaNs that propagate around quite a bit. For example, make sure you are using fmax(a, b) instead of std::max<double>(a, b).
This is a game originally from 1999. Although i doubt it would make a difference.
C# has the base-10 high accuracy decimal type: https://learn.microsoft.com/en-us/dotnet/csharp/language-ref...
This is a problem in one of my company's applications, as we have a background thread doing work entirely with `decimal` objects, but providing a readout for the GUI necessitates a lock on every write (even if never read), and another for the read by the GUI. There's barely any overhead (nanoseconds worth), but the logic to work around it is a pain, and, if you forget to actually use a lock, good luck with that bug.
.NET 8, however, will introduce[0][1] proper IEEE-754 decimal float types, including `Decimal32` and `Decimal64` which will allow atomic reads/writes.
If all of your operations occur with some reasonable minimum denominator, just use ints. If not, that arithmetic is going to become unbounded really fast.
I’m willing to bet that this has to do with how we historically have handled monetary values which is storing and computing it in the respective currency’s fractional unit. The advantage is that you can still do math operations directly on this value (as opposed to an object that contains it) and at most you’ll be off by, in the case of the US dollar, one cent. Because we cannot represent fractional units of the already smallest unit of currency, we have to choose a value anyway to charge or dispense. Unlike, say, if we stored it in dollars as a floating point and we can start compounding errors from the floating point type.
What interesting is that pre computers, we didn’t even treat currency values as an real decimal (for base 10 currencies) and the decimal point was simply a convenient way to store partial values. I note this because you don’t see old ledgers where they store more than 2 decimal places, therefore IMO, this was just an integer in disguise all along.
Old habits die hard?
I've spent 20 years mostly working in finance. You'd be surprised at the prevalence of floating points used to represent currency. I cringe every time I see it, but it's surprisingly common (and wrong).
More correctly, pricing of securities (from exchanges) is done with integers and a scaling factor. The factor is typically static and doesn't need to be transmitted on every tick. The factor tells you effectively how many fractional digits are present (e.g. the actual price is multiplied by 10^-factor). Factors of 4 or even 6 are somewhat common, but some securities have to go with less precision. I remember in particular Berkshire Hathaway causing issues with overflow using 32-bit ints in the last decade (because they never split their shares, the share price is quite large).
We all cringe but then there’s a “floating point or gtfo” ultimatum that most languages present to you. People would be happy to not use FP. But the reality is, you can have a monetary column in a 30 years old database engine, but not in a 5 years old language runtime. When you only have a hammer…
Because numerators and denominators can blow up easily, rational types effectively require storing them as bigints. That makes them bad from a performance viewpoint.
Assuming your application will work fine with fixed-size rationals (which, IMO, is highly unlikely), the natural way to store rationals in fixed-size storage wastes lots of room.
For example, in a (int32 nominator, int32 denominator) pair, there are about 2³² ways to encode ‘1’ that way, 2³¹ to encode ½, etc. I also think such a fixed-size rational type isn’t very natural to work with
Rationals also require regularly computing a gcd when you add (1/3 + 1/6 isn’t 9/18 but 1/2) or multiply (10/21 × 7/5 isn’t 70/105 but 2/3) them, slowing down things more (you can use heuristics to avoid some of those simplifications, but not doing one when that’s possible may mean your rationals keep huge numerators and denominators, slowing down operations)
A rat64 could be:
- 1 sign bit
- 3 format bits. Determines where the decimal is located, e.g. 30.30 vs 52.8.
- 60 bits of numerator and denominator. The split is determined by the format bit. 50.10 would be handy for any percent/ppt operations (e.g. Most USD operations)
Might need an error bit, but that's my 5 minute gist.
Could it? Is there a fast way to do GCD in hardware?
Googling gave me https://en.wikipedia.org/wiki/Binary_GCD_algorithm, which needs O(log₂(max(u, v))) operations to compute gcd(u,v), but I wouldn’t know whether that’s the best we can do in hardware, or whether that’s ‘as fast as floats’.
Also, I don’t see how your format describes a rational type. Rationals store numbers as p/q for integer p and q, not with a decimal point.
I would imagine it would not need to fully reduce after every operation, there's probably tricks where if you know the factors going in, there will be obvious ones after multiplication/division.
It's not my best idea :p
The trouble is this isn't enough, even for ordinary usage. The numerator and denominator grow in proportion to the total number of operations you have performed. For example, if you start with `1` and then multiply by `80/81` a thousand times, you get a number that's around 1e-6, but when expressed as a rational the numerator and denominator have hundreds of digits:
Actually if you had an int64 type which was scaled by flicks, that'd give you quite a lot of latitude for most day to day stuff.
A 1/3 off discount on a $10 item is $6.67 (or $6.66 if rounding in the customer's favor), not $10/3.
(Except datetime, did you mean timestamp? A timestamp is an instant in time, and it often makes sense to store it in high precision because you're saying exactly when something happened. A datetime is for communicating between humans who are using some particular calendar; it rarely makes sense to have more than minute precision.)
While hardware support for full number towers might be neat, I don't think anyone is suggesting that int and floats should not have language/standard library support - only that there should be a blessed option for precise arithmetic.
Usually the slow correct answer is preferable to the quick wrong answer (esp in business logic).
The Great Debate @ARITH23: John Gustafson and William Kahan
https://www.youtube.com/watch?v=LZAeZBVAzVw
Kahan points out disadvantages of interval maths.
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
"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.
Rationals might not be the solve all problems type, but here they seem very applicable.
loop { x ← a*x }
loop { x ← a*x + f(t) }
[0] 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).
For money systems, we also tend to round on every step to the nearest penny.
What you don’t have with rationals is the problem of 10.00 - 4.10 + 3.20 ending in a 9.
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.
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.
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:
[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.
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.
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_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.)
Why can’t they store HP internally as “millihealth” integers, do integer arithmetic (including division), and then divide that by 1000 purely for display?
This is exactly why heroes won't die in Dota2 when toggling off armlet while having 1 hp
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.
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!
bool is_alive(const Entity* unit) {
return unit->hp > ZERO_FLOAT;
}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.
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?
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
I misread the equation and thought it's `old_hp * (new_maxhp / 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).
Otherwise you get loss from the division and then multiply that loss (by >1).
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
Psstt... Dividing is not associative for the reals.
I told my GF that last night I had insomnia and found myself researching why Aztec monks die when picking up a relic, and that doing so resulted in plumbing the depths of an important computer science topic.
She said "Sounds like you were reading Hacker News". She knows me so well now :)