News:

Simutrans Chat Room
Where cool people of Simutrans can meet up.

[patch] Allow convoys to follow their schedule in reverse automatically

Started by yobbobandana, June 03, 2010, 01:15:03 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

knightly

Hi Yobbobandana

Quote from: yobbobandana on June 22, 2010, 04:34:18 AM
The only problem I'm having is constructing adequate test-cases for the routing behaviour. It seems to do what it should in all cases I've tried. But in particular I'm not sure how to test the code in haltestelle_t::rebuild_destinations() that adds stops to "warenziele" ordered by distance. I couldn't see how this affects routing, with or without my patch applied.

rebuild_destinations() is triggered when something that affects routing is changed. For instance, it is triggered when you add/remove stop(s) to/from a schedule/line, or when you add a new stop or remove an existing stop on the map, etc.

BTW, I would suggest not to use "circular", as it is ambiguous. In fact, the original route implementation is already circular : A > B > C > D > A > B > C > D > ... , with the stops forming a closed loop. In your case, I would rather suggest to use "bidirectional" -- that makes it clear that the route is served by vehicles heading opposite directions.

Edit :

For rebuild_destinations(), you would expect that a line that serves A > B > C > D > E > F > G > H with F as the origin to have the following order of stops in the warenziele :
   Current implementation :  G H A B C D E
   Bidirectional but not mirrored : (E G) (D H) (C A) B
   Mirrorred (regardless of bidirectional) : (E G) (D H) C B A
Stops grouped in brackets mean that their order are interchangeable [i.e. (C A) means both A-C or C-A are acceptable]. Of course, this is only for ST Standard, which currently does not consider inter-stop distance or travelling time; for EXP, you need to check, for the bi-directional but not mirrorred case, which route, normal or reverse route, is faster to reach a stop.

Edit :

Forgot to mention : you may need to call welt->set_schedule_counter() when bidirectional or mirror flag is toggled, in order to trigger recalculation of warenziele and routes.

Hope this helps!

Knightly

yobbobandana

Hi Knightly, thanks for your help :).

I've verified that stops are indeed added to warenziele in the correct order for bidirectional/mirrored schedules.

For bidirectional schedules it treats them as a single schedule that passes all stops in both directions. The current code handles this well already, and it looks like I can do the same thing easily for Experimental.

So for example A>B>C>D>E from stop D will check destinations E>A>B>C>reset_distance>C>B>A>E, replacing destinations B and C on the way back. If the route was mirrored it would check E>reset_distance>C>B>A>B>C.

You are quite right about the term "circular", I couldn't think of a good word to replace it with but bidirectional works well :).

I just double-checked and welt->set_schedule_counter() seems to be called automatically. Changing the bidirectional/mirrored flags on a schedule will treat it as a new schedule, which seemed the easiest thing to do.

Here is an updated patch:
* Replaces "circular" with the more apt "bidirectional".


knightly

[Previous comments removed]

Edit :

I think some special handling is necessary with bidirectional (but not mirrorred) lines and reversing.

For instance, what if a bidirectional line has only one convoy? Then this line is actually unidirectional. Warenziele entries would then have to be in line with the direction (normal or reverse) of the single convoy. And if its direction is reversed later, warenziele needs to be updated.

And what if a bidirectional line has more than one convoy, but the player has manually switched the directions such that all of them are heading the same direction? In that case, the line has become unidirectional.

How about a non-bidirectional line having more than one convoy, and the player manually switches one of them to the reverse direction? It becomes a bidirectional line and warenziele needs to be rebuilt.

Unlike the mirror flag, setting the bidirectional flag of a line/schedule alone does not automatically make it bidirectional. Setting the bidirectional flag only indicates the wish to enforce bidirectionality; actual directionality depends on the directions of convoys associated with the line. Thus, some extra logic is needed to keep track of the actual directionality of a line, and increment schedule counter whenever the directionality changes.

On the other hand, it is also necessary to increment schedule counter when the player reverses the direction of a lineless convoy.

Edit :

