[Freeciv-Dev] Re: [RFC] Path finding implementation.

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Tue, 30 Jul 2002, Raimar Falke wrote:

> On Tue, Jul 30, 2002 at 05:30:16PM +0100, Gregory Berkolaiko wrote:
> > On Tue, 30 Jul 2002, Raimar Falke wrote:
> > 
> > > On Tue, Jul 30, 2002 at 01:06:34PM +0100, Gregory Berkolaiko wrote:
> > > > On Mon, 29 Jul 2002, Raimar Falke wrote:
> > > > 
> > > > > > so the name is not good, EC can be bigger than
> > > > > > PF_MAX_EXTRA_COST, but it will effectively mean that we'd prefer a 
> > > > > > longer
> > > > > > but safer route.  Although I am not a big fan of this practice, I
> > > > > > regocnize it might be useful.
> > > > > > 
> > > > > > But the EC supplied to safe-path routine should not exceed 
> > > > > > PF_MAX_EXTRA_COST
> > > > > 
> > > > > I don't see how this will solve the problem above.
> > > > 
> > > > What is the problem above, maybe we are talking about different 
> > > > problems?
> > > > Is it "to ensure that the frontier tiles will be dequeued basing on the 
> > > > time that it takes to reach them, i.e. a tile that is (k+1)turns away 
> > > > will 
> > > > never be considered before a tile k turns away" ?
> > > 
> > > Yes this is the problem. Ok I try it another time: we have a position
> > > and want all (micro) paths from this position which end in a safe
> > > position in this turn. If they can go over safe tiles or not isn't the
> > > problem here. We need the user-supplied ECOT because the path choosen
> > > needs it. However this user-supplied ECOT can return such big ECOT
> > > that a tile at (k+1)-turn is returned before a k-turn tile is
> > > returned. It doesn't depend how you choose the ECOT and the COP
> > > function. It was a design goal that you can compensate big ECOT with a
> > > turn and vice versa.
> > 
> > Don't you think that asking a user to supply ECOT not exceeding 
> > PF_BMC_FACTOR when also supplying is_position_dangerous call-back is 
> > quite reasonable?
> 
> I think it is a restriction which can be removed quite easy. The
> callback are a few lines and the code which calls the callback is also
> only a few lines. This is nothing compared to the
> is_position_dangerous support.

Ah, but I think there is a possible problem with allowing ECOT return 
values over PF_BMC_FACTOR:

in plain_map1 the only value of ECOT that plays a role is the forbidding 
PF_IGNORE_COST.  Otherwise the sorting is done wrt the time to dest.  
Fine.

Suppose we found that tile b is reachable from a in exactly one turn.  We 
use plain_map2 to read off the path a->b.  But now the ECOT plays full 
role and there is no guarantee that the selected path a->b will not take 
longer than one turn.  So although b _is_ reachable in one turn the 
recorded path will take longer.

> 
> > Not incorrect but suboptimal.  Never mind for now.  I was just confused by 
> > the the two calls to expand from macro_get_next_position
> 
> Feel free to optimize it.

I will.  Unfortunately now I'm trying to work, although rather 
unsuccessfully :(  Maybe during the weekend.

G.