[Freeciv-Dev] goto algoritms

[Thue Janus Kristensen <thue@xxxxxxx>]

Here are two suggestions to a new goto function.

-goto_1.diff is basically the old goto cleaned up and simplified (though
still as functionel). It also prevents the reported RR loop bug by
checking if the map size is uneven in dir_ok.

-goto_2.diff is different from goto_1.diff in that it doesn't use dir_ok
to prevent RR loops. Instead, when two routes are found to a tile and
both take their last turn on rail only the first one will be marked.
Because of the way the algoritm floods the map this will also be the
shortest route.
This will remove a little bit of the idea of find_a_direction, which
chooses between routes of equal length, but since routes on rail
almost always will arrive the same turn it doesn't matter that much.
As to effiency, not having to use dir_ok should save some calculation,
but will also mean that mean that all rail will be searched to find a
path. This penalty can be lessened by doing a few optimizations, which I
haven't done.
This one also _always_ finds the shortest path, unlike goto_1 and the one
in CVS.

The comment inside goto_2 has not been updated. A few comments need to be
changed in goto_1 too.

None of them are adequately tested for CVS, though they seem to work
nicely.

I haven't tried profiling yet, but it would surprice me a lot if
goto_1.diff was slower than the one currently in CVS. How fast goto_2 is
in a real game I do not know, but it should depend on the amount of rail.
Unless goto_2 is substatially slower than goto_1 I suggest we use goto_2,
as it is always correct, and simpler. Also, as shown the profiling made of
1.10, the goto is important, but not that critical to performance.

-Thue

goto_1.diff.gz
Description: GNU Zip compressed data

goto_2.diff.gz
Description: GNU Zip compressed data