Transport Tycoon Forums

IMPORTANT DISCLAIMER: This is my personal project and I'm not speaking in my capacity as somebody with commit access here. Me posting this patch here does not imply any decision regarding if, when and which cargo destinations implementation might get merged to OpenTTD trunk. Other patches have the same chance as this patch to get included.

Hello all,
welcome to this thread announcing YACD - Yet Another CargoDestinations to the world. This patch brings cargo destinations into OpenTTD by creating specific demand between towns and industries. This means that you'll have to shape your network according to where the cargo wants to go, because if you don't, your trains will just run empty! This is significantly different from Cargodist, which will route the cargo along your existing network and not to a specific fixed destination.

How to play:
Start by enabling cargo destinations for either pax/mail, industry cargoes or all cargoes in the advanced settings, section Economy. Begin a new game (you can load an existing save, but completely reorganizing a network before you go into bankruptcy is hard work).

Let the game run for one or two months, this is needed to properly collect some internal statistics. Then click on any town or industry to see where the cargo wants to go to and build your network accordingly Please note that the cargo to/from towns is actually routed to a specific tile of the destination town, which is randomly determined. The tiles near the town's centre will be chosen more often than those further away, so start there. In order to capture all possible cargo from town A to town B (or from an industry to a town), you'll have to cover both towns completely.

The GUI integration isn't complete yet, but the station view will show you the waiting cargo sorted by either final destination, next hop (i.e. the next stop of the vehicle the cargo wants to board), transfer station (station where the cargo will exit the vehicle again, final delivery counts as transfer for this) or source (unchanged). The total cargo tab of the train detail window will show the final destinations of all cargo aboard.

Highlights:

• A new challenge
• Predetermined tile-to-tile cargo destinations
• Dynamic cargo routing which will spread out cargo over multiple connections
• Automatic transfer handling at stations
• Will not break totally when using conditional orders or other indeterministic constructs
• Highly configurable, but hopefully with sane defaults

Some missing features:

• Better performance (a full 2k by 2k map will be very heavy on your CPU)
• NoAI support
• Better NewGRF interaction, e.g. for stockpile limits

Technical information:
YACD will be released in form of a git-style patch, which any sane (this does not include TortoiseSVN) patch tool will be able to apply (use -p1 for the standard GNU patch). The version numbering will consist of a major and a minor version. The minor version will increment on any change and the major version will increment when the patch isn't savegame compatible with the previous version. I will not maintain savegame compatibility over trunk savegame changes.

Compiled binaries are available at http://bundles.openttdcoop.org/yacd/ (with thanks to the openttdcoop guys).

The latest patch version will always be attached to this post. Older version will be available from the archive. Alternatively you can pull from my git repo. This repo will occasionally be rebased, so please read the instructions.


I hope this different way of playing OpenTTD will be fun, but that is something only you can decide. Please let me know your thoughts.

-- Michael Lutz

Nice!

I will try to test this soon

Lets be honest, you being a dev means that coding style etc is more likely to be correct, and just generally looking better

_________________
AroAI - A really feeble attempt at an AI

• Unix *is* user-friendly. It is not ignorant-friendly and idiot-friendly.
• Duct tape is like the force. It has a light side, a dark side, and it holds the universe together... -- Carl Zwanzig
• I am always doing that which I cannot do, in order that I may learn how to do it. -- Pablo Picasso
• Time LINE...? Ehh, time isn't made out of LINES. It is made out of circles. That is why clocks are round! -- Caboose, RvB

Congratiulations, this looks quite nice.

So, the actually interesting new thing about this patch seems to be that you're using "geographic" destinations and utilizing the pathfinder to check for the best next links.

Cargodist on the other hand doesn't care about geography and builds an abstract link graph. That might have been a mistake, I don't know. The reason was that I didn't want to care about speeds, travel times, number of vehicles on a route and such things as in fact the only relevant thing is the capacity of a link. What I didn't know is that capacity is so hard to measure ...

Another thing I'd like to know is how you get the load balancing into that setup. I never quite understood the inner workings of Yapf and I guess that's where I have to look. Maybe you can shed some light on this.


Actually I cleaned up all the cargodist code using Rubidiums suggestions a few months ago. So I guess the difference won't be too big. However, I'm not going to actively compete here. If I feel that YACD is on its way to trunk I'll abandon cargodist. Maybe we can exchange some ideas, though and find the best solution together.

_________________
The guy on the picture is not me, it's Alonso.

Hmm. My previous comment didn't come across as i intended... Nevermend...

I like the working together thing though

_________________
AroAI - A really feeble attempt at an AI

• Unix *is* user-friendly. It is not ignorant-friendly and idiot-friendly.
• Duct tape is like the force. It has a light side, a dark side, and it holds the universe together... -- Carl Zwanzig
• I am always doing that which I cannot do, in order that I may learn how to do it. -- Pablo Picasso
• Time LINE...? Ehh, time isn't made out of LINES. It is made out of circles. That is why clocks are round! -- Caboose, RvB

