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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Fri, May 31, 2002 at 12:42:39PM +0100, Gregory Berkolaiko wrote:
> On Thu, 30 May 2002, Raimar Falke wrote:
> > On Wed, May 29, 2002 at 05:11:43PM +0100, Gregory Berkolaiko wrote:
> > > On Wed, 29 May 2002, Raimar Falke wrote:
> > 
> > There there 3 different metrics to measure the "goodness" of a path:
> >  - BMC
> >  - extra cost (danger and pseudo BMC for unknown tiles)
> >  - time (turns and moves_left)
> > and there is is_safe_tile but this just remove some paths in a kind of
> > pre-processing step.
> > 
> > So you can judge a path just by its BMC or just by its time. So in
> > general you may want to do something like:
> >  goodness = BMC*factor1+extra_cost*factor2+turns*factor3+moves_left*factor4
> > 
> > So if we assume that factor1 is 0 you see that you can balance a
> > higher turns value with a smaller extra_cost value. Depending on the
> > values you can say that 1 turns can be balanced by n extra_cost
> > (points).
> > 
> > This model is a lot clearer than the previous one. So I have attached
> > a 10th version of the interface. You can now specify a function which
> > does calculate the "goodness" of a path. This also allows you to make
> > a path with turns=n, moves_left=0 equivalent to turns=n+1,moves_left=6
> > which is needed for settlers.
> > 
> > The patch also made the definition of is_position_safe a lot
> > clearer. It is also renamed.
> 
> The only combination of factor3 and factor4 that makes sense to me is 
>       factor3 = full_move_points(punit)
>       factor4 = 1

For settlers this isn't true: it doesn't matter if 2 points are left
or 3 at the destination. Only the turns and the fact that there is at
least one point left is important.

> If you take something else it might jam Dijkstra.

Dijkstra will work if the cost of a path is >= the cost of the path
excluding the last step. I.e. every step has to add somthing >=0. This
can be enforced by the code.

> BTW, Dijkstra method requires a single value as an estimate of the 
> goodness of a path.  Do you propose this COP function to do it?

Yes.

> I generally welcome this COP function but it takes too many arguments.  
> It should be of the form:
>       move_points_spent + factor * extra_cost,
> where
>       move_points_spent = (turns+1) * full_move_points(punit) - moves_left
> 
> Now, as I pointed out earlier, the extra_cost is a user-supplied function 
> already, so the user should build the factor into it.  So there is no real 
> need for COP to be user-supplied.

See above.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "It is not yet possible to change operating system by writing
  to /proc/sys/kernel/ostype."              sysctl(2) man page