[Freeciv-Dev] Re: find_the_shortest_path()

[Jason Dorje Short <jshort@xxxxxxxxxxxxx>]

Raimar Falke wrote:
> 
> On Tue, Sep 18, 2001 at 02:41:55AM -0400, Jason Dorje Short wrote:
> > I have several comments/questions on find_the_shortest_path() in
> > server/gotohand.c.
> >
> >
> > A comment [1] says:
> >
> > /*
> > To avoid RR loops (which may cause find_a_direction() to move a unit in
> > cute little cycles forever and ever...), when we have more than one path
> > to a tile and the second one is via RR (move_cost 0), we do NOT mark the
> > extra path.
> > */
> >
> > However, Dijkstra's algorithm doesn't have this problem since any time
> > the point is encountered a second time and the movement cost is no less
> > it is not considered a second time.
> 
> You may have two paths to a certain position. These two paths have the
> same move costs. The first path has 3 rail-road steps and the second
> has 6544 rail road steps. You find the second path before the first.

That may be possible (although I assume the implementation of the
algorithm will prevent it by looking at the fewest-step path first; I
have not checked), but it does not make the comment any more correct.

The comment claims that some checking for RR paths is done.  In fact no
such checking is done, as the later comment attests - things just work
out because Dijkstra's algorithm already takes care of this problem.


As for the rest, I think a lot of cleanup could be done to this code -
but it will be difficult to guarantee the correctness of the new code
without a full understanding of the current code, which will take some
time.  A simple replacement of parts of the code with function calls
should be easy enough, though.

jason