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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Wed, 31 Jul 2002, Raimar Falke wrote:

> On Wed, Jul 31, 2002 at 12:43:01PM +0100, Gregory Berkolaiko wrote:
> > 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.
> 
> This code
> 
>     if (pf_last_position(&possible_neighbour->path_from_prev)->turn >
>         turn) {
>       freelog(DISCARDED_DIRS_LOG_LEVEL, "  pos=(%d,%d): too long", tmp_pos.x,
>               tmp_pos.y);
>       continue;
>     }
> 
> was put there to catch these.

But that would mean that there will not be any paths from a->b, when there 
exists one, which is even worse.  At least do
  plain_get_path(plain_map1, ..., &possible_neighbour->path_from_prev)
that'd give maybe a suboptimal but still possible path.

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

Not for me, it seems, unfortunately.

G.