Optimizations in route search

[Dwachs]

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 ?

[prissi]

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.

[Dwachs]

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.

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.

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.

[Dwachs]

this is now incorporated