Yet Another Pathfinder
From OpenTTD
You can find more information on what exactly needs doing in the discussion for this article. Remember to use the Manual of Style and to remove this template once the article has been expanded.
Yet Another Pathfinder (YAPF) is the latest software algorithm used by OpenTTD to control vehicle movement.
YAPF is the third attempt at creating a pathfinder algorithm for OpenTTD. The first new algorithm was New Train Pathfinding (NTP), which only works on trains. The second was New global Pathfinding (NPF), which works on all vehicles and is quite intelligent, but bogs down the system after many vehicles have been built. The goal of YAPF is to provide the power and flexibility of NPF while at the same time being very optimized, relieving the CPU load.
The remainder of this article is meant for developers.
Contents |
[edit] Improvements over NPF
According to a forum post by KUDr, there are 3 major improvements in YAPF compared to NPF:
- NPF creates a node for each tile while YAPF extends the node by following the tile/trackdir until something important (station, waypoint, choice, etc.) is seen. This node extension is called a "segment".
- YAPF caches its segments - begin/end tile/trackdir, cost, last signal tile/trackdir, etc.
- YAPF has a much more complex structure - it is template based to allow the compiler to optimize calls between YAPF modules by inlining.
These improvements increase the performance of YAPF over NPF but also make the code more complex and harder to understand.
[edit] Tuning
Several options of YAPF can be tuned up. I will not describe all of them because they are clear what they do.
There 4 options (3 actualy) that are quite mysterious:
rail_look_ahead_max_signals = 10
rail_look_ahead_signal_p0 = 500
rail_look_ahead_signal_p1 = -100
rail_look_ahead_signal_p2 = 5
First one checks how many signals YAPF have look ahead of our train. The next options are used to calculate penalty array using following formula, where the parameter "i" is the value of the rail_look_ahead_max_signals :
p=p0 + p1*i + p2*i*i
So, we have following array of signal penalties for the specified number in rail_look_ahead_max_signals as result:
p[]={500,405,320,245,180,125,80,45,20,5}
Now some examples.
For (the first) 3 signals: Red,Red,Red: penalty=500+405+320=1225
For (the first) 4 signals: Red,Green,Red,Green: penalty=500+0+320+0=820
The final cost will be added to path cost. This can help to reduce traffic jams when we have some trains blocking a way (4 semaphores ahead) and we have alternate way.
This is internal YAPF stuff and is not supposed to be tuned really. Developer put a lot of effort to calculate right values into p0,p1,p2.
The only tunable value is p1 penalty. Fine value range is from -100 to -90. If you go outside that range, penalty array will have weird values and trains would start to go not as you expect.
If you want more agresive load balancing go for p1=-90 and you will get following array:
p[]={500,415,340,275,220,175,140,115,100,95}
You can also try following settings. These were successful in load balancing my entrances to
very busy stations:
rail_look_ahead_max_signals = 10
rail_look_ahead_signal_p0 = 1000
rail_look_ahead_signal_p1 = -200
rail_look_ahead_signal_p2 = 10
You get following table:
p[]={1000,810,640,490,360,250,160,90,40,10}
[edit] Dependant Projects
You can't change one part of the code without some effect on the other parts, and pathfinding is a huge part.
[edit] Path Based Signalling
One of the main projects that has been put on hold until YAPF is finished is Path Based Signalling (PBS). The PBS code was interwoven in with the NPF code, and was considered too buggy and the code too messy to stay in the main branch. Once YAPF is complete, work should begin on a completely new PBS algorithm.
[edit] Speed Signs
A modest project to control which trains go on which tracks based on their speed, Speed Signs will also be affected by YAPF once it is implemented.
