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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

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.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Python is executable pseudocode. Perl is executable line noise"
    -- Bruce Eckel