Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Feature #8095: Allow automatically separating vehicles in shared orders #8342

Open
wants to merge 7 commits into
base: master
Choose a base branch
from

Conversation

twpol
Copy link

@twpol twpol commented Nov 17, 2020

This is my proposed code for allowing vehicles (of all types) to be automatically separated amongst their shared orders with the click of a single button (once for each shared order), to massively reduce the micromanagement needed for optimal passenger journeys.

I filed issue #8095 initially to check that the feature was acceptable, and it was suggested I go forward with a PR.

As this is my first-time contributing code to OpenTTD, even though I have read the contributing guidelines and linked materials, I will also probably have missed/misunderstood something so please let me know where and how I might have messed up.

As part of that, I have tried to document the algorithm itself and surrounding code with comments but if anything isn't clear, or the details would be better served elsewhere, let me know.

src/base_consist.h Outdated Show resolved Hide resolved
@twpol twpol force-pushed the feature/automatic-separation branch from 2999e3b to df56e94 Compare Nov 17, 2020
@James103
Copy link
Contributor

@James103 James103 commented Nov 17, 2020

Commit messages must follow a specified format. Instead of "Update ...", you should either merge that commit into your previous commit or use a commit message that's something like "Fix: grammar".

@twpol
Copy link
Author

@twpol twpol commented Nov 17, 2020

Commit messages must follow a specified format. Instead of "Update ...", you should either merge that commit into your previous commit or use a commit message that's something like "Fix: grammar".

Yes, that's Github's fault because I simply clicked to apply the suggested fix and it wasn't in that form. I fixed it locally and pushed an updated version now.

Copy link
Member

@LordAro LordAro left a comment

Thanks for this! Code looks fine on brief inspection. Will require some actual testing though :)

src/saveload/saveload.h Outdated Show resolved Hide resolved
src/vehicle.cpp Outdated Show resolved Hide resolved
@andythenorth
Copy link
Contributor

@andythenorth andythenorth commented Dec 10, 2020

Testing this, I got an assert, but I do not know if that is related to the current mac build, or specific to this PR :)

I've seen the assert twice in short succession. I can't get it to trigger in current master using same savegame.

Crash log attached; the savegame will be pretty useless, it contains multiple unreleased grfs.

Archive.zip

@JGRennison
Copy link
Contributor

@JGRennison JGRennison commented Dec 10, 2020

Testing this, I got an assert, but I do not know if that is related to the current mac build, or specific to this PR :)

I've seen the assert twice in short succession. I can't get it to trigger in current master using same savegame.

Crash log attached; the savegame will be pretty useless, it contains multiple unreleased grfs.

You'll probably want to locally cherry-pick c98717c for testing on Apple/LLVM.

@twpol
Copy link
Author

@twpol twpol commented Dec 10, 2020

You'll probably want to locally cherry-pick c98717c for testing on Apple/LLVM.

Would it be helpful for people testing if I rebased this PR onto that commit (or another newer commit)?

@LordAro
Copy link
Member

@LordAro LordAro commented Dec 10, 2020

Always :)

@twpol twpol force-pushed the feature/automatic-separation branch from 139dbb5 to 4e97ebd Compare Dec 10, 2020
@twpol
Copy link
Author

@twpol twpol commented Dec 10, 2020

@andythenorth Hopefully the builds just generated will be more successful for you. 🙂

@andythenorth
Copy link
Contributor

@andythenorth andythenorth commented Dec 10, 2020

No assert. UI seems straightforward.

Simple case works as expected for me in test cases with ships, trams, trains. No full load orders, no explicit timetable, no conditional orders. Works great.

Cases that were expected to 'break' the separation and do:

  • using full load orders on some stations
  • setting wait times at some stations

Cases I thought would break, but appear to work:

  • 3 different tram routes, each busy, all including an order for the same 1 tile station; separation appears to be maintained well for all 3 routes
  • 1 route severely overloaded with trams, with close stations so that tram jams can block station exits; the algorithm handled this surprisingly well; there were still jams, but trams mostly spaced out well