Conceptually, bidirectionality (both the directive to enforce it by alternating initial direction of individual convoys, as well as the actual state of it) is a property of lines only. They should not appear in the schedule copies of individual convoys (and definitely not in the schedules of lineless convoys). Thus I would suggest to move the bidirectionality flag from schedules to lines.

Besides, I would also suggest to relocate the reverse flag from convoys to schedules, as each convoy has its own copy of the schedule. In that way, the following code :
Quote
void convoi_t::advance_schedule() {
   // check if the convoi should switch direction
   if( fpl->is_mirrored() ) {
      if( fpl->get_aktuell()==0  ) {
         reverse_schedule = false;
      }
      else if( fpl->get_aktuell()==fpl->get_count()-1 ) {
         reverse_schedule = true;
      }
   }
   // advance the schedule cursor
   if( reverse_schedule ) {
      fpl->advance_reverse();
   } else {
      fpl->advance();
   }
}
could be encapsulated inside schedules. Convoy code should not know how mirrorring is implemented, or decide whether to advance schedule index normally or in reverse.

Edit :

A minor suggestion : maybe it's more convenient to pass arguments by reference (instead of pointers) to schedule_t::increment_index(). In that way, you don't need to take the address of the variables, and later deference them again in the function body.

yobbobandana

Quote from: Knightly on June 23, 2010, 07:51:31 AM
A minor suggestion : maybe it's more convenient to pass arguments by reference (instead of pointers) to schedule_t::increment_index(). In that way, you don't need to take the address of the variables, and later deference them again in the function body.

I preferred to pass by address just because it makes it more obvious that the variables will be changed, but I should've checked what the style was in other places :). I've updated this and as you say it's cleaner as such.

Quote from: Knightly on June 23, 2010, 07:51:31 AM
Besides, I would also suggest to relocate the reverse flag from convoys to schedules, as each convoy has its own copy of the schedule. In that way, the following code :could be encapsulated inside schedules. Convoy code should not know how mirrorring is implemented, or decide whether to advance schedule index normally or in reverse.

I've moved the logic out of simconvoi.cc (it just uses increment_index now), but I still currently have the reverse flag kept as part of the convoy... If I move it to part of the schedule then there is the question of if the direction is not the same, is it the same schedule? In particular, I would probably leave the direction out of sprintf_schedule and sscanf_schedule, but I'm not sure whether this would be desired in all cases.

Well, I'll see what it looks like after I'm done with the next part.

Quote from: Knightly on June 23, 2010, 07:51:31 AM
Conceptually, bidirectionality (both the directive to enforce it by alternating initial direction of individual convoys, as well as the actual state of it) is a property of lines only. They should not appear in the schedule copies of individual convoys (and definitely not in the schedules of lineless convoys). Thus I would suggest to move the bidirectionality flag from schedules to lines.

True, the bidirectional flag should be part of the line. In terms of the UI though, even for lineless convoys you can "promote" their schedule to a line, so I'd need to find some better place of editing this. So far methods of editing the line just give you the schedule to edit, so in terms of the UI lines and schedules are almost identical.

So I'm not too sure where it could be edited from.

Similarly for the direction flag, I couldn't see how to easily add it to the schedule editing UI without adding another row to the buttons at the top.

I could possibly add another row for the active direction, and hide the "bidirectional" button for individual convoys. Then the bidirectional flag could sensibly be added to the line, and the direction flag to the schedule. I do like setting the direction from the convoy info window though.

Quote from: Knightly on June 23, 2010, 07:51:31 AM
I think some special handling is necessary with bidirectional (but not mirrorred) lines and reversing.

For instance, what if a bidirectional line has only one convoy? Then this line is actually unidirectional. Warenziele entries would then have to be in line with the direction (normal or reverse) of the single convoy. And if its direction is reversed later, warenziele needs to be updated.

...

Unlike the mirror flag, setting the bidirectional flag of a line/schedule alone does not automatically make it bidirectional. Setting the bidirectional flag only indicates the wish to enforce bidirectionality; actual directionality depends on the directions of convoys associated with the line. Thus, some extra logic is needed to keep track of the actual directionality of a line, and increment schedule counter whenever the directionality changes.

On the other hand, it is also necessary to increment schedule counter when the player reverses the direction of a lineless convoy.
Ahh yeah you're right... thinking about it I'll probably need to keep track of the served directions on a per-goods-type basis too, to catch a situation like all the buses going one way and all the mail vans going the other.

Well this will be my challenge for this weekend :).

knightly

Quote from: yobbobandana on June 26, 2010, 02:01:48 AM
I preferred to pass by address just because it makes it more obvious that the variables will be changed, but I should've checked what the style was in other places :). I've updated this and as you say it's cleaner as such.

I see your point, and thanks for updating ;)


Quote from: yobbobandana on June 26, 2010, 02:01:48 AM
If I move it to part of the schedule then there is the question of if the direction is not the same, is it the same schedule?

According to your scheme, 2 schedules should be the same if they differ only by direction. Just as the current stop index (aktuell) is not checked in schedule_t::matches(), you don't need to check direction in that function.


Quote from: yobbobandana on June 26, 2010, 02:01:48 AM
In particular, I would probably leave the direction out of sprintf_schedule and sscanf_schedule, but I'm not sure whether this would be desired in all cases.

If I understand it correctly, sprintf_schedule() and sscanf_schedule() are for converting schedules to/from strings, a means of passing schedules when they are updated. It doesn't seem to be harmful at all to include direction as well. In sum, you may treat direction as a transient state much like aktuell. The advantage of putting the direction flag in schedule_t is that, you can encapsulate all processing and relevant data inside the same class, and you don't need to pass the direction flag every time.


Quote from: yobbobandana on June 26, 2010, 02:01:48 AM
True, the bidirectional flag should be part of the line. In terms of the UI though, even for lineless convoys you can "promote" their schedule to a line, so I'd need to find some better place of editing this. So far methods of editing the line just give you the schedule to edit, so in terms of the UI lines and schedules are almost identical.

Similarly for the direction flag, I couldn't see how to easily add it to the schedule editing UI without adding another row to the buttons at the top.

So I'm not too sure where it could be edited from.

I could possibly add another row for the active direction, and hide the "bidirectional" button for individual convoys. Then the bidirectional flag could sensibly be added to the line, and the direction flag to the schedule. I do like setting the direction from the convoy info window though.

IMHO it is not a good idea to forsake what would otherwise be the conceptually correct code structure just because of UI constraints. UI constraints can be overcome or circumvented. For instance, the bidirectional option can be placed in the header of the lower-right panel (where convoys are listed) inside the line management frame. Once the bidirectional option is removed from schedule gui, you have a free slot to put the direction option. Alternatively, you may still keep the direction option in the convoy info window for convenient checking and update -- you only need to change event handling code by calling the appropriate schedule_t functions.


Quote from: yobbobandana on June 26, 2010, 02:01:48 AM
Ahh yeah you're right... thinking about it I'll probably need to keep track of the served directions on a per-goods-type basis too, to catch a situation like all the buses going one way and all the mail vans going the other.

Good point about the good categories :) So, the bi-directional problem is really more complicated then it seems in the first place ...


Quote from: yobbobandana on June 26, 2010, 02:01:48 AM
Well this will be my challenge for this weekend :).

Good luck ;)

jamespetts

Quote from: Knightly on June 26, 2010, 08:48:28 AM
If I understand it correctly, sprintf_schedule() and sscanf_schedule() are for converting schedules to/from strings, a means of passing schedules when they are updated. It doesn't seem to be harmful at all to include direction as well. In sum, you may treat direction as a transient state much like aktuell. The advantage of putting the direction flag in schedule_t is that, you can encapsulate all processing and relevant data inside the same class, and you don't need to pass the direction flag every time.

These two methods are used for passing data accross a network/the internet for multi-player games (a feature that is currently work-in-progress in Standard). For the schedule feature to work with multiplayer games, any extra data must be transmitted through these methods.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

prissi

Since discussion is still going on, I will not commit it this week.

But in principle, a reverse flag should be a schedule option. For a line, it should indicate bidirectional operation. Thus the flag could be only interpreted differently for lines. Programmwise one could thing of an union (for those booleans). The prinf_schedule would just handle an additional boolean and only the context would give its meaning (make every second convoi with schedule revers flag set) or actually drive schedule reverse.

yobbobandana

I finished updating this yesterday, but as I ended up redoing almost the entire patch, it still needs testing and sanity-checking on my end.

I'll go over the changes I've made, so if anyone sees an obvious problem, or better way of doing it, let me know.

Tracking which goods are serving which directions for a line:

Currently goods served by a line are tracked via the uint8 vector "goods_catg_index".

I added two more of these to line_t: "fwd_goods_catg_index" and "rev_goods_catg_index" to track the goods served in each direction on the line.

The obvious alternative was adding a single vector representing the directions served for each entry in goods_catg_index, but it would have been more clunky to implement.

The worst effect of this is probably slowing down "line_t::recalc_catg_index()" as non-mirrored lines with both directions served will need to check all three of the vectors for changes.

With them, it's pretty easy to check whether any specific goods type is served in a specific direction by the line, and also whether a direction is served at all (just check if the appropriate vector is empty). I added functions for this and haltestelle_t::rebuild_destinations() now uses them.

Variable changes

bool convoi_t::reverse_schedule -> schedule_t::advance_reverse (direction flag)
bool schedule_t::bidirectional -> line_t::also_reverse (convoys added to line in both directions)
bool line_t::start_reversed -> removed in favour of using the line's schedule's advance_reverse flag

UI changes

Moved the "also reverse" button from fahrplan_gui_t to line_management_gui_t (so it doesn't show for individual convoys).

It's still in the same place, but I'll probably move it so that the advance_reverse flag can be edited from the schedule gui.

convoy_info_t still has the button to switch the convoy's direction. It updates the warenziele properly now when toggled.

Other

There were a raft of small changes too, mainly to support the variable reshuffling.

I'll post the updated patch once I've made sure it works as intended.


yobbobandana

Here's the updated patch.

I added another row to line_management_gui_t and put the "also reverse" button there. This allowed a button for the schedule's advance_reverse flag to be added to fahrplan_gui_t.

In the extra space I added a text box so that the line's name can be viewed and edited (useful for setting the name of a new line).

However I have a strange problem that the textinput element only accepts modifications if the depot window isn't open. I couldn't see any reason for this.

I changed line_management_gui_t::infowin_event to return the swallowed flag from fahrplan_gui_t::infowin_event so that key events were swallowed properly, but I might have done this incorrectly as I'm not too sure how the focus and event swallowing works. When the depot window isn't open, it works fine...

What do I need to do to make sure the textinput for the line's name correctly swallows keyboard events and edits the name?

Apart from this issue, everything I tested seemed to work.

Here's a screenshot of the updated line_management_gui and the patch.

PS: it's quite confusing that there are two different windows titled "Line Management".

knightly

Hi Yobbobandana

May I know, why do you change from "bidrectional" to "also reverse"? IMHO the meaning is not clear with "also reverse".

As to updating warenziele and routing, since now network mode is in place, any change that needs to be passed to connected players should go via the network interface with a tool. For instance, you have a button in the convoy info window to toggle the direction of the schedule, and the associated code does eventually initiate world update. However, other players will not be aware of the change as they are not notified of the change. For "also reverse", it is not part of schedule_t, so you need to include it as part of the change line tool parameter. For details, you may take a look at the WIN_CLOSE case in fahrplan_gui_t::infowin_event(), line_management_gui_t::infowin_event(), as well as convoi_t::call_convoi_tool(), wkz_change_convoi_t::init() and wkz_change_line_t::init()]

Hope this helps

Knightly

jamespetts

Yobobbandana,

is this now fully compatible with Experimental? This should be a very useful additional feature when complete (if not complete already)...
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Zeno

May I ask what happened with this patch? I wonder if it's just stopped due to holidays or if it's been abandoned...

