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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Thu, 10 Oct 2002, Raimar Falke wrote:

> On Thu, Oct 10, 2002 at 11:12:05AM +0100, Gregory Berkolaiko wrote:
> > On Thu, 10 Oct 2002, Raimar Falke wrote:
> > > 
> > > > We can even get them safe without is_dangerous_tile, but their movement 
> > > > will be restricted.
> > > 
> > > How?
> > 
> > Return tile_behaviour NO_ENTRY for off-shore tiles.
> 
> Then we get safe ships but then optimal exploration behavior is
> impossible.

True.  But the exploration is still useful, I tried it and triremes 
discover many new continents (of course it depends on their distance, but 
in general you discover something).

> > > There is another drawback: caching. If caching proves to be usefull
> > > the middle layer has to provide its own caching structure. ZOC stuff
> > > for example have to be cached per tile. This will intruduce another
> > > cell-like struct. It will create more hardware cache misses. So the
> > > KISS interface will yield a slower implementation. The question is how
> > > much slower?
> > 
> > What is a KISS interface?
> 
> http://www.houghi.org/jargon/KISS-Principle.html

Nice dictionary.  I enjoyed reading it.

[..]

> > > > My opinion is a good default COP-function will provide future writers 
> > > > of 
> > > > get_ECOT call-backs with all the freedom they'll ever need (without 
> > > > going 
> > > > to the drak side, of course).
> > > 
> > > Remember the settler case: it doesn't matter if a settler arrvies with
> > > 1 or 2 points left at long as the number is >0. We have to support
> > > this somehow.
> > 
> > We discussed it long and hard and my conclusion was that it is impossible 
> > to achieve using a COP call-back.  If you disagree, please give me a COP 
> > and I'll try to get a counterexample.
> 
> For the settler case the COP function will be:
> 
> int my_get_COP(int total_BMC, int TEC, int turns, int moves_left)
> {
>   if(moves_left==0) turns++;
> 
>   // if we work without EC
>   return turns;
> 
>   // with EC
>   return turns * SOME_FACTOR + TEC;
> }

Without EC this COP is of course absolutely irrelevant: the fastest path 
is always the fastest path.

Now with EC, here's a counterexamle:
  D
 / \
A   B--C
 \ /
  E

Strating position of an Engineer (6 MPs) is A, he is on full moves, needs 
to get to C.

Basic Move Costs are:
A-D = 0 MP
A-E = 0 MP
D-B = 0 MP
E-B = 3 MP
B-C = 4 MP

Extra Costs are:
D = 1
0 otherwise

There are two paths to B,
A-D-B  (0 turns spent, 6 moves left, 1 extra cost): COP = 1
A-E-B  (0 turns spent, 3 moves left, 0 extra cost): COP = 0

So at B, the path A-E-B is selected (correctly).  And, as a consequence, 
the path to C is
A-E-B-C (1 turns spent, 5 moves left, 0 extra cost): COP = SOME_FACTOR

whereas the best path is obviously
A-D-B-C (0 turns spent, 2 moves left, 1 extra cost): COP = 1


The above is valid in the case SOME_FACTOR > 1.  If it is equal to 1 
(which seems quite ridiculous to me), you can still extend the 
counterexample.  I believe you don't want to set the factor to 0...

> The callback is easy. And I have no problem if we provide a default
> (you decide) if no callback is given.

It is easy but it gives you only imaginary flexibility, slows down the 
code and makes it less readable.

G.