Push-pull

1.8 introduces in-place train flipping, allowing trains to reverse without having to “bounce” off a track or platform end, which has been a meme in the game since 1.1 days. After 1.8 stabilized during its beta period it was time to implement the next step of this feature: push-pull. Push-pull capable train sets can change direction without reorienting and without rearranging their cars and locomotives. The game has an explicit flag to mark these kinds of trains, and it also assumes any train with a locomotive or control car a both ends of the train is also capable of push-pull, even without the flag. All the foundation work was prepared and tested as part of other 1.8 features so it was straightforward to enable this. A boolean flag is kept per train, and it is negated every time a train reversal happens. Then the code which projects the train on the tracks checks the flag, and does the projection starting at the end or the front, depending on its value.

Partial multithreaded signal processing

Train AI has evolved in the last few versions of the game to be massively multithreaded, including areas which were initially looking very hard to parallelize, like track reservation. But one area has remained single threaded: signal checking. Every train which is about to cross a signal, or which is already waiting at one, is moved out of the parallel processing loop and into a final, single threaded loop, which is run after all the parallel trains are processed.

Signal checking requires the assurance no other indeterminate train is also trying to reserve or check on the checked path. Giving this assurance in the parallel section of the train AI is computationally equivalent to just doing this processing in a single thread (and much simpler too).

But on thinking on this problem a bit more, I realized there’s at least one thing trains can do in parallel: use the last frame reservation/occupation track map (complete and immutable, but out of date) for signal checks in parallel, but only accept the result if a reservation or occupation is found. If the path is clear, do not trust the result, and move themselves into the single thread queue for later processing. This means there’s less trains to process in the single thread part and it finishes earlier (to give you an idea, in a save with thousands of trains and 8 CPU cores, the parallel part and the single threaded part usually take the same time, despite the parallel part processing 8 times more trains). This is working fine and it gives some speedup, but more importantly it get me thinking to further parallelize signals based on the concept of separate reservation maps.

And I did find a way to make all signal processing parallel. If the previous idea could be called pessimistic (it only accepts a negative result), the new idea builds on top of it by being optimistic: if the pessimistic check finds the way to be clear, then a path is reserved, assuming it is really clear. But crucially, this path is reserved in a separate track map, the speculative reservation map, and it is tagged with the train ID. After all the trains in a thread are done, but before the thread ends, the thread spins in a semaphore waiting for all the other threads. When this wait is done, it means there are no more speculative reservations to do, and every thread then start scanning the speculative reservations of the trains they control. This check compares the train IDs of reserved and overlapping segments, and selects a winner with the simple criteria of the lowest train ID. After this processing is done, a list of winning and losing trains is ready. Losing trains are stopped at the signal, and winning trains are allowed to keep moving (or start from a signal stop).

And it worked! It was quite interesting to see such a interdependent simulation be 100% multithreaded. But in the end it had a flaw, and I had to disable it: it assumes only one signal will be checked per train per simulation frame. For trains traveling at high speed and crossing over closely spaced signals this is not true (sim frames max out at 1.6s max, plenty of time to cross over two or more signals at 300 km/h in the game world, but probably not in the real world). Salvaging the feature would have required to introduce some irregular motion in these cases, and I decided to not do it in the end.

Train destination advance on departure and train picking experiments

A goal of 1.8 was to make timing, lines and trains behave more intuitively. Push-pull and line stops timing based on the exact point of stop are examples of it. The final item in this theme for 1.8 was to make train destinations change at the time of departure, rather than at the time or arrival. This is more of an aesthetic feature, since trains have since 1.5 had a separate dedicated “pax current stop” data structure, properly set to the line stop, so pax have been ignoring the current train destination for quite some time. But after this change train AI and pax AI concept of waiting stop finally match.

Implementing this feature had some unintended fallout in other areas, like some code which previously kicked out pax when a train line changed into a depot line not working anymore. This got me thinking into the reasons to have such code, with pax being so stiff about boarding trains, then I remembered about the actually very loose criteria pax use to pick a train, just checking line and stop. I’ve had a steady flow of bug reports about this, specially from players making sophisticated use of orders, so I decided to enable strict train picking in pax AI. And it worked, but it also turned out many player saves depend on the buggy behavior.

(1.9) Late train boarding for pax

