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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Fri, 4 Oct 2002 rf13@xxxxxxxxxxxxxxxxx wrote:

> > 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.
> 
> This is one extra callback per position.
> 
> Also the same position can be given back twice. This may confuse the
> user. This is the main reason why IMHO dangerous positions shouln't be
> returned.

Yes, I agree.

> > 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...
> 
> The best (micro-)path (COP) should be used in between the safe positions.

Ok.

On Fri, 4 Oct 2002 rf13@xxxxxxxxxxxxxxxxx wrote:

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

The problem is that with so many restrictions and corrections, the 
path-finding will becme highly unstable (not as a code but as an ideal 
process).  It will become an arcane art to specify call-backs which will 
combine to produce reasonable results.

But this is the problem of the end user, so for now it's clear for me what 
to do.

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

Unfortunately your format of COP callback allows functions which break 
Dijkstra rules.  This is a separate discussion though.

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

We have rather different attitudes to the subject.  You seem to prefer to 
have many call-backs, while I would rather have one which does it all.
For this particular proposal,
        int get_extra(int x, int y, int curent_extra, void *data)
provides for the desired freedom.

G.