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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Sat, 25 May 2002, Ross W. Wetmore wrote:

> 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 ...

Yes, I just want to generate standard map from which the shortest safe 
routes from O to A and to B can be read.

> 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.

This is _the_ problem.

Your method #1 doesn't work: you construct initial cost-map completely 
ignoring danger effects.  This might lead to an unsafe path being marked 
out and, which is worse, a safer but longer path being ignored.

To illustrate this I slightly modified my graph: segment h->i now costs 5 
and there is an alternative safe but expesive route h->X->A (the figure is 
attached).  In your method #1 the path through X will not be marked at 
all in the first pass.

Now scroll down to method #2

> 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. 

Exactly.  I could not fully understand your description below, so I will 
give the two methods that I invented yesterday, I suspect they are 
equivalent to your one (scroll down):

> 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?

Notation: MP == move points.

%%%%%

Method G.1:

Do the conventional warmap, recording at safe tiles the shortest time to 
get there and the direction.

Unsafe tiles should be split into 6 (where 6 is the max MP of the 
unit), indexed by j = 1..6.   For an unsafe tile D, in D[j] we record the 
shortest time and direction to get to D while still having j MP left.

Thus in the attached picture g[6] will contain time=18, dir=c,
g[4] will contain time=8, dir d and g[2] won't contain anything.

Any move from safe S to unsafe D will potentially generate two entries at 
D: for just moving to S with whatever moves you have left and for camping 
at S overnight and then moving.

The problem with this method is to organize memory management.

%%%%%

Method G.2:

On any arrival to unsafe tile D we go into a small sub-Dijkstra with the
aim to get through the unsafe cluster.  Let's do an example:

We first arrive to g from O with 3 MP left.  Consider g: we can get to 
h with 2 MP left.  Consider h: cannot get anywhere withour staying 
overnight at h --- don't record anything.

....

At last we arrive to g from c with 6 MP left.  At h we are with 5 MP.  
From h we can now get to X with 0 MP left, which is okay since X is safe.  
We can also get to unsafe j which we do not record.

This can be implemented by setting up a second queue with higher priority 
irrespectful of the distance to tile.  In the example above this queue 
will be holding h (from time to time).


Note: The two methods do exactly the same thing, G.2 is just a 
rearrangement of the operations performed in G.1.  G.2 might be a bit 
slower though.


Opinion: I agree with Raimar, this should be handled separately from the 
mainstream cost-map.  I, however, disagree with him on two other points,
(a) spelling of "trireme" and (b) the above is only a trireme problem.

This is a very important problem of finding a safe route through danger
zones.  Human players do it as a matter of fact, e.g. when approaching an
enemy city with bodyguarded catapult and positioning it on a hill and not
on a flat open place.


Best wishes,
G.

waiting1.gif
Description: GIF image