YACD - Yet Another CargoDestinations (v2.3 released)

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

User avatar
fonso
President
President
Posts: 945
Joined: 13 Oct 2007 08:28

Re: YACD - Yet Another CargoDestinations (v2.3 released)

Post by fonso »

Just a quick reply before I read all the stuff: You may want to look at my preliminary work on extracting some relevant parts of YACD and rebasing them onto current trunk. See branches "yacdmess1" and "yacdmess2" in my repository at https://github.com/ulfhermann/openttd (it's not as messy as it sounds).
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: YACD - Yet Another CargoDestinations (v2.3 released)

Post by fonso »

The idea is pretty complicated and probably involves a lot of work in implementing the various algorithms and integrating the result into the game. It may work but it looks like it's going to take a long time to get that really waterproof.

My idea is more along the lines of taking the "demand links" part from yacd up to the place where it's mapped into stations, and then simply stuffing the demands into the link graph and skipping the demands calculation there (if "destinations" mode is selected). Additionally I'd try to streamline it so that it doesn't refer to single houses as base unit of demand, but to towns instead. The latter should help with performance problems.
The guy on the picture is not me, it's Alonso.
Dwachs
Engineer
Engineer
Posts: 46
Joined: 02 Jun 2005 07:28

Re: YACD - Yet Another CargoDestinations (v2.3 released)

Post by Dwachs »

Aphid wrote: This algorithm is further detailed in http://download.springer.com/static/pdf ... 2&ext=.pdf
I cannot open this url, some error message appears. Can you please post the DOI or the title/authors of this reference?
User avatar
fonso
President
President
Posts: 945
Joined: 13 Oct 2007 08:28

Re: YACD - Yet Another CargoDestinations (v2.3 released)

Post by fonso »

As some of you may have noticed, I've done some work to reimplement a YACD-like behaviour on current trunk. I'm sure it's possible but it's simply not so much fun for me. There was a reason why I did it differently after all. As I'm not going to finish this work I'll explain what I've done so far so that someone else can pick it up where I left. You can find the current state of affairs in the "dest2" branch in my repository.

Destination selection

As michi_cc told me the destination selection is not the performance bottleneck in YACD I decided to keep that in the main thread. It would be hard to do that in a thread anyway. However, instead of storing the destinations by town/industry I store them ordered by cargo in specialized data structures "CargoDestinations" which are fairly compact. This is because in a later step it should be easy to copy the destinations into a link graph job with fairly little overhead. Remember that link graph jobs run in different threads and thus need their private copies of everything they use. I know that std::map is not a particularly compact data structure. Some kind of hash map could be used instead if that gets to be a problem. I've radically simplified michi_cc's implementation of destination selection. All destinations are selected randomly in my implementation and all the settings are gone in favour of constants. This can be changed later. I figured the result is good enough for a first test.

Destinations are simple pairs of CargoSourceSinks. They don't tell the amount of cargo to be delivered. The amounts are to be calculated by the usual distribution algorithm. Link graph jobs would simply run a constrained version of the demand handler which would only assign demands by destinations given in the CargoDestinations object for its cargo.

Creation and usage of destinations data structures

