Orthogonal Income Patch

[Aphid]

This is a corner case that will generally not happen in a typical game, yet I found out it was possible while digging in the source code.

Economy.cpp, line 986 states;

Code: Select all

return BigMulS(dist * time_factor * num_pieces, cs->current_payment, 21);

So if the first argument f can be >= 2^31, we have an overflow risk. Interesting sidenote: the formula accepts a signed integer while some of the multiplied variables are unsigned.

Let's use the following shorthand names in the following bit of logic;

• 'dist' = d'
  'time_factor' = t
  'num_pieces' = n
  train length in cars = c
  max. cargo per car = m

We know the following statements are true:

m < 2^8 (from NewGRF spec)
c < 2^8 (127 tiles max train length from game)
d < 2^12 (technically slightly less due to a map array error, but we assume a safe number here)
t < 2^8.

8+8+12+8 = 36 > 31.

Thus, technically, in corner cases, trains can make less money than they should. To test this, you need a train with the full complement of 255 cars that have a high capacity (above 64 units per car will do the trick), going the full corner-to-corner distance on a 2Kx2K map in a very short time. To test this try making a maglev MU train with the following specs:

max. speed: 4,000 kph
power: 65535 hp per unit
capacity: 200 passengers per unit.

The total train contains 50,800 passengers. Multiply that by 4000 tiles and say 200 for the time factor we get 40640000000, or 40,64*10^9, which is about 20 times more than 2^31.

. Because the integer is signed in the multiplication, the integer overflow will do weird things.

I'm In the process of writing a patch to allow 'square' distance payments and wondering how to best deal with this. I'm thinking of using doubles for the entire calculation and converting the double to an int64. (edit: and replacing the C-style casts with static_cast as is used for all other type conversion between standard numerics) Since a double has 52 bits of mantissa there is no effect. Ideas?

[Eddi]

you can never use floating point types (float or double) in game logic, because it can cause desyncs.

[Aphid]

So in essence, that means I have to write my own

Code: Select all

uint sqrt (uint x)

function? I get some rounding errors but of course I could also compute

'int sqrt(x*65536)'

or similar to get some extra arbitrary precision and later on right-shift more. The difference to the end-user is then negligible.

By the way, this is a very interesting subject to me, can they cause desyncs because different compilers treat floats differently? Or different operating systems / processors? There's supposed to be a standard; IEEE 754. Reading some sources, notably http://www.cs.berkeley.edu/~wkahan/ieee ... EEE754.PDF (1997) yields that Microsoft (who else) chose to ignore the standard and make its fp's return 'INFINITY' instead of 'NaN' upon division by zero. But when my only operation is one multiplication, can desyncs still occur, and why?

[Eddi]

the desyncs happen because the standard does not define how rounding should happen.

e.g. the result will differ slightly if the FPU uses 80 bit floats internally and rounds to 64 bit floats on the final result (that is pretty much all intel processors), or when the FPU uses 64 bit floats all the way through (rounding errors will add up faster this way)

[Core Xii]

you can never use floating point types (float or double) in game logic, because it can cause desyncs.

Only with the stupid lock-step networking that OpenTTD relies on. With proper server-client architecture you can use floating point math perfectly fine.

[PikkaBird]

you can never use floating point types (float or double) in game logic, because it can cause desyncs.

Only with the stupid lock-step networking that OpenTTD relies on. With proper server-client architecture you can use floating point math perfectly fine.

I'm sure we're all waiting with bated breath for your description of a "proper server-client architecture" for OpenTTD. Preferably one that wouldn't require a dedicated T1 line and/or every player to be in the same room.

[frosch]

m < 2^8 (from NewGRF spec)
c < 2^8 (127 tiles max train length from game)
d < 2^12 (technically slightly less due to a map array error, but we assume a safe number here)
t < 2^8.

8+8+12+8 = 36 > 31.

While that part of the code changed recently and my knowledge is not quite up to date, I believe payment still happens per CargoPacket. Since a CargoPacket is not split over multiple vehicles, you have to set c = 1. On the other hand you have to consider ships, thus m < 2^16.
So, I guess you need a ship with capacity 2^11 = 2048 to trigger to issue.

[Aphid]

So there's basically a few alternatives to fix the fp issue, one of which is to re-invent the wheel. However, I believe it's irrelevant for this patch now;

Since in actuality, I can use a little trick to not use fp numbers. Instead of the manhattan or euclidian distance, use the 'ottd plane distance'. Makes more sense from a gameplay concept too.

(sqrt(2) - 1) * n + m, where n = min(dx, dy), and m = max(dx, dy).

By the way, it is possible to make different compilers, machines, processors, etc. use the same floating point calculations. Many networked games depend on them and do not transmit entire gamestates. The real problem is the sheer amount of code needed. For example on windows you can use a #pragma to 'force' 'strict' fp behaviour from the compiler, e.g. standards-compliant 52-bit rounding. Intel's compiler requires a different instruction to deviate from 64-bit behaviour. Also it requires care to make sure that all compilers do not try to 'optimize' the code parts that use fp calculations if exact precision is needed. Chaotic systems and so forth. Making the end-result nice and pretty may be a challenge.