I actually like this fact about Cargodist, so hopefully you don't abandon it.

_________________
Screenshots :: Isle of Sodor

You can obey coding style and proper commit splitting without having commit access just as good; it's just that many people think that's something for later and don't realize how much work they save by caring from the start on. My personal advice for everybody who wants to code a (bigger) patch with the intention of getting it into trunk: Starting coding in trunk quality from the very first line on, otherwise you'll never achieve your goal or at least do all the work twice.


YAPF itself is completely deterministic and will only ever return the best path. The key to get load balancing into the equation is to have some pathfinder penalties that vary over time. In YACD, the two most important penalties for load balancing are a penalty on the time since the last vehicle serviced a link and a penalty on the cargo amount waiting on that link.

As an example, take a situation where two stations A and B are connected by the links 1 and 2. Link 1 is the "better" link, i.e. faster, less transfers and cheaper transport mode (cheapness: ship < bus < train < aircraft). Now let's have some cargo heading to B arrive at A. Link 1 is the better link, so cargo will initially wait on link 1. As more cargo arrives, the penalty for waiting cargo on link 1 will increase until a point where link 2 is now better. The next arriving cargo will now wait on link 2. This increases the penalty on link 2 as well, so the next cargo will go back to link 1. Repeat. In short, the better link gets more cargo, but as the waiting cargo amount increases, the cargo will "spread out" to more and more links with a higher base penalty.

A second point to create some dynamics is the last vehicle time penalty. This penalty is increased for each day where no vehicle starts travelling a link and is reset to zero each time a vehicle stops at the start station (A in this example). At the same time, the desired link will be recalculated for a part of the waiting cargo packets. This means that when a vehicle for link 2 arrives at A, the penalty of link 2 will decrease a bit and those packets that are recalculated will likely switch from link 1 to 2. Those two effects make sure that several not too different links will all get a share of the total cargo.

-- Michael Lutz

I am thrilled that there is continued effort to get some sort of cargo destinations into OpenTTD. I do hope that you can somehow draw something useful from fonso's work so his work will not have been vain, if your patch happens to be the one to go to trunk some day.