In order for this to work a mapping of Stations to CargoSourceSinks needs to be known. Ignore the crude implementation I'm giving for that - I don't think that would work. In fact we need three mappings per cargo: One mapping from origin stations to producing industries/towns/HQs near them (source_stations), one from consuming industries/towns/HQs to destinations stations near them (sink_stations), and one from producing industries/towns/HQs to consuming ones (destinations). The last one is already given in my code. The "origins" map also given there may actually be unnecessary. Also the num_expected_destinations is unnecessary as it's always recalculated before it's used.
The demands handler will in fact only query one thing: "I have this station that somehow supplies cargo and I want to know which other stations will have a demand for that cargo." Given the above mappings one could look up the producing industries/towns/HQs around the station from source_stations, then look up their destination industries/towns/HQs in destinations, and finally find stations associated with those in sink_stations.
The industry and town GUI will also only query one thing: "I have this cargo source and I need all cargo sinks for it." This can easily be answered by the destinations map.
I'm not aware of any other code needing information about cargo destinations. Now the question that remains is how to construct those mappings and how to keep them up to date. The destinations map is easy. As the code shows there are few places where the towns/industries/HQs actually change and we can directly hook into them and update the destinations. The other two maps are a bit more complicated. We don't want to check all stations' coverage areas for each house built in some town just to figure out if any of them will now accept or be supplied with cargo from that town. We can easily identify the places to hook into in order to keep the association of industries to towns up to date, though. This is just every place where RecomputeIndustriesNear is called. Instead of only updating Station::industries_near there we can additionally update the CargoDestinations. A similar approach should be possible for headquarters. There are only a few places in the code that do anything with those and we can just directly hook into them. For towns I would add a periodic job to stations, such as the one that recomputes station acceptance. It would run a tile loop and check which towns the houses around the station belong to. It's probably enough to run it every 1036 ticks (two game weeks) so, compared with the acceptance tile loop, it shouldn't be too expensive.

Integration into link graph

Once this is all in place the mapping for the a link graph job's cargo can be copied into the link graph job when it's started, the demand handler can query the destinations and limit itself accordingly, and in the end of the link graph run we'd need another handler to check how many destinations have been connected for each source station. It's important to do it in the end as the demand handler may identify demand for stations that aren't actually reachable, e.g. because the vehicles serving them have "no unload" orders. That handler, the "connections" handler, would query every possible destination node (found by above method of querying CargoDestinations) for FlowStats that have any possible origin node as origin and a flow share for local delivery associated with that origin. It would then compare those numbers with the number of destinations given for the source industries/towns/HQs. The resulting ratio would be fed back into the stations' GoodsEntries to determine how much cargo a station would receive. If only few destinations are connected most of the cargo would be discarded. If a lot of them are connected most of the cargo would show up at the station. This is rather crude as there may be multiple industries of the same kind around a station and the proposed mechanism doesn't distinguish between them. All cargo supplied by them would be treated the same. However, to keep things simple I'd still do it like that. If you're so inclined you could as well feed back a detailed list of SourceSinks and their connectedness, though.

Misc

The CargoDestinations objects will have to be loaded and saved of course - the global ones as well as the ones contained in the link graph jobs. For that to work the ones in the link graph jobs will have to be const of course. Then there should be an adequate number of settings to tweak the behavior. Especially the distribution mode settings should be extended to allow selecting "destinations, symmetric" and "destinations, asymmetric" in addition to the current options where appropriate. It would probably be nice to have a separate group "town effect cargoes" (such as goods, water, food) in there as you may want to specify a different behaviour for those. The station GUI should probably show the connectedness and the resulting ratio of discared cargo.
The guy on the picture is not me, it's Alonso.
Wasila
Tycoon
Tycoon
Posts: 1498
Joined: 15 Mar 2008 07:02

Re: YACD - Yet Another CargoDestinations (v2.3 released)

Post by Wasila »

Just started using a patchpack with YACD and I have a quick question - what is the definition of 'local destinations'? Within the town, or...?
Michi_cc
OpenTTD Developer
OpenTTD Developer
Posts: 619
Joined: 14 Jun 2004 23:27
Location: Berlin, Germany
Contact:

Re: YACD - Yet Another CargoDestinations (v2.3 released)

Post by Michi_cc »

Wasila wrote:Just started using a patchpack with YACD and I have a quick question - what is the definition of 'local destinations'? Within the town, or...?
Yes, local is for destinations in the same town (weighted by the distance from the centre tile, i.e. nearer to the centre == more likely).

-- Michael Lutz
mfans
Traffic Manager
Traffic Manager
Posts: 163
Joined: 04 Feb 2009 13:33

Re: YACD - Yet Another CargoDestinations (v2.3 released)

Post by mfans »

