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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

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.

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

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Make it idiot-proof and someone will make a better idiot."