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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Thu, Aug 01, 2002 at 12:52:39PM +0100, Gregory Berkolaiko wrote:
> On Wed, 31 Jul 2002, Raimar Falke wrote:
> 
> > On Wed, Jul 31, 2002 at 07:23:55PM +0100, Gregory Berkolaiko wrote:
> > > On Wed, 31 Jul 2002, Raimar Falke wrote:
> > > 
> > > > On Wed, Jul 31, 2002 at 05:18:49PM +0100, Gregory Berkolaiko wrote:
> > > > > On Wed, 31 Jul 2002, Raimar Falke wrote:
> > > > > 
> > > > > > On Wed, Jul 31, 2002 at 02:56:36PM +0100, Gregory Berkolaiko wrote:
> > > > > > > On Wed, 31 Jul 2002, Raimar Falke wrote:
> > > > > > > 
> > > > > > > > On Wed, Jul 31, 2002 at 01:11:59PM +0100, Gregory Berkolaiko 
> > > > > > > > wrote:
> > > > > > > > > > > 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.
> > > > > > > > 
> > > > > > > > I don't understand.
> > > > > > > 
> > > > > > > on plain_map1 you find that path a->1->b takes you 1 turn.
> > > > > > > so you ask plain_map2 to give you the best path taking into 
> > > > > > > account the 
> > > > > > > ECOTs.  such path is a->c->b, it has much lower EC than a->1->b 
> > > > > > > but it 
> > > > > > > will take you 1.5 turns.  you ignore it, thus ignoring every 
> > > > > > > possibility 
> > > > > > > of getting from a to b.
> > > > > > 
> > > > > > Yes the code will ignore every possibility of getting from a to b 
> > > > > > _in
> > > > > > one turn_ in such case.
> > > > > 
> > > > > Which means that supplying ECOT that gives values greater than 
> > > > > PF_BMC_FACTOR will produce misleading results.
> > > > 
> > > > We don't have a PF_BMC_FACTOR (yet).
> > > 
> > > Please don't nitpick.  You have COP which is equivalent to having
> > > BMC_FACTOR (plus numerous other things that can screw up the algorithm).
> > 
> > Do I get this correct? With get_COP callback we don't have problems
> > and without the callback we have problems?
> 
> No.  With get_COP callback you get the same problems plus other ones too.
> 
> But you are right, this seems to be the last point of contention.  It 
> seems that COP is only needed for is_position_dangerous handling so far 
> and I hope to be able to do it differently.

> We should also think however about the possibility of having 
> can_transit_tile call-back.

We have the whole time or haven't we. IMHO it is wrong if the
can_transit_tile returns true for safe places. If this function should
return true for other position for which ones?

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "At the beginning of the week, we sealed ten BSD programmers
  into a computer room with a single distribution of BSD Unix.
  Upon opening the room after seven days, we found all ten programmers 
  dead, clutching each other's throats, and thirteen new flavors of BSD."