[Freeciv-Dev] Re: Path-finding in the presence of danger

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

Raimar,

On Sat, 28 Sep 2002, Gregory Berkolaiko wrote:

> My path-finding with is_position_dangerous switched on seems to work, but 
> without Cost of Path (COP) yet.  There are a couple of questions I want 
> your opinion on:
> 
> 1. Should dangerous positions be returned (it's no problem with my 
> algorithm)?
> 
> I tend to say yes to that, after al the end-user can filter them out using 
> the call-back that he supplied in the first place.
> 
> 2. COP should only be calculated at the safe positions, right?  It's a 
> simple question, but I am unable to figure it out now...
> 
> Better go to get some sleep.

Aha, so I got some sleep and here's what came with it:

my current algorithm won't work if the extra cost has a chance of spilling 
over and affecting the movecost.  That is, if COP is
        movecost*10 + extracost
then each 10 extracost points get "converted" into a movecost point in the 
eyes of the Dijkstra engine and this will conflict with navigating across 
the dangerous tiles.

It will work if the extracost is considered only as a tie-breaker: 
        path1 is better than path2 
                      iff
        path1.movecost < path2.movecost
                      or
        (path1.movecost == path2.movecost
                      and
        path1.extracost < path2.extracost)

Which is essentially implemented by setting COP to be
        movecost*LARGE_FACTOR + extracost
and ignoring all paths with extracost >= LARGE_FACTOR

It is possible to change the code to code with such "overflowing" 
extracosts (to essentailly use your algorithm although slightly 
optimized), but it will take time (both mine and then CPUs).

Personally, I think that allowing such overflowing extracosts to operate 
together with is_position_dangerous is a bit too much.  The end-user will 
have hard time predicting the effects of the call-backs he specifies even 
without this feature (this is why I am strongly against user-specified COP 
functions).

And another idea I had: in some situations, it makes more sense to MAX 
extracosts rather than sum them.  This can be easily handled by passing 
the current extracost to the get_extra_cost call-back.  The call_back can 
then do whatever to the extracosts, even multiply them together in some 
imaginative manner to get the probability to survive by the end of the 
path.

G.