Cargo Distribution

[fonso]

For the time after 1.4 I'm currently thinking about two more distribution modes, in addition to symmetric, assymetric, and manual, to complement the cargodist functionality:

1. One mode that does take capacity into account when calculating demands and reduces the distribution to simple waybill dispatchment. This should be fairly easy to do. Just don't assign any demands and run some kind of BFS-based distribution algorithm to generate paths over links with free capacity instead of running the MCF solver. Then eliminate cycles just as with MCF.
2. One mode that takes the relative size of the link graph in terms of covered production and acceptance of cargo into account. It then reduces the amount of cargo delivered to stations in "small" link graphs and increases that for stations in "large" link graphs. Like that you have to deliver cargo to many different places to attract the maximum amount of cargo from source stations. This is deliberately different from what YACD and previous destinations patches do. It won't predetermine destinations but just modify the amount of cargo you get. This mode is somewhat harder to implement for several reasons:
   • Catchment areas can overlap. That's not a problem when counting production, but it is for counting acceptance. You shouldn't be able to cheat it by building 5 stations around each industry. The obvious solution of keeping track of which tiles are covered by which stations is not trivial.
   • You can connect link graphs by building dummy links and then dropping them again. There's currently no way of splitting a link graph once it has been connected. Either that has to be implemented or there has to be some other way of preventing people from exploiting the link graph merging for getting more cargo without actually distributing it over a larger network.
   • Global accpetance and production may not be easy to measure. For passengers and mail one could try to deduce it from the total number of houses on the map or add up the statistics kept for towns, but that would be an approximation at best. For industries production is easy to determine but acceptance would involve looking at the tiles again. Maybe the tile acceptances can simply be added up by the tile loop but I'm reluctant to adding any code to the tile loop as it's a very hot code path.

[MildaIV]

What I dont like on current distribution for passangers is, that amount of destinations dont affect demand. If you have one destination on other edge of map you get same number of passangers like when you have hundreds of close targets. So when you open new link you loose demand on existing destinations. Second thing I dont like is relative small efect of distance(regardles of its setting). Local transit networks should be mandatory as base for longrange routes.

[fonso]

Yes, that's exactly the problem I'm trying to solve with the second proposition. There are of course simpler ways of doing that. The algorithm could simply count the number of stations in the link graph and grant bonus cargo for link graphs with more than e.g. 5, 20, 50, 100 stations. That would be a matter of about 10 lines of code. There are about as many ways to cheat it, though.

[3298]

Ah, I see, you're tackling the cargo reduction now. That's what has been bothering me about Cargodist: without cargo reduction, it encourages point-to-point connections to get the most cargo for the least trouble. With point-to-point connections, Cargodist might as well be turned off, it doesn't even matter. Without this planned mode, that is.

This would be my way to do it. Maybe you have a similar approach in mind, maybe yours is better (in that case: good job), but I'll post it in the hope that you can profit from it.

You want the amount of cargo delivered to a station for loading to be reduced to a fraction of what's currently delivered. To be precise, this fraction is reachable_accepting_places / total_accepting_places. I'm just counting the places here, ignoring any acceptance limitations which could be present with NewGRF industries.

The total number of accepting places is the easy part, just count 'em all. Or keep the value in memory for each cargo type and update it when an accepting place appears or vanishes. (It doesn't even have to be saved because it is obviously easy to re-calculate from the map during loading.)
Now, the reachable places. I'd add a list to a linkgraph which counts the reachable destinations. When updating the linkgraph, go through all accepting places on the map and do the following for each of them: Take the stations which have the place in their catchment areas, figure out which linkgraphs they belong to (I'm sure you have a function for that somewhere), and add the place to the linkgraphs' lists.
We don't need any order in the list, we only need to be able to count the items in it, and it must be one which ignores multiple additions of the same item. With some sort of hashing this should be possible in constant time in most cases.
I'm not sure whether it's already possible to get from a cargo-accepting place to the stations which have it in their catchment areas. You or the other devs are more familiar with that code.
Wait, another idea just came to my mind: if it's easier to get from a station to the accepting places in its catchment area, you could just swap the iteration over stations and accepting places, i.e. you go through the list of stations and fetch the nearby accepting places. After all, the purpose of this is that you look at all station + accepting place pairs where the place is in the station's catchment area.