I play with r24990M+YACD,and I find some destination of cargo, with a sign "+" in the window, which "+" when you press, sometimes is not showing the details of the destinations, it means I can not see the name of destinations with the sign "-". Is this a bug, or I can have some updated version of YACD to play, I love it.
Damrus
Engineer
Engineer
Posts: 21
Joined: 23 Apr 2014 14:23

Re: YACD - Yet Another CargoDestinations (v2.3 released)

Post by Damrus »

Hey there,

I've been using this patch as part of the "Yet Another Patch Pack based on YACD" and loving it so far. However, I have this problem to which I have only one very unsatisfying solution.

This is my problem: http://i.imgur.com/yrE9a65.png

Every city has major lists of destinations, and if I'm using a game script I can't see the details and I cannot fund new roads or buildings or build a statue in city because.... well its just not visible. I've got a 1900 by 1200 pixel screen so I'd guess that would give me some room to play with.

But other then reducing the amount of towns and hotels I have (72 towns and 20 ish hotels?) is there another way to reduce the amount of destinations a singel town will go for?

Thank you for reading! :]
User avatar
LaPingvino
Engineer
Engineer
Posts: 31
Joined: 13 Dec 2006 15:36
Skype: lapingvino
Location: Portela, Loures, Portugal
Contact:

Re: YACD - Yet Another CargoDestinations (v2.3 released)

Post by LaPingvino »

Now after the release of 1.4.1 with CargoDist in stable and already patched, what are the plans for YACD?
Mi tradukis OpenTTD al Esperanto :)! Ĉu vi bezonas helpon? Mesaĝu min!

Playing my own translation :).
Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4763
Joined: 09 Sep 2007 05:03
Location: home

Re: YACD - Yet Another CargoDestinations (v2.3 released)

Post by Alberth »

Let it die in peace.


In the cargodist thread however, a proposal of adding more yacd-ish functionality was started some time ago, don't know the exact state of it, though.
Damrus
Engineer
Engineer
Posts: 21
Joined: 23 Apr 2014 14:23

Re: YACD - Yet Another CargoDestinations (v2.3 released)

Post by Damrus »

Let it die in peace.
That seems a bit dark : l
User avatar
kamnet
Moderator
Moderator
Posts: 8548
Joined: 28 Sep 2009 17:15
Location: Eastern KY
Contact:

Re: YACD - Yet Another CargoDestinations (v2.3 released)

Post by kamnet »

Considering that YACD's author has stopped supporting it, and nobody is actually developing it, that would be the best course of action to take IMO.
User avatar
Dave
Moderator
Moderator
Posts: 17243
Joined: 26 Dec 2005 20:19
Location: North London

Re: YACD - Yet Another CargoDestinations (v2.3 released)

Post by Dave »

Damrus wrote:
Let it die in peace.
That seems a bit dark : l
Common usage in the world of technology. Letting a project die is just a way of saying it's been discontinued.

Don't worry, it's not meant darkly.
Official TT-Dave Fan Club

Dave's Screenshot Thread! - Albion: A fictional Britain
Flickr


Why be a song when you can be a symphony? r is a...
Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4763
Joined: 09 Sep 2007 05:03
Location: home

Re: YACD - Yet Another CargoDestinations (v2.3 released)

Post by Alberth »

Dave wrote:
Damrus wrote:
Let it die in peace.
That seems a bit dark : l
Common usage in the world of technology. Letting a project die is just a way of saying it's been discontinued.

Don't worry, it's not meant darkly.
Indeed, it was an experiment, and we learned a lot from it.

- This form of routing cargo has a much different game play effect than cargo dist.
- The current implementation is too expensive in CPU time, you'll hit CPU limits too soon (the current game already has this problem)
- There is no easy road to reduce that CPU cost (at least nobody found one so far)

The latter is also the reason why its author abandoned this project. Fundamental changes are probably required, making it easier to discard this code and redo everything. First however, one needs to figure out how to do this kind of cargo routing in a cheap way (as in, costing no or little CPU time).
Post Reply

Return to “OpenTTD Development”

Who is online

Users browsing this forum: No registered users and 17 guests