-
Notifications
You must be signed in to change notification settings - Fork 0
Pathfinding Algorithms
Simutrans is a transport simulation and therefore pathfinding algorithms are essential to its operation. They are a very important factor in determining the performance of Simutrans and are a major constraint on design choices.
Simutrans is now in its third decade and its pathfinding algorithms are the result of a great deal of generous and careful effort. In particular, in 2010 James Petts and Knightly re-wrote the pathfinding code in Extended in order to base routing on actual measured journey times whenever possible. Their work is not 'broken' and this is not a bug report. To the best of my knowledge their work used the best available algorithms. However, around the year 2010 there was a great deal of academic and commercial research into pathfinding algorithms and as far as I know, none of this research has found its way into Simutrans yet. The purpose of this article is to place that research into context for the benefit of future contributors to our project. In order to do that, I will need to understand the outline of the existing pathfinding code. I hope to edit this post as I learn more and as other people correct my errors.
Wikipedia has a helpful glossary of graph theory terms.
To the best of my limited knowledge, Simutrans uses pathfinding algorithms in five main places.
Firstly, there is an algorithm used to route player convoys (buses, trains, ships, etc.) between stops, waypoints & depots. Convoys are located on tiles, but more than one convoy may be on a tile and convoys may spread across several tiles. I believe this is mostly coded in simconvoi.cc.
Secondly, there is a algorithm used to route goods (passengers, mail & freight) using public (i.e., player) transport between stops. This is called the Path Explorer; the core was written in 2010 by Knightly but it has been substantially improved by James' addition of class-based routing and multi-threading. At least in Extended, the Path Explorer (coded in pathexplorer.cc) carries out the calculations in the background and updates a table which is then accessed by the goods generation algorithm. JOURNEY MAP - NOT TO DO WITH VEHICLES (IMPORTANT LATER)
Understanding the Opportunities
TOWN_BASED GENERATION
Understanding the New Research