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

[rf13@xxxxxxxxxxxxxxxxx]

On Mon, Oct 07, 2002 at 12:32:11PM +0100, Gregory Berkolaiko wrote:
> On Mon, 7 Oct 2002 rf13@xxxxxxxxxxxxxxxxx wrote:
> 
> > On Fri, Oct 04, 2002 at 08:00:09PM +0100, Gregory Berkolaiko wrote:
> > > Raimar,
> > > 
> > > You answered this question already but I cannot find it in the archives.  
> > > So please explain again.  In path_finding_macro in expand() you set up 
> > > two 
> > > maps.  What are they for?
> > 
> > > It seems one is to find positions reachable within one turn and the 
> > > second 
> > > is to find the path leading to them but also taking into account the 
> > > extra_cost and COP?
> > 
> > Fully correct.
> > 
> > It may need redesign because of the introduction of get_TB.
> 
> Let's ignore tile behaviour for now.
> 
> > > 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 ;)

> 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

-- 
 email: rf13@xxxxxxxxxxxxxxxxx