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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Fri, Oct 11, 2002 at 01:33:41PM +0100, Gregory Berkolaiko wrote:
> On Thu, 10 Oct 2002, Raimar Falke wrote:
> > > > > 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.

Nice example. A lot of words could have been saved if this example was
shown earlier. It looks like I haven't thought about the problem
enough. I agree with you that a get_COP callback doesn't solve this
problem and that we should have a fixed formula for COP.

My proposal:
 if TM_NONE:
    COP=((TURN_FACTOR*total_BMC)/move_rate)+TEC
 else:
    COP=((TURN_FACTOR*((turns+1)*move_rate-moves_left))/move_rate)+TEC

and TURN_FACTOR is a define (2^16 for example).

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx