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

G.