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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

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?

IIRC this is the last open point. Can we just leave it in and remove
it if we have shown that you can reach the same results without it. If
the callback is included or not is only a small change in the
code.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  This message has been ROT-13 encrypted twice for extra security.