[Freeciv-Dev] Re: find_the_shortest_path()

[Gregory Berkolaiko <gberkolaiko@xxxxxxxxxxx>]

 --- Jason Dorje Short <jshort@xxxxxxxxxxxxx> wrote: 
> 
> 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.

I really struggled to undertand it too.
Here is what it does:
prior to that all paths out from source X were marked on local_vector
until we arrived to destination Y.  But the local_vector contains many
paths from X to nowhere now!
To fix it we backtrack from Y and re-mark the paths, now on
warmap.vector.

> 
> > >       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.

The comments might not be clear but I mantain they are correct.
Example:  assume we are in danger of getting infinite loop X <-> Y
where X and Y are neightbouring tiles connected by railroad.
Assume the algorithm has already assigned the correct cost, say 3, to
both of them.  At some point it gets X from the queue and considers it's
neighbours.  In principle it could have marked path from X to Y (since
3+0 does not increase cost of Y) but it doesn't because of "=" in the
condition
if (warmap.cost[x1][y1] <= warmap.cost[x][y])
http://www.freeciv.org/lxr/source/server/gotohand.c?v=cvs#L683

If X and Y were connected by road, X had cost 2 and Y had cost 3,
algorithm would still mark path from X to Y (2+1 does not supersede 3),
see
http://www.freeciv.org/lxr/source/server/gotohand.c?v=cvs#L840


best,
G.

____________________________________________________________
Do You Yahoo!?
Get your free @yahoo.co.uk address at http://mail.yahoo.co.uk
or your free @yahoo.ie address at http://mail.yahoo.ie