YACD - Yet Another CargoDestinations (v2.3 released)

[Arie-]

I doubt it, however there are some problems with all attempts for cargodestinations in one way or another. For example the increase in CPU requirements, as long as there are no feasible solutions to these problems attempts like these are not likely to hit trunk.

[Wasila]

I was fairly sure that a cleaned up version of CargoDist would make it into trunk... increased CPU requirements shouldn't be an issue as long as the feature is toggeable.

[fonso]

If I had the patience to bug the developers about trunk inclusion and what they think about it chances for cargodist to get accepted would probably be higher. At some point, and especially when michi_cc suddenly showed up with a different implementation after two years of me running in circles, I got severely tired of that. I'll happily explain any technical details, change things in the code, implement something like "more intelligent thread scheduling" or similar things if they actually lead to some result.

It would also help if someone set up a public testing server to identify and publish any problems there might be with multiplayer support of cargodist. Lack of testing was one of the points I heard quite often. I guess cargodist is actually quite well tested and bug reports got fewer and fewer in those last months. However, there is no way to show that to the devs and I'm also tired of setting up and recruiting people for public test games. I'll happily join any game set up by someone else and debug any problems arising there, though. I'm mostly free on evenings and weekends for things like this but better ask me if you want me to join.

[Zmapper]

I can host a YACD 2.3 server, and will likely have one up tonight. (12/26) Look for "Zmapper YACD".

EDIT: Scratch what I said earlier about not finding a zip file. They are on the first post of this thread.

Because the server is on my laptop, it will likely be turned off at midnight or so MST. When I wake up, the server will be back up and running again. Hope to see you playing!

[viki2]

Is there any patch against r23640 or nearby out their?

If not, I'll try to merge it and post the patch on succeed.

[viki2]

If not, I'll try to merge it and post the patch on succeed.

Ok, I tryed and it doesen't work

If someone else wants to use the things I already done, see the attachment... Some things I have already merged and correktet by hand but there are also some left.

[kopjekoffie]

I tried the patch from viki2 against 1.2.0 RC2: see the openttd-patch.txt for the results

But my build server in virtualbox sucks, sow i need to install it again.

[FooBar]

I tried the patch from viki2 against 1.2.0 RC2: see the openttd-patch.txt for the results

Why would you even try that? It's stated that it's a) buggy, and b) for r23640.

[kopjekoffie]

Of course I have made manual adjustments, but i try to make this patch up to date against trunk/stable. I don't know if it is buggy, because i don't have any build platform yet.

[FooBar]

If you want to update this to something current, you can better start with a working patch as base than something the creator labeled as 'buggy'. In this case that would be the original YACD 2.3 patch.

[JazzyJaffa]

I was interested in this style of play and looking at the performance issues with this patch so I rebased michi_cc's changes to bring the patch up to date.
(I got lazy and added one commit for the save version number but will go back and put that change in the older commits at some point)

http://github.com/benjeffery/openttd/tree/yacd

This means you can get a patch at http://github.com/benjeffery/openttd/co ... .yacd.diff or just compile the checkout.

