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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Thu, Oct 10, 2002 at 11:12:05AM +0100, Gregory Berkolaiko wrote:
> 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.

Then we get safe ships but then optimal exploration behavior is
impossible.

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

http://www.houghi.org/jargon/KISS-Principle.html

The interface I proposed to Ross.

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

For the settler case the COP function will be:

int my_get_COP(int total_BMC, int TEC, int turns, int moves_left)
{
  if(moves_left==0) turns++;

  // if we work without EC
  return turns;

  // with EC
  return turns * SOME_FACTOR + TEC;
}

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

The callback is easy. And I have no problem if we provide a default
(you decide) if no callback is given.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx