[Freeciv-Dev] Re: Path-finding in the presence of danger

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Thu, 10 Oct 2002, Raimar Falke wrote:

> On Wed, Oct 09, 2002 at 03:29:11PM +0100, Gregory Berkolaiko wrote:
> >
> > Each tile stores a list of possible paths to it.  Any two paths will be 
> > stored simultaneously only if the one with the larger COP takes less time.
> > More details on IRC, if you wish.
> 
> But IMHO this list isn't limited to two paths. You have to store all

Yes, the number of stored paths can be greater than two.  But for any two 
stored paths the above condition will apply.

> paths which provide a better COP for a given time (BMC cost). So you
> effectively have the best (COP) path for each possible BMC cost. Do
> this sound good?

Pretty much so, best COP for each possible BMC.  Since there are only 
finitely many possible BMCs (0, 1, 2, ..., move_rate-1), we don't get 
exponential blowup: the time required is move_rate*time(Dijkstra).  Still 
it's a mess and not worth my time.  (3) is a reasonable constraint.

> > > > So my position on this issue is following:
> > > >  1. a tile can possibly be undesirable only if the unit ends a turn on 
> > > > it.
> > > >  2. the unit is not going to end a turn on an is_dangerous tile, 
> > > >  3. the extra cost of is_dangerous tile can safely be assumed to be 
> > > > zero.
> > > > 
> > > >  4. (3.) a very reasonable constrain on the problem we are considering,
> > > >  5. dropping this constraint will mean very unreasonable complication of
> > > >     the code.  
> > > >  6. code is highly versatile as it is and very heavy too.
> > > > 

[..]

> > > IMHO we should provide an implementation of is_dangerous_tile so that we 
> > > get
> > > trieremes save.
> > 
> > We get triremes safe without 3.
> 
> > We can even get them safe without is_dangerous_tile, but their movement 
> > will be restricted.
> 
> How?

Return tile_behaviour NO_ENTRY for off-shore tiles.

> > My current implementation involves the same call-backs.  I am strongly 
> > against their inlining as well.  Essentially my current implementation 
> > follows the idea of your proposal, but without the clear 3-layer split.  I 
> > think I argued for a similar split initially, but gradually gave up :)
> 
> There is another drawback: caching. If caching proves to be usefull
> the middle layer has to provide its own caching structure. ZOC stuff
> for example have to be cached per tile. This will intruduce another
> cell-like struct. It will create more hardware cache misses. So the
> KISS interface will yield a slower implementation. The question is how
> much slower?

What is a KISS interface?  In any case, I will now try to finalise the 
danger-pf and incorporate it in the general pf, then I will need your help 
in looking for bugs and to brush up the style and then we can hack it into 
three layers (or at least switch off caching) and run some tests.

> > > I'm still for get_COP. Or at least a function callback to modify the
> > > moves_left and turn values.
> > 
> > My opinion is a good default COP-function will provide future writers of 
> > get_ECOT call-backs with all the freedom they'll ever need (without going 
> > to the drak side, of course).
> 
> Remember the settler case: it doesn't matter if a settler arrvies with
> 1 or 2 points left at long as the number is >0. We have to support
> this somehow.

We discussed it long and hard and my conclusion was that it is impossible 
to achieve using a COP call-back.  If you disagree, please give me a COP 
and I'll try to get a counterexample.  

It might be possible to solve using more devious techniques, I'l have to 
think.

G.