prissi

It is part of experiemental. I tested this behaviour, and it had quite some unexpected behavoir, especially with trains. Thus I decided to not incorporate this in standard.

sdog

Quote from: prissi on February 02, 2012, 08:56:21 PM
It is part of experiemental. I tested this behaviour, and it had quite some unexpected behavoir, especially with trains. Thus I decided to not incorporate this in standard.

I think there is a point to this. Still this is the feature of experimental i miss the most when playing standard.


update the selection of correct platforms was moved from this patch into it's own development. (both are implemented in experimetnal though) discussion can be found here: [size=78%]http://forum.simutrans.com/index.php?topic=5285.msg51703#msg51703[/size]


The unexpected behaviour mostly comes from the exception in the code where a train does not call at the first suitable platform but continues to the platform specifically in the list when the latter is near enough. I should like to suggest to get rid of that exception alltogether.

Just let trains always call at the first suitable platform when reverse route or circular route flags are set, and the stop has no "wait 'till loaded" property.

The other source of unreliable behaviour is more difficult to fix, completely seperated circular lines do not work, if there is no connection between both ways, as a train has to way-find the route to the platform in the schedule. It will be much less of a nuisance when the previous thing is done. Since in that case players can connect bi-directional tracks directly after and before stations without disabling the patch.


ps.: this mostly is directed at experimental, but perhaps if it works better reliably it might be re-evaluated for standard?

omikron

The trains in experimental actually do stop at the first platform of the destination they pass through and ignore the scheduled stop.

See here: http://forum.simutrans.com/index.php?topic=9087.0

omikron

prissi

Standard had a defined behaviour in mind. Without choose signals any train (or car) will go exactly where ordered. This patch breaks this and can easily generate unsolvable deadlocks. I even posted about this several month ago in the experimental forum section.

Fabio

If there is ever going to be an automatic return path for trains, it'll have to be enforced in schedule, not during running.

I wonder, when I select the button for the return trip, couldn't the trip be simulated, ADDING TO SCHEDULE the first platform met?  It wouldn't be worse than now, and after schedule dialog is closed, the path will still be 100% deterministic...

Actually, pushing this idea a bit further, every new stop could be tested and an error risen if the previous stop and the new one are not connected...

jamespetts

Quote from: fabio on February 02, 2012, 11:40:12 PM
I wonder, when I select the button for the return trip, couldn't the trip be simulated, ADDING TO SCHEDULE the first platform met?  It wouldn't be worse than now, and after schedule dialog is closed, the path will still be 100% deterministic...

Won't this cause the exact same problems whenever the schedule is modified that this patch was designed to obviate in the first place?
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

sdog

@fabio
but then it would be the same inconvenient situation as now, where stops appear twice in a schedule. making changes in the schedule very difficult and the schedule list confusing.

much more "Tracking which goods are serving which directions for a line" would not work: http://forum.simutrans.com/index.php?topic=5262.msg52721#msg52721

Ring lines would still be impossible, as they are in standard now.

@prissi
"Standard had a defined behaviour in mind. Without choose signals any train (or car) will go exactly where ordered. This patch breaks this and can easily generate unsolvable deadlocks."

Together with the "call at first suitable platform that is passed" patch the train will still go the same route it would without those patches.  The only difference is, that it does not go all the way. The behavious is still well defined and deterministic. Wouldn't deadlocks become less likely, when trains allready halt when encountering a suitable platform instead of turning through stations to get to the designated platform?

Zeno

Mmmm... what about adding two tabs, one for the first run and other for the return path? This would avoid the confusion of having everything twice in the list and also the need of calculating the back path "on demand".

jamespetts

Quote from: Zeno on February 03, 2012, 08:50:30 AM
Mmmm... what about adding two tabs, one for the first run and other for the return path? This would avoid the confusion of having everything twice in the list and also the need of calculating the back path "on demand".

I suspect that this would be very confusing for new players.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Zeno

You're probably right. That second tab should be available only when clicked the "reverse" option, so the return path would be created in the second tab. I suspect that it would be hard to keep control there, as long as the route would be splitted somehow to allow editing in two different paths...

