Potential Performance Boost: Implementing the New Tsinghua SSSP Algorithm

[Yona-TYT]

(This was created with AI, but the news is real, https://iiis.tsinghua.edu.cn/en/info/1018/2438.htm)

Hi everyone,
I've been following a recent breakthrough in computer science that might be highly relevant for Simutrans performance, especially when dealing with extremely large maps.
A team from Tsinghua University recently published a paper that breaks a 41-year-old record in graph theory. For the first time since 1984, they have improved upon the complexity of Dijkstra's algorithm (using Fibonacci heaps) for the Single-Source Shortest Path (SSSP) problem in directed graphs with non-negative weights.

The Technical Part:
While the classic Dijkstra/Fibonacci heap implementation sits at \(O(m + n \log n)\), the new algorithm achieves a complexity of \(O(m \sqrt{\log n})\). It replaces traditional priority queues with a "Two-level Bucket Hierarchy."

Why this matters for Simutrans:
As hardware allows us to run increasingly massive maps (reaching tens of millions of tiles), pathfinding overhead for passengers, mail, and freight becomes a critical bottleneck.
On an extreme scale:

• The \(\log n\) factor in traditional Dijkstra starts to weigh heavily on CPU cycles during massive route recalculations.
• The new "Bucket Hierarchy" structure is designed to be more hardware-friendly regarding cache hits compared to the random memory access patterns of large heaps.

Discussion points:

• How deeply is the current Dijkstra/A* implementation tied to the core engine, and would it be feasible to swap the priority queue for a Two-level Bucket Hierarchy?
• Would the constant overhead of this new algorithm be too high for "standard" maps, or could it be implemented as an optimization for large-scale simulations?
• Has anyone looked into the paper yet regarding its potential implementation in C++?

References:

• Original Paper: "A Deterministic Algorithm for the Single-Source Shortest Path Problem" by Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, et al. (FOCS 2024).
• Technical Context: Quanta Magazine - Computer Scientists Break 40-Year-Old Dijkstra Record

I'd love to hear the devs' thoughts on whether this could eventually help mitigate performance drops in massive savegames.

[Matthew]

Thank you for posting this. I also find it fascinating because in the very long term it does seem like new algorithms could transform the possibilities for Simutrans.

The Quanta article that your LLM cites is here and is well worth reading, as it explains the problem and gives an overview of the solution in non-technical language that even non-mathematicians like me can understand.

The same team seem to have put a more recent paper claiming to describe an even faster variation.

But a Google search threw up a couple of significant concerns. According to this Reddit comment, the Tsinghua algorithm isn't parallelizable, but Dijkstra is. Although multithreading can throw up multiplayer synchronization problems, it seems more likely to deliver big gains than this algorithm.

Another another comment in the same Reddit thread argued that this algorithm was very unlikely was very unlikely to be superior to the route-finding systems that major map providers created in the 2010s. I looked into this a few years ago and it was very interesting. In the 2000s, Google and Microsoft were giving away big grants to anyone who thought they could improve routefinding times for online mapping, and they succeeded in making huge gains. As I (a non-mathematician) understand it, the big breakthrough was calculating routes hierarchically, and to a lesser extent constructing those hierarchies based on known data other than time. E.g. if your country has a motorway or interstate highway network, use that as a first draft of your hierarchy. Perhaps in Simutrans, we might use town roads vs rural roads in a similar way.

In the 2010s, the focus of the Big Tech research effort turned to public transport and how to accommodate the fact that timetables can make a big difference. As we all know, a half-hourly train that takes 20 minutes can arrive faster than an hourly train that takes 10 minutes. Microsoft's RAPTOR algorithm claims to be faster than Dijkstra for this specific scenario. There's a layman's explanation on the OpenTrip website (which also has a useful reading list on the whole subject). The Microsoft team say that RAPTOR is highly parallelizable and does not need large amounts of memory (in a context where some online mapping algorithms needed terabytes of memory). In my opinion (and I really don't know much about this), that looks more promising for Simutrans than the Tsinghua research at the current time. There is a C++ implementation of RAPTOR on GitHub, but the copyright status is unstated (so presumably proprietary) and it's just a student project.

[prissi]

Our pathfinding is really only demanding for building ways and for ships. For trains and routing, the search depth is very small.

Furthermore, the distance of the next point in terms of nodes is always 1 in simutrans, no need to sort to get the next point. The algorithm there is only of relevance if the actual distance are different (as they are in Experimental). But then, Experimental uses a lookup table which is O(1). Only for recalculating that table, much time is spent.)

For large areas, whe have actually a hierachical pathfinder, which is quite fast as entire areas are treated as one tile. It was written by an actualy Prof. of mathematics (DWachs), so I am pretty sure, it was state of the art for bidrectional graphs (which the current one does NOT improve).

Profiling Simutrans shows that passenger routing and stepping the objects of the world are the biggest bottlenecks of well-developed games. Passengers look at most 8 hops, but the probelm are non-route passengers, because they have to change all possible 8 nodes. This is not solved by the new algorithmen, as still all nodes has to be cheack to be sure no conenction can be reached with 8 (or hao many configured) hops.