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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Fri, 31 May 2002, Raimar Falke wrote:

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

give me an example of COP-function _not_ satisfying this:
"The only combination of factor3 and factor4 that makes sense to me is
         factor3 = full_move_points(punit)
         factor4 = 1"
and I'll give you an example of the above.  Or, to save my and your own 
time (I suspect reading my explanations is harder than inventing things 
yourself), just think for a while.

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

However BMC and RRcount were _not_ combined into a single value.  As soons 
as you start multiplying them by factors and adding them, you get 
problems.

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

Before Per pointed it out, I wrote it in my email
        http://arch.freeciv.org/freeciv-dev-200205/msg00604.html
only you didn't notice it ;)

> 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)?!

The case of "no-stop" tiles (aka "the trireme case") is a separate issue.  
I don't think it can be handled in the main path-finding routine.

I think the path-finding routine should minimize the sum
        danger + move_points_spent
where "danger" is user supplied and possibly also BMC is user-supplied.
And that's all.

If you want more complicated estimators of a path's length, we should 
discuss it when we have clear-cut examples.

G.