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

G.


> 
> >  At least do
> >   plain_get_path(plain_map1, ..., &possible_neighbour->path_from_prev)
> > that'd give maybe a suboptimal but still possible path.
> 
>       Raimar
> 
>