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

> 
>       Raimar
> 
>