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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Fri, May 31, 2002 at 04:18:36PM +0100, Gregory Berkolaiko wrote:
> 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

Shouldn't happen.
> 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.

Dijkstra needs indeed one value. However also the old goto agent code
used multiple values for this: the BMC and the railroad count.

So we can use the BMCs if the COPs are equal. And the railroad counts
if the BMC are equal.

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

This is something.

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

If I would have a clear idea I would show the code. We are still here
to discuss the interface. It would be nice if it supports these
things. The same way it would be nice if it supports the trireme (this
is the correct spelling!?). We also have to think about general ideas
since it may be possible that another user (auto-explorer, attacking
code) has even other requirements. Per has pointed out that the
trireme case isn't this special as previously thought. BUT we also
have to avoid over-engineering. The other extreme would be code
duplications. Maybe we should make a list of extra features with their
costs (code-size, runtime)?!

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  "Real Users find the one combination of bizarre
   input values that shuts down the system for days."