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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Sun, 2 Jun 2002, Raimar Falke wrote:

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

that is possible.  but also see below


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

I meant "it was me who first said that the 'trireme case' is useful for 
other things too" ;)

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

It's possible, but it would make main path-finding much heavier IMO.

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

Okay, let's fix the numbers, r+s = 3, t = 1.
So the path X->A->Y is better, if you are going to Y.
But what if you are going to Z with Y->Z costing 1 point?

Then X->A->B->Y->Z suddenly becomes better than X->A->Y->Z.  But we are 
not constructing _all_ the paths X to Z and then selecting the one we 
need, we are construction the best path.  And it is at the tile Y that we 
have to decide, which of the routes you want to keep!!

Strangely, this problem can be solved by a method very similar to what I 
think we should use for triremes...  But I still think it should be 
treated as a special case.

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

That is fine.  Since the user supplies danger function, he can incorporate 
f there.

G.