Transport Tycoon Forums

So, this is the (n+1)th attempt to provide passenger and cargo with destinations and then getting them there using the existing transport links as efficiently as possible. This means it includes what others call "load balancing". I have moved the main description of cargodist into the wiki, see http://wiki.openttd.org/Passenger_and_c ... stribution. Here you'll only get some status information on the progress for the different mile stones.

• DONE Calculate the capacity and usage of a link between two stations as well as the average supply of a good at a station.
  
• DONE Calculate connected components of the link graph.
  
• DONE Define the transport demand between a pair of stations.
  
• DONE Find a good approximation for the resulting multi commodity flow proplem.
  
• DONE Core flow mapping.
  
• DONE Vehicle loading.
  
• DONE Station GUI.
  
• DONE Smallmap zooming. See viewtopic.php?f=33&t=32923
  
• DONE Display link statistics in smallmap.
  
• DONE Optimization of cargo loading (including FS#3135, FS#3266, explicit reservation lists, generic desync-safe multimap and station cargolists sorted by next hop).
  
• LOOKING AS NASTY AS IT SHOULD Warning when starting game with cargodist on and default non-stop off.
  
• REJECTED Scale supply according to available destinations.
  
• DONE Count cargo at all stations to determine rating at source station.

You can also pull from my git tree now. It's at git://github.com/fonsinchen/openttd-cargodist.git and contains hierarchical branches named as follows:

      master
        |
        |\------------\----------\---------------\----------\
        |             |          v               |          |
        |             |    moving-average        |          |
        |             |          v               |          v
        |             |      capacities          |     reservation
        |             |          v               |          |
        |             v      components >>>      |          |
        v          texteff       v               |          |
  smallmap-zoom-in    |   <<< demands            v          |
        |             |          v           multimap       |
        |             |         mcf              |          |
        |             |          v               |          |
        |             |   flowmapping-core       |          |
        |             |          |               |          |
        |             \---------\|/--------------/----------/
        |                        v
        |                    cargomap
        |                        |
        |/----------------------/ \--------------\
        v                                        v
  smallmap-stats       >>> warning-sign    station-gui  supplyscale <<<
        |                        |               |          |
        \-----------------------\|/--------------/----------/
                                 v
                                cd

The branches mostly correspond to the milestones mentioned above. The optimizations of cargo loading are in reservation, multimap and cargomap. cargomap sorts the packets in cargolists so that they can be retrieved more quickly. As the vehicle loading had to be rewritten in large parts to support this, the original "flowmapping-vehload" branch has been dropped and cargomap directly pulls from flowmapping-core now and adds its own vehicle loading. Packets in stations are sorted by next hop in a multimap. Unfortunately multimaps in the standard C++ library don't give any guarantees on the order of elements with equal keys. That's why it was necessary to implement my own multimap which does (branch multimap). texteff creates different profit and transfer indicators if both is present in one loading session. All branches are merged in cd. Master is a clone of the main openttd repository. So if you want the latest version of everything, do the following:

git clone git://github.com/fonsinchen/openttd-cargodist.git
git checkout origin/cd

Of course, with git you can also pull the milestones one by one and examine each step independently. This might be nice if you're reviewing the code.

I have my own patch generation system based on git which produces patches of each commit in a separate branch "patches". In particular you can always download a patch against a recent trunk version here. The trunk version the patch applies to is always recorded here.

When playing with cargodist please use non-stop orders for trains and road vehicles. Orders without the non-stop flag are nonderministic and cargodist won't do what you expect with them. You can make non-stop the default for new orders in the advanced settings.

This sounds very nice, better than the approximate estimation of traffic we have to rely on now.

1) If the station has passengers piling up, it needs more trains
2) If trains are consistantly partially empty, you can remove trains.

It takes so long to check 2) that most routes end up with too many trains, and any shared track ends up with so many trains on it that half the game is spent upgrading it.

Assuming you get this finished, it could be a massive time saver

The timesaving when estimating which routes are over- and underloaded is already feasible. The only problem is that you can't decipher the numbers in the smallmap for short links. If someone comes up with an idea how to solve that and if that's easy to do I'll implement it. For now I'll stick to saving and configuration.

OK, I'll come up with an idea myself: The overall capacity of a link could be represented by the width of a line and the usage ratio by its color. Then you don't need the numbers anymore. I'll try to implement it.

