[Freeciv-Dev] Re: Path-finding in the presence of danger

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Tue, 8 Oct 2002, Raimar Falke wrote:

> On Mon, Oct 07, 2002 at 03:33:52PM +0100, Gregory Berkolaiko wrote:
> > On Mon, 7 Oct 2002 rf13@xxxxxxxxxxxxxxxxx wrote:
> > 
> > > On Mon, Oct 07, 2002 at 12:32:11PM +0100, Gregory Berkolaiko wrote:
> > > > On Mon, 7 Oct 2002 rf13@xxxxxxxxxxxxxxxxx wrote:
> > > > 
> > > > > > BTW, I have serious reason to believe that it will be _very_ 
> > > > > > difficult to 
> > > > > > find the best micro-path using extra_cost and COP.  I am pretty 
> > > > > > sure your 
> > > > > > algorithm will also fail to do it in one way or other, but I will 
> > > > > > need to 
> > > > > > understand it more, so please help me here.
> > > > > 
> > > > > Why is it difficult? You only have to provide the _exact_ last macro
> > > > > path destination state as the start of micro path searching. This is
> > > > > the reason for the extra start_* parameter of plain_get_map.
> > > > 
> > > > Here is an example on which your algorithm will choke, AFAIU:
> > > >   d
> > > >  / \
> > > > A   B
> > > >  \ /
> > > >   e
> > > > 
> > > > Capital letters (A,B) are safe.  d and e are dangerous (no stop 
> > > > possible).
> > > > Unit starts in A with full 6 MPs.  Move costs are:
> > > > A-d: 3 MP
> > > > d-B: 3 MP
> > > > A-e: 6 MP
> > > > e-B: 3 MP
> > > > 
> > > > Extra costs 
> > > 
> > > > (when converted to move points)
> > > 
> > > You can't do this. There is no limit on how large a COP may get per
> > > turn. Next example please ;)
> > 
> > *sigh* Sometimes I feel like we live on different planets...
> > 
> > Let me put it this way:
> > 
> > extra costs of tiles are:
> > 6 for d and 0 for everything else.
> > 
> > and the get_COP used is
> >     BMC_of_path + EC_of_path
> 
> I also assumed this. Sorry my fault.
> 
> > Before any more nitpicks come my way, I would like to point out that all 
> > turn modes are equivalent in this example.
> > 
> > 
> > > 
> > > > are:
> > > > A, B, e: 0 MP
> > > > d : 6 MP
> > > > 
> 
> > > > The run of plain_map1 in expand() will rightly conclude that the safe 
> > > > tile 
> > > > B is reachable within one turn.
> 
> Correct.
> 
> > > > The run of plain_mp2 will conclude that the best way to reach B,
> > > > taking into account extra costs, is by following A-e-B.
> 
> Correct.
> 
> > > > Unfortunately this path involves a stop at e and is therefore
> > > > not possible.
> 
> Correct.
> 
> So what is the problem? 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;
> +    }
> 
> should be activated and so there is no micro-path from A to B.

The problem is that _there_is_ a micro-path from A to B:
        A-d-B

The algorithm cannot find it, that is the problem.

G.