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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Fri, 31 May 2002, Raimar Falke wrote:

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

There are two problems here: 
1. COP-cost of a step might become < 0
and
2. COP-cost of a step depends on the previous steps taken.

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

You either have some brilliant ideas on how to make it work or you are 
missing something very basic.

This "2t1p is equivalent to 2t2p" idea might make Dijkstra choose bad 
paths (notation 2t1p is "2 turns and 1 points _used_ up to now").

The problem is that you cannot just "define" arbitrarily what paths are 
better and what are worse, you've got to do in a way which allows you 
dynamic _construction_ of better paths.

Say you arrived to B using 2t2p.  Few iterations later you discovered a 
path which is 2t1p.  You COP is gonna say that it's no better, so you 
discard it.  But this difference in 1 point can (a) turn out to be crucial 
few step later or even (b) accumulate with similar errors.

My suspicion is that you want to be able to say something like:
out of
        2t1p with 3 dangers,
        2t2p with 2 dangers and
        2t3p = 3t0p with 1 danger
the second one is better than first since we don't care for extra point 
and is also better than third since loosing a turn outweights the decrease 
in danger.

I think your demands are unrealistic.  Maybe I just don't understand them,
but you never supplied a nice example with full description of the goals
and the possible paths, not just vague statements of the type "I want to
trade one point here for 2 points there".

G.