NPF patch (occupation check)

[TBOT]

I've done some work on improving the NPF, mainly because it very reluctant at considering alternative routes when the optimal one was crowded/jammed.

So I've modified the cost function a bit:

1. Occupied track is weighed against the distance from the train:
This allows a train to look at how crowded a route is, and consider less crowded alternatives. The distance from the train is taken from the cost to reach a node. A weight is calculated upon that:
With x being the cost to reach this node, and high_limit, low_limit and max_weight as added 'npf_rail_occupied_*' variables.

Code: Select all

for x <= high_limit: w = max_weight
for x >= low_limit: w = 1.0
for high_limit < x < low_limit: linear interpolation between max_weight and 1.0

This cost of an occupied tile is multiplied with this weight (with the exception of extra cost for red signals).

The initial values chosen for the variables are:
max_weight = 3
high_limit = 1000
low_limit = 5000

This means that till a distance of roughly 10 tiles the weight of 3 applies (i.e. triple the length of the occupied track may be chosen as alternative), and that after roughly 50 tiles no extra weight is given.

Note that these are very rough guesses, based on what seemed to work for me. The values may be heavily dependent on train speed (maybe the limits should be scaled with it?) and network layout, so feel free to play around.


2. Red presignal entries which are not the first encountered also get a penalty:
In general this allows custom tweaking of weights. An example may be crossovers on a double track, which should be very strongly discouraged if the destination track is occupied. The more red presignal entries, the more likely a suboptimal alternative is chosen, which in the example may be an alternative approach with tunnels/bridges.

The penalty can be changed with the 'npf_rail_red_entry_penalty' variable.


3. The higher firstred penalty now also applies to presignal entries:
In line with the 2nd change, so the direct choice for a red presignal entry is even more strongly discouraged.



Attached is a patch upon r4341 (I hope I did it right ), as well as a windows executable. Please feel free to test around and tweak the variables (especially for different train speeds).

Edit: updated attachments to use integer math and fixed the interpolation. Making the technical note useless .


Technical note:
In the weight implementation I use a floating point variable, for which no unified type was available. While floats should be supported on pretty much every platform, their behaviour may not be the same and therefore may cause very rare desyncs in network games.
Also the config file doesn't support input of floats (as far as I could see), so the max_weight variable is limited to rounded numbers only.
Should floats be a major objection I guess the weight can be given in 1/10'ths or something.
Any thoughts?

[suikerpluimpje]

sounds very nice. I will try it this afternoon.

[madman2003]

Floating point math is not acceptable for these kinds of things as far as i know, for the very reason you already mentioned.

Since the end result is going to be an int, why not do integer math, just scale up the calculations and at the end define cost as weight/scalefactor. That way you have minimized rounding errors as far as i can tell.

[XeryusTC]

sounds very nice. I will try it this afternoon.

Same thing here, I will try it when I fix the patches I already applied (I kinda screwed up) and I'll add this one.

[TBOT]

Since the end result is going to be an int, why not do integer math, just scale up the calculations and at the end define cost as weight/scalefactor. That way you have minimized rounding errors as far as i can tell.

Yeah, that's the way to go without floats, already figured that one out. Still floats are fairly intuitive to use in something like this .

Anyway, this shouldn't spoil the fun for now (it's still a concept), and the chance it'll go wrong is virtually non-existant (the error has to survive integer cutoff, and after that still be big enough to actually change a route).

[madman2003]

This patch (if it behaves on the long run) might be nice to have openttd, but it will never get in if it uses floats. I've included a patch which does it the way i would do it, but ofcource you know more about the patch

[TBOT]

This patch (if it behaves on the long run) might be nice to have openttd, but it will never get in if it uses floats. I've included a patch which does it the way i would do it, but ofcource you know more about the patch

Updated the original attachments. It now uses the scalefactor (your patch would cause integer cutoff errors though). Also, I've fixed an error in the formula, as the linear interpolation was actually applied wrongfully (swapped a sign...).