Cargo Distribution

[Eddi]

well, there are integer-root algorithms

[MildaIV]

You dont need euclidian math as OTTD dont use direct paths. Planes and ships are using axes directions and diagonal directions. What you need is to add diagonal direction:

diag = min(dx, dy)
axe = max(dx, dy) - diag

dist = diag * sqrt(2) + axe

While you need one branch (for min and max) and float multiplication, it is still faster than sqrt. If float operation is to be avoided, than you can use aprox fraction like *577/408.

[fonso]

It's certainly possible to change that. However, the manhattan distance thing is part of the "original style". I don't know if people would appreciate a change. If you want to do it, add a "uint DistanceAxeDiag(TileIndex t1, TileIndex t2)" to map_func.h and map.cpp and then replace all occurences of DistanceManhattan in the link graph directory by DistanceAxeDiag. It would be fairly trivial. Post the patch to flyspray and then we have something discuss.

[MildaIV]

I don't know if people would appreciate a change.

Maybe if it is optionable.

If you want to do it, add a "uint DistanceAxeDiag(TileIndex t1, TileIndex t2)" to map_func.h and map.cpp and then replace all occurences of DistanceManhattan in the link graph directory by DistanceAxeDiag.

Did it. Only replaced metrics in linkgrapgh and in GetOrderDistance (from square euclidian)
It dosn't resolved case on my last picture but resolved other cases, where planes really do longer flights.

Post the patch to flyspray and then we have something discuss.

Can you be more specific how to do it ?

The bigest problem of this patch are road vehicles which are not moving diagonaly.

[Eddi]

well, in the case of your picture, the distance is again equal for this pseudo-diagonal metric. in fact, i don't see many cases where this metric performs better than the manhattan metric at all.