I have yet to try your patch, but what you wrote sounds quite good to me.
Generally I like the concept that destinations are predetermined and you can look them up and then have to try to satisfy them.
What happens though with pax/cargo with an unconnected target? Are they not generated in the first place? This would likely make early game quite difficult because only a fraction of the passengers of without-YACD would be spawned until you have a reasonable network.
This behavior simulates the person/cargo thinking "no public transport to there? Okay, then I'll go by car" OR "Okay, then I won't go anywhere". Maybe this assumption should not be followed in 100% of the cases. IMO pax should sometimes (maybe higher chance the further away the target[1]), and cargo should always[2] think instead "Not possible to go there? Okay, then I'll go somewhere else". (If your answer to this is "then deactivate YACD for cargo", it's not the same because you still have to provide the right balance for the connected targets, much like CargoDist.)

i.e. a mixture of predetermined and influenced-by-connectivity targets.


[1] Reasoning: People seldom (exception being businesspeople) NEED to get to a specific far away location and may settle for other locations if one is not reachable / very hard to reach (think vacation) and OTOH more likely to travel to well connected locations.
[2] Reasoning: Producing industry owners want to sell their goods; they would rather send it to a different target than they originally planned to, rather than letting it rot in their storage.


The GUI should still display where the cargo actually *wants* to go, so you can extend your network according to these needs.
Random thought: cargo not going to their wanted target could have reduced fare to form an incentive to actually create the needed connections.

_________________
* @Belugas wonders what is worst... a mom or a wife...
<Lakie> Well, they do the same thing but the code is different.
______________
My patches
check my wiki page (sticky button) for a complete list

My disclaimer in the first post is of course not totally true. Me posting this patch here does imply that the decision on if, when and which cargodest implementation will get merged is still open. It's still entirely possible for cargodist to get chosen. I'm not posting this patch as some kind of "competition" with cargodist either. I've simply been exploring a different way of realizing cargo destinations. The players have to decide what they like more.

My patch is mainly about the creation of cargo packets with fixed, tile-based destinations. This is also the part of the patch where most of the brain work went into. The usage of YAPF to route the cargo to the destination is solely based on the fact that this was the least work for me, not that it is the best solution. So if the cargo routing algorithm of cargodist can work with predetermined destinations, it's certainly worth a try to see whether it works better than what I have now.



Yes, if cargo can't reach the intended destination, it will not be generated. This models a world where you compete with other, implicit transport opportunities. There's also a limit on the cost of the path from A to B, this means that cargo from A to a B that is near A will not consider a route going around the whole map.

This does not make early games unduly difficult though. If there's demand from A to B, you don't need to provide anything more than a direct connection from A to B to get the cargo. No network needed. Additionally, each town will also have some local pax/mail demand, which is easy to capture with a bus and a few stops. The key to success is deciding on the right A and B. This requires more thinking that just transporting coal over the biggest possible distance, but IMHO more thinking == better game.


Maybe you should actually play it first The GUI does display where the cargo wants to go, the detail windows of each town/industry shows the amount to each destination. The station view shows the destination/next hop of the waiting cargo, so you can see which of your routes need upgrading.

-- Michael Lutz

one of the features of CargoDist is that you can influence whether more cargo is generated for local destinations or for far away destinations. tuning this towards local is possibly helping the early game.

PS: i have difficulties pronouncing "YACD", may i suggest "YACDest" as name?

_________________
You might not exactly be interested in Ferion, but if you are, have fun

The amount of local cargo isn't fixed but based on the population of the destination towns. The algorithm tries to scale the total outgoing cargo in such a way that small towns won't be supplied with a multitude of the pax they generate themselves. As towns at the beginning are generally small, the initial local percentage will often be near the allowed maximum. When the towns grow, the local percentage will decrease.

In general, the situation at the start of a game with default settings will be some like this: Some big cities with a high local percentage, as most destinations will be smaller towns. The smaller towns near a city will likely have the city as one of their destinations where most of their demand will go to. Local percentage is very low here. Things get bit less predictable when several cities or towns cluster.


The official name will stay YACD, but you may pronounce it any way you like

-- Michael Lutz

Eddi: strangely I find it no harder to pronounce this than xkcd. (actually it's easier, "yay-ceedee" (which also carries our enthusiasm about the effort to implement cargo destinations into OpenTTD ) or "yassidy", compared to "ex-kay-ceedee")



Uh, I figured that that's what is being displayed in your current implementation.
What I meant to say was if you implemented what I was suggesting (pax sometimes; cargo always choosing another destination if their desired destination is not connected), you should still (i.e. as it is now in your patch) display in the detail window of the town/industry the actually desired destination.
I will follow your suggestion to actually play it though as soon as I find some time


I can live with this model quite fine for passengers (by foot, personal car)[1], but not so much for cargo (cargo just doesn't move itself unlike to passengers). Cargo has to be transported by someone, somehow. And this can and imo should be done only by explicit (human or AI controlled) companies, not invisible implicit ones.
This way players who want to can live in a kind of sandboxy world where they are the only choice for industries to get their cargo transported (by playing solo and without AIs). Others that want a (more realistic (drat, now I said the word)) world with competition, can play with other (AI or human controlled) companies.
If you implement (only) the model with implicit transport opportunities, you would imo force-couple the cargo destination feature with (implicit) competition, which some players may not want?

summa summarum,
I think there is justification for (configuration switches for) another model that limits/removes these implicit transport opportunities for pax/cargo.

With the current model, from what I've read, I would activate it only for passengers, not for cargo.


[1] In fact I love it! It spawned the idea in my head that (in another patch) based on these numbers actual personal car traffic could be generated between the source and destination, given there is a road connection. Now that would be sexy

_________________
* @Belugas wonders what is worst... a mom or a wife...
<Lakie> Well, they do the same thing but the code is different.
______________
My patches
check my wiki page (sticky button) for a complete list

There's also a different world interpretation if you don't like the word competition You are a transport business and a customer wants you to transport cargo from A to B. Either you can do that and you get the job, or you can't and you don't get the job.

Humour aside, the basic premise and algorithm of YACD is the generation of cargo with predetermined, fixed destinations. Exaggerated, everything else (cargo routing, GUI etc.) is just there to get something playable. I can certainly understand if somebody doesn't want those fixed destinations, but we have cargodist for that already. Some kind of YACD and cargodits hybrid could possibly offer both, but please keep in mind that this would make two big patches even bigger, which is never a good sign.

-- Michael Lutz

Of course I would love any of the two (or any other implementation) of cargo destinations in OpenTTD. I'm just afraid that once one of them makes it into trunk, the model it offers will be considered set in stone. I would love to be ultimately able to choose between classic (no set destinations), YACD style (destinations fixed w/o considering connectivity) and CargoDist style (destinations fixed according to connectivity) for each of pax/cargo. But that's just my dreaming.

I understand your concerns about patch size/complexity though, and will stop pestering you now

At least until I've actually played it and am maybe able to post more informed posts..

_________________
* @Belugas wonders what is worst... a mom or a wife...
<Lakie> Well, they do the same thing but the code is different.
______________
My patches
check my wiki page (sticky button) for a complete list

I haven't tried YACD yet (playing a FIRS test game at the moment), but I will soon.

On a tangent - Railroad Tycoon 3 had an interesting model of 'implicit shippers'. Cargo would slowly move across the map towards destinations. The assumption was that there were unseen people, packhorses, boats, etc hauling the cargo. It took terrain into account, so cargo would move faster near a river, and hardly at all in mountains.

This was fun and interesting, and it meant that secondary industry would eventually start producing even without a rail connection

_________________
Want to help OTTD development? Here's the official list of bitesize patches needed: http://wiki.openttd.org/Todo_list

FIRS Industry Replacement Set (Released)
HEQS Heavy Equipment Set (trucks, industrial trams and more) (Finished)
FISH is Ships (Released)
CHIPS Has Improved Players' Stations (Finished)

I see. This is much simpler than my algorithm and better integrated with the rest of the game. There are drawbacks, though. As you don't have a concept of capacity of the whole route something like the situation shown in the attached save can happen. It is probably possible to fix this by considering the waiting cargo on the whole route, but with long routes and a lot of branches this would be quite heavy on the CPU, I guess. Or maybe not. Somehow you can efficiently find the routes after all. In cargodist I do those calculations in separate threads and periodically merge the results back into the main game.

Edit: In fact I might be wrong. The other route does get used more when more cargo is waiting at Montpellier Woods. The situation stabilizes at about 400 pieces of livestock waiting there. Nice ...

_________________
The guy on the picture is not me, it's Alonso.

I wouldn't really say this is a fail, it just some edge case where slightly different pathfinder penalties result in a better flow. The waiting cargo is considered at each transfer (i.e. where cargo leaves a vehicle), it's just that pf.yapf.route_station_waiting_factor could be a bit higher in this case. Alternatively or additional pf.yapf.route_transfer_cost could be decreased a bit.

In general, the pathfinder penalties will certainly still need some tuning, so please report if you find some situation that could be handled better.

-- Michael Lutz

It seems your routing algorithm is clearly superior to cargodist's: No delays, no capacity calculations, better integrated with the rest of the game and it's even faster. Now, what I'm thinking about is implementing an optional "distribution mode" on top of YACD. Instead of fixing the destinations by searching the map it would assemble all reachable sinks for each connected source and distribute the demands among those. Then we'd have the same behaviour as with cargodist. It should be possible to utilize the pathfinder to search for those sinks. After all the routing information is already there. What do you think? Is that feasible?

_________________
The guy on the picture is not me, it's Alonso.

Differently determining a fixed destination of a cargo packet is possible without much pain, it's all going through one central function. If you also want to dynamically reroute the destinations it gets a bit more complicated as you'd need to hook into the load/unload handling at the proper points. It might also create stability problems in the pathfinder, because when destinations change the waiting cargo penalty changes, which might introduce oscillations into cargo routing.

-- Michael Lutz

I was thinking about changing UpdateCargoLinks so that it just creates reachable destinations (and finds all of them). As it's not called that often and the routes themselves don't change that often either it can't oscillate too badly.

Some other things I noticed:

1. It's most likely not enough to do PrefillRouteLinks when the game is started or orders change. After all they time out after a while and the vehicle might still be doing a "full load" that depends on the route being available.

2. You can in fact prefill conditional orders and even refit orders. I've managed to do so in cargodist and it works OK. Refits are easy: You just virtually remove the refitted wagons from the consist. Conditionals are sort of tricky. I resorted to just evaluating them based on the current state of the vehicle. For "always" and "speed" that's correct in any case, for "age" and "needs service" it's still likely to be the same when the vehicle visits the link. For "load percentage" it's impossible to say. Here I've implemented a special function that just chooses the next hop most cargo is waiting for if the vehicle is just loading and the next order is dependent on load percentage. Like that it always loads something and that's probably what people want to achieve with such a setup.

3. There's that nasty new order which makes vehicles stop but prevents them from loading - you can set both "no loading" and "no unloading" now. In terms of YACD or cargodist this is like a waypoint.

Do you intend to provide a graphical route map as overlay on the smallmap or the main viewport? Maybe it's not that necessary for YACD as you can always get all information from the town/industry and station windows.

_________________
The guy on the picture is not me, it's Alonso.

Ideally, links expiry wouldn't be necessary, but as long as indeterministic networks are possible, it's a necessary thing. The order prefill in YACD can certainly be improved, right now I just implemented a simple version to avoid the wait until the vehicle has completed the whole order list.


"no loading" and "no unloading" is handled in the pathfinder stage, i.e. only valid connections from one link to the next are considered based on the incoming and outgoing order. (Which also means that no links need to be updated when the (un)loading state of an order changes.)


It might not be necessary, but I like such a graph, so yes, it's intended to provide one. (Obviously proper function is more important than some GUI eye candy though.) I was thinking more about a simple graph like the original cargodest and not necessarily like cargodist with all the capacity information.

-- Michael Lutz