This patch implements jump-point search for route searching of ships. Here is an older discussion:
http://forum.simutrans.com/index.php?topic=11276
The patch saves a lot of computational work for ship path finding. The change of the route search algorithm is very tiny. Most of the patch is devoted to post-processing to eliminate unnecessary turns.
Here are some profiling results for the yoshi game:
Trunk - unpatched
0.39 4.15 97913/97913 route_t::calc_route(karte_t*, koord3d, koord3d, fahrer_t*, int, int) [17]
[18] 6.7 0.39 4.15 97913 route_t::intern_calc_route(karte_t*, koord3d, koord3d, fahrer_t*, int, unsigned int) [18]
0.25 1.52 11233059/17022286 grund_t::get_neighbour(grund_t*&, waytype_t, unsigned char) const [31]
0.37 0.18 5317166/5519298 binary_heap_tpl<route_t::ANode*>::pop() [84]
0.13 0.19 8652492/9600752 ribi_typ(koord3d, koord3d) [120]
0.13 0.12 8665780/76465330 grund_t::get_weg(waytype_t) const [36]
0.06 0.13 5470725/7113285 vehikel_t::get_ribi(grund_t const*) const [154]
0.14 0.04 6461320/6664035 binary_heap_tpl<route_t::ANode*>::insert(route_t::ANode*) [188]
With the patch
0.25 3.06 97796/97796 route_t::calc_route(karte_t*, koord3d, koord3d, fahrer_t*, int, int) [22]
[23] 5.0 0.25 3.06 97796 route_t::intern_calc_route(karte_t*, koord3d, koord3d, fahrer_t*, int, unsigned int) [23]
0.10 1.07 6258633/12078059 grund_t::get_neighbour(grund_t*&, waytype_t, unsigned char) const [36]
0.11 0.10 6244638/74233760 grund_t::get_weg(waytype_t) const [32]
0.05 0.15 5818508/7478251 vehikel_t::get_ribi(grund_t const*) const [144]
0.07 0.13 6231353/7556078 ribi_typ(koord3d, koord3d) [159]
0.08 0.07 3112768/3333357 binary_heap_tpl<route_t::ANode*>::pop() [196]
...
0.06 0.03 3514376/3735528 binary_heap_tpl<route_t::ANode*>::insert(route_t::ANode*) [264]
...
0.00 0.02 6246/6246 route_t::postprocess_water_route(karte_t*) [573]
Route-search going down from place 18 to 23 of the most time-consuming tasks. A lot of calls to methods like grund_t::get_neighbour and the binary-heap methods are saved. The new algorithm avoids to visit water tiles more than once.
Please test!
This should also reduce the size needed for ship pathfinding quite a lot (which may help when the threaded n network will be ever implemented.) Also it would be still ok with axle loads.
Thanks for comitting. I wonder: Would this not work too for way building (although it may mean no automatic alterations for terrain then).
Would it be possible to have ships that are constrained to water with a depth of 1? In other words: Can we have "coastal" ships that only consider "shallow" tiles when computing paths. This would very much reflect some of the larger river ships.