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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Sun, 30 Jun 2002, Raimar Falke wrote:

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

I picture it like this.  AI says "let's iterate through all places 
reachable and/or attackable by this sub".  pf_get_map plugs in the 
relevant callback ensuring that:
1. places occupied by enemy naval units are returned by the iteration
2. sub isn't allowed to pass through such places.

pf_next_whatever doesn't return anything abnormal, it's up to the user to 
get the coordinates and to figure out whether he wants to go or not.

Next thing AI says "let's see where this transport can go" and pf_get_map 
puts it normal sea movement callback ensuring that transport doesn't 
attack anything.

Next thing AI says "give me a map for this chariot, but overlapping into 
the sea by one square, cos I want to figure out where should I send my 
trireme to pick it up".  And pf_get_map puts in yet another BMC callback 
cleverly coded by you or me or even Ross (but we really want to avoid 
having his code in CVS, so better you or me) ;)

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

For the whole path.
If you insist, we can go for long int wich effectively means that 
PF_MAX_*COST can be around 10^9.  But I don't think it's necessary.

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

if we agree that total_BMC is undefined if turn mode is other than 
TM_NONE, then define

cost = (mode == TM_NONE ? total_BMC : (turn+1)*move_rate - move_left)

and have

cop = a*cost + b*EC

now we need only one factor, correct?

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

Trust me :)

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

Smashing.

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

If you say so :)

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

maximization of uncovered tiles would be a pain...

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

I think the current eXplorer mode is adequate apart from triremes sinking.

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

Let's have both then and if the tests show that getting the whole position 
in one go is faster than getting only necessary info but in many goes, 
I'll happily follow your way.

So shall we have:

/* 
 * Performs one iteration on the map.  The current posistion and 
 * the costs can be read using following utility functions 
 */
bool pf_iterate_map(pf_map_t pf_map);

/*
 * Provide info about current position of the map iteration.
 */
int pf_get_current_x(const pf_map_t);
int pf_get_current_y(const pf_map_t);

/* Here cost is BMC in TM_NONE case and (turns+1)*move_rate - points_left 
 * otherwise. */
int pf_get_current_cost(const pf_map_t);
int pf_get_current_extra_cost(const pf_map_t);

/*
 * Return full info about current position in the map iteration.
 */
struct pf_position *pf_get_current_position(const pf_map_t, 
                                            struct pf_position *);

?


G.