Cases I didn't try that I would expect to break:

  • conditional orders

@twpol
Copy link
Author

@twpol twpol commented Dec 12, 2020

I'm glad things went well; your results are mostly what I'd expect.

To expand a bit on the expectations from me:

  • Full load is itself a separation method, so it's not compatible. I don't see a reasonable way to use both features together, and automatic separation was inspired by the difficulty in vehicle spacing in cases where full load is not appropriate. I'm open to making this explicit in the help text and/or UI, e.g., by disabling the automatic separation button if there are full load orders.
  • An explicit timetable is also currently not compatible, but I wonder if we could reset the timetable lateness via automatic separation to make them work together?
  • Conditional orders might be okay if there is a stable average journey time for the group of shared order vehicles (e.g., each vehicle always takes the same route). If that average is unstable (e.g., routes are based on demand), you'll have problems with automatic separation.

However, I'm particularly intrigued by this:

  • setting wait times at some stations

Are you referring to setting the stay time at a station in the timetable? In my testing, this seems to behave itself. It makes the vehicles wait for the timetabled time instead of their loading time, but that time is all included in the automatic separation measurement of journey time, so the automatic separation waits at the first station take account of that.

Where you might have problems, is if the wait time causes vehicles to queue up on the approach to the first order station. In this scenario, automatic separation believes itself to be responsible for that queue and reduces the wait times accordingly.

@2TallTyler
Copy link
Member

@2TallTyler 2TallTyler commented Dec 14, 2020

I agree about disabling the automatic separation button if there are full load orders. Is it possible to have a tooltip explaining why the button is greyed out?

src/vehicle.cpp Outdated
* vehicles, so that the extra time queuing does not have an adverse effect on separation */
int round_trip_time = round_trip_count > 0 ? round_trip_sum / round_trip_count : 0;
int vehicles = vehicles_operating + vehicles_queuing;
int separation = max(1, vehicles > 0 ? (int)(round_trip_time * ((float)vehicles_operating / vehicles) / (int)vehicles) : 1);
Copy link
Contributor

@ldpl ldpl Dec 14, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Shouldn't be using float as it's not desync-safe. Also wouldn't hurt to add a comment why exectly are queeing vehicles a problem and how is extra (vehicles_operating / vehicles) solving it.

Copy link
Author

@twpol twpol Dec 15, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I've removed the float usage and refactored the code and written a big comment which, I hope, explains the algorithm and logic behind it. It's slightly altered from the version reviewed here, but play tested to be suitable and is easier to explain. 🙂

@TrueBrain TrueBrain added candidate: yes size: small labels Dec 14, 2020
@andythenorth
Copy link
Contributor

@andythenorth andythenorth commented Dec 15, 2020

Where you might have problems, is if the wait time causes vehicles to queue up on the approach to the first order station. In this scenario, automatic separation believes itself to be responsible for that queue and reduces the wait times accordingly.

Yes this is exactly the case. I set a wait at the first station in the order, and the station (roadstop) has capacity for 1 vehicle. I don't have the savegame, and I can't remember the exact outcome, but I could try and repro if it helps. However I had no expectation that case would be handled, and I don't think it needs to be.

@TrueBrain
Copy link
Member

@TrueBrain TrueBrain commented Dec 15, 2020

Would you mind rebasing your Pull Request? It would allow us to create a preview (new feature). Tnx :)

Copy link
Member

@TrueBrain TrueBrain left a comment

Did not test it yet; will do after you rebase. Some minor coding style thingies, but overall it looks really good :D Happy to see such a clean implementation of such feature :) Awesome work, tnx!

