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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

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