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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

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!

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

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.

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?)
 b. How to incorporate is_dangerous_tile in the code and avoid slowing 
    down of the mainstream algorithm (I have some ideas on it)
 c. Can we drop get_COP callback (for speedup and code clarity)

Tell me whem you have free time and I'll send you the latest versions of 
path_finding with and without danger.

G.

On Wed, 9 Oct 2002, Raimar Falke wrote:

> On Tue, Oct 08, 2002 at 07:08:01AM -0700, Raimar Falke wrote:
> 
> After a day I came to the following:
> 
> 1) my current solution is pessimistic: it won't find a path if there
> is one. This is better than optimistic because it won't put ships in danger.
> 
> 2) AFAIK there is no easy solution. The problem is: we have start and
> goal (both safe) position and search the best (COP) path which
> satisfies a certain condition (only needs one turn). One solution is
> brute-force: we just create all paths. We chop the search tree using
> the two conditions (abort if no moves left are remainging or goal
> reached). The so found paths are sorted by COP and the best one is
> choosen.
> 
> If we can guarantee that we find the path with the minimal COP at
> first (and lucky we can do this) we don't have to create all paths. An
> algorithm which does this is a modified Dijkstra which operates on
> paths and not on positions. Main loop will look like:
> 
> init paths_to_consider
> 
> while have paths in paths_to_consider:
>   p=get path with lowest COP from paths_to_consider
>   if moves left at end position of p < 0:
>     continue
>   if end_position of p == goal:
>     break // finished
>   loop over neightours of end pos of p:
>     add expaned path to paths_to_consider
> 
> Worst case estimation: trireme with 5 moves (Magellan) and one save
> position. My current solution will search (2*5+1)^2=121 paths of
> length 5. The above solution will at most create 8*7*7*7*7=19208 paths
> of length 5.
> 
> Side note: the problem "search the best path which satisfies a certain
> condition" is the same at the general "saerch a path from A to B and
> don't stop at dangerous position at the end of turn". The algorithm
> above will also solve this general problem BUT it will be a lot more
> expensive.
> 
>       Raimar
> 
>