Patch: speed-up route search for ships

[Dwachs]

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

Code Select Expand


                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

Code Select Expand


                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!

[prissi]

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.

[prissi]

Thanks for comitting. I wonder: Would this not work too for way building (although it may mean no automatic alterations for terrain then).

[wlindley]

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.