Hacker News Reader

Comment by SomaticPirate | Hacker News Reader

This came during my OMSCS Game AI course as an example of the dangers of using floats to represent game object location. If you get further from the origin point (or another game element you are referencing from) you are losing precision as the float needs to use more of the significand to store the larger value.

View on HN

I love how that became part of the "mythology" of Minecraft as the "Far Lands", where travelling far from the world origin made terrain generation and physics break down, subtly at first, and less so as you kept going.

It's like the paranormal trope of an expedition encountering things being disconcertingly "off" at first, and then eventually the laws of nature start breaking down as well. All because of float precision.

That makes me think of games where the story places the protagonist in a simulation, which is incredibly convenient for the real-world developers and authors. All the quirks and limitations of the real game (invisible barriers, fail on killing a story-critical NPC, etc.) can be blamed on issues in the fictional one.

For example, the Assassin's Creed series.

Was curious what this looked like so did a google.

From the wiki, far lands ("spongy walls of terrain") aren't caused by precision loss but integer overflow in the terrain generation.

https://minecraft.wiki/w/Far_Lands

If you have a large set of lets say floats in the range between 0 and 1 and you add them up, there is the straightforward way to do it and there is a way to pair them all up, add the pairs, and repeat that process until you have the final result. You will see that this more elaborate scheme actually gets a way more accurate result vs. simply adding them up. This is huge, because there is a lot of processing done with floats where this inherent issue is entirely disregarded (and has an impact on the final result).

Donald Knuth has all of that covered in one of his "The Art of Computer Programming" books, with estimations about the error introduced, some basic facts like a + (b + c) != (a + b) + c with floats and similar things.

And believe it or not, there have been real world issues coming out of that corner. I remember Patriot missile systems requiring a restart because they did time accounting with floats and one part of the software didn't handle the corrections for it properly, resulting in the missiles going more and more off-target the longer the system was running. So they had to restart them every 24 hours or so to keep that within certain limits until the issue got fixed (and the systems updated). There have been massive constructions breaking apart due to float issues (like material thicknesses calculated too thin), etc.

There are some really simple examples of that. Just try adding 1 to a half precision float in a loop. The accumulator will stop increasing at a mere 2048, since 2049 is not representable it rounds 2048 + 1 back down to 2048.

So as the sum grows with the square, the error function grows in the same magnitude. A very interesting excersise. I'll get an AI to choke and puke on that.

Define boundary conditions -- how much precision do you need? Then you can compute the min/max distances. If the "world" needs to be larger, then prepare to divide it into sectors, and have separate global/local coordinates (e.g. No Man's Sky works this way).

Really though, games are theater tech, not science. Double-Precision will be more than enough for anything but the most exotic use-case.

The most important thing is just to remember not to add very-big and very-small numbers together.

The problem with double-precision in video games is that the GPU hardware does not support it. So you are plagued with tedious conversions and tricks like "global vs. local coordinates" etc.

100! OTOH - Constant factor scaling between game and render world space fixes a lot (gfx often need less precision than physics). - most view coords are in view or clip space, which are less impacted, so large world coords tend not to code-sprawl even when introduced.

> Define boundary conditions -- how much precision do you need?

imagine if integer arithmetic gave wrong answers in certain conditions lol why did we choose the current compromise?

In my experience, most code that operates on integers does not anticipate overflow or wraparound. So it is almost always guaranteed to produce wrong results when these conditions occur, and is only saved by the fact that usually they doesn't occur in practice.

It is odd to me that every major CPU instruction set has ALU codes to indicate when these conditions have occurred, and yet many programming languages ignore them entirely or make it hard to access them. Rust at least has the quartet of saturating, wrapping, checked, and unchecked arithmetic operations.

The trick is to get your ALUs to do some of the math for you. Oh I miss the days of the 68020 fast barrel shifter and the 68030 byte smears. Tricky stuff lost to the silicon/sands of time.

Compromises. We had BCD for finance, binary for games, and floating point for math. I wrote a sample 'make change' using floating, BCD, and integer( normalizing by multiplying by 100). The integer ripped thru it, but surprisingly BCD kept up with FP, and with compiler optimizations, in certain edge cases and unit tests was significantly faster.

You get surprising things with common place problems.

They're not "wrong" -- the error bars are well-defined.

Signed Integer Overflow OTOH is Undefined Behavior, so it's worse.

Kerbal Space Program required a lot of clever engineering to cram an entire solar system into the constrains of 32 bit floats. There are articles and videos out there, highly recommended!

Didn't they just do the normal "The world is centered on you" trick? And then switched to 64 bit coordinates anyway?

That's one of the things, yeah. IIRC they tried 64-bit but gave up on it, one reason being the rendering code was hardwired to 32-bit, so there was no real benefit in the end.

There are other solutions they had to find. The game has two "orbital mechanics engines". One runs a physics simulation and the other is just ellipse math, making the rocket "move on rails". That's why you can't time warp under a certain altitude (that's the real physics simulation).

There are also things in rendering, how they faked the large-scale graphics of Kerbin, involving problems with the depth buffer I believe.

Reply on news.ycombinator.com