Cargo Distribution

Forum for technical discussions regarding development. If you have a general suggestion, problem or comment, please use one of the other forums.

Moderator: OpenTTD Developers

Eddi
Tycoon
Tycoon
Posts: 8258
Joined: 17 Jan 2007 00:14

Re: Cargo Distribution

Post by Eddi »

well, there are integer-root algorithms
MildaIV
Engineer
Engineer
Posts: 52
Joined: 11 Nov 2005 09:07
Location: Czech Republic
Contact:

Re: Cargo Distribution

Post by 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.
User avatar
fonso
President
President
Posts: 945
Joined: 13 Oct 2007 08:28

Re: Cargo Distribution

Post by 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.
The guy on the picture is not me, it's Alonso.
MildaIV
Engineer
Engineer
Posts: 52
Joined: 11 Nov 2005 09:07
Location: Czech Republic
Contact:

Re: Cargo Distribution

Post by MildaIV »

fonso wrote: I don't know if people would appreciate a change.
Maybe if it is optionable.
fonso wrote: 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.
fonso wrote: 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
Tycoon
Tycoon
Posts: 8258
Joined: 17 Jan 2007 00:14

Re: Cargo Distribution

Post by 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
Engineer
Engineer
Posts: 52
Joined: 11 Nov 2005 09:07
Location: Czech Republic
Contact:

Re: Cargo Distribution

Post by MildaIV »

Eddi wrote: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.
Eddi wrote: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.
Eddi wrote: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
Tycoon
Tycoon
Posts: 8258
Joined: 17 Jan 2007 00:14

Re: Cargo Distribution

Post by 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.
User avatar
fonso
President
President
Posts: 945
Joined: 13 Oct 2007 08:28

Re: Cargo Distribution

Post by 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.
The guy on the picture is not me, it's Alonso.
MildaIV
Engineer
Engineer
Posts: 52
Joined: 11 Nov 2005 09:07
Location: Czech Republic
Contact:

Re: Cargo Distribution

Post by MildaIV »

MildaIV
Engineer
Engineer
Posts: 52
Joined: 11 Nov 2005 09:07
Location: Czech Republic
Contact:

Re: Cargo Distribution

Post by MildaIV »

fonso wrote: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;
User avatar
cirdan
Director
Director
Posts: 539
Joined: 07 Apr 2007 18:08

Re: Cargo Distribution

Post by cirdan »

Eddi wrote: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
Tycoon
Tycoon
Posts: 8258
Joined: 17 Jan 2007 00:14

Re: Cargo Distribution

Post by 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)
User avatar
cirdan
Director
Director
Posts: 539
Joined: 07 Apr 2007 18:08

Re: Cargo Distribution

Post by 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.
Eddi wrote: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.
User avatar
m3henry
Tycoon
Tycoon
Posts: 1985
Joined: 15 Feb 2006 12:00
Location: Hampshire

Re: Cargo Distribution

Post by 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
Attachments
Screenshot 2014-03-31 23.25.55.png
Screenshot 2014-03-31 23.25.55.png (109.75 KiB) Viewed 909 times
The occasional look back at your past can teach you a great many things...
Wahazar
Tycoon
Tycoon
Posts: 1451
Joined: 18 Jan 2014 18:10

Re: Cargo Distribution

Post by 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.
Formerly known as: McZapkie
Projects: Reproducible Map Generation patch, NewGRFs: Manpower industries, PolTrams, Polroad, 600mm narrow gauge, wired, ECS industry extension, V4 CEE train set, HotHut.
Another favorite games: freeciv longturn, OHOL/2HOL.
Antaguana
Engineer
Engineer
Posts: 10
Joined: 05 Oct 2013 08:58

Re: Cargo Distribution

Post by 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.
User avatar
fonso
President
President
Posts: 945
Joined: 13 Oct 2007 08:28

Re: Cargo Distribution

Post by fonso »

Antaguana wrote: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.
The guy on the picture is not me, it's Alonso.
User avatar
fonso
President
President
Posts: 945
Joined: 13 Oct 2007 08:28

Re: Cargo Distribution

Post by 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.
The guy on the picture is not me, it's Alonso.
User avatar
fonso
President
President
Posts: 945
Joined: 13 Oct 2007 08:28

Re: Cargo Distribution

Post by fonso »

This patch implements the base/bonus thing mentioned above. I'd love to hear some feedback on how it works for you.
The guy on the picture is not me, it's Alonso.
User avatar
Pyoro
Tycoon
Tycoon
Posts: 2558
Joined: 17 Oct 2008 12:17
Location: Virgo Supercluster

Re: Cargo Distribution

Post by 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" ^^
Post Reply

Return to “OpenTTD Development”

Who is online

Users browsing this forum: No registered users and 20 guests