Complete.Org: Mailing Lists: Archives: freeciv-dev: May 2002: [Freeciv-Dev] Re: [RFC] Path finding interface #9

# [Freeciv-Dev] Re: [RFC] Path finding interface #9

[Top] [All Lists]

 To: rf13@xxxxxxxxxxxxxxxxxxxxxx Cc: freeciv-dev@xxxxxxxxxxx Subject: [Freeciv-Dev] Re: [RFC] Path finding interface #9 From: Gregory Berkolaiko Date: Fri, 24 May 2002 17:34:58 +0100 (BST)

```I am working on the path-finding implementation right now.  And I
encountered a problem in an area that I thought we solved.

It's the "waiting in a safe place" problem.  Some direct applications
include triremes (waiting to regain full MP before a dash across a
channel) and diplomats (waiting out of reach of the enemy and then making
a dash to subvert city).

The solution lies, of course, in recording the safe tile S twice, once
with the minimal moves required to reach it and once with the min moves +
what amounts to spending the turn here.  However there is a problem in
what to record as the best time to reach a dangerous tile
D, if there are multiple routes leading to it, each with a different
number of moves_left when at the tile D.

I attach a picture aimed to illustrate this problem.  O is the origin.  A
and B are the possible destinations (and you don't know which one you need
a priori).  Red circles are the dangerous tiles.  Your unit has 6 move
points at the start of each turn.

What shall be recorded at the tiles g,h,i after the completion
of the algorithm?  Note that the best route to A is O-d-g-h-i-A and the
best route to B is O-e-f-g-h-i-B: a situation alien to the classical
Dijkstra method.

Please let me know your expert opinions, but don't rush, the problem is
more difficult that it might seem.

G.
```

waiting.gif
Description: GIF image