I really want to remove line+stop picking and replace it with strict train+run+stop picking, which will finally make pax pick the exact train they need in their trip. But since pax refuse to board late departure trains, some player saves depend on the buggy behavior of pax to not collapse. So for 1.9 I looked into what it would take to allow some form of late train boarding for pax, while enabling strict train matching.

The key is to come up with a robust set of rules which is consistent with the pax path system, and which is not dynamic, to avoid all the “fun” pax-in-circles situations from pre 1.5 times. And it turns out it is possible to come up with a rule to allow late boarding, which is 100% static (like the timetables): a pax can board a late train if the predicted arrival into the next stop of its trip happens before the departure of the next train of its trip. It is advisable to add some pad time, since pax deciding to board an already late train arriving just 5s before their next train departs are likely going to miss it. This rule also fails for pax whose next stop is their final destination, so in this case an arbitrary rule can be applied: allow the maximum station wait for a pax, so trains delayed up to 3h are acceptable in this case.

A set of rules exists now. But pax only lookup a single path, based on the time of the week. If pax had to also lookup paths in the past when they face a delayed train (based on the scheduled time of the train, not the current time), the performance of the game would collapse. Additionally the pax path system is entirely dependant on the extremely effective (99.9% hit rate) station destination cache, which only stores the single dominating train+run+stop for a given destination, and discards it when its time of departure is past. To enable late boarding this cache system had to be reviewed to support multiple trains per destination, and to have two concepts of expiration: dominating expiration and late boarding expiration (these are the “scheduled” and “max late” columns in the screenshot, displayed as countdowns):

This table shows the content of the destination cache for a given station. Let’s look at the entries which will deliver the pax to Mollet. VRMC-0017 has two entries in this case. One is for a direct link to Mollet, which is a stop in the line. This stop scheduled departure is already in the past, as evidenced by the red -5s countdown. But its maximum late boarding countdown still shows almost 3h of time left, by application of the rules. The same train is also interesting for some pax which want to go to Santa Mogoda. This station is not the V2 line, so Mollet will be a transfer stop for these pax. It is the same train on the same line and run and stop, so the stop scheduled departure is also -5s. But the maximum late boarding shows a very different number than before, with just 1:37 left. This means that pax who want to go Santa Mogoda will consider boarding this train if it manages to arrive to and depart from Glories in the next 1:37, but not one second later, because doing so would guarantee they will miss their connection in Mollet.

The system is now place in 1.9 and working very well, so pax in 1.9 will be strict-only. But it does have a flaw: since it is a cache, it is empty on load. The dominating paths will be filled immediately the moment the simulation starts running trains in stations, but at this moment there is no effort to “backfill” the cache with late train departures for newly loaded games. I will consider doing later this if the performance impact is not too bad.

(1.9) N-track platforms

Track+point pathfinding opened the door to many simulation improvements in 1.8, but not everything made it for 1.8. I originally wanted to revamp line stop points too, but there’s was already a lot of changes, so I left it for 1.9. The first step for this change is not actually in line stops. It is in the track platforms themselves and the concept of platform, which in 1.9 will be just any sequence of 1 to N track segments (the overlapping station name and node will be fixed):

This means platforms do not ever need to be a pair of track segments. Maximum platform length will still be enforced, as the non-branching and restricted signal support. The default station will still create 2 track platforms, and players will need to use track promotion or the platform tape tool to create platforms with 1 or more than 2 tracks.

(1.9) Track+point line stops

1.9 line stops store the stop position for trains as a point in a track, with a direction, and a certain length (matching the line reference train length by default). This is in fact also the case 1.8, but unlike 1.8, 1.9 will expose this in the UI for players to pick these specific points and directions when setting up a stop. You can think about it like if every line stop in every line had its own private platform stop signal. The easy single mode from 1.8 and earlier will still available and enabled by default, with the game automatically finding some reasonable point of stop and showing an arrow button, just like it did in 1.8. But switch to the 1.9 mode and the arrows disappear, and you can click on any point of any platform track, like if you were setting a signal.

The 1.8 mode will have one extra trick: it will retain the capability of auto centering trains. Stops set in this mode in platforms without platform stop signals (the default in the UI and also for all imported 1.8 lines) can ignore the track+point and move the point so the train appears centered in 2 track platforms. Stops set in 1.9 mode will never recenter the train, but will display a preview of the reference train length while setting up the stop.