[Freeciv-Dev] Re: [RFC] Path finding implementation.

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Sun, 30 Jun 2002, Raimar Falke wrote:

> On Sun, Jun 30, 2002 at 12:01:50AM +0100, Gregory Berkolaiko wrote:
> > Raimar, did you notice that the only thing you actually agreed to was the 
> > variable renaming?
> 
> No one said it would be easy.

It just seems that your idea of reaching a compromise is to sit and wait 
till your opponent agrees with all your demands.

> > On Sat, 29 Jun 2002, Raimar Falke wrote:
> > 
> > > > 2. I think railroad isn't really needed.  If you really want a 
> > > > tie-breaker, use turns.
> > > 
> > > This was intended as a measure against loops. Not sure if it is
> > > needed.
> > 
> > not needed.  see your own cmp_function.
> 
> I don't understand.

remove railroads from you cmp_function and try to visualize situation when 
a route with a loop is selected in lines 556-564 of your path_fincing.c

> > b) put "assert(0)" instead of "continue" above
> 
> No. Note that we are testing here neighbour and not the
> current_cell. I agree that the latter should always be IS_KNOWN.

my mistake.

> > > This sounds like a problem. Please tell me why do you need this
> > > flexibility. The last time we discussed this you brought the backward
> > > idea up (which is needed for city centeric cases). So we added the
> > > backwards flag. What else do you need?
> > 
> > I can come up with many things.  Submarines attacking ports, amphibious 
> > units, estimating the time for a cavalry to go to a port and then being 
> > ferried to New York...
> 
> Note that path_finding.c leaves attacking to the caller. It would add
> another piece of complexity if we add this to path_finding.c

no it wouldn't if we have call-backs.

however these call-backs should be visible inside path_finding.c only.  
thus they become a detail of implementation, rather than interface.

the down-side of it is that all wrappers would have to go to 
path_finding.c

> > But actually, I am ready to agree to your implementation, provided there 
> > is a possibility to put wrappers like 
> >     pf_map_t pf_get_map_by_unit(struct unit)
> > inside the path_finding.[ch]
> > 
> > No sane person should be forced to use parameter struct.
> 
> There is no arguing about this. I agree that only a few callers will
> use the "raw" pf_get_map function.
> 
> However I'm not so sure if we are able to make a generic
> pf_get_map_by_unit which only takes the unit. Because for example
> there is no generic extra_cost1 callback which can be used by this
> function.
> 
> The code in ai/ may provide such function. But then it would not be
> placed in common/path_finding.
> 
> > > > Now, let's load the header file...
> > > > Comments rated 1->5 reflecting strength of my feeling about them.
> > > > 
> > > > >  *  (which all have to be >=0)
> > > > >  *  - cost of a path (COP) as returns by get_cop.
> > > > >  *  - best path: a path which has the minimal COP. If two paths have
> > > > >  *  equal COP the behavior is undefined.
> > > > 
> > > > (4) I don't like cops, but I can live with it, if you absolutely insist.
> > > > I think 
> > > >         time_to_dest * PF_IGNORE_COST + extra_cost_to_dest
> > > > should be the universal cop.
> > > 
> > > PF_IGNORE_COST?
> > > 
> > > > > /*
> > > > >  * The step is ignored completely if any extra cost or the sum EC is
> > > > >  * larger than or equal to PF_IGNORE_COST.
> > > > >  */
> > > > > #define PF_IGNORE_COST        FC_INFINITY
> > > > 
> > > > (5) I'd like it to be finite.  You are using 100 in your_cop anyways.
> > > 
> > > It is finite ;) And 10^9 is a small number compared to other numbers
> > > ;)
> > 
> > Very witty remark.  Now, can we have a number which is less than 10^9 
> > please?
> 
> How large? And why?

I missed another thing.  Instead of IGNORE_COST, I want
#define PF_MAX_COST  255     /* maximum BMC */
#define PF_MA_EXTRA_COST  1000 /* maximum extra cost */

the numbers above can be as large as you want provided 
        PF_MAX_COST * PF_MAX_EXTRA_COST
fits in an int.  I hope it's not too restrictive. :)

I need it to have a standard cop function.

> > > The 100 is really just a number in this example. It doesn't have any
> > > value. The factor will mostly influenced by a function similar to
> > > access_danger.
> > 
> > what if somebody combines extra_cost which returns values up to 300 with a 
> > COP function which uses the worthless number 100?
> 
> What should happen? The user has control over both and if the user
> screws it up somehow the user has just screwed it up.

If you use standard cop-function with PF_MAX_EXTRA_COST instead of 100, 
the user will have to look for some other place to screw up.

We discussed it at length before and you failed to come up with an example 
where user needs to define a cop-function

> > > > >     int x, y;
> > > > >     int turn, remaining_move_points;
> > > > >     int BMC_of_next_step;
> > > > > 
> > > > >     /* Total BMC required to reach this position. */
> > > > >     int total_BMC;
> > > > 
> > > > (3) Do you really need the total_BMC ?  Isn't turn + remaining_points 
> > > > enough?  Causes some unnecessary problems with my implementation...
> > > 
> > > It was included to allow easy adoption of existing code. It is
> > > basically the number calculated by gotohand.c. And it my be used to
> > > get a rough turn estimation when you use TC_NONE.
> > 
> > Yep, sorry, I forgot that you always want 3 variables when you can do away 
> > with one.  Let total_BMC stay, but it will only have meaning if TC_NONE is 
> > used.  If something else is used, you can have turn + remaining_points. 
> > Is that acceptable?
> 
> But total_BMC is computed in all cases. So in the TC_NONE case you
> don't have a better metric. However in the non-TC_NONE you can still
> access it.

total_BMC is computed in all cases in your code only.  that's partly the
reason why it takes so long.  please give me an example where (turn,
remaining_points) is not enough, other than TC_NONE.

> > > > Do you plan any parameters to extra_cost that are not contained in 
> > > > pf_map?
> > > 
> > > The known state is cached and can be passed. A user can do not much
> > > with the map argument. Note also that the callback can be called
> > > everytime. And if you really want to use the map in some way you can
> > > pass it via the user_data parameter.
> 
> > Do you want to trust extra_cost_fn to "a user"?
> 
> I don't understand. Do you ask if the function type should be public?

I ask if the function should be allowed to come from outside 
path_finding.c
Maybe it should, fine.

> > > > >  /*
> > > > >   * Callback which can be used to provide extra costs depending on
> > > > >   * the path to this tile. Can be NULL. Parameters are path and
> > > > >   * extra_cost2_data.
> > > > >   */
> > > > >  int (*extra_cost2) (const struct pf_path *, void *);
> > > > 
> > > > (2) A cost depending on the whole path ?!?!  That's quite exotic.  
> > > > Please 
> > > > justify.
> > > 
> > > I think (I don't have code yet) that this is needed if you want to
> > > maximize the uncovered tiles/turn. Think auto explorer.
> > 
> > I think it's too much bother for very little gain, but let it be.

I thought some more about it and decided that such maximization would be a 
pain to implement.  In principle I am not against such extr_cost, but I 
think the relevant code should be commented out until someone comes up 
with such a call-back, which I think will never happen.  Otherwise it's 
another piece of gratuitous code.

> > > > > /*
> > > > >  * The last position of the next best path is written in the given
> > > > >  * location. Returns FALSE if no more positions are available in this
> > > > >  * map. Behavior is undefined after pf_get_path was called.
> > > > >  */
> > > > > bool pf_get_next_location(pf_map_t pf_map, pf_location_t * location);
> > > > 
> > > > (3) Scrap returning the location.  See below
> > > > 
> > > > > int pf_get_location_x(pf_map_t pf_map, const pf_location_t location);
> > > > > int pf_get_location_y(pf_map_t pf_map, const pf_location_t location);
> > > > 
> > > > (3) I prefer my:
> > > > int pf_get_current_x(const pf_map_t);
> > > > int pf_get_current_y(const pf_map_t);
> > > > int pf_get_current_cost(const pf_map_t);
> > > > int pf_get_current_extra_cost(const pf_map_t);
> > > 
> > > This holds state in the object. I dislike this.
> > 
> > Oh, tell us about it!
> 
> > And your object doesn't hold the state?
> > What's that on the top of yer heap then?
> 
> The heap isn't visible to the user.

Neither state is visible to the user.

> > The second argument is gratuitous.  And if it's something that will take 
> > clocks to compute, like pf_position, it's just plain wrong.
> > 
> > Yes, pf_get_turn(const pf_map_t) would be convenient too.
> 
> So we have to decide between an explicit object passed between
> pf_get_next_location and the query functions. And whether there is one
> query function (which can be merged with pf_get_next_location) or
> multiple.

My proposal is the current interface without the "location" passed back 
and forth.  Which is essentially multiple query functions.

If for some reason you want to store all available info about certain 
node, feel free to allocate a pf_position and fill it at your expense.

G.