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

[rf13@xxxxxxxxxxxxxxxxx]

On Sun, Sep 29, 2002 at 06:17:00PM +0100, Gregory Berkolaiko wrote:
> 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.

The whole point of extra cost was that it is possible that extra cost
can compensate move cost and the other way around.

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

Or this could mean that the implementation has to cope with all COP
functions which follow the Dijkstra rules.

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

You are right that it may be nice to not force addition by allow more
freedom. We had this feature in version 11 of the interface with the
extra_cost2 callback.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx