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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

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.

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

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

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

G.

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

G.