YACD - Yet Another CargoDestinations (v2.3 released)

[fonso]

fonso: You telling me (or whoever implements it) where to look could be really helpful, thanks!

I'm always happy to give advice on the code I've written.

1. You're right, this is difficult because it probably involves random numbers, and due to the way random numbers are implemented they have to be generated in the main thread. We basically need a random tile (well, a station next to that tile because we shouldn't access the map in the link graph thread) which accepts the cargo type we are currently looking at. There should be some parameter, though, to influence this randomness. YACD has it somewhere in the config, and even though I'm not entirely sure what it exactly does (that part of the code didn't change much, no reason to touch stuff that isn't broken), it seems to tell how close to the source tile a destination is considered "nearby". Nearby destinations get more demand, and there are separate settings for towns and industries.
The only design question I have in this area is: Do we want to choose the destination tile in the main thread, or do we want to pass some cargo acceptance information as part of the linkgraph structure and choose the destination in the link graph thread from this and a random number? By the way, there is some helpful stuff for cargo acceptance in trunk, committed shortly after r23400. It is used for subsidies and was largely YACD code.

Random numbers for the link graph jobs aren't difficult. You could refactor the random number generator to allow for separate instances working independently from each other. Then you could add such an instance to the link graph job. Finding accepting stations is also not a problem as each link graph job only handles a specific cargo and has information about supply and acceptance. Distance is also no problem as each link graph already contains the distances between all its nodes. About your question: You should definitely do as much work as possible in the link graph thread. However, before actually writing any code you should figure out a concept on how to determine which nodes should be destinations of cargo from which other nodes. In addition you will probably want to assign something like demand between industries and/or towns before and only derive demand between stations from that. This is where it gets complicated: Which towns and industries are actually relevant? How do you make the information available to the link graph jobs?

My suggestion to keep it simple would be the following:
1. Destinations aren't actually calculated before the link graph exists. In the beginning each industry or town is "free" and doesn't list any destinations.
2. Reachable industry and town IDs are listed in the link graph nodes (which is not as trivial as it sounds, btw)
3. Depending on output volume a town or industry may have one or several destinations (towns or industries). Those are just the first ones being connected to it in the link graph. The information about those destinations is saved as some kind of list in the link graph job and after joining the link graph job becomes persistent and is then added to all new link graph jobs of the respective cargo. (so that other companies can build parallel routes)
4. The "destinations" demand handler only assigns demands that follow those destinations.
5. The destinations can then be shown in the town or industry GUI.

Of course this doesn't meet the requirement of pre-existing destinations. Destinations are still generated from the link graph. However, once a destination is established it stays around forever and there is a limited number of destinations per source. Note that you don't have to determine global production, global demand, distances of all possible destination tiles or similar things like that.

3. (the first one) Cargo generation seems to be the logical place to do this.

You have to familiarize yourself with the concept that actual cargo routing and computation of the routing scheme are two completely separate things in cargodist. This has proven to be quite advantagious and IMHO you should stick to it. So no, cargo generation is about the worst place to do that.

Note that YACD does have symmetric and asymmetric demand too, but it seems hardwired to be symmetric for passengers and asymmetric for everything else.

You may want to add two additional demand modes: symmetric destinations and asymmetric destinations.

On the other hand, I would already be kinda happy if Cargodist dropped cargo based on how many potential destinations are unreachable. On a second thought, that should be quite a bit easier to pull off.

Think again. How do you determine "potential destinations"? If you find a good solution for that please go ahead. I've tried and I couldn't.

[Hyronymus]

My town window looks totally different to be honest.

Town window.png (74.12 KiB) Viewed 4849 times

I'll fiddle with the settings for long distances a bit and see how it turns out.

[3298]

My town window looks totally different to be honest.

OpenTTD r25942? You're definitely not playing YACD. The stuff in your town window is probably from a game script. Some citybuilder-type one, I guess. And those passengers not wanting to travel to the other town... the link graph recalculation does not take 9 months, and the train route should have a non-zero capacity which means some cargo should use it, so there is something weird going on there.

Random numbers for the link graph jobs aren't difficult. You could refactor the random number generator to allow for separate instances working independently from each other.

That's an excellent idea. One step closer to real multi-core support (unrelated to Cargod*st).

