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

No.  With get_COP callback you get the same problems plus other ones too.

But you are right, this seems to be the last point of contention.  It 
seems that COP is only needed for is_position_dangerous handling so far 
and I hope to be able to do it differently.

We should also think however about the possibility of having 
can_transit_tile call-back.

G.

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