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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Wed, Oct 09, 2002 at 03:29:11PM +0100, Gregory Berkolaiko wrote:
> On Wed, 9 Oct 2002, Raimar Falke wrote:
> 
> > On Wed, Oct 09, 2002 at 01:57:33PM +0100, Gregory Berkolaiko wrote:
> > > Raimar,
> > > 
> > > I agree with you on "no easy solution".  The "check _all_ paths" solution
> > > is not a solution, it's death in disguise.  Just consider a diplomat
> > > trying to find a way to an enemy city across enemy rail-network -- this is
> > > a likely customer of is_dangerous_position and the number of paths is
> > > exponential!
> > 
> > If I'm correct we only need to start the "all path search" if we didn't
> > found a way with my current code.
> 
> yes right.  but even if this happens once in the situation above, it'll
> bring down the server!
> 
> > > There are other possibilities which are polynomial, according to my
> > > estimates, but they are ugly.
> > 
> > Please show.
> 
> 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
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?

> > > 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.
> > > 
> > > If you decide to try for the most general case, it's up to you, but I
> > > think we shouldn't allow this to stand in the way of other developments.  
> > > And I certainly don't want to spend my time on it.  Therefore I suggest we
> > > accept the constrain 3. for now, try to work the code into CVS and then
> > > add modules if wanted.
> > 
> > If we accept 3. I can also remove the second plain map from my code.
> 
> Right.
> 
> > 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?

> > > I feel there are three issues to be discussed:
> > 
> > >  a. Are we going for the structure outlined in your email to Ross (I do 
> > >     like it, but is it worth the bother?)
> > 
> > This structure involves callbacks which can't be inlined. This is IMHO
> > the only drawback. A speed-vs-flexiblitiy tradeoff.
> 
> 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?

> > >  b. How to incorporate is_dangerous_tile in the code and avoid slowing 
> > >     down of the mainstream algorithm (I have some ideas on it)
> > 
> > Faster than my pessimistic code?
> 
> I expect it to be faster than your pessimistic code even without plain_map2.
> But this is not supported by any data yet.
> Right now I have two "separate" versions of path-finding, fitting to the 
> same interface.
> 
> > >  c. Can we drop get_COP callback (for speedup and code clarity)
> > 
> > I want to add to some older email that get_COP allow functions which doesn't
> > satisfy Dijkstra BUT we can and do catch these.
> > 
> > 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.

> > > Tell me whem you have free time and I'll send you the latest versions of 
> > > path_finding with and without danger.
> > 
> > I should have my development environment back online at the weekend.
> 
> I'll brush up the code by that time.  It will be done in the assumption of 
> 3.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx