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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Sun, Jun 02, 2002 at 08:25:20PM +0100, Gregory Berkolaiko wrote:
> 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.

Dijkstra only needs the "one" value to compare it against other
values. But you can also compare multiple values (I don't call them
vectors because they don't have vector semantics). No need to use
factors.

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

I read the thread. Solving this with your parallel approach should be
possible. Or what was the question?

> > 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 it _can_ be done.

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

BMC of all steps is 1. Move rate = 3. We want to go from X to Y.

step  |  BMC | danger 
=====================
X->A  |   4  |   0
A->B  |   0  |   r
B->Y  |   0  |   s
A->Y  |   1  |   t

path        | BMC  | turn | moves_left | danger
===============================================
X           |   0  |  0   |    3       |   0
X->A        |   4  |  1   |    2       |   0
X->A->B->Y  |   4  |  1   |    2       |   r+s
X->A->Y     |   5  |  1   |    1       |   t

Settler case: if the turn numbers are equal it should choose the path
with the lower danger MIN(r+s, t).

Some other case: (the user supplies a number f) it should choose the
path with the minimal 3*turn+(3-moves_left)+f*danger.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "When C++ is your hammer, everything looks like a thumb."
    -- Steven M. Haflich