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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Tue, Oct 08, 2002 at 02:08:47PM +0100, Gregory Berkolaiko wrote:
> On Tue, 8 Oct 2002, Raimar Falke wrote:

> > > > > 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)
> > > > > 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.
> > > > > 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.
> > > > > Unfortunately this path involves a stop at e and is therefore
> > > > > not possible.

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

Ahhh. Yes. Now I see. Mhhh. Indead. That is bad. I don't see an easy
(reuse of the code in path_finding_plain) solution at the moment.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx