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

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

I think you may need to explain a little more what sort of output 
result you are looking for or how you intend to use it. But 
assuming this is a standard warmap generation, and path generation 
is done as a subsequent step ...


The appropriate values for the warmap at g are the path independent 
raw movecosts, if you intend to use the warmap for multiple paths 
that will have different modifiers. I don't see how any single value
stored at such a location can deal with more than one path 
dependent effect. The problem too is that it is usually the path
segment you haven't yet completed that determines the effect.

So we continue on building a path independent warmap ignoring the
danger constraints for now.

To assemble a path vector, you step backwards from a target. 
To do this taking into account additional effects like "danger",
one must in effect continue through the full danger path segment
as a single unit move (i.e. this is the constraint). The path from 
A or B will leave you with a different raw back count at g which is
the end of the danger segment, so you know the danger segment
count is 3 plus the last step to i. This is simple enough to code
in that if you are in danger you must keep going as part of the 
same single step.

Now, because the danger count is 4 or 5, only steps into g of 0-2
or 0-1 are allowed safely. Thus you eliminate all but c, f coming
from B and c, f, d coming from A. You presumably pick the lowest
count of these as the next element of the path. The constraint
you apply is that (>i + 3 + g<) <= 6 && is_min(next_count(g<*)) in
some sort of cryptic pseudo code form.

If you need the exact move cost of the path, then you may need to 
stall before entering g. You can only determine this from the 
forward count in the warmap though, if there are no other stalls. 
To put it another way, you need to leave the constraint value in 
the specific path segment for g as the move constraint to enter g, 
which is what I think you were asking, but in the path dependent
vector, not the actual warmap.

If you complete the path vector by back stepping, then count it 
forward again, you can add stall values to reach the next move 
turn to any running move count total at points like entering g, 
whenever you fail the constraint at those points.

Having done this, you have a path vector and an accurate move count
that includes stalls for path dependent effects like danger.

But note, this may no longer be the shortest path. Both the stalls
and the constraint limitation applied at g may result in a final
cost that is more expensive than one the unconstrained warmap
ruled out. And although it will correctly generate the paths, and
shows the algorithmic elements, it yo-yos a lot more than seems
reasonable in doing it.


To build the constraint into the actual warmap generation, one 
needs to do something really clever to handle path segments as 
pseudo single moves, i.e. from the above, you really don't know
how to adjust at g until you traverse h, i and A or B. 

For mumbling purposes, let's see where this might lead ... 

If one computed the normal cost for g but marked it as invalid, on
the next step from g one would likewise compute the normal cost for
danger tiles and mark them as invalid. But for a safe tile, one
would need to evaluate the cost by backtracking to g choosing the
constrained route into g and add any stall. This then becomes the
count value for the safe tile. If there is no safe count there is no
update. When you add the constraint and stall "on the path segment"
which needs it, the tile count is now a true move count. And since
any updated tiles can still be reset to a lower path count as the
warmap iteration progresses, you will guarantee shortest path with
apprpriate backtrack direction vector when you finally reach A or B.

When you reach A or B you will have exact path counts including stall
without the need to backtrack and recount.

When you backtrack from either A or B to generate the path, then 
you may need to play the above danger game to insert the stall
value at the entry to g in the path vector so the unit will know
when to take its preparatory siesta during a do_unit_goto().

Does this make sense? or help in any way?

Cheers,
RossW
=====

At 05:34 PM 02/05/24 +0100, Gregory Berkolaiko wrote:
>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 Converted: "c:\program files\eudora\attach\waiting.gif"