YACD - Yet Another CargoDestinations (v2.3 released)
Moderator: OpenTTD Developers
Re: YACD - Yet Another CargoDestinations (v2.3 released)
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.
Re: YACD - Yet Another CargoDestinations (v2.3 released)
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.
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.
Re: YACD - Yet Another CargoDestinations (v2.3 released)
I cannot open this url, some error message appears. Can you please post the DOI or the title/authors of this reference?Aphid wrote: This algorithm is further detailed in http://download.springer.com/static/pdf ... 2&ext=.pdf
Re: YACD - Yet Another CargoDestinations (v2.3 released)
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.
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.
Re: YACD - Yet Another CargoDestinations (v2.3 released)
Just started using a patchpack with YACD and I have a quick question - what is the definition of 'local destinations'? Within the town, or...?
Re: YACD - Yet Another CargoDestinations (v2.3 released)
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).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...?
-- Michael Lutz
Re: YACD - Yet Another CargoDestinations (v2.3 released)
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.
Re: YACD - Yet Another CargoDestinations (v2.3 released)
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!
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!
- LaPingvino
- Engineer
- Posts: 31
- Joined: 13 Dec 2006 15:36
- Skype: lapingvino
- Location: Portela, Loures, Portugal
- Contact:
Re: YACD - Yet Another CargoDestinations (v2.3 released)
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 .
Playing my own translation .
Re: YACD - Yet Another CargoDestinations (v2.3 released)
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.
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.
Re: YACD - Yet Another CargoDestinations (v2.3 released)
That seems a bit dark : lLet it die in peace.
Re: YACD - Yet Another CargoDestinations (v2.3 released)
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.
Do you like drones, quadcopters & flying toys? Check out Drone Strike Force!
Base Music Sets: OpenMSX | Scott Joplin Anthology | Traditional Winter Holiday Music | Modern Motion Music
Other Projects: 2CC Trams | Modern Waypoints | Sprite Sandbox & NewGRF Releases | Ideabox | Town Names | Isle of Sodor Scenario | Random Sprite Repository
Misc Topics: My Screenshots | Forgotten NewGRFs | Unfinished Graphics Sets | Stats Shack | GarryG's Auz Sets
Base Music Sets: OpenMSX | Scott Joplin Anthology | Traditional Winter Holiday Music | Modern Motion Music
Other Projects: 2CC Trams | Modern Waypoints | Sprite Sandbox & NewGRF Releases | Ideabox | Town Names | Isle of Sodor Scenario | Random Sprite Repository
Misc Topics: My Screenshots | Forgotten NewGRFs | Unfinished Graphics Sets | Stats Shack | GarryG's Auz Sets
Re: YACD - Yet Another CargoDestinations (v2.3 released)
Common usage in the world of technology. Letting a project die is just a way of saying it's been discontinued.Damrus wrote:That seems a bit dark : lLet it die in peace.
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...
Dave's Screenshot Thread! - Albion: A fictional Britain
Flickr
Why be a song when you can be a symphony? r is a...
Re: YACD - Yet Another CargoDestinations (v2.3 released)
Indeed, it was an experiment, and we learned a lot from it.Dave wrote:Common usage in the world of technology. Letting a project die is just a way of saying it's been discontinued.Damrus wrote:That seems a bit dark : lLet it die in peace.
Don't worry, it's not meant darkly.
- 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).
Who is online
Users browsing this forum: No registered users and 4 guests