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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

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

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.  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.
> > 
> > The algorithm I was proposing in the notes breaks on a more sophisticated 
> > example but it breaks all the same.
> > 
> > > > It is still possible to take into account the extra cost of the 
> > > > non-dangerous tiles.  This does make certain sense: you are not going 
> > > > to 
> > > > stop at the dangerous tiles, so it does not matter whether they are 
> > > > nice 
> > > > or not.
> > > 
> > > I don't understand you.
> > 
> > What I am saying is that we should postulate that extra cost of a 
> > dangerous tile is 0.  Otherwise path finding might not be possible (in a 
> > reasonable way, not enumeration of _all_ paths).
> > 
> > The above postulate is actually quite reasonable: since we are not going 
> > to stop at a dangerous tile, we won't collect whatever extra cost it has.
> 
>       Raimar