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

[rf13@xxxxxxxxxxxxxxxxxxxxxx (Raimar Falke)]

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.

> There are other possibilities which are polynomial, according to my
> estimates, but they are ugly.

Please show.

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

I agree that we shouldn't allow this problem to slow the rest down.

IMHO we should provide an implementation of is_dangerous_tile so that we get
trieremes save.

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

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

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

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

        Raimar