Here is a small patch with some small optimizations in route search:
-- every node now remembers the direction from where it was visited -> no need to check this tile again
-- store the best current node extra and do not put it into queue -> saves some extra insert / pop operations
Any thoughts ?
The mark routines of the map should also avoid visiting a node more than once. But I think you mean saving calculation time by remembering the from tile.
About the second optimisation: May be helpful. Profiling with a simple ship should give a good idea. I may be able to connect my main development computer to the net again tomorrow, so I may do some profiling there too.
When I did profiling (years ago) ribi_typ() in explicitely casted koord was faster. May have changed though with GCC 4.x.
Still the find route need anyway change, since it ignores way costs so far completely.
Quote from: prissi on February 04, 2013, 04:20:50 PM
The mark routines of the map should also avoid visiting a node more than once. But I think you mean saving calculation time by remembering the from tile.
Before the marking is accessed, first get_neibhbor() and ist_befahrbar() are called, both need some processing time, which is redundant. As the route will never go back.
Quote
About the second optimisation: May be helpful. Profiling with a simple ship should give a good idea. I may be able to connect my main development computer to the net again tomorrow, so I may do some profiling there too.
This should mostly help with straight connections: it will follow a straight track without juggling with the queue.
Quote
When I did profiling (years ago) ribi_typ() in explicitely casted koord was faster. May have changed though with GCC 4.x.
The get_2d showed up in the profile output, so I tried to save this. This is not the most essential part of the patch, and can be left out.
this is now incorporated