src/command.cpp Outdated Show resolved Hide resolved
*/
void OrderClick_AutomaticSeparation()
{
if (DoCommandP(this->vehicle->tile, this->vehicle->index, !this->vehicle->AutomaticSeparationIsEnabled(), CMD_ORDER_AUTOMATIC_SEPARATION | CMD_MSG(STR_ERROR_CAN_T_DELETE_THIS_ORDER))) {
Copy link
Member

@TrueBrain TrueBrain Dec 15, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The error message seems wrong for this command?

Copy link
Author

@twpol twpol Dec 15, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ah, I forgot this. But I am also not sure what error message, if any, should go here. The command can only fail if you don't own the vehicle or try and run it on a non-primary vehicle, neither of which I believe to be possible through the GUI.

For now, I've removed the error message here, but please do let me know how this should be handled if that's not right.

src/saveload/saveload.h Outdated Show resolved Hide resolved
src/vehicle.cpp Outdated
* to over-compensate rather than aim exactly for the ideal (which is very approximate here). */
int round_trip_time = round_trip_count > 0 ? round_trip_sum / round_trip_count : 0;
int vehicles_moving_ratio = max(1, vehicles - 2 * vehicles_queuing);
int separation = max(1, vehicles > 0 ? ((round_trip_time * vehicles_moving_ratio) / vehicles) / vehicles : 1);
Copy link
Member

@TrueBrain TrueBrain Dec 15, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

a * b / c / d == ((a * b) / c) / d. Adding those extra () doesn't add anything, but it suggests it does, confusing the reader it is something special. I suggest removing them :)

Copy link
Author

@twpol twpol Dec 15, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It's been a while since I did C++ like this, thanks for reminded me; parentheses removed.

this->first_order_last_departure = max(last_departure + separation, now);

/* Debug logging can be quite spammy as it prints a line every time a vehicle departs the first manual order */
if (_debug_misc_level >= 4) {
Copy link
Member

@TrueBrain TrueBrain Dec 15, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Who is going to be the user of this debug statement? I ask, as I wonder if it is useful to keep in now you did your initial work? Honest question, more of thinking out loud :)

Copy link
Author

@twpol twpol Dec 15, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It's a good question. 🙂

Honestly, I'd like to keep the code, both for future development and curious/bug reporting users, but debug misc=4 might well be the wrong door to put it behind.

A higher debug misc level, or a compile-time constant (if OpenTTD uses those for debugging code)?

src/vehicle_base.h Show resolved Hide resolved
@TrueBrain TrueBrain added the work: minor details label Dec 15, 2020
@twpol twpol force-pushed the feature/automatic-separation branch from c47f488 to aac99f5 Compare Dec 15, 2020
@TrueBrain TrueBrain added the preview label Dec 15, 2020
@DorpsGek DorpsGek temporarily deployed to preview-pr-8342 Dec 15, 2020 Inactive
@twpol
Copy link
Author

@twpol twpol commented Dec 15, 2020

Did not test it yet; will do after you rebase. Some minor coding style thingies, but overall it looks really good :D Happy to see such a clean implementation of such feature :) Awesome work, tnx!

Thanks!

Rebased onto latest code and fixed everything I can, further suggestions welcome.

@andythenorth
Copy link
Contributor

@andythenorth andythenorth commented Dec 18, 2020

I saw this deadlock, with all separated vehicles waiting in stations. Using 'stop all vehicles' and 'start all vehicles' (for each vehicle type) cleared it.

Happened after loading a savegame, but that might be coincidence.

I can't repro by reloading the save. The savegame also uses unreleased grfs and grfs have been reloaded many times, so it's not helpful for debugging.

Probably not much you can do with this report, but if I see it again, I'll try and get a repro.

@twpol twpol requested a review from TrueBrain Dec 21, 2020
@TrueBrain TrueBrain removed their request for review Dec 21, 2020
@twpol
Copy link
Author

@twpol twpol commented Dec 23, 2020

Rebased onto latest code and fixed everything I can, further suggestions welcome.

@TrueBrain Are further changes needed? I've commented on and updated everything I can, so I am not sure what is expected of me next, if not for another review pass.

@TrueBrain
Copy link
Member

@TrueBrain TrueBrain commented Dec 23, 2020

No, you are good for now :) We now have to review the code, and talk over what we think about a feature like this. Sorry, the removing of "reviewer" is just as I don't want others to think I am going to do it; I might, but it can also be another dev'er :P