if the only purpose of the metric is to determine which is further away, you can also use the squared euclidean distance (which doesn't need to calculate a square root), but this makes it more difficult to determine how much further away it is, so it might screw with the calculation of alternative routes.

maybe you can also introduce a stopover penalty, but that may make things more difficult, because you might want to distinguish stops where the vehicle continues and ones where the vehicle needs to be switched. this way, people would prefer direct or express routes over frequently stopping routes.

[MildaIV]

in fact, i don't see many cases where this metric performs better than the manhattan metric at all.

There are quite lot of them. And in this cases its really difference in planes flight times.

if the only purpose of the metric is to determine which is further away, you can also use the squared euclidean distance

I suppose that link graph sums distances, so its not usable.

maybe you can also introduce a stopover penalty

I'am now little surprised how it is posible, that direct routes are shorter after fonsos patch at all There must be some little penalty allready.

[Eddi]

the thing is, you can only guarantee that there is exactly one shortest path if your metric fulfills the "parallelogram equality":
||x-y||^2+||x+y||^2 = 2(||x||^2+||y||^2)
(it's called this way, because if x and y span a parallelogram, x-y and x+y denote the two diagonals)

and of the "common" metrics, only the euclidean metric does this. with all other metrics, you always get situations where multiple shortest paths exist.

[fonso]

Yes, there is a stopover penalty. The dijkstra algorithm regards each leg of a path as one tile longer than it is.

If neither metric fullfills the parallelogram equality but the new one is better in some other way we may still prefer it.

Flyspray is our bugtracker at http://bugs.openttd.org . if you post your patch there i'll review it and bring it up on IRC.

[MildaIV]

Patch on http://bugs.openttd.org/task/5941

[MildaIV]

Yes, there is a stopover penalty. The dijkstra algorithm regards each leg of a path as one tile longer than it is.

Iam not sure if rounding of diagonal distance cant in some cases add or substract nearly 1 tile length so make one stop route shorter. It can be eliminated by using 1.5koeficient instead of 577/408 and storing distance in multiple of 2, but on longer routes it makes much biger error.
It also sipmlifies calculation.
if (dx > dy)
return 2*dx+dy;
else
return 2*dy+dx;

[cirdan]

the thing is, you can only guarantee that there is exactly one shortest path if your metric fulfills the "parallelogram equality":
||x-y||^2+||x+y||^2 = 2(||x||^2+||y||^2)
(it's called this way, because if x and y span a parallelogram, x-y and x+y denote the two diagonals)

Huh? I would like proof of this, please, specifically the "only if" part.

The parallelogram equality characterises Hilbertian norms, which are those that are induced by a scalar product. The uniqueness of the shortest path between two points is characterised by the strict convexity of the norm, i.e., the fact that the unit sphere contains no proper segment. And those two things are certainly not the same.

[Eddi]

try the following sketch:

assume you have a point a, and a closed, convex set X. in a hilbert space, you have a unique point x in X, which is closest to a, in a non-hilbert space, there exists a point x in X which is closest to a, but you cannot guarantee the uniqueness.

now consider a sequence of closed spheres B1, B2, ... Bn around a point b.

for each Bi you construct the point bi, which is closest to a. then all these bi lie on a shortest path from a to b.

(this is proof that in a hilbert space, the shortest path is unique. to prove the other direction needs a bit more trickery, and maybe my postulate was formulated too broadly, as i had a specific type of metrics in mind. there may well be "obscurer" metrics which don't show this behaviour. also keep in mind that we're in a 'discrete' subset of |R^2 here)

[cirdan]

Your reasoning just proves that shortest paths are unique in a Hilbert space, which is evidently true since a Hilbert norm is uniformly strictly convex. That is why I specifically asked for the "only if" part.

to prove the other direction needs a bit more trickery

Only if "needs a bit more trickery" means "jumping to conclusions". The well-known family of norms ||x|| = (|x_1|^p + ... + |x_n|^p)^(1/p) are all strictly convex for p>1 but only a Hilbert norm for p=2.

[m3henry]

It bothered me that cargo is always shown on the right hand side of the grey line in the cargo flow map. So I posted a patch to flyspray which makes the linkgraph_gui draw lines on the screen respect the handedness of road vehicles.

Example screenshot for clarity

[Wahazar]

Apologise my break into interesting discussion about functional analysis

One trivial suggestion concerning multiplayer - to display cargodist settings in server summary (right upper panel in multiplayer window).
Because cargodist have multiple options, I propose to display three possible states:
1. if all options are manual, wrote "disabled cargodist"
2. if some options are manual, some not, wrote "partial cargodist"
3. if every options are not manual, wrote "enabled cargodist".

It would help to choose server without joining and settings checking.

[Antaguana]

How do you calculate the saturation levels on a path.

I have a loading station that regularly has a number of trains waiting to take cargo to a destination station but very little cargo is supplied to them as the link is "saturated".
As a result the cargo all banks up waiting to go to another station and then try to make its way back the the original destionation.

Another way to explain that.
Station A has cargo waiting to go to Station B via station C (and D also in this case) when there are a large number of trains waiting to take cargo from A to B.

Also station C is in the other direction and D is past B so the A to B distance is certainly shorter.


The thought I am having (without seeing the algorithm) is that this might occur if you calculate the saturation based on number of carriages that move between the stations. As A to B are not moving (due to having no cargo and wait for full orders) they might not be considered as free capacity. Where as as soon as a train to C comes in it is full and leaves again.

[fonso]

How do you calculate the saturation levels on a path.

I have a loading station that regularly has a number of trains waiting to take cargo to a destination station but very little cargo is supplied to them as the link is "saturated".
As a result the cargo all banks up waiting to go to another station and then try to make its way back the the original destionation.

I really need a savegame to see what's going on there. The capacity of a link will never drop below what it would be if the largest consist that has it in its order list would serve it once a month. The reason for this complicated construct is that it's near impossible to know in advance how long a consist will take to go from one station to another and even what capacity it will have.

However, if the link is only saturated (in contrast to overloaded) and the other ones are overloaded there must be some other benefit for the MCF algorithm to use the other links. Normally it would happily overload the link with the waiting vehicles, too, causing them to serve it more often and in turn increasing capacity. The benefit can simply be that another path is shorter or it can be a side effect of a low value for the accuracy or short path saturation settings. It could also be that you have a large value for the recalculation interval setting (which used to have a bad default; read back a few posts to find the discussion) and the link graph just never gets updated.

So, please post a savegame and point out which stations are showing what unexpected behaviour. Then I can determine if it's a bug and fix it if necessary.

[fonso]

Reading back on http://www.tt-forums.net/viewtopic.php? ... 0#p1113795 and the follow ups and after all the other feedback I got I think I can state the following:

I can probably ignore all the considerations about multiple stations serving the same houses and industries or people connecting their link graphs with fake links. In the general case they won't and if they do then this is a minor cheat compared to all the other nasty things you can already do. Consequently I can collapse the whole second part of the post to a very simple algorithm revolving around 3 additional settings:

1. Base cargo supplied to stations: A percentage of the current amount that is given to stations independent of the link graph they're part of
2. Maximum bonus cargo for large link graphs: Percentage to be added to the base cargo if the station is part of a large link graph. Can be negative so that cargo supply is further reduced when the link graph grows.
3. Number of stations in link graph to get full cargo bonus: A number between 1 and 64k. The cargo bonus you get on top of the base cargo is the size of your link graph divided by this setting multiplied by the maximum bonus.

By setting them to 100%/0%/1 you get the current behaviour. As the size of a link graph is very easy to determine this is a simple and effective way to simultaniously reduce the cargo flooding and give you an incentive (of whatever kind you choose) to connect your link graphs.

If cheating becomes a real concern one could easily determine the connectedness of link graphs and somewhat less easily the amount of real cargo acceptance served by a link graph. Those numbers would provide effective counter measures. But as generally the game is largely based on trust between the players and the players will set up rules to be followed outside the game logic, I'd like to see some real cases before I do that.

[fonso]

This patch implements the base/bonus thing mentioned above. I'd love to hear some feedback on how it works for you.

[Pyoro]

Since I've been compiling OTTD for the new map features and daylength anyways I quickly added this.
I seems to do what it's supposed to do, I think. Base cargo definitely works. Second is a bit difficult to tell since I just played a rather small game

In any case my main issue has always been those ridiculous amounts of passenger this produces and the base cargo setting helps a lot there. Although it's rather crazy having to set it to like 10% (with daylength 6) and still get "a lot" ^^