(PS I've removed the subsidy part of the patch for now - it needs more fixing!)

[aantono]

What's the current development status of YACD? The 2.3 version has been released a year ago and no changes since. (At least not according to http://bundles.openttdcoop.org/yacd/) Has the development stopped?

[Alberth]

Yes, no new posts == no things worth mentioning have been done and no new thoughts have been thought.
That holds for every topic in this and many other forums.

[Zephyris]

So as I understand it the performance issue lies in cargo generation, specifically pathfinding to see if the selected target can be reached (*):

1. Tile makes cargo.
2. Destination tile for the cargo is randomly selected.
3. Use pathfinder to see if a route exists from a station near the tile to the target.*
4. If there is, move the cargo to the station. Otherwise don't.

This is based on this irc log: http://thegrebs.com/irc/openttd/2011/12/30
And my limited understanding of the first commits in the yacd git: http://www.icosahedron.de/openttd/git/y ... godest.cpp

Here are two (naive) ideas. You never know, maybe my childlike naivity will help!

1. Schrödinger's Package [pun intended]
Some tiles, eg. houses, make small packets of cargo often. Every time they make cargo yapf is called, and this is the performance cost. Instead of determining whether the cargo destination can be reached on production move it to the nearest station anyway. Only calculate whether the destination is reachable, i.e. call yapf, when a vehicle comes to try and collect it; if it is then load it up, otherwise delete it. Assuming cargo packet production is more frequent than vehicle visits this should give a performance increase. GUI might be an issue though; cargo for unreachable destinations would appear.

2. Don't generate cargo destinations that randomly
There must be a huge amount of futile calls to yapf as (especially early in the game) the vast majority of destinations must be unreachable. You list "Predetermined tile-to-tile cargo destinations" as a key feature of this cargo destination implementation but this seems to be what is killing the performance. Would it be much worse if the generation of cargo was limited to destinations known to be near stations?

I would also be interested in knowing what your arguments against:
* Abstract cargo pathfinding (e.g. using the stations as a network of nodes) rather than yapf. I would expect this could boost the speed of cargo destination, especially if you were happy with only selecting destination tiles near stations.
* Caching whether a destination is available for a tile. It wasn't clear to me how often the destination for a tile changes (every cargo packet? never? something else?). If it changes relatively infrequently then surely caching would provide a massive performance boost?

It would be great if you could answer any of these questions; cargo destinations is one of my dream OpenTTD features and I would love to help if possible.

[Michi_cc]

First of all, some definitions: Let's call the process of finding a way for cargo to reach its destination routefinding, to distinguish it from the pathfinding of vehicles. Also, YAPF should be read as Yet Another Pathfinder Framework, as it is by no means restricted to only operate on tiles.

YACD maintains a list of possible destinations for each source (towns and industries). When cargo is generated, it will be randomly assigned a destination out of this list. If the destination is a town, a destination tile is further selected by a weighted random function.

The so built cargo packet is passed to a YAPF specialization operating on the route network formed be the orders of the vehicles in the game to find which station, if at all, the packet should start its life at. First it checks if the target is covered by a station at all, if not, we are already finished and drop the packet. After that, the the order network is walked to find the best destination station using various variable penalties. The result of that is the target station plus the vehicle (well, order) to board next and where to leave that vehicle. The calculations are repeated upon leaving the vehicle and periodically while waiting in a station.

This is the basic routefinding. It can be quite costly, especially if the order network is poorly connected or even disjoint, as this can easily cause walking the whole network. The nearer the packet is to the destination, the less expensive it gets, as we walk a smaller part of the network. Thus the biggest hit is the very first routefinding where the packet isn't even fixed to a company is most expensive.

1. Schrödinger's Package [pun intended]

You're still doing the calculation no matter what, unless the cargo packets would be merged. To guarantee fair cargo distribution, no source has a single fixed destination which makes packet merging unlikely.

Would it be much worse if the generation of cargo was limited to destinations known to be near stations?

It would, as the whole point of YACD in contrast to e.g. cargodist is to provide goals and challenges and not a very fancy automatic transfer order replacement (sorry fonso). It is quite moot anyway, as a cache of station coverage is easily kept and used to early out of the routefinding. It's still not very effective, as performance only really suffers in a well developed and played game (lots of houses), where most of the map is likely already covered.

The answers to your last two questions are already somewhere in the lengthy sermon above

[fonso]

It would, as the whole point of YACD in contrast to e.g. cargodist is to provide goals and challenges and not a very fancy automatic transfer order replacement (sorry fonso).

Why sorry? "fancy automatic transfer orders" are exactly what I want with cargodist. This has the side effect of providing some challenge as cargo moves by its own agenda and not by yours, but the main problem I'm solving is making it possible that cargo is transported bidirectionally over a multihop network composed of different vehicles' orders without requiring excessive micro-management of those orders.

[Michi_cc]

Because it doesn't sound very glamorous But it was mostly meant as a tongue-in-cheek comment anyway.

[Dwachs]

@michi_cc

The routefinding uses A* algorithm, with heuristic based on Manhattan distance to target. Is this heuristics admissible? Ie does it always provide a lower bound to the true distance? Is there a reason, why you choose this heuristics? Did you perform any test with other heuristics? No critics, I am just curious

In simutrans, we use plain breadth-first search. This has the following advantage: if a lot of cargo packets of the same type (thus sharing the same network)
want to perform route-finding from the same destination, then the search tree can be reused in consecutive calls to the routefinder. Such a situation occurs when a vehicle arrives at a station and all the unloaded cargo has to do routefinding in order to calculate its next transfer stop.

Ofc, this cannot be used during cargo generation, but it helped to improve performance to some extent.

[Zephyris]

Ofc, this cannot be used during cargo generation, but it helped to improve performance to some extent.

If this were a viable way to improve performance then by calculating cargo destination accessibility in bulk once it is at the station (i.e. Schrödinger's) then it would presumably experience the same benefit.

[Expresso]

1. Schrödinger's Package [pun intended]

You're still doing the calculation no matter what, unless the cargo packets would be merged. To guarantee fair cargo distribution, no source has a single fixed destination which makes packet merging unlikely.

But perhaps it's possible to group (not merge) cargo packets which are at the same location and need to go to the same destination station? That could reduce the amount of computations, because now you need to calculate destinations only once for multiple cargopackets.

In order to catch situations where something might change, destination stations could keep track of which cargo groups/packets want to go to it. If something happens to the destination station (removal, catchment area change), the station could inform the cargo packets of a change to make sure the destinations of the individual cargo packets are recalculated.

This imho reduces computations and thus allows for larger games.