An idea that pops out of my head is to draw the higher level network not only in the minimap but as a overlay in the main viewport. That way there is more space for more details. Though the overview that might be as important is lost then. And would probably require quite some initial coding time to get that started.

updated. See first post.

updated again. See first post. But if no one is interested I will stop updating and only tell you when it's done ...

No no, don't do that! If you keep us aware of how things are coming along, then we're comforted in a small way that you're still working on it. As a Cargodest fan, i'm interested in your work. But like most of us, i'm more interested in its implementation and what it means to gameplay. This is why we want to know how it's going.

Remember, a lot more folks are interested in your work than those who will actually place a comment in this thread.... Our deep-down dream is that you don't give up, especially because you don't think anyone cares about what you're doing!

So, I found a new toy called git. It allows me to easily create and maintain hierarchical patches on top of each other. So I can give you the link capacities which are fairly useful on their own as standalone version, which is still being maintained while I work on other parts of cargo distribution. As patches to be applied on top of that you get first connected components and then demands. Others will follow. While I did all that I also cleaned up the code so that it conforms to OpenTTD coding standards (or at least tries to). Due to the 3 file limit I'll post only the capacities patch and an all-in-one patch with all of cargo distribution in the first post.

This looks very good, especially compared to what you had when I first posted.

Any chance of a binary? Visual Studio is having a disagreement with my laptop

Not from me. I don't use Windows. But of course anyone is free to build a Windows binary. And if you tell me the exact problem you are having I might be able to find out if it's related to my code and fix it if that's the case.

I tried to use your combined diff from the first post. However examinating the patch I found out that SVN tortoise would probably not understand it, so i used patch.exe from cygwin. From reading the patch I figured -p0 is the correct way to apply it but that fails:

G:\Programming\OpenTTD\Trunk>patch -p0 < cargodist_r15743.diff
patching file source.list
Assertion failed: hunk, file ../patch-2.5.9-src/patch.c, line 354

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.

-p1 gives:

G:\Programming\OpenTTD\Trunk>patch -p 1 < cargodist_r15743.diff
missing header for unified diff at line 5 of patch
can't find file to patch at input line 5
Perhaps you used the wrong -p or --strip option?
The text leading up to this was:
--------------------------
|diff --git source.list source.list
|index 6f34894..0080d24 100644
|--- source.list
|+++ source.list
--------------------------
File to patch:

I type source.list and <enter>

But then I get

patching file source.list
missing header for unified diff at line 21 of patch
can't find file to patch at input line 21
Perhaps you used the wrong -p or --strip option?
The text leading up to this was:
--------------------------
|,7 @@ heightmap.cpp
| highscore.cpp
| ini.cpp
| landscape.cpp
|+linkgraph.cpp
| map.cpp
| md5.cpp
| minilzo.cpp
--------------------------
File to patch:

Which seams to correspond to part of the changes to source.list.

I also tried google for patch.exe and downloaded it directly from GnuForWindows, but that just gave the same errors. (not surprisingly as it is the same version)



I don't know if it is anything you can do about it really, just wanted to inform that I tried to do something but it failed.

Edit: I have "updated" to version r15743 using SVN, which is the revision in the patch file name.

Very cool project. I'll have to try compiling it this weekend. Any chance we can see a few pictures of the map overlays?

-p0 should be correct. The problem is that git produces diffs with some special lines the windows patch.exe doesn't understand. I'll try to create a Windows-friendly patch by manually running diff between two different trees later when I prepare today's update. And I'll give you a screenshot ...

I'd try removing the "index" and "new file" lines.

And Zuu, what's the output of patch -v or patch --version?

patch 2.5.9

And then the copyright notice.

Very much not the answer I was expecting. My patch(1) ("patch 2.5.8", from Cygwin) can apply the patch just fine. Are you sure that the line endings in the diff and the source match?

So here are the three patches up-to-date with configurable demands functions per cargo class and with an antisymmetric demand function. I removed all the index and /dev/null entries. Please tell me if that helps.

About line endings, most likely not. As SVN tortoise convert the line endings if I recall correctly. Meaning that I need to convert the patch file too. As reading your post I guess the patch tool do not handle differences in line ending characters between source and patch file. (or at least not without applying some flag for that)

Thanks for pointing out that DaleStan.

Thanks for the offer, but it's nothing to do with your code I can't even make it compile trunk and I'm at a complete loss as to why not. I need to try a different compiler when I get the time.

I have updated the first post and the patches. I'm using git's patch format again as no one could say if the other one is better. You get the all-in-one patch in this post.