If you have any idea why the problem that @andythenorth happened, that would be great too.

@twpol
Copy link
Author

@twpol twpol commented Dec 23, 2020

Okay, great, thanks!

I'll see if I can figure out what happened with #8342 (comment)

@DorpsGek DorpsGek temporarily deployed to preview-pr-8342 Dec 27, 2020 Inactive
@twpol
Copy link
Author

@twpol twpol commented Dec 27, 2020

I haven't been able to figure out a possible cause of the deadlock in #8342 (comment) :(

I've made some small improvements to the code and am going to rebase onto the latest code now.

@andythenorth
Copy link
Contributor

@andythenorth andythenorth commented Dec 27, 2020

I haven't been able to figure out a possible cause of the deadlock in [#8342 (comment)]

Some things don't get a reliable repro unless they get enough players using them. The deadlocks were trivially resolvable by using stop-all, start-all for each vehicle type.

My vote would be (if this passes review) to push it to a nightly and let players find out if the deadlock recurs. That has the risk we have to back it out, causing disappointment, but eh, fair gamble. Also...not my decision anyway :)

@JGRennison
Copy link
Contributor

@JGRennison JGRennison commented Dec 27, 2020

Without having tested it yet, in its current form this is very likely to go wrong if the date change cheat is used.

You will need to adjust first_order_last_departure in all cases where the date is changed.
e.g. OnNewYear (when MAX_YEAR is reached), SetStartingYear and ClickChangeDateCheat.

/* Check this feature is enabled on the vehicle's orders */
if (!this->AutomaticSeparationIsEnabled()) return;

/* Only perform the separation at the first manual order (saves on storage) */
Copy link
Contributor

@JGRennison JGRennison Dec 27, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The first manual order is not necessarily a suitable point to wait.

In particular it would be advisable to also exclude waypoint orders, conditional orders and depot orders.

if (!(v->vehstatus & VS_STOPPED)) {
vehicles++;
/* Count vehicles queing for the first manual order but not currently in the station */
if (v != this && v->cur_speed == 0 && v->cur_implicit_order_index == first_manual_order && !v->current_order.IsType(OT_LOADING)) {
Copy link
Contributor

@JGRennison JGRennison Dec 27, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

What's the rationale for this heuristic?

That a vehicle is stopped somewhere does not necessarily imply that it is queuing immediately before the target station.
If a train is quite normally stopped at a red signal en-route it would have a disproportionate effect on the separation.

@JGRennison
Copy link
Contributor

@JGRennison JGRennison commented Dec 27, 2020

ResetAutomaticSeparation should probably also be called when skip or go to/service at depot commands are called. (CmdSkipToOrder and non-order parts of Vehicle::SendToDepot).

@JGRennison
Copy link
Contributor

@JGRennison JGRennison commented Dec 27, 2020

You might want to consider disabling separation if conditional orders are present, as the RTT estimation may produce nonsensical results.

@JGRennison
Copy link
Contributor

@JGRennison JGRennison commented Dec 27, 2020

Adding or removing a vehicle to/from shared orders should probably also call ResetAutomaticSeparation.

if (ret.Failed()) return ret;

if (flags & DC_EXEC) {
vehicle->SetAutomaticSeparationIsEnabled(p2);
Copy link
Contributor

@JGRennison JGRennison Dec 27, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

If automatic separation was previously enabled, this should probably call ResetAutomaticSeparation, as otherwise any old values left in first_order_last_departure will take effect and cause bugs.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
candidate: yes preview size: small work: minor details
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

10 participants