Fabio

Duplicated backwards stops (possibly using the pathfinding algorithm) could be flagged and appear e.g. in blue in schedule list.
Pressing Duplicate/mirror button, the last one in schedule will be flagged as end_of_line; start_of_line and end_of_line could appear in red. As it is now, start_of_line and end_of_line are not duplicated (for good reason)

Blue duplicated stops could then be customized as desired by the player (giving the same freedom as now, just default would be a more useful one). Maybe a Move stop button (move -> select in list stop to be moved -> click on the map where to relocate it) would be convenient as well.

Add stop button would add the stop BETWEEN end_of_line and first of duplicated, assuming the flag of end_of_line and duplicating the one which was previously end_of_line (becoming blue).

Insert stop button would work instead as it does now, and so would remove stop. This could allow for (partly) split paths.

Colours would give players a decent hint of what is first run and what is return trip and, most importantly, all this implementations would not affect ANYTHING outside schedule dialog.

jamespetts

But then, what happens when a player has edited the reverse portion of the route, then wishes to add a stop to the middle of the outward portion? How exactly will the programme handle that?
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Zeno

Well, when adding a new stop A after B and before C then the program should add a stop on the reverse after C, if C is found. We should expect it to be automatic, not to be intelligent :D

jamespetts

Suppose that we have a schedule like this:

A>B>C>B>A>B>D

and it is reversed. Suppose that we add a stop between B and C. How will the program deal with this if this suggestion is implemented?

Suppose further that the reverse portion only has been edited thus:

D>B>X>B>A>B>C>B>A

How would that be accomodated in the forward part of the shcedule if it, in turn, were amended thus:

A>B>C>B>A>B>Y>D

?

How, in other words, would the programme know (1) whether to add "Y" to the reverse; and (2) whether Y should go before or after X if it is added?
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

wlindley

How is it "not deterministic" to have, just like in Experimental, a flag that says whether to reverse the list, and a flag that simply says whether the next stop is "up" instead of "down" the list?  Why are we debating all this complexity, when Experimental's implementation is so simple and functional?

omikron

Apparently because prissi thinks it is not easily communicable to novice players, and I would agree with him. However, reversing as it works currently is not necessarily that much easier to undersyand and definitely more annoying since you have to change everything manually..

It is, however, possible to use both sets, as in exp currently. One may manually schedule the return trip, or one could use the 'mirror' function, if one understands how it works.

omikron

prissi

Instead of the return tircket option in the schedule one could add a return trip. THen one can promote this to a linge again and it will hail those stops.

But concerning automatic choosing: This will run into problems as soon as your stations are on sidetracks and the main track is a through track. With such a layout trains will go always to their station assigned, i.e. run always nearly a full circle on a circle line or go various turn on a two-way line. Exactly like those runaways trains in OpenTTD searching for depots at strange positions.

wlindley

Ah.  How about having only one check-box "Add Reverse Trip" which would show, in a different color, the reverse stations after the final station.  The "next stop" indicator could be set to any of those automatically-computed stations, but they would not be editable.  Editing the actual stations would adjust the reversed stations.

omikron

That's a good idea, wlindley, but it doesn't solve the problem with different platforms. We would have to add the exp-behaviour in that case, and it woudl all be back to the old debate.

omikron

wlindley


Fabio

If we use routing for finding next return stop (to be added to the schedule list), couldn't we do like this?

Find Platform:
   - try default platform
   - if default platform is one way (wrong direction), try another platform
   - if next next stop is met in the path, try another platform
and so on

sdog

The automatic platform choosing is not absolutely nevessary for this. It can be easily worked around. (See posts on first page)

A slight change to platform chose signals would also be a possibility.

Please dont forget, that the current replicate backward causes the same chaos on bi-directional train lines.
Regardless of those platform difficulties, isn't it by far the clearest UI sollution to run the schedule in reverse, instead of adding duplicated stops automatically?


prissi

I tried to remove the replicate backwards button countless times. But player voted for it.