The International Simutrans Forum
Community => Community Discussion => Topic started by: Yona-TYT on May 09, 2026, 06:48:08 PM
(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.