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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Sun, Jun 30, 2002 at 04:29:43PM +0100, Gregory Berkolaiko wrote:
> 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

I agree that it isn't needed.

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

If you include attacking you have to decide:
 - should a unit attack the enemy
 - should the unit continue traveling after the fight (assuming that
 the unit won)
 - how you return the information that there would be a fight to the
 user

Whether you do this by callbacks or with parameters doesn't matter to
the added complexity.

> 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 */

Are these for a step or for a path?

> 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

If we remove the cop-function the user have to provide two factors
(out of a, and c) to fixate the

 cop = a*BMC + b*EC + c*turn

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

This suprises me a bit but if you say so.

> please give me an example where (turn, remaining_points) is not
> enough, other than TC_NONE.

Ok. Then lets say that total_BMC is undefined if you use a value 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.

The extra cost function will certainly come from outside
path_finding.c.

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

The callback or the path_finding implementation.

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

Ok just add an assert(extra_cost2==NULL) in your pf_get_map.

Do you have any other suggestion how to solve the problem of
maximization uncovered tiles/turn?

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

A user would have to issue at least two calls (pf_get_current_x and
pf_get_current_y) after pf_get_next_location. And since calls are
expensive I would vote for the pf_get_next_position without
alternative functions.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "I heard if you play the NT-4.0-CD backwards, you get a satanic message."
 "That's nothing, if you play it forward, it installs NT-4.0"