Author Topic: Load long distance passengers patch  (Read 24282 times)

0 Members and 1 Guest are viewing this topic.

Offline Markohs

  • DevTeam, Coder/patcher
  • Devotee
  • *
  • Posts: 1559
  • Total likes: 2
  • Helpful: 86
  • Languages: EN,ES,CAT
Load long distance passengers patch
« on: September 25, 2014, 10:22:07 PM »
As discussed here: http://forum.simutrans.com/index.php?topic=13974.msg138725;topicseen#msg138725

A preliminary patch, working, but not finished:

https://dl.dropboxusercontent.com/u/30024783/longdistance.patch

 On any schedule of a particular convoi, or in the schedule of the line, you can change its passenger/good loading priority to prefer loading the ones that have a longer trip ahead, in opposition to current option now, that picks the ones that will get unloaded sooner:




 Code needs polish, and this priority is not saved on the savegame. I was thinking turning that bool get_islongdistance() into uint8 get_loadingpolicy(), giving 0 for the current default policy and 1 for this new one, reserving rest for future extensions of this.

 Turning "if (longdistance)" into a switch(policy){case 0: blablabla" should be almost as fast as this implementation.

 Comments (constructive ones), welcome.

 I don't like the text "Long distance", since it's not descriptive enough, anyone has a better idea?

Offline Sarlock

Re: Load long distance passengers patch
« Reply #1 on: September 26, 2014, 01:27:58 AM »
Thanks for putting the effort in to this, Markohs.

I agree that the text needs to be more descriptive (while still fitting within the confines of the window).  Maybe "load long distance cargo first" and a tooltip that gives more detailed information?

I'm excited about the routing possibilities that this adds to the game.
Current projects: Pak128 Trees, blender graphics

Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 4806
  • Total likes: 191
  • Helpful: 108
  • Languages: EN, NO
Re: Load long distance passengers patch
« Reply #2 on: September 26, 2014, 05:01:51 AM »
I agree that the text needs to be more descriptive (while still fitting within the confines of the window).  Maybe "load long distance cargo first" and a tooltip that gives more detailed information?

I don't know. "Long distance" is a term used for certain services, so you can associate it with that. What "load long distance cargo first" is good for is not quite as obvious, perhaps.

Offline Combuijs

  • Web Team
  • Devotee
  • *
  • Posts: 1387
  • Total likes: 22
  • Helpful: 53
  • Maintainer of maps.simutrans.com
    • Combuijs
  • Languages: EN, NL
Re: Load long distance passengers patch
« Reply #3 on: September 26, 2014, 08:19:40 AM »
Hmm, difficult indeed.

What about a radiobox at the right of of minimum load, with options:

first stop loaded first
last stop loaded first
Bob Marley: No woman, no cry

Programmer: No user, no bugs



Offline Markohs

  • DevTeam, Coder/patcher
  • Devotee
  • *
  • Posts: 1559
  • Total likes: 2
  • Helpful: 86
  • Languages: EN,ES,CAT
Re: Load long distance passengers patch
« Reply #4 on: September 26, 2014, 08:55:11 AM »
Hmm, difficult indeed.

What about a radiobox at the right of of minimum load, with options:

first stop loaded first
last stop loaded first

 That whould associate the idea of the loading policy with just one stop in the mind of our players, and confuse them, I think.

 How about (seeing "Long distance" term is accepted by Ters):

Loading goods preference: [X] Short Distance [  ] Long Distance

 That whould make room for a third option (if it's implemented in the future) called "Proportional". Further explanation on the mouseover help text, and update the in-game documentation.

 I think I will move this line just under the "serves line", and add a horizontal line, because "Minimum load" and "monthly wait time" affect just to one stop, no? Just because this setting affects to the whole schedule, not to just one stop.

Offline Combuijs

  • Web Team
  • Devotee
  • *
  • Posts: 1387
  • Total likes: 22
  • Helpful: 53
  • Maintainer of maps.simutrans.com
    • Combuijs
  • Languages: EN, NL
Re: Load long distance passengers patch
« Reply #5 on: September 26, 2014, 10:26:32 AM »
Quote
Loading goods preference: [X] Short Distance [  ] Long Distance

 That whould make room for a third option (if it's implemented in the future) called "Proportional". Further explanation on the mouseover help text, and update the in-game documentation.

 :thumbsup:

Quote
I think I will move this line just under the "serves line", and add a horizontal line, because "Minimum load" and "monthly wait time" affect just to one stop, no? Just because this setting affects to the whole schedule, not to just one stop.

Surely a separation that is much clearer, yes. As an alternative for position you could move the line just above or under the line name as this also concerns the whole schedule.
Bob Marley: No woman, no cry

Programmer: No user, no bugs



Offline DrSuperGood

Re: Load long distance passengers patch
« Reply #6 on: September 26, 2014, 01:33:20 PM »
The problem with this is that it greatly raises the average transportation distance that the convoy is full since it will always choose people to unload at maximum distance down as opposed to next stop up (which possibly results in empty convoys). The result is that you will have convoys running more full for longer which means more profit. Basically it will make the current commuter snake exploit even more profitable.

Offline Zeno

  • ENASSA Designer
  • Devotee
  • *
  • Posts: 1995
  • Total likes: 3
  • Helpful: 30
    • Zeno's Simutrans Creations
  • Languages: ES, EN, CAT
Re: Load long distance passengers patch
« Reply #7 on: September 26, 2014, 01:53:49 PM »
The result is that you will have convoys running more full for longer which means more profit.
Yeah, actually that's the purpose of the patch.

Offline Markohs

  • DevTeam, Coder/patcher
  • Devotee
  • *
  • Posts: 1559
  • Total likes: 2
  • Helpful: 86
  • Languages: EN,ES,CAT
Re: Load long distance passengers patch
« Reply #8 on: September 26, 2014, 02:20:01 PM »
Yep, as zeno says that's the idea. The idea is giving a tool to our players to make their networks perform better.

Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 4806
  • Total likes: 191
  • Helpful: 108
  • Languages: EN, NO
Re: Load long distance passengers patch
« Reply #9 on: September 26, 2014, 04:15:19 PM »
In essence, it's for solving the cases where there are two lines, one stopping at A and B, and one stopping at A, B and C, where A and C are major hubs while B is a lesser stops. B can actually be several lesser stops, and there might be similar ones near C that the first line doesn't serve, but the second one and some other line do. This would be a typical overlap between stops served by a local line and an intercity line respectively. It might be less suitable when there are more than two major hubs on the route. As explained in the thread this war forked from, without this option, you may find that the second line steals all the passengers from the first, leaving the first line running empty from A to B, while passengers for C are stranded at A.

Offline Markohs

  • DevTeam, Coder/patcher
  • Devotee
  • *
  • Posts: 1559
  • Total likes: 2
  • Helpful: 86
  • Languages: EN,ES,CAT
Re: Load long distance passengers patch
« Reply #10 on: September 26, 2014, 06:52:18 PM »
Bad news, this has a catastrofic side effect I have to think how to avoid, situation is:

A <> B <> C

One line goes A>B , with short distance activated
Another A>B>C>B Long distance prefered.

 It goes as intended, as we thought it whould go, when second train goes to A, it picks all travelers to C, and if it's free room available, to B.

 What's the problem? After departing C, when it reaches B in the "return" path, it might end picking passengers to C!!! in preference to passengers to A.

 I think I can fix this somehow, I'll think about it, anyone has any idea?

 Righ now it looks like:



 On the image example, Nottingham is A, Wells is B, and Leeds is C. The tram just departed Wells(B) to head Nottingham(A), and loaded a passenger to Leeds(C).

EDIT: I think I need to check first if this train is returning to the same station it's being considered, and just start processing from there, backwards.
« Last Edit: September 26, 2014, 07:09:41 PM by Markohs »

Offline Michael 'Cruzer'

  • Devotee
  • *
  • Posts: 195
  • Total likes: 2
  • Helpful: 5
  • Founder of pak192.comic
    • Marktplatz für Parkplätze
  • Languages: DE, EN
Re: Load long distance passengers patch
« Reply #11 on: September 26, 2014, 07:49:24 PM »
This patch sounds great!

I think I can fix this somehow, I'll think about it, anyone has any idea?
You may first check every station in the list if it is a duplicate and remove duplicates which are later in the list. Then you only use the resulting list for your calculation.
Founder and Ex-Maintainer of pak192.comic. Provider of Simutrans Hosting rental service.

Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 4806
  • Total likes: 191
  • Helpful: 108
  • Languages: EN, NO
Re: Load long distance passengers patch
« Reply #12 on: September 26, 2014, 08:49:52 PM »
Bad news, this has a catastrofic side effect I have to think how to avoid, situation is:

A <> B <> C

One line goes A>B , with short distance activated
Another A>B>C>B Long distance prefered.

 It goes as intended, as we thought it whould go, when second train goes to A, it picks all travelers to C, and if it's free room available, to B.

 What's the problem? After departing C, when it reaches B in the "return" path, it might end picking passengers to C!!! in preference to passengers to A.

Doesn't sound much different from what Simutrans handles already. When loading at B when going from C towards A today, it won't consider loading passengers for C even if there is room. They will have to wait until the train has turned around at A.

Offline Markohs

  • DevTeam, Coder/patcher
  • Devotee
  • *
  • Posts: 1559
  • Total likes: 2
  • Helpful: 86
  • Languages: EN,ES,CAT
Re: Load long distance passengers patch
« Reply #13 on: September 26, 2014, 11:42:14 PM »
mmm... the algorithm has to me more complicated than I initially though. To avoid a n^2 cost (or something like that I can't figure it out now) algorithm I need some data structures, still on it. Will use more cpu than the actual algorithm, but it will not be terrible, I think.

For the curious, the current state of the patch:

https://dl.dropboxusercontent.com/u/30024783/longdistance-2.patch

EDIT2: *SOLVED*. The problem was not *so* simple to solve, processing the schedule stops in order, and considering nothing more than how full the convoi was, was in fact a lot hiding of computational complexity. I should have suspected this as this smells *similar* to the knapsack problem.

 Well, to make it short, and with an example, in our previous example:

A>B>C>B

 When train goes to A, and starts loaging cargo, you know wich is the farthest station in the schedele? Our intuition tells us that it's C, right? No, it's B. It's the last entry. This is a problem.

 Also, on:

B>C>B>A

 The farthest one, as I already commented, it's A. Another problem.

 Second problem is easily solved, I just transverse the list from the *current* stop, and I "cut" the schedule when I reach the current stop again, so:

B>C>B>A

turns into:

B>C

 Problem solved, we still need to solve the first one. (Consider that are even worse situations like A>B>C>D>B>C, that are solved also by the algorithm that I'm exposing, we use the simple example for simplicity)

 Ok, after I apply the solution just exposed, I transverse the list, and calculate the *minimum* number of stops the traveler will have to do to reach *each* station on the schedule, so:

A>B>C>B

 Assumming that we are just loading at A:

B is 1 stop from A, and also at 3 stops. So B is at distance 1
C is 2 stops from A

 Then I use our first discussed algorithm, so we transverse the list in *reverse* order.

 I start with B, the B that's 3 stops away, I *know* there is a shortest path at just distance 1, according my previous calculations, so I *IGNORE* this stop
 Then C, at 2 stops away, that's coherent with my notes that indicates that's effectivelly at distance 2, so I *LOAD* the convoi with passengers to C.
 *IF* the convoi still has available space, I check passengers for B, at distance 1, and my notes indicates this is the correct minimum distance, so I *LOAD* more passengers here.

 Well, that was done, with one hash table. Could be worse, but still, quite a lot of load. And you know what? If my intuition about this is correct, proportional loading will require this approach, or a similar one to the problem (or maybe not, maybe just with the intial "cut" it's enough,since you load *all* stations, in not a precise order, just in proportion to the passengers "waiting".

 Performance, it's worse than our current, simple but fast, implementation.

 *BUT* assuming we can pre-calculate this hashes (minimum distances), and re-use them, storing them on the schedule_t class, and knowing schedules are just updated manually by the player (that's really not often), whis can work, because if the hashes are stored in memory, and not created on every convoi load, this is *very* assumible.

 Anyway, if anyone has a better idea, or comments about this, just tell me. The patch, with debug printf and get_rep() instead of get_id() (that needs to be reverted but I'm too tired to do it now):

https://dl.dropboxusercontent.com/u/30024783/longdistance-3.patch

 If anyone needs a binary to test, just tell me (or maybe anyone wants to upload one), but if you ask me for it, please take your time to test and publish your impressions later, please.

EDIT3: Before going to sleep, I compiled a windows version, might not work in something less than windows 7, and *could* require you to install Microsoft redristibutable librarties, probably 2013 ones, or not, or something else, won't look more about it right now :) :

https://dl.dropboxusercontent.com/u/30024783/Simutrans_longdistance.exe
http://www.microsoft.com/en-us/download/details.aspx?id=40784
« Last Edit: September 27, 2014, 02:28:50 AM by Markohs »

Offline Sarlock

Re: Load long distance passengers patch
« Reply #14 on: September 27, 2014, 01:25:10 AM »
If you can resolve this issue, you're killing two birds with one stone...this has been an annoyance for a while.  This is common with circular lines -- I assume your test case was a circular route.
Current projects: Pak128 Trees, blender graphics

Offline DrSuperGood

Re: Load long distance passengers patch
« Reply #15 on: September 27, 2014, 01:28:21 AM »
Quote
It goes as intended, as we thought it whould go, when second train goes to A, it picks all travelers to C, and if it's free room available, to B.

 What's the problem? After departing C, when it reaches B in the "return" path, it might end picking passengers to C!!! in preference to passengers to A.
How is this implemented currently? I know that there is protection for this where by it will only pick up passengers to the following stops before it returns back to the stop and heads off to different stops. This is why when doing the cargo bounce exploit you cannot use the source station as a bounce location. It will only pick up the goods at the very last stop at the station before it goes off to their destination.

Offline Markohs

  • DevTeam, Coder/patcher
  • Devotee
  • *
  • Posts: 1559
  • Total likes: 2
  • Helpful: 86
  • Languages: EN,ES,CAT
Re: Load long distance passengers patch
« Reply #16 on: September 27, 2014, 02:03:51 AM »
How is this implemented currently? I know that there is protection for this where by it will only pick up passengers to the following stops before it returns back to the stop and heads off to different stops. This is why when doing the cargo bounce exploit you cannot use the source station as a bounce location. It will only pick up the goods at the very last stop at the station before it goes off to their destination.

 It just starts looking the schedule from the point it's at that moment the convoi loading, and looks forward, if it reaches a point it's poiting to the same station the train is, the good loading it's considered "complete", because you can be sure, the train will return to this stop, in the correct direction, later.

EDIT: Before going to sleep, I compiled a windows version, might not work in something less than windows 7, and *could* require you to install Microsoft redristibutable librarties, probably 2013 ones, or not, or something else, won't look more about it right now :) :

https://dl.dropboxusercontent.com/u/30024783/Simutrans_longdistance.exe
http://www.microsoft.com/en-us/download/details.aspx?id=40784
« Last Edit: September 27, 2014, 02:26:59 AM by Markohs »

Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 4806
  • Total likes: 191
  • Helpful: 108
  • Languages: EN, NO
Re: Load long distance passengers patch
« Reply #17 on: September 27, 2014, 08:48:17 AM »
mmm... the algorithm has to me more complicated than I initially though. To avoid a n^2 cost (or something like that I can't figure it out now)

Although you came up with some solution, I wouldn't really be worried over O(n^2) on lists of usually far less than 100 elements. (Unless each step is quite expensive, which I don't assume for just finding duplicate stops in memory.)

Offline TurfIt

Re: Load long distance passengers patch
« Reply #18 on: September 27, 2014, 08:15:00 PM »
Well, to make it short, and with an example, in our previous example:
A>B>C>B
 When train goes to A, and starts loaging cargo, you know wich is the farthest station in the schedele? Our intuition tells us that it's C, right? No, it's B. It's the last entry. This is a problem.
?? I don't follow how B is the farthest station. It's the last entry, but for the purposes of pax loading at A, C would be the farthest station for any definition of farthest I can think of... Indeed B is the closest station occurring next in the schedule. Duplicates need to be trimmed.


I start with B, the B that's 3 stops away, I *know* there is a shortest path at just distance 1, according my previous calculations, so I *IGNORE* this stop
 Then C, at 2 stops away, that's coherent with my notes that indicates that's effectivelly at distance 2, so I *LOAD* the convoi with passengers to C.
 *IF* the convoi still has available space, I check passengers for B, at distance 1, and my notes indicates this is the correct minimum distance, so I *LOAD* more passengers here.
The result here makes sense for loading to the farthest stations first, but if the 3 stop away B is the farthest as claimed above, ignoring it make no sense.


Although you came up with some solution, I wouldn't really be worried over O(n^2) on lists of usually far less than 100 elements. (Unless each step is quite expensive, which I don't assume for just finding duplicate stops in memory.)
I expect the 'simple' n^2 algorithm would tend to be faster here than using simutrans horribly performing hashtables...
  1. from the current stop, search the schedule forwards looking for the same stop again. i.e. the "cut" step for when the convoi revisits the same station
  2. now iterate backwards from the index found above to get your loading candidates.
  3. for each loading candidate, search backwards from them to the current stop looking for a duplicate of the candidate.
  4. if found, then the candidate is visited earlier in the schedule, and hence is not the farthest, skip it.
  5. if not found, it then is the farthest, load cargo.
Should give the same result as your hashtable algo without all the hashtable overhead.



Patch provided does not compile:
Code: [Select]
In file included from bauer/../gui/karte.h:8:0,
                 from bauer/brueckenbauer.cc:25:
bauer/../gui/../dataobj/fahrplan.h:28:36: warning: scoped enums only available with -std=c++11 or -std=gnu++11 [enabled by default]
bauer/../gui/../dataobj/fahrplan.h: In constructor 'schedule_t::schedule_t()':
bauer/../gui/../dataobj/fahrplan.h:33:69: error: 'schedule_loading_algorithm' is not a class or namespace


gui/fahrplan_gui.cc: In member function 'virtual bool fahrplan_gui_t::action_triggered(gui_action_creator_t*, value_t)':
gui/fahrplan_gui.cc:657:65: error: 'schedule_t::schedule_loading_algorithm' is not a class or namespace
gui/fahrplan_gui.cc:666:27: error: 'schedule_t::schedule_loading_algorithm' is not a class or namespace

simhalt.cc: In member function 'void haltestelle_t::fetch_goods(slist_tpl<ware_t>&, const ware_besch_t*, uint32, const schedule_t*, const spieler_t*)':
simhalt.cc:1873:19: error: 'schedule_t::schedule_loading_algorithm' is not a class or namespace
simhalt.cc:1876:19: error: 'schedule_t::schedule_loading_algorithm' is not a class or namespace
Extraneous  'schedule_loading_algorithm::' needs to be removed.
The warning is quite irritating too, ~40 instances cluttering things up on a full build.

Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 4806
  • Total likes: 191
  • Helpful: 108
  • Languages: EN, NO
Re: Load long distance passengers patch
« Reply #19 on: September 27, 2014, 09:24:46 PM »
?? I don't follow how B is the farthest station. It's the last entry, but for the purposes of pax loading at A, C would be the farthest station for any definition of farthest I can think of... Indeed B is the closest station occurring next in the schedule. Duplicates need to be trimmed.

I think he was trying to explain what the naive algorithm would think, especially since he follows up with a solution for how to find C and not B.

Offline DrSuperGood

Re: Load long distance passengers patch
« Reply #20 on: September 28, 2014, 12:22:33 AM »
Quote
scoped enums only available with -std=c++11 or -std=gnu++11 [enabled by default]
You cannot use c++11 features as far as I can tell as that would wreck backwards compatibility. Thus why there still is a custom decleration of sint32 etc instead of using int32_t which is part of an earlier standard (or something).

The migration to a newer standard of C++ is a big deal and has to be decided upon by project managers since it is basically saying "we will no longer support you" to some people. This should usually occur after some milestone (in this case, a major release) which becomes the last milestone for those unsupported systems to use. In all cases it will not happen just to add support to a minor feature like convoy pickup priority.

Offline Markohs

  • DevTeam, Coder/patcher
  • Devotee
  • *
  • Posts: 1559
  • Total likes: 2
  • Helpful: 86
  • Languages: EN,ES,CAT
Re: Load long distance passengers patch
« Reply #21 on: September 28, 2014, 12:42:22 PM »
@Turfit: I didn't even think about copying the schedule and delete duplicates. Copying a schedule will trigger a lot of data structures creation/destroying anyway no? It might end being even more expensive. Another option is just allowcating myself a C++ array, and manipulating it, with numbers, I think that's what I will do. That makes a lot of sense, thank you! Removing duplicate stops, it's clearly the way to go.
@Turfit and DrSuperGodd, about the C++11 standard parts. I didn't even knew that was part of that standard, I'll change it.

 Anyway, drsupergood, in our enviroment it's not about planning to use newer standards, it's that you need to accept we'll never move forward technologically because we have a operating system like Haiku to support.

 I sometimes wonder how many players use (maybe just prissi), that keeps us stuck to that old compiler. I just looked it and the 112.2 compiled for haiku has been downloaded 87 times. So I'd just etimate in a wild guess we have under 20 players that use haiku. I say, I whould drop support to that operating system.

 That's one of the reasons we don't use STL neither, and we are stuck to that tpl data structures (even if they perform poorly, as exposed byTurfIt). Don't even think about moving ahead, C++11 will simply not happen, ever. Because *any* compiler you have in *any* modern computer, supports STL and C++11, years, years ago.

 But  don't worry, I'll change the code, the reason I defined that enum taht way was to abstract the details of the implementation to other classes, so we could change it in the future (since the other classes didn't need to declare it as uint8, I know it's a minor detail, but I try to avoid this kind of sutuations if I have the chance to). I know to increment/decrement it, I use a uint8 declaration, but planned to remove that using a ++/-- overload.

In all cases it will not happen just to add support to a minor feature like convoy pickup priority.

 Yes, I know this is a minor feature, but don't forget it's a feature no one bothered to implement. We tend to look at the game as just our (the programmers) creation and think we should decide what's in/out of it. But don't forget the important thing about this piece of software we develop as programmers its that it's a game, so we have players to satisfy. And their wishes are very important too, if they are reasonable wishes.

 To our players all this techincal talk is just insignificant, and just want to use the game, and its features.
« Last Edit: September 28, 2014, 12:52:43 PM by Markohs »

Offline Vladki

Re: Load long distance passengers patch
« Reply #22 on: September 28, 2014, 02:03:15 PM »
I have compiled the patch on Linux, with the fixes mentioned by TurfIT.

Then I changed one line to prefer long distance goods - it seems to work OK, but the other lines (defaulting to short distance) started to load cargo that should have been loaded on the way back. So it seems that you have somehow broken the original loading mechanism.

Offline Markohs

  • DevTeam, Coder/patcher
  • Devotee
  • *
  • Posts: 1559
  • Total likes: 2
  • Helpful: 86
  • Languages: EN,ES,CAT
Re: Load long distance passengers patch
« Reply #23 on: September 28, 2014, 02:52:08 PM »
I'll have it a look, Vladki, thx

Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 4806
  • Total likes: 191
  • Helpful: 108
  • Languages: EN, NO
Re: Load long distance passengers patch
« Reply #24 on: September 28, 2014, 03:13:38 PM »
Because *any* compiler you have in *any* modern computer, supports STL and C++11, years, years ago.

I'm not so sure with regards to Windows anymore. The mingw community has splitt in two, with one half going stale while the other is a bit chaotic. Microsoft's compiler is free, but isn't as feature rich as GCC. It doesn't even support plain C, just C-ish C++. There also doesn't seem to be much support/documentation for the compiler. It seems you're just supposed to use Microsoft Visual Studio, and the features you get there without paying might change at a whim. In particular, the ability to target Windows XP might be in risk, which would hurt a larger part of the community than dropping Haiku.

Offline Markohs

  • DevTeam, Coder/patcher
  • Devotee
  • *
  • Posts: 1559
  • Total likes: 2
  • Helpful: 86
  • Languages: EN,ES,CAT
Re: Load long distance passengers patch
« Reply #25 on: September 28, 2014, 10:03:01 PM »
I'm not so sure with regards to Windows anymore. The mingw community has splitt in two, with one half going stale while the other is a bit chaotic. Microsoft's compiler is free, but isn't as feature rich as GCC. It doesn't even support plain C, just C-ish C++. There also doesn't seem to be much support/documentation for the compiler. It seems you're just supposed to use Microsoft Visual Studio, and the features you get there without paying might change at a whim. In particular, the ability to target Windows XP might be in risk, which would hurt a larger part of the community than dropping Haiku.

 I have msvc 2013 here and you can make xp binaries without a problem, still. Also, mingw has support for many aspects of C+11. You also have clang available in Windows. Windows support for c++11 is available everywere, as well that on linux or any modern operating system, comeon.

 What you will maybe have some problems finding nowadays is gcc 2.95 that shipped haiku.

 Its not that I hate haiku, I just say, if it's stopping us to do anything good, just drop it, who cares about that OS.

 I fixed the bug, Vladki, thanks for the report, well spotted. Soon I'll have the new version of the patch with turfit suggested changes, and without C++11 code.

Offline Spacethingy

Re: Load long distance passengers patch
« Reply #26 on: September 28, 2014, 10:24:19 PM »
If you guys could possibly solve P=NP? while your at it, that'd be great! :D

On a serious note, this would a very welcome addition to Simutrans, IMHO. Quite a subtle change, yet a very good one.
Life is like a new Simutrans transformer:

You only get one of them, and you can't have it on a slope.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 8795
  • Total likes: 319
  • Helpful: 229
  • Languages: De,EN,JP
Re: Load long distance passengers patch
« Reply #27 on: September 28, 2014, 11:04:42 PM »
The long distance option will just add as a quick overcrowding switch. In a situation where A->B->C->B is the only line serving B, then B will be very quickly starved forever from people going A->C and back. (THis is almost the standard from bus lines serving the townhall or a factory and an exchange point).

Such situations were the reason why the loading was switched from fifo to next for next stop. Making this a schedule option is rather like an exploit and micromanagement.

Offline isidoro

Re: Load long distance passengers patch
« Reply #28 on: September 29, 2014, 12:25:51 AM »
Going back to the problem.  Am I thick or in a schedule like: A B C C B D, you can use two indexes for begin and end.  Take the first stop and try to find it again in the schedule.  If found, make the end index point to the previous station of this second apparition.  And repeat for all the remaining stations?

In the example:
1) A B C C B D, look for A.  No A.  The candidates remain.
2) A B C C B D, look for B.  Trim -> A B C C
3) A B C C, look for C.  Trim -> A B C

Farthest station: C, then B

It can be n², but only in worst case.  And doesn't require additional memory.


Offline TurfIt

Re: Load long distance passengers patch
« Reply #29 on: September 29, 2014, 02:32:53 AM »
@Turfit: I didn't even think about copying the schedule and delete duplicates. Copying a schedule will trigger a lot of data structures creation/destroying anyway no? It might end being even more expensive. Another option is just allowcating myself a C++ array, and manipulating it, with numbers, I think that's what I will do.
No, I meant to just search in the existing schedule. No need to copy it, or to allocate anything else. It's not so much eliminating the duplicates as skipping them during the backwards iteration phase of the algorithm I tried to describe above.


I sometimes wonder how many players use (maybe just prissi), that keeps us stuck to that old compiler. I just looked it and the 112.2 compiled for haiku has been downloaded 87 times. So I'd just etimate in a wild guess we have under 20 players that use haiku. I say, I whould drop support to that operating system.
AFAICT, Haiku moved to GCC4 over 5 years ago...
MinGW is probably the current laggard with whatever they've done in the current versions being completely incompatible with Simutrans and its required libraries. I'm stuck with gcc4.7 to be able to get a working build, trying a 4.8 needs the newer mingwWRT which seems to break everything. Of course 4.7 supports a newer standard then Simutrans is coded too...


The long distance option will just add as a quick overcrowding switch. In a situation where A->B->C->B is the only line serving B, then B will be very quickly starved forever from people going A->C and back. (THis is almost the standard from bus lines serving the townhall or a factory and an exchange point).

Such situations were the reason why the loading was switched from fifo to next for next stop. Making this a schedule option is rather like an exploit and micromanagement.
If B is starved/overcrowding, then there's simply not enough transport capacity serving the stops. In that case, with the current algorithm, pax would be piling up at A for C and v.v.. With the long distance algorithm, they pile up at A for B, B for A and C, and at C for B.
I do think the current algo is the best, but I don't see any exploit with this proposal.


Yes, I know this is a minor feature, but don't forget it's a feature no one bothered to implement. We tend to look at the game as just our (the programmers) creation and think we should decide what's in/out of it. But don't forget the important thing about this piece of software we develop as programmers its that it's a game, so we have players to satisfy. And their wishes are very important too, if they are reasonable wishes.

 To our players all this techincal talk is just insignificant, and just want to use the game, and its features.
Frankly, I don't really see the point in this feature. The current loading routine requires the player to configure their lines in a certain way. If they don't do that, the results are sub-optimal. This feature simply changes what that optimal configuration is. The examples given in the other thread are simply indicative of the network not being set up 'correctly' for the existing routine. Certainly having this option change what's optimal is valid, but if a player is using it, are they really playing the same game? Where does one draw the line between players learning the game mechanics and playing within them, v.s. changing the game to suit how a player thinks it should work?

Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 4806
  • Total likes: 191
  • Helpful: 108
  • Languages: EN, NO
Re: Load long distance passengers patch
« Reply #30 on: September 29, 2014, 05:46:05 AM »
I have msvc 2013 here and you can make xp binaries without a problem, still. Also, mingw has support for many aspects of C+11.

I didn't say XP wasn't still supported, but I noticed that for the latest version, XP support was reintroduced in update 1. Whether it was intentionally or accidentally dropped in the initial release is unknown to me, but it's a bad omen. As for mingw, I wrote that it is becomming less and less of an alternative, not because of lacking support of new C++ standards (though that might soon be a problem as well), but for lacking support for new Windows-standards.

The long distance option will just add as a quick overcrowding switch. In a situation where A->B->C->B is the only line serving B [...]
(emphasis added by me)

It is not for that situation. As I have written several times, the problem this will solve always involves two or three lines: one long distance line and one or two local lines. Sure, it's easy for beginners to activate the option in the wrong situations, but I think the effects are so immediate that the player might understand the connection. I don't see it as much worse than what throuble beginner can get into with signals, and choose signals in particular.

Frankly, I don't really see the point in this feature. The current loading routine requires the player to configure their lines in a certain way. If they don't do that, the results are sub-optimal. This feature simply changes what that optimal configuration is. The examples given in the other thread are simply indicative of the network not being set up 'correctly' for the existing routine. Certainly having this option change what's optimal is valid, but if a player is using it, are they really playing the same game? Where does one draw the line between players learning the game mechanics and playing within them, v.s. changing the game to suit how a player thinks it should work?

The only way I know to solve this problem is to ensure that no pair of two stops share more than one line for a certain type of freight. If there are two alternatives, you can bet the system will load on the line least optimal for use between those two stops, causing overcrowding on stops only served by that line. I am not 100 % sure this change will help much, and the situations were it might help are limited, but I think it has a fair chance. One of my games, which I have sort of retired, has a good test case for this change, but I haven't had the time to test this out yet.

Offline Markohs

  • DevTeam, Coder/patcher
  • Devotee
  • *
  • Posts: 1559
  • Total likes: 2
  • Helpful: 86
  • Languages: EN,ES,CAT
Re: Load long distance passengers patch
« Reply #31 on: September 29, 2014, 07:11:09 AM »
Ok turfit, got it know. You are right, it's a simple solution and easy to understand/read. No additional mem structures. It will perform poorly in schedules I'd say wuth more than 50 stops but that's not a common situation.
If gcc 4.7 is the highest one supported properly by mingw, it's more than enough to support STL and certain features of C++11. Why don't we just assume gcc 4.7 as a minimum compiler version and allow developers use features supported by that compiler? I'd like for example being able to use std:set, and scoped enums from c++11.

Offline Vladki

Re: Load long distance passengers patch
« Reply #32 on: September 29, 2014, 07:13:40 AM »
There are real world situations that can be simulated by this. Think of an urban tranport going from ghe center to the far outskirts of the city. Convoys are overcrowded in the center but almost empty at the suburbs. If you just add more convoys you lose money. So you establish a second link that has the same stops but runs only half way to help the overcrowded stops. That is something done in real world and this patch helps to do it in simutrans. There are not many such occasions in most games but it is still helpful.

Yes, you can solve the above scenario by splitting the line in two, one with more capacity than the other and forcing the passengers to transfer. But it looks weird if there is no other line to trasfer to.

Sent using recycled electrons.


Offline Markohs

  • DevTeam, Coder/patcher
  • Devotee
  • *
  • Posts: 1559
  • Total likes: 2
  • Helpful: 86
  • Languages: EN,ES,CAT
Re: Load long distance passengers patch
« Reply #33 on: September 29, 2014, 07:51:24 AM »
As Ters and Vladki expose, this feature it's of importance not on one schedule in particular. It's when various lines are serving the same route, when they share stops, when this new feature can prove to be useful. It mimetizes what in real world are "express" lines, or long distance routes.

 Right now, with the only loading policy, you end being in a situation, where, to try avoid station overcrowding, and to keep lines profitables, you can't really have schedules with more than two stops, because when there are 3 points to be connected, as the two sub-lines are not balanced, you will end in the line being unprofitable, or having segments on the line that underuse available free coach capacity.

 So, in practise, to have a properly working network, a profitable one, and speaking of long distance traffic, you are left to point to point connections, and huge hubs. You have also circular networks, but they are really more suited to urban than to inter-urban trafic. Circular lines, are so profitable, that on public network servers, it's common to see players make *HUGE* circular lines interconnecting cities, some of them underground. This is very different of how things work in real life, and a "exploit". One of the reason this is often seen, it's because big schedules (with many stops), *ARE NOT PROFITABLE UNLESS THEY ARE CIRCULAR*.

 I say, on a simple setup, this new loading way, makes no difference, it's just on long networks, with multiple lines sharing paths, when this feature shines and it's useful, imho. And in my oppinion, it's simple enough to not be a burden to our users, and easy to understand/use. Anyway I migh be wrong, so maybe before getting into trunk, we can publish another 120 release candidate, with this change in, and if we get positive feedback with our users, let it be inside the game, we can allways rollback this change if it's not really worth it.

 I say, try it, explore it, it might end being more useful than you think, people can find new uses for it. Or maybe not.

Offline DrSuperGood

Re: Load long distance passengers patch
« Reply #34 on: September 29, 2014, 11:38:37 AM »
Quote
One of the reason this is often seen, it's because big schedules (with many stops), *ARE NOT PROFITABLE UNLESS THEY ARE CIRCULAR*.
Heaven forbid that it is just because circular lines are more efficient throughput wise than terminal lines. You can get nearly 100% more traffic through a station in a circle than in a terminal. Some times I even have circular lines with parallel platforms so another train can arrive while one is leaving for even higher throughput, something that only works 50% of the time in terminals. This is the main reason all my lines are circular in pak64, even if the line consists of only 2 stops!

It is easy to make a terminal based line profitable. Just throw in enough traffic and your making tons of money. For example a point to point connection through a huge city (underground for even higher population density as pickup is too small otherwise) and with enough stops it will be running 100% full all the time and making a ton of money.

The main problem is circular pickups. Particular a "tram underground" in pak64, which I have become quite famous for using over the past year in servers. The symmetry of traffic (passenger in = out) combined with high profitability of trams and near maximum throughput means a lot of profit. I was making >500k a month per line and some cities were 2-3 lines deep. Analysis shows that the actual problem is the passengers from the very first stop after the transfer loading and paying for all other intermediate stops up to the transfer. One can even think it is fair as their end stop is like 20-30 stops down the line even if physically they should have just walked there. This is obviously not a problem with bi-directional flows since then the furthest stop is at most half the loop away so they are a lot less profitable.

The only solution would be some kind of passenger satisfaction. "I will not take your tram because this is total rubbish that I must pay for 30 stops to reach one 5 tiles away". Or maybe even just a limit to how much non-direct distance passengers are willing to pay for ("I am not paying for the transport company's stupidity, they should make a more efficient transport system").