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

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

At 08:30 PM 02/05/25 +0100, Gregory Berkolaiko wrote:
>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.
[...]
>> 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.

I think we reached the same conclusion up to this point. And you are 
correct that if the danger segment is more than a move in length, then
ignoring danger in the warmap generation will lose safe paths. But it
is perhaps useful to examine elements of the problem in isolation which
is why I left the long first part in in the original message.


>> 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):

I think they are cousins at least. A little more inbreeding and we may
have either a super-species or one with a permanent genetic defect.

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

I think this actually caches the stall computation and backtrack 
selection moving forward, rather than doing it everytime you backtrack
in my case. It is constant time, and will win if there are more than 
6 safe tiles found after the danger segment, which is almost a given.

So this is a very good refinement.

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

I would probably fill in 5, 3, 1 and 0 with values so you could do a 
lookup based on what you need vs a search, but this is noise level
optimization and might change depending on the actual code/usage.

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

I don't think the method is complete. You need to move beyond the first
unsafe point to a subsequent safe point for the data to actually be used,
or in the above, you need additional data at D to make the final choice. 
This doesn't seem to go far enough to talk about this - so it is part 1
with the next as part 2 rather than a completely separate method, no?

>The problem with this method is to organize memory management.

You need an extended field in the warmap at g. This is a pain but not
an irrecoverable issue.

<Aside>
As a quick example, define an interface for extended fields/structs
that has a linked list and maybe type index plus its additional data.
In this case the additional data (or sub-struct element) is an array
of size MP+1 costs plus the back-tile index.

The original warmap needs a link element added to every map location.

Any time you add an extended field to an element, you malloc the block
to the typed blocksize and link it to the chain. Then when you free the
warmap you need to walk any extended field lists freeing their elements
in addition to freeing the original warmap data. 

If you need to add more extended fields, then the code is already there
to handle the free, and you just need to malloc and link it in. 

The other part is a lookup routine that returns any extended element 
from such a list, as in walking the list until it hits the type index.
This too can be generalized so after the first two extensions you have
working code for arbitrary nesting by induction.

Done up front as a generic interface, you avoid rewriting the code
everytime someone needs to add a new field or piece of data. If you use 
no extended fields, you pay only the base link memory cost. If you add 
various extended fields, you pay only for what you dynamically add.

This might play into the modular move_cost function ideas where each
move_cost sub-element probably has its own data block and a modular
stack consists of extended fields of form {(costfn *), <local_data>}.
</Aside>

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

First, you don't need to do a "sub-Dijkstra". As in my example, you just
need to mark the unsafe tiles as "invalid" meaning you can't stop there
and continue normally. Any subsequent updates that would require you to
stop or stall at such a tile would be dropped or equivalently have a
MAX_COST value.

But when you do reach a safe tile from an unsafe one, you have to do more
than just accumulate the single step move_cost. You need to step back 
through all the unsafe path segment until 1) you run out of MP, or 2) you
reach g and index back to the "safe" way to enter g given the accumulated
steps for the unsafe path segment. At this point, if you find you need to
stall before entering g, then you add this stall time to the movecost at
the unsafe tile (i.e. at the end of the path segment, not at g).

Because you are correctly computing the minimum movecost path for stepping
along the unsafe route, and always *adding* penalties as soon as you reach 
a safe tile, you can do this within the current Dijkstra loop. The key
point is that the movecost for a safe tile beyond the unsafe segment will
include the stall and/or higher cost of the alternate back route. If you
can reach this point during subsequent Dijkstra steps with a lesser cost
not going through the unsafe path, this will happen normally.

If you have a chain of such unsafe tiles each with its own indexed list
then you may end up walking back a number of steps, failing to find
something, falling back up through the walk to take the next best case
at a higher level until you eventually find an unsafe segment that is
shorter than a single move.

[Aside]
Note, if you are going to this level to track move boundaries for 
unsafe moves, you also want to do it for safe ones, i.e. if you arrive 
at a point with less than enough movepoints to continue 100% of the 
time, you want to add a stall time to the movecost into this next tile. 
This of course means that your unit move turns are accurately given 
by the movecost values at every tile point in the warmap.
[/Aside]

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

Unless you omitted something, G1 didn't look past the initial unsafe
tile, and didn't do any operation to actually use the data it stored.
So it wasn't complete until you did the G2 computation for this.

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

I agree as well on the separate movecost function.

But then, I was never in the one size fits all "mainstream cost-map" 
camp from the beginning :-).

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

I think the problem is one instance of a fairly important class that
must be deal with. There seems to be growing concensus on this point.

>Best wishes,
>G.
>
>Attachment Converted: "c:\program files\eudora\attach\waiting11.gif"

Cheers,
RossW
=====