My biggest concern with this method is the potentially huge number of accepting places for town-accepted cargo with the many towns on larger maps. What about this: for houses, bundle several of them to a single accepting place. For example, you could cut the map into pieces of, say, 4*4 tiles and merge all houses in the same piece into an accepting place for whatever cargoes have town effects.

I think it's easily possible to get to the accepting places outside the tile loop. You can iterate over industries and over towns with the FOR_ALL_whatever macros, I think a town's houses can be reached somehow as well, and if you think the house groups are a good idea, you could throw them into towns as well. Stations are just as easy to go over, with the benefit that you usually have less stations than accepting places. And wasn't there a hard limit for the number of stations? It feels safer with such an upper bound.

... Oh crap, I just found a network where this doesn't work as expected. Take two coal mines (1 and 2), two power plants (A and B), two stations (a and b) and the following links: 1->a, a->A, 2->b, b->B and a->b. They have to be considered on the same link graph because the possible.routes for the coal (1->a->A, 2->b->B and 1->a->b->B) share some sections with each other, so the approach above would say "both A and B are reachable on this network" and then let 1 and 2 produce the full amount of coal even though A is not actually reachable from 2. I'll still leave the algorithm in the post to save you from running into that issue.

So this leaves us with the option to flood-fill the linkgraph from every single node with a producing industry nearby (I'm sure you keep track of these somewhere), while counting the accepting places. (Or adding up all the acceptance limits for the NewGRF industries with acceptance limits.) Flood-fill is not too expensive itself (O(n) if I remember correctly), but having to do it n times could really hurt. I don't know the complexity of your flow solver, but if it's O(n^2) as well or even better, this flood-filling may take more time than the solver, which is currently (at least as far as I know) the most time-consuming part of Cargodist.

[MildaIV]

And what about station rating? Will it be affected by cargodist? Current way how it works sucks.

[fonso]

What is wrong with station rating? I wouldn't modify it as that has too many side effects (industries closing, towns going mad ...). Simply reducing the cargo supplied to the stations is enough to give you an incentive to expand your network.

Those convoluted calculations proposed by 3298 are exactly why I want to avoid maintaining an association between stations and "accepting places" at all costs. There's simply no fun in it. If I implemented that stuff I could as well do it YACD-style with predetermined destinations.

[Simons Mith]

I'm not sure whether this oberservation helps, but I want to put it out anyway. One thing which bugs me a bit about the game at the moment is the way the game places industries out in the middle of nowhere. There is no discernible relation between the placement of power station a and nearby coalmines b, c and d. But, imagine there was. Imagine the reason the reason power station a was in some particular spot was because it minimised the transport costs to the mines it actually uses, in proportion to the amount of coal it uses from each? After all, the game assumes a pre-existing 'ghost transport network' that's present before the player starts building transport lines of his own.

Is there some way you could use the geographical information from the map to inform the ideal cargo flow for each industry? Assume each serves/is served by the nearest 4-6 industries, and was intentionally built at the spot that minimises its total transport costs. You could even infer an industry's production/consumption capacities from this.

[MildaIV]

Instead of counting Global acceptance you can count simplified aproximation of it. based on map like population density. Than count reachable destinations multipled by their distances(atractivity of this destinations). While costly to compute you dont need to update it frequently. This can affect station rating as I mentioned earlier or cargo generation, as you noted is simpler.
Can you create virtual stations(nodes) for overlaping stations reachable from all stations at 0 cost?

[fonso]

You can chain overlapping stations to no end and not all overlapping stations have to serve the same sources and destinations. Collapsing them into "virtual" nodes is probably not easier than keeping an association of cargo sources/sinks to stations. One could approach it from the other side: What useful properties are easily available? Notably, one can easily determine how many towns and industries are being served at all. So one could make a kind of prisoner's dilemma out of it: Determine the total amount of cargo bonus by the global rate of service and then split that bonus among all link graph components by some property that doesn't involve the cargo sinks or sources anymore. Calculating connectedness of a link graph component is not really a problem. So for the case of falsely merged link graphs one could just split the bonus further. However, the remaining question is how to determine what share of the total bonus a link graph component should actually get.

The naive answer is that it should be determined by the number of accepting stations in the link graph but that will of course prompt people to build multiple accepting stations for each cargo sink. Alternately one could make the shares depend on the added supply in the component. This value cannot be manipulated as easily but it's somewhat hard to understand why one should get more cargo by delivering coal from two mines to one power plant than by delivering coal from one mine to two power plants.

[Eddi]

What i didn't understand is why it matters whether the linkgraph is connected or not.

Why would it matter that the two available destinations are delivered by the same company, as long as they are both delivered?

Suppose there are two companies: 1,2
three sources: A,B,C
two destinations: X, Y

1 serves the routes A->X, A->Y and B->X
2 serves the routes B->Y and C->Y

A has two reachable destinations: X (via 1) and Y (via 1)
B has two reachable destinations: X (via 1) and Y (via 2)
C has one reachable destination: Y (via 2)

why should A produce more than B?

[MildaIV]

it's somewhat hard to understand why one should get more cargo by delivering coal from two mines to one power plant than by delivering coal from one mine to two power plants.

I don't think that this algohitm is suitable for industry cargos. Only for pax, mail and maybe valuables. I dont understand it as producing more for more targets, but producing less for not enough targets. i.e. I want to go to neighbour city to visit my friend, but no company take me there, so I have to go by car or stay at home
Personaly I am not using cargodist for industry cargos at all. I like railroad tycoon system of price diferences for them.

[3298]

convoluted calculations

Is that really what it looks like? Oh dear. To me that's a rough sketch for the implementation. Well, I usually jump straight to the editor, making such a sketch in my head, after five minutes I begin to write code.

Those convoluted calculations proposed by 3298 are exactly why I want to avoid maintaining an association between stations and "accepting places" at all costs. There's simply no fun in it. If I implemented that stuff I could as well do it YACD-style with predetermined destinations.

Hm, true. But how do you want to determine the fraction of reachable accepting places (you've put that into quotes; I wanted to use a word describing both industries and houses) then?
Looping through all possible destinations certainly looks Cargodest-like, but other than a little bit of caching (it's about counting the places, not assigning them as destinations over and over, so we can cache) I see no way around checking the graph for what's connected. (Technical detail: When flood-filling from the second, third, etc. node, you can reuse the reachability data of the already processed nodes when encountering them during the flood-fill. For even better results, something based on Tarjan's algorithm for finding strongly connected components in a graph can be used, the nodes in a strongly connected component have a common list of reachable nodes.) ... I'm doing convoluted calculations again, right?

Regardless, I appreciate that you are willing to spend time on a feature which never was in Cargodist (as far as I know) - and it was a popular patch without that feature. Thank you.

[MildaIV]

When we talking about future I have yet one thing in my mind. Currently it's quite a problem at default setting find route where add new plane. You can easily add plane to route which is overloaded by cargo that is using second, third etc. shortest route. What can help is ability to display shortest/other path loads filtered. It can be at station and/or graph. This will reduce my need to increase saturation of shortest path to its maximum xD.

[fonso]

What i didn't understand is why it matters whether the linkgraph is connected or not.

The whole idea is to encourage you to connect your networks. One way to do that is granting bonus cargo for connecting link graphs.

[MildaIV]

I have yet one problem with shortest path routing. I started new game with patched nightly. While all direct routes are now shorter than one stop routes, there are some one stop routes which seems shorter, but cargodist dont think so. In case on my picture, cargodist choose shortest path in one direction, but on other way it think another route is shorter.

In my old game(after fix) I have examples which are much longer and still considered shortest path.

[Eddi]

in most places, the game uses manhattan metric, not euclidic metric, so some "intuitively longer paths" are actually the same length

[fonso]

Those two routes are pretty certainly of equal length for cargodist as it uses Manhattan distance.

[MildaIV]

When Im looking at my maps, it seems like manhattan metric is the reason. Why is manhattan metric used on anything else than road vehicles?

[Eddi]

because it's easier to calculate

[Transportman]

because it's easier to calculate

Isn't it also because Manhattan distance can be done with integers, while the straight line requires floating points?