More pax pathfinder features

In addition to the new board and disembark options developed in December, I also tackled two additional major changes to the pax pathfinder prior to the 1.11 beta release.

Pax pathfinding can now consider a pax staying inside a train for more than 2 train runs. This limit has been in the game since 1.5 and it is now finally removed. The pax pathfinder can now plan a path leg which keeps the pax inside the train until the train starts a technical line or an already visited station appears (not just the boarding station), whichever comes first, over any amount of train runs, including an entire week worth of them.

But this new capability means two trains doing the same run cannot be considered to be equal. Or two runs, or even ten. The full ride must be scanned until the leg finalization rules apply. And not being able to ignore trains doing the same itineraries would slow down the pathfinder. So a new system of hashes over train rides has been implemented. Basically every train departure from every station now has an associated unique hash, which comes from the sequence of stops and the times of arrival. This would be actually quite useless if it wasn’t for the fact there is a clear rule on to when to stop considering such a train ride: the train re-visits a station, or it starts a tech line. The probing and hashing of train legs stops when these conditions hold, and this is precalculated as part of the timetables. This makes it possible for pax to quickly evaluate if two (or more) given departing trains are in fact doing the same route from their POV, and then discard any later duplicates. This greatly cuts down on the amount of train rides the pathfinder will explore while making it possible to consider any train (unique) train ride.

“Figure 8” or “pretzel” shape lines are now better supported. These lines, in conjunction with single line stations, have had limited support in the pax pathfinder. In 1.11 the game is able to detect more cases of a transfer station, including cases of a line crossing over itself on the same station, or a common looking line having a single direction loop in one end (in this case, the station(s) just before the loop are marked as transfer). This means there are now some cases where pax can disembark in a station and pick a train of the same line, to avoid the loop part of a “figure 8” line for example.

These lines have been challenging since a very major optimization of the pathfinder is to divide stations in two groups: transfer and non-transfer. Only transfer stations are considered as intermediate stops in a multi leg path. The timetable rebuild applies a simple heuristic to decide if a station is transfer or not: two or more different lines visit it. If only one line visits a station, it is not a transfer station. In 1.11 this heuristic is now more complicated for the case of only one line visit, with two extra rules. The first, if a line visits a station three times or more, then it is considered a transfer station. The second, even if it’s a single line, and it only stops twice, the station would be considered transfer if the previous or next station in the line only have a single stop (imagine the center of the “8” shape).

Tunable pax pathfind heuristic

The pax pathfinder heuristic is a number, ideally for every possible pair of stations in the map, which informs the pathfinder of what is the shortest possible trip time for the whole week. This is the hint the pax pathfinder uses to explore possible train legs while finding a path, and it must be an admissible heuristic. Unfortunately it is not possible to calculate this number without taking multiple minutes of real time for any medium or larger save, since it is equivalent to finding all paths for all stations for the whole week. Instead another number is derived: the shortest sum of leg times between stations, without waiting times. These sums do not reflect any real path time, but they remain admissible since they won’t ever overestimate a possible path. Unfortunately they make the pathfinder slower, making it explore lower quality paths compared to what the real heuristic would.

A trick to make this alternative heuristic faster is to multiply it by a bias factor. The larger number makes. But it also means it can sometimes pick paths which are not the optimal path, since it will be the case in some instances that the heuristic is a slower value than the real optimal path.

In 1.11 it is now possible for players to tune this bias down if desired. Turning the bias all the way down to 0 makes the sim slower (quite a bit), but means the heuristic becomes fully admissible again, and excepting bugs, pax paths should always be optimal paths. In practice this problem almost doesn’t exist, and so far I’ve only seen it reported in very large, very complex saves. Even in these cases it’s not needed to go all the way down to zero. For this reason the bias remains at 100% by default.

Speed controls in shared sim multiplayer

Being able to change the sim speed inside a shared sim multiplayer session has bee requested for a long time, and it is now implemented in 1.11. The hoster of a shared sim session now has speed controls, including pause. These apply almost immediately and the game remains usable at all sim speed levels, including pause, CPU allowing. Internally this has been prepared as part of the 1.11 multiplayer changes. The hoster server thread has full control over the clients sim clocks. Basically no client is allowed to simulate a game frame unless the server tells it to do so. Based on this system, changing speeds or pausing is just a matter of the server not sending new frame commands to the clients. Also new in 1.11 is the fact editing commands are coupled to simulation frames only when needed, so they can run even in pause mode.

Better than boarding controls: boarding filter based on leg times

Boarding and disembark controls have been well received in the 1.11 beta, but the feature is still a bit too broad of an stroke, so to speak. Ideally the act of deciding for a train would consider many factors, including things like fares, distances, zone restrictions, etc. Although those are all cool and enrich the simulation, they require very major changes to the pax pathfinder. But it would still be cool to make the board control finer controlled.

What often motivates these feature requests is the pax behavior of always taking the earliest arrival path, even if means riding a long distance train just to make a local trip. A rule like “don’t take this train if your trip is for a shorter distance than X” would be effective to restrict these paths. Distance is a non-entity at the pax pathfind level, so its proxy, trip leg time, is used instead. In 1.11 it is now possible to restrict boarding a line stop based on how long the pax plans to ride trains servicing said stops, so only pax planning to stay in the train for a certain minimum of time are allowed to ride it. Since this rule is entirely based on time, and independent of any other context or data, it is fully compatible with the current pathfinder, with minimal performance impact.

Real map time zones

Better time zones is a feature request as old as v1.1, and it is now implemented in the 1.11 beta. There are now 3 possible time zone modes: “Always 0”, which considers the entire world as the same time zone at offset 0h; “Simplified”, which is the same as 1.11.10 and earlier versions (1h offset every 15deg longitude); and “Approximate”, which uses a low resolution map of the real world time zones. The new approximate mode is accurate up to 5km away from the limits of real world time zones.

The real map of time zones is a very complex collection of polygons, which at their full resolution would be of similar complexity to a country borders map. The game often asks itself “what is the time zone of this coordinate”, and this operation must be as fast as possible. A point-polygon hit test, over 100+ polygons, some with thousands of edges, is not exactly fast, no matter how much fancy indexing you throw at it. So I decided to use a raster image instead. This is accomplished with this ugly map:

This is a rasterization of the real world time zones, with pixels of 5km on the side on the equator, and smaller as it gets nearer the poles. This is good enough most of the time but some cities built on the limits of time zones might get assigned the wrong one. Still, compared to the old system, it’s a huge improvement.