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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

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