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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Tue, Oct 08, 2002 at 07:08:01AM -0700, Raimar Falke wrote:
> Ahhh. Yes. Now I see. Mhhh. Indead. That is bad. I don't see an easy
> (reuse of the code in path_finding_plain) solution at the moment.

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

-- 
 email: rf13@xxxxxxxxxxxxxxxxx