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

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

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: rf13@xxxxxxxxxxxxxxxxxxxxxx
Cc: freeciv-dev@xxxxxxxxxxx
Subject: [Freeciv-Dev] Re: [RFC] Path finding interface #9
From: Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>
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.

Attachment: waiting.gif
Description: GIF image


[Prev in Thread] Current Thread [Next in Thread]