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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

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

G.