WarCraft III Epsilon Zero

[Berb]

Well I've been working on a geometry detection system (mainly lines with strictly linear motion for now) and it's been giving me a lot of problems. The concept behind it is relatively simple; I update the objects on a stack but whenever the velocity of the object is changed I calculate a collision-course with any of many defined lines.

Now, during development I consistently encountered problems where objects would seemingly "randomly" pass right through lines without any collision. I found that the problem of this was because it was really poor at floating-point math. Occasionally it would predict the intersection point of a horizontal line (y = 100) to be something stupid, like 100.001 which would screw up my calculation.

So what I did was implement a value labeled as epsilonZero. This value is a very low value that is supposed to prevent poor floating point mathematics from screwing with my geometry detection.

My first value for this was 0.000061 which seemed to be the point at which comparisons would fail. For example, 2 + 0.00006 would be equal to 2 but 2 + 0.000061 would not.

Implementing this value did not work practically, and objects still passed through lines.

The next value I implemented was 0.0001 which worked a little better. I realized that the preciseness of 0.000061 was too precise for the engine in Warcraft. This seemed to fix certain untypical cases but there were still occasions where my system would tell me that 600.001 is not on the line with a dimension of 600 (even though no values of 600.001 were actually used).

I then proceeded to use 0.001 as my epsilon-zero value; and the problem seemed to be similar to the one described right above. Instead of 600.001 not being in the bounds, however, the value was something arbitrary like 600.003.

So I bumped up the value of epsilon-zero to 600.002. This seemed to solve the immediate problems and objects seemed to stop passing through lines (note that this is used to add to the position of the object as well as deduct from the component of the line - basically meaning the net difference would be 0.004).

The reason I posted this is because for many things floating-point math can be very useful in Warcraft. The poor math procedures that obviously take place in the background really make it difficult to use this effectively. I couldn't imagine spending hours on debugging only to find that it was a stupid floating point error that was causing problems (thought it is sometimes easier to see).

Does anybody know a foolproof value for epsilon-zero that will avoid floating point math errors?

It seems like the more I increase the value of my epsilon-zero constant it simply takes longer for the game to crash. It seems as though there is an extremely slowly incrementing margin of error. Testing with 350 moving objects my FPS stays up at 64 but it seemed to take 50~ seconds before the game crashed (from an object moving through a line). This is with an epsilon-zero value of 0.003.

With an epsilon-zero value of 0.005 objects seem to occasionally get "stuck" in the line, but the duration of the game before crash is indefinitely increased. Right now I am at 160~ seconds but I've got 3 objects that seem to be "stuck".

With an epsilon-zero value of 0.0045 I have ran to 60~ seconds without a crash, and only 1 object being stuck in the wall. Also note that I bumped up the amount of objects from 350 to 450.

 

[Dr Super Good]

Welcome to the curse of floats. Especially since they are single precision.

The problem is that floats are only accurate to a certain number of significant figures. As such, a value like 60000000 in a float will have no meaningful values after the decimal point where as a value like 0.016 can have values even smaller that count.

What you need is a function to compute the "ulp" of the floating number you are using and base your precision on a multiple of that.

An ulp of a float value is the positive distance between this floating-point value and the float value next larger in magnitude.

Ulps give a measurement of how accurate a number is (the error it can have can be calculated using them).

I do not know how to calculate an Ulp sadly, try wikipedia or the IEEE specification for simple precision floats (which I assume WC3 follows some variation there of).

 

[Berb]

Well a 32-bit float (known as single-precision) has an epsilon value of 2^(-24). The numeric value of this calculation in Warcraft III is 0 because it is too small. Taking the idea that it would be in powers of 2 I tried to improvise. Bumping the value down to 2^(-7) seems to work the best (one or two objects still get caught in lines) as bumping it up to 2^(-8) makes a crash happen fairly quickly due to objects leaving the game area.

The value of 2^(-7) is 0.0078125. The value of 2^(-8) is 0.00390625. Neither of these values function better than my 0.0045 constant (which is a little below 2^(-7.5)).

I have used floating-point math in Java (which is where you're referencing from) and it works astronomically better than whatever they've got set up in Warcraft III. In Warcraft III it seems like there's a chance that 0.001 will randomly be added to your real variable in any given situation, even if you are not performing math with it.

In Warcraft it seems even 0.003 isn't even that rare to encounter on floating point math problems. Going from 2^(-24) with a 32-bit float to 2^(-8) with a 32-bit float is unheard of in Java, yet Warcraft III seems to make that precision loss on simple linear calculations.