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: Allow automatically separating vehicles in shared orders #8342

Closed
wants to merge 8 commits into 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.

Outstanding issues - #8342 (comment)

  • When should automatic separation be unavailable?
  • Integration with timetables
  • Queuing detection and behaviour

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

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 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

Choose a reason for hiding this comment

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

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 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

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 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 commented Dec 10, 2020

Always :)

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

twpol commented Dec 10, 2020

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

@andythenorth
Copy link
Contributor

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 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

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 Show resolved Hide resolved
@TrueBrain TrueBrain added candidate: yes This Pull Request is a candidate for being merged size: small This Pull Request is small, and should be relative easy to process labels Dec 14, 2020
@andythenorth
Copy link
Contributor

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

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

Choose a reason for hiding this comment

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

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
src/order_gui.cpp Outdated Show resolved Hide resolved
src/saveload/saveload.h Outdated Show resolved Hide resolved
src/vehicle.cpp Outdated Show resolved Hide resolved
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

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

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 Outdated Show resolved Hide resolved
@TrueBrain TrueBrain added the work: minor details This Pull Request has some minor details left to do label Dec 15, 2020
@twpol twpol force-pushed the feature/automatic-separation branch from c47f488 to aac99f5 Compare December 15, 2020 22:31
@TrueBrain TrueBrain added the preview This PR is receiving preview builds label Dec 15, 2020
@DorpsGek DorpsGek temporarily deployed to preview-pr-8342 December 15, 2020 22:34 Inactive
@twpol
Copy link
Author

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

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 December 21, 2020 15:49
@TrueBrain TrueBrain removed their request for review December 21, 2020 20:06
@2TallTyler 2TallTyler added this to the 14.0 milestone Dec 21, 2023
@twpol

This comment has been minimized.

@JGRennison

This comment has been minimized.

@2TallTyler

This comment has been minimized.

@twpol
Copy link
Author

twpol commented Dec 22, 2023

Changing first_order_last_departure to use type TimerGameTick::TickCounter instead would mean that you don't need to do anything in ShiftDates at all. now would then be TimerGameTick::counter instead of needing to calculate a DateTicks total from date and date_fract. This would probably also make things more future-proof with respect to upcoming changes,

Done.

@twpol
Copy link
Author

twpol commented Dec 22, 2023

Unless I am mistaken, the remaining issues (excluding any bugs/issues spotted in the code itself) are:

When should automatic separation be unavailable?

  • Conditional orders: they are not guaranteed to make the order duration unstable, but it seems likely that they will.
  • Fully filled in timetable: (see below) this might be made to work.

Integration with timetables

A timetable with all numbers filled in except the wait time at the first manual load/unload order is expected to function correctly with automatic separation as it is currently. If the timetable is completely filled in, it will stop working correctly. Should we disable automatic separation or try adjusting the timetable departure time/lateness to do separation?

Queuing detection and behaviour

The algorithm for calculating queuing vehicles is certainly not completely accurate, but so far it is the best heuristic we have. We need to adjust for queuing road vehicles (playtesting shows this). But what about other vehicle types?

@TrueBrain TrueBrain changed the title Feature #8095: Allow automatically separating vehicles in shared orders Feature: Allow automatically separating vehicles in shared orders Dec 22, 2023
@twpol
Copy link
Author

twpol commented Dec 22, 2023

A timetable with all numbers filled in except the wait time at the first manual load/unload order is expected to function correctly with automatic separation as it is currently. If the timetable is completely filled in, it will stop working correctly. Should we disable automatic separation or try adjusting the timetable departure time/lateness to do separation?

Looks like if I update the lateness_counter based on the expected next departure time vs now, at the same point it is calculating when automatic separation wants the vehicle to depart (i.e. when loading/unloading completes), it works with fully timetabled vehicles. They'll be early or late throughout their orders as normal but will always leave the first manual load/unload order on time or late (if the gap to the previous vehicle is more than the desired separation).

