[Freeciv-Dev] Re: [RFC] Path finding interface #9

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Wed, 29 May 2002, Raimar Falke wrote:

> On Tue, May 28, 2002 at 08:07:17PM +0100, Gregory Berkolaiko wrote:
> > Raimar,
> > 
> > 
> > On Tue, 28 May 2002, Gregory Berkolaiko wrote:
> > 
> > > On Tue, 28 May 2002, Raimar Falke wrote:
> > > > 
> > > > Is it true:
> > > >  - if we remove the is_position_safe and let the trireme issue out
> > > >  that the best path is independent of the choose policy (TC_MINIMUM,
> > > >  TC_AVERAGE, TC_MAXIMUM)?
> > > 
> > > no: you have 6 moves/turn, choose between these 3-segment paths:
> > > (a) 5-6-5
> > > (b) 6-6-2
> > > (c) 5-2-6
> > > 
> > > MINIMUM will go for (a)
> > > MAXIMUM will go for (b)
> > > AVERAGE will go for (c)
> > 
> > Personally I see no sense in these 
> >     turn_cost_factor, move_cost_factor.
> > Why would you ever need such clumsy and complicated function as
> >     turn_cost_factor * turns_needed 
> >     + move_cost_factor * (move_rate - moves_left)
> >     + sum(basic_move_cost * PF_BMC_FACTOR + extra_cost) ???
> > 
> > In my opinion 
> >     move_points_spent + sum(extra_cost)
> > is enough, if move_points_spent is calculated according to one of the 
> > 3 models: MIN, MAX and AVE.
> > 
> > If you disagree, please give examples.
> 
> Suppose you have two paths. The one is short and dangerous (higher
> extra_cost) and the other is long but not so dangerous (lower
> extra_cost). You than need a method to trade danger against extra time
> for the path. As we have seen BMC isn't enough to capture the length
> of a path.

This is perfectly catered for by the formula
        move_points_spent + DANGER_WEIGHTING * sum(extra_cost)

However, as extra_cost function is user-supplied, the user can (and 
should) incorporate the DANGER_WEIGHTING into the extra cost.  Hence the 
final quantity to minimize,
        move_points_spent + sum(extra_cost)

Just a reminder, move_points_spent is not merely a sum of BMCs but the 
estimation of the length of the path, in move-points.

> Suppose you have five values for danger than you need to express
> something like: every tile where the danger is one step higher I will
> take another path which takes me 0.2 turns longer to arrive.
> 
>       Raimar

Best wishes,
G.