1. Destinations aren't actually calculated before the link graph exists. In the beginning each industry or town is "free" and doesn't list any destinations.

Destination calculation in YACD is kinda cheap, just pick a house/industry accepting the cargo. For industries YACD does it in O(n) due to the fact that there are weights; for houses it picks a town in the same fashion, and then chooses a random house inside it.

2. Reachable industry and town IDs are listed in the link graph nodes (which is not as trivial as it sounds, btw)

Reachability on a directed graph ... there should be algorithms to solve that one. In the worst case, I can take this simple algorithm: floodfill beginning from every node, which is O(n^2) if I'm doing the math right. But anyway, caching the reachable destination stations should help.

3. Depending on output volume a town or industry may have one or several destinations (towns or industries). Those are just the first ones being connected to it in the link graph. The information about those destinations is saved as some kind of list in the link graph job and after joining the link graph job becomes persistent and is then added to all new link graph jobs of the respective cargo. (so that other companies can build parallel routes)
4. The "destinations" demand handler only assigns demands that follow those destinations.
5. The destinations can then be shown in the town or industry GUI.

Of course this doesn't meet the requirement of pre-existing destinations. Destinations are still generated from the link graph. However, once a destination is established it stays around forever and there is a limited number of destinations per source. Note that you don't have to determine global production, global demand, distances of all possible destination tiles or similar things like that.

This is what Cargodest is not meant to do: it adapts to the player's network.

You have to familiarize yourself with the concept that actual cargo routing and computation of the routing scheme are two completely separate things in cargodist. This has proven to be quite advantagious and IMHO you should stick to it. So no, cargo generation is about the worst place to do that.

Hm, now stuff is getting technical. This is definitely worth thinking about, but I'm not sure I understand the "actual cargo routing" correctly. If I do, it would simply mean to follow the calculated route stored in the cargopacket to the destination.
I was thinking of using the link graph thread to offload the pathfinding to the destination to another thread which has access to an abstract representation of the transport network. This would be the calculation of the routing scheme. This approach would require the main thread and the link graph thread to talk to each other much more, but this interaction would mainly consist of two queues for cargopackets, one where the path is to be calculated, one where they are passed back with a path.

Think again. How do you determine "potential destinations"? If you find a good solution for that please go ahead. I've tried and I couldn't.

Potential destinations seemed pretty easy to me. The number of potential destinations is just the number of tiles on the map accepting the cargo. With some caching this can be obtained from a simple table (one entry per cargo type): count them at game start, and update it each time a tile's cargo acceptance changes. The real issue is the number of reachable destination tiles. If that is known, just multiply the generated cargo by reachable divided by total destinations.
I was thinking under the assumption that the linkgraph already exists and can be read when cargo is generated, it would help for the calculations related to reachable destinations.

[TERdON]

This is what Cargodest is not meant to do: it adapts to the player's network.

I agree on the concept that destinations should not be chosen only from the reachable ones, but that does not necessarily imply the above statement. In real life, travel flows tend to follow not shortest manhattan distance, but shortest travel time. One could imagine using some kind of weighting or similar affecting the distribution of the cargo among the destinations (e.g. weighting based on line capacity, travel time, number of changes, ...) even though the actual list of destinations is the same, essentially achieving a bonus for traveling along existing transport links.

This is however likely something that would be good to have tunable, if it is ever implemented.

[Eddi]

the way i'd like the feature to work is like this:

on cargo production, the resulting cargo has the following options:

• x% chance to pick a predetermined location of the industry's "partners" (YACD-Style) to define a minimum network that should be serviced
• y% chance to pick a random location on the map (YACD's 'cargo to other locations') to favour players with larger-than-minimum networks
• z% chance to pick a random connected location on the map (Cargodist-Style) to get you started before the minimum network is fully established.

[3298]

TERdON:
I admit that the statement you quoted was not very precise. For Cargodest, the choice of destinations should be network-independent, the route to that destination is a different story. YACD does take both travel time and distance into account as pathfinder penalties.

This distribution stuff you suggest feels like Cargodist, maybe combined with some sort of cargo reduction depending on the list of reachable destinations (think passengers fed up with public transport, they would take their own car/bike or a taxi because their destination is unreachable; this would also be an explanation for cargo disappearing from very full stations), which is what I was aiming for with my "I would already be kinda happy"-suggestion. That would of course be tunable once we know how to efficiently find out how many destinations are reachable. Some percentage of the passengers who wanted to go to unreachable places is rerouted to reachable ones, so they are not dropped, but passed into Cargodist's distribution mechanism. (We can't reach this doctor? But that one has a station right in front of his door, let's go there instead.)

Eddi: That would indeed make every player happy. Just set the percentage for a mode you don't like to 0. But first things first: make Cargodest work together with Cargodist.

[Hyronymus]

My town window looks totally different to be honest.

OpenTTD r25942? You're definitely not playing YACD. The stuff in your town window is probably from a game script. Some citybuilder-type one, I guess. And those passengers not wanting to travel to the other town... the link graph recalculation does not take 9 months, and the train route should have a non-zero capacity which means some cargo should use it, so there is something weird going on there.

As read on OpenTTD wiki:

As of June 2013, Cargodist is included in trunk

Call me silly but that led me to believe it's an integrated part of OpenTTD by now.

[Eddi]

yes, but this thread is about a different patch implementing a different (but related) thing

[fonso]

The route calculation and the actual routing are independent in that the route calculation takes place in the link graph threads and outputs planned flows through stations such as "of all the cargo from A passing through this station send x% to B, y% to C and z% to D". Those plans are then executed when routing the cargo, without any further calculation. This is what makes the actual routing so cheap, computationally.

If you find a way to predetermine all source-destinations pairs to be served (either in terms of stations/nodes or in terms of industries/towns with an additional mapping of those to stations/nodes) before the link graph calculation, you are mostly done. The demands handler can easily be modified to only assign demands to those predetermined pairs and everything following that is based on demands assigned by the demands handler. My previous suggestion is based on the assumption that predermining all source-destination pairs to be served might be difficult.

[Hyronymus]

yes, but this thread is about a different patch implementing a different (but related) thing

Which shares the same name? Confusing.

[FLHerne]

yes, but this thread is about a different patch implementing a different (but related) thing

Which shares the same name? Confusing.

CargoDist (for distribution, now included in trunk) is quite a different name to YACD (Yet another CargoDestinations, this thread).

Even if you miss the non-obvious vowel difference, the 'Yet Another' suggests both that it's a different thing and that other similar things exist.


Oh, and there was a third, older, patch called simply 'CargoDest', which gets confused sometimes with both of the above. Luckily everyone's forgotten about it now.

[Hyronymus]

yes, but this thread is about a different patch implementing a different (but related) thing

Which shares the same name? Confusing.

CargoDist (for distribution, now included in trunk) is quite a different name to YACD (Yet another CargoDestinations, this thread).

Even if you miss the non-obvious vowel difference, the 'Yet Another' suggests both that it's a different thing and that other similar things exist.


Oh, and there was a third, older, patch called simply 'CargoDest', which gets confused sometimes with both of the above. Luckily everyone's forgotten about it now.

Point taken, I will not bother you lot any longer.

[Eddi]

based on the assumption that predermining all source-destination pairs to be served might be difficult.

just a bunch of ideas:

• all houses and industries (or industry-tiles) get a node for themselves that serves as a source/sink of cargos
• each town gets a node that doesn't create/accept cargos
• each house-industry-node gets connected to its town node
• each pair of town nodes gets connected to each other
• these nodes form a "network" independent of each other (possibly modeling "individual transport")
• each station that is built gets its node connected to all house-industry-nodes in its catchment area
• connections between station nodes like now

[fonso]

based on the assumption that predermining all source-destination pairs to be served might be difficult.

just a bunch of ideas:

• all houses and industries (or industry-tiles) get a node for themselves that serves as a source/sink of cargos
• each town gets a node that doesn't create/accept cargos
• each house-industry-node gets connected to its town node
• each pair of town nodes gets connected to each other
• these nodes form a "network" independent of each other (possibly modeling "individual transport")
• each station that is built gets its node connected to all house-industry-nodes in its catchment area
• connections between station nodes like now

There we are at "count all houses". Try it, if you must. But don't be surprised that repeatedly iterating over all houses or even over all pairs of houses does take time. Mapping all houses and industries as nodes will drastically increase the sizes of link graphs (which is O(n^2) where n is the number of nodes), with potentially nasty consequences.

[Eddi]

well, the point of my idea was that the size of the graph (number of edges) is O(n^2+m) where n is the number of towns and m the number of houses. and "iterating over all houses" can be done in the tileloop (i.e. cycle every 256 ticks, with 1/256th of the map processed during each tick)

[DC-1]

I've updated my patch to show destination of cargoes on airplanes, road vehicles and ships. I think this is the right way to update the height of window.

Ship with passengers

ship-cargo3.png (8.75 KiB) Viewed 4536 times

Helicopter with passengers

air-cargo.png (9.1 KiB) Viewed 4536 times

[TERdON]

Feature request: Similarly to the nice addition just above, it would be nice to see not only to where industries deliver, but which the source is too (so e.g. a factory would list the farms that are delivering to it...)

[Aphid]

In fact, what you'd have to do to get cargo destinations on top of cargodist is the following:

1. Come up with an algorithm that determines destinations and specify what kinds of input it needs.
2. Extend the link graph data structures to provide that input to link graph handlers.
3. Collect the data to be fed to the algorithm at the right places in the main game thread.
3. Add another link graph handler to replace the demand handler or extend the demand handler. That handler has to implement said algorithm and assign demands only to specific destinations instead of all reachable nodes. The handler will be run in the link graph thread. Make sure it only accesses data from the link graph it gets passed. Otherwise you'll get desyncs.
4. Some boilerplate: Change some settings to allow "destinations" mode in addition to "symmetric", "asymmetric" and "manual", save/load stuff and so on.

In contrast to popular belief I think that the most complicated things are actually 1 and 3. How exactly is it supposed to work and how do you get it done without constantly looping over all houses and similar wasteful things?

I'm going to go ahead and try my hand at the problems encountered with implementing numbers (1) and (3). Specifically, the problem of computing the 'connectivity'.

Let us consider one cargo, for example passengers.

Let's first extend our 'link graph' by providing a node for each industry and house on the map for each source or sink of our cargo. Connect any such nodes to station nodes whenever this station has said node in its coverage area to form the 'extended link graph'. E.g. the house nodes are part of the station node, it has a list of which houses, industries, etc. are in its influence area.

The 'extended link graph' contains four kinds of nodes.

Type 1 nodes are sinks
Type 2 nodes are sources
A node can also be both type 1 and 2, denoted type 3 or neither, denoted type 0.

For each node with a type, we also know quite easily the cargo source fraction. In the case of symmetric cargoes, this can be used as an estimator for the weight of a type 1 node.

Our goal is to compute some sort of estimation of the 'connectivity' of a node, where this is defined as the percentage of cargo that is released onto the network. The 'connectivity' of a node is simply a multiplier onto the amount of cargo given, and is capped at 0.0 and 1.0, quite obviously.

So 1.0 < C(x) < 0.0.
Also quite obviously a fully connected node should have a C of 1.0 and an unconnected node should have 0.0.

We want to estimate the connectivity of a node without having to search through the graph for each node. This requires an expensive A* operation.

To that end I propose the following algorithm (pseudocode).

I assume we have a function RP(G, x) that produces a random walk from a given source node which continues walking until it either hits a dead end or a node that it has previously discovered. It takes in the graph walked on and the node to start with.

I also assume there is a function W() that counts the number of outgoing links, and V() that counts the number of incoming links. These counting functions can be weighed by the sink size of the nodes the links point to so that the algorithm will give a bijective strictly increasing (in the probabilistic limit) indication for the size of C. (It will do this anyway even unweighed).

Let G be the link graph, H the inverse link graph, and x a node.
Let S be the summation operation over an index i.

Code: Select all

P = RP(G, x)
foreach(i in P)
{
	b[i] = W(P[i-1]) / V(P[i]);
	c[i] = 0;
	j = 0;
	do
	{
		Q = RP(H, x[i]);
	}
	while(x[0] NOT IN Q);
}
iff there is a node in P <> x[0] then return S[i](b[i] * c[i]);
else return 0;

This algorithm is further detailed in http://download.springer.com/static/pdf ... 2&ext=.pdf


Using the estimator allows us to get a pretty accurate guess without having to traverse every node. And from the size of the link graph we have a good estimation of the connectivity. It has one caveat and that is when dealing with graphs that have nodes that are highly connected. It may end up in an infinite loop. Thus adding a few 'loose nodes' to such a graph allows you to get out of this possibility, albeit distorting the results a bit.

Extra additions to this procedure can weigh the results further, for example by manhattan distance to the originating node or by the size of the sink in question (important for passengers, the size of the sink should be the population count of the building).

We can then fill in the size estimations for every other node by repeating the algorithm and by reusing results from adjacent nodes that have already been computed in a smart way, for example by first filling in any nodes that connect to soley the node in question with the same result, plus the value of the originating node itself iff their connection is one-way.

Subsequently, keep doing the node that requires the least number of algorithm calls to know an estimation of its connectivity value, using values from connected nodes as reference.


However, the question rises, do we really need the estimator? Can we not simply compute the size?

First off, let's get some upper limits for the link graph. Provided that we 'integrate' the induvidual houses into the connected station(s)' links 15,000 is quite a reasonable estimation for the maximum size of a link graph (5,000 trains with 6 stations each, half of which overlap). This would make 60,000 a reasonable estimation for the amount of edges (getting each train its own route). Doing simple DFS on a graph is O(V(V+E)) which is about 900M operations. Note that it's still okay if we can do these operations in about three months, which is around 210s.

A modern processor can reach around 10GOPS/thread, this means there are about 2,300 instructions available for the inner algorithm. Furthermore, the algorithm is potentially multi-threadable as well because the computation for each node is independent. Do it 'for each cargo' and you are left with about 70 instructions on a dual-core system (we can use one core here), or 210 on a quad-core system. Thus it's actually fairly feasible to keep re-compute time under three months on a modern system.

Storage space is not very relevant, because we're not interested in 'which' nodes in particular are connected, but rather either which of the predetermined destinations is connected (industry cargoes), or the weighted amount of connectivity by manhattan distance (passengers, mail, bank valuables, ...)

EDIT;

There's more methods of doing this. Instead of making it mathematically complicated, you could also use some assumptions to make the amount of calculations required minimal in our particular case scenario.

We create the 'walker' network. Each cargo packet is always generated instead of being generated only when there are player station(s) nearby. The 'walker' network is a network that connects each tile to its four neighbours. On a NxN map it thus has N^2 vertices and 4*N*(N-1) directed edges. It has a fixed (slow) speed attached to it, say 8 km/h. All of the links have infinite capacity but low desirability. Initially, all cargo is being sent over this walker network to specific destinations. Any destination can always be reached by a route that is O(1) to calculate so the complexity of this network is quite low. <-- RT3 uses this method.

Because the structure of the 'walker network' is known, there is really no need to create many objects for it. Any cargoPacket can simply have a sort of 'limbo' state to indicate it is on this network, together with two coordinates for its position.

Cargo will only travel over a player's network when it realizes it can 'cut off' part of its walker journey. E.g. when a packet can travel from S-(w)->A-(bus)->B-(w)->E it will take the bus for that leg instead (or whatever other construction is in place). The bus station effectively connects to the link in the 'walker network' where it is situated (where the station's sign is). Cargo on player's networks doesn't come directly from industries, it comes from the 'walker network'.

In order to 'reintroduce' station acceptance areas we need only 'limit the amount of vertical and horizontal links' the cargo may travel on the walker network when going via a player network.

[zooks]

First off, let's get some upper limits for the link graph. Provided that we 'integrate' the induvidual houses into the connected station(s)' links 15,000 is quite a reasonable estimation for the maximum size of a link graph (5,000 trains with 6 stations each, half of which overlap). This would make 60,000 a reasonable estimation for the amount of edges (getting each train its own route). Doing simple DFS on a graph is O(V(V+E)) which is about 900M operations. Note that it's still okay if we can do these operations in about three months, which is around 210s.

I'm not sure about this estimate of the upper limit. I propose to maybe look at a large sample of openttdcoop games and possibly let people provide complex games to get a grasp on the worst-case.

Other than that, great work on trying to push this forward!

[TERdON]

On the other hand, the estimate should be pulled down (possibly a lot) by many vehicles having shared orders. In case of large maps with big flows I even expect this to be even more common...