[Freeciv-Dev] Re: find_the_shortest_path()

[Jason Dorje Short <jshort@xxxxxxxxxxxxx>]

Gregory Berkolaiko wrote:
> 
> Hi Jason,
> 
> First of all I am glad that somebody other than me is looking at
> gotohand.c  There is a lot to be cleaned up there.  But caution must be
> exercised.

Certainly.

>  --- Jason Dorje Short <jshort@xxxxxxxxxxxxx> wrote:
> > /*
> > 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.  Later on [2] we have:
> 
> AFAI understand find_the_shortest_path maps all possible paths of the
> same length to a destination.  For flexibility reasons.  Client-side
> gotos don't have to be that flexible: they can always ask the human for
> help.

Not *all* possible paths - if it did that it would have infinitely many
loops in the case of railroads.  It never maps loops.

It also moves backwards from the destination to remove all "blind"
alleys so that there's just one path.  This I don't entirely understand.

> >       if (warmap.cost[x1][y1] <= warmap.cost[x][y])
> >         continue; /* No need for all the calculations. Note that this also 
> > excludes
> >                      RR loops, ie you can't create a cycle with the same 
> > move_cost */
> >
> > which makes the first comment wrong (or at least misleading).
> 
> no, both comments are correct. the algorithm will mark two equivalent
> pahts unless the last step of the second path has movecost 0.

The first comment is definitely not correct.  It claims railroads are
handled differently, which is not the case (out-of-date, no doubt).  It
also claims this is necessary to avoid RR loops, which is incorrect as
well.

jason