The attached patch also fixes the possible integer overflow bug, and with its primary function adds a setting to the advanced settings menu, allowing a user to select 'balanced' income distance calculation. This basically means that an orthogonal railway is no longer more profitable than a diagonal one, and the same for any linear combination of diagonal and orthogonal parts.

[Aphid]

Rebased against current Trunk::

[adf88]

So if the first argument f can be >= 2^31, we have an overflow risk.

Why don't you just develop 64-bit version of DivMulsS?

Code: Select all

/**
 * Multiply two integer values and shift the results to right.
 *
 * This function multiplies two integer values. The result is
 * shifted by the amount of shift to right.
 *
 * @param a The first integer
 * @param b The second integer
 * @param shift The amount to shift the value to right.
 * @return The shifted result
 * @pre INT64_MIN <= a * b <= INT64_MAX
 */
static inline int64 BigMulS(int64 a, int64 b, uint shift)
{
    return (a * b) >> shift;
} 

Or just inline this expression:

Code: Select all

return ((int64)dist * time_factor * num_pieces * cs->current_payment) >> 21; 

Or reorder args:

Code: Select all

return BigMulS(dist, time_factor * num_pieces * cs->current_payment, 21); 

[Eddi]

return (a * b) >> shift;

that looks totally wrong, because the result of a 64-bit multiplication is a 127-bit value, but by the time the shift is evaluated, the high 63 bits are already thrown away, because they don't fit into the register.

[adf88]

I put "@pre INT64_MIN <= a * b <= INT64_MAX" into doxygen block to clarify that. This is a little odd so I proposed also to inline this operation and resign with the BigMulS function at all.

[Aphid]

Updated it after some comments about calling conventions so that the original function call for the income function works via a wrapper.

By the way, I see no need for BigMulS to exist when my first value is a 'Money' (which is an int64) anyway. int64*int32 gets cast to int64 if I'm not mistaken.

[Wahazar]

Sorry sticking to this thread, I don't want to produce a new one.
I want to clarify for myself, is it absolutely prohibited to use floats in openttd,
even for calculations inside function (output to int)?
I know that real programmers use integers, but I need to compute exponential function.

[Alberth]

Technically are allowed only for things you display to the user, but that happens practically nowhere.

The reason is that in MP, different OpenTTD games must run in sync while being connected over the Internet. It is absolutely vital that all the computation results match with all other computers in the same game. Floating point numbers don't have that property.
(think different processor architecture, using different OS, with different math libraries in their compiler)

[Wahazar]

Even if trunc(float*2.0) shl 1 was done?

Seems that I must write int exp function based on Taylor series.

[Rubidium]

Even if trunc(float*2.0) shl 1 was done?

Yes; the C standard doesn't guarantee a specific floating point behaviour, there are known CPUs with buggy floating point implementations, not all CPUs have a floating point unit and compilers have options for "fast math" causing different behaviours as well. Since neither is under control, even something simple as multiplying and dividing can yield a slightly different value, which is made worse by rounding/truncation.

[Eddi]

Even if trunc(float*2.0) shl 1 was done?

Just imagine if the result of "float*2.0" was 1.0000000000 on one computer and 0.9999999999 on the other (tiny error of 10^-10). then trunc() will result in 1 or 0. BOOOM desync explodes in your face. and it doesn't matter how small the rounding errors will get, there WILL be differences.

Seems that I must write int exp function based on Taylor series.

sounds like a nightmare between rounding and overflow.

you should rather calculate your final curve instead of a generic exponential function, and then interpolate at a few points, e.g. with splines.

PS: "integer" exponential function x^y is typically implemented by square-and-multiply.

Code: Select all

pow(x,y) {
 assert (y>=0)
 if (y==0) return 1
 z=pow(x,y/2)
 if (y is odd) return z*z*x
 else return z*z
}

[Wahazar]

I tought that every financial calculations are performed on server side and broadcasted to clients.
Now I read a little about this game network protocol and see all this float rounding issue more clearly.
(BTW, are random actions like engine breakdowns, also deterministic due to common random seed?).

I don't like idea of lookup table, all I need is exponential decay function A*exp(-x),
it can be expanded as sum of (-x^n)/n!, I suppose that if each part of the sum would be subsequently multiplied and divided,
should not suffer from roundings and overflow, if A is set appropriately.

[Alberth]

I tought that every financial calculations are performed on server side and broadcasted to clients.

Nope, too much bandwidth needed for that

(BTW, are random actions like engine breakdowns, also deterministic due to common random seed?).

Yes.

I don't like idea of lookup table, all I need is exponential decay function A*exp(-x),
it can be expanded as sum of (-x^n)/n!, I suppose that if each part of the sum would be subsequently multiplied and divided,
should not suffer from roundings and overflow, if A is set appropriately.

Can't you make an approximation? People are not going to notice it's not a prefect exp function.