Distance curve as interpolated points

The original plan and implementation for the distance factor of the pax curve was to use some smooth function, like the Gaussian function. This was implemented back in March and it worked well, but it felt too limiting. There’s plenty of interesting shapes which don’t really fit a single function, much less if also wanting to do more than one demand “hump”, as in the case in real life demand curves.

So I discarded this idea and instead made the distance function a discrete, linear interpolated function, like it is done for the time demand:

This allows to input any curve you can imagine, at the cost of some detail, but the tradeoff is worthy. It also solves the UX problem of explaining what is a standard deviation. Instead you just move the nodes up and down. There’s a series of distance ranges, each of lower resolution, but able to express the whole possible range of distances in the game. So both “normal” saves and continent and planet size networks are covered.

The default distance function I propose is just the superposition of some Gaussians centered in the same average, tweaked so it falls off in the distance a lot smoother than a peaky gaussian would look like, without some very long slope. I encourage and expect players will change this as they see fit. But if doing so appears tedious with the in-game UI, there’s also full export and import support for TSV files for all curves, both time and distance, so you can use spreadsheet software to do your own formulas. Make sure you use the exported TSV as an exact template to follow. In particular the distance points are not a suggestion, they are a rule, and any other point will be ignored.

Origin/destination station picking based on best path

The main feature of 1.12, unbiased geographical pax generation, was mostly completed in March, and in April only saw some bug fixes and optimizations. But one related aspect remained to be explored: the fact pax pick their origin and destination stations randomly, from the set of stations covering their origin and destination points. The best solution would be to pick these stations based on the optimal path trip time. So I spent most of April trying to make this possible (very easy) and not slow down the sim by 100x (very hard).

As I mention, it is very easy to implement the basic idea of this feature. Gather all possible of pairs of covering origin and destination stations, find all the best path for each pair, and pick the pair of stations with a path with the earliest arrival time. This is, of course, extremely slow. It means every new spawned pax implies potentially dozens, if not hundreds of pathfinds, while the random system (or 1.11) only needs one (at least one pathfind is always performed, to make sure there’s a timetabled train which can complete the journey with less than 3h origin wait).

The only way this could possibly remotely work out is with extensive caching, so this was implemented. In 1.12 activated map tiles have their own simulation processing and state, so now each activated tile keeps a pax pathfind cache in that tile state, similar to how stations also have a departures pathfind cache. While this cache worked fine, it was still too slow. The reason is that there is a very massive amount of paths to be considered. Even if all the previous pathfinds get cached, the possible variety of destinations is ever growing. Combined with the fact this cache is also ever expiring (just like the station pathfind cache), the cache hit rate was very low in some dense, ironically well serviced saves (high TPH defeats the pathfind caches, since the paths expire faster).

It was looking quite grim, I was going to scrape the feature. But there was another way. Something I have avoided for 4 years, because it’s very hard to design and get right, but it really looked like the only solution: time-bound pathfinding. This means that, instead of asking the pathfinding algorithm, “I want to go from station A to B, what is fastest path?”, you ask “I want to go from station A to B, what is fastest path that takes less than time T?”.

How does this help with the problem of picking from a set of possible origin and destination stations? First you sort these possible pairs of stations by estimating their trip time using the same EAT heuristic used by the A* pathfinder. Ranked this way, perform a normal pathfind for the (according to the heuristic) fastest path. This is now a real path time, store it as the best time, then move to the second pair. Only this time, you call the pathfinder with a time bound, using the previous best time as the bound. And this is the crucial step: the pathfinder will immediately trim any edge expansion which it estimates in a path time higher than the time bound (this estimation corresponds to the real current path cost + heuristic to the goal, it’s just the value used for ranking nodes in A*). For this to work at all the heuristic needs to be perfectly sound. If it’s not, it will discard possible better paths. The in-game heuristic is only partly sound, unless you move the bias slider all the way to the left. Since this is acceptable at the pax path level, and the bias is going to be the same when picking stations, I decided it was acceptable for station picking. Then keep iterating over the ranked pairs, storing path times as the best time if any appears. If at any time, the heuristic estimation of a pair is higher than the current real best path time, you can stop, since it’s impossible for a faster path to appear.

The combination of these optimizations (ranking pairs by heuristic, A* trimming based on a bound, early quitting the search) results in a fast enough pax spawn sim to at least not cut out the feature. There’s still a huge amount of pathfinds being performed, but they complete very quickly thanks to the time bound cutting them short and the heuristic pair ranking quickly finding the maximum bound. It’s about 2x to 3x slower than random picking, which is much faster than the 50x to 100x it started at, but too slow to make it the default. So 1.12 allows players to select the station picking strategy, and best path is one of the options.

Origin/destination station picking with walk times

An additional optimization which also introduces some degree of realism is considering walking time to the stations. Since pax spawn is now based on geographical points, it is possible to estimate a rough walking time cost. For now this is just simply 1 m/s (slow) in a straight line (unrealistic short, so it evens out the slow walking pace). This is an optimization because it allows to discard more station pairs, even before any pathfinding has been performed. For example, if the walking cost to/from origin/destination is slower than just the walking cost between the origin/destination geographical points, then the path is discarded. And once pathfinding is considered, walking cost is also considered, so a path might be discarded even if it’s the fastest path if the walking cost makes it slower overall than some other path. This combination of checks discards many short paths in dense, high TPH urban networks, which helps a lot with performance.

Walking cost is generally disabled in random pick mode, except for the most basic check of “just walking to destination” vs path time. There’s an intermediate setting of only considering walking cost for station picking, which in essence is equivalent to picking the nearest station. And the final full featured station pick mode, which considers both walking cost and the best path.

POI editor interface

For the POI UI I continued with the idea POIs are essentially a sign with a population amount and demand curve assigned. Signs and POIs now have their own separate creation tool in the track editor, but are otherwise edited in the normal track edit mode, just like buildings or stations.

Some players have expressed wanting to share maps of POIs of their own making, and it will be possible to do so with blueprints and Ctrl-Shift-V for pasting into their original locations. For demand curves in blueprints, I decided to handle them like mods in blueprints: the game will warn the user the clip they are going to paste contains one or more new demand curves, and ask to keep them (so they are added as new demand curves to their game), or replace them with the default population curve. For now there’s no limits to this feature or the number of demand curves, despite the potential impact, so I will use the beta series to test if a limit is needed in practice.