@2TallTyler
Copy link
Member

2TallTyler commented Dec 22, 2023

That timetable implementation should work, yes. It is mostly unnecessary to use timetables and auto-separation in this way, but I see no reason to restrict users from using both at once. I could certainly see some "realism" gameplay that uses both and using both is somewhat error-proof since auto-separation just keeps timetabled vehicles spread out.

Edit: You may be able to use lateness_counter to space out vehicles leaving the first station, instead of adding a second way of delaying vehicles. This could be cleaner if you're updating lateness_counter anyway.

@2TallTyler
Copy link
Member

Hello, I hope you had a good holiday. Just as an update, we are looking at doing a 14.0-beta1 release as early as next week so we can start testing a few big PRs. That doesn't preclude this PR making it into 14.0-beta2, but I wanted to explain this all to you so you don't see beta1 and get discouraged. 🙂

In response to your comment above regarding outstanding issues, I think you are correct.

  1. Regarding conditional orders, I would not bother with them for now. You could just disable auto-separation if there's conditional order. You'll have to add an error message that's triggered both when trying to enable auto-separation on a vehicle that has a conditional order, and when you add a conditional order to a vehicle that has auto-separate already enabled.
  2. Regarding timetabling, it sounds like you're on the right track with lateness_counter. I'll be interested to see your results.
  3. I have no issue with your heuristic, but it does need testing. Once you deal with points 1 and 2, I can set up a public test game (as we did for Feature: Region-based pathfinder for ships (buoys no longer required!) #10543 and will do this weekend for Feature: Setting for minutes per calendar year #11428) and see if anyone can break it.

I don't know your availability over the next couple weeks, but I'm around and am happy to do my end of the work. I am very excited for this PR and would really like to see it in 14.0 if you have the time. 😃

@2TallTyler
Copy link
Member

Hi @twpol, I hadn't heard from you and was thinking about how I might help finish this when I had a spark of inspiration: Most of the attempts at autoseparation run into issues with gridlock at the point where vehicles wait. In your case, it's the first order and you have some logic that tries to break up logjams, but this is hard to test.

So I thought, what if we did the autoseparation delays inside the infinite-capacity-wormhole of a depot? Instead of a toggle on the vehicle orders for autoseparation (we're rapidly running out of space for a button), add that behavior to the depot itself similar to how you select service and refit behaviors, where we have plenty of button space.

I've started working on this approach, and although it's in rough state and doesn't work properly, I like the approach enough to continue working on it. Feel free to let me know your thoughts: https://github.com/2TallTyler/OpenTTD/tree/depot-autoseparation

@twpol
Copy link
Author

twpol commented Feb 4, 2024

Oh, urgh, I did not see any of these recent messages. Not a fan of the depot approach, at all, but it seems I'm too late to avoid that being the chosen solution here?

I really wanted a single button (which could be auto-on with a user setting) to do this. 😭

@2TallTyler
Copy link
Member

Yes, sorry. We released OpenTTD 14.0-beta1 yesterday, with the depot approach.

@twpol
Copy link
Author

twpol commented Feb 4, 2024

Does that mean there is no way forward for this PR/approach now?

@2TallTyler
Copy link
Member

2TallTyler commented Feb 5, 2024

No way that I can see, no. Sorry!

@twpol
Copy link
Author

twpol commented Feb 6, 2024

Okay, that's devastating. We were so close to achieving a great outcome and now it looks like OpenTTD is stuck with an option that doesn't satisfy my desires, needs an extra hoop-jump for every route, and I think even needs more vehicles for the same throughput (at least for trains) due to the extra entry/exit time of the depot.

It should be clear why I won't be attempting any further contributions to OpenTTD.

Goodbye.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
candidate: yes This Pull Request is a candidate for being merged preview This PR is receiving preview builds size: small This Pull Request is small, and should be relative easy to process work: minor details This Pull Request has some minor details left to do
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet