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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Sun, Jun 30, 2002 at 06:59:55PM +0100, Gregory Berkolaiko wrote:
> 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.

So you want a "also return paths which end in fights" flags?

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

Haven't we already agree that we need functions for unit meeting?

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

I'm not sure what is gives you but we can define such constants.

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

Almost. In the SMA case the get_cop would be:

  if moves_left==0:
    turns++
  return a*turns + b*EC

How can we model this?

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

I disagree. What would you want for your initial explorers? To
discover huts (since there are distributes equally you have to
maximize your uncovered tiles/turn) and to explore the surroundings to
find good city spots. The current eXplorer mode doesn't meet the last
task.

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

Not happily but I agree. So that we can come to an end.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Of course, someone who knows more about this will correct me if I'm
  wrong, and someone who knows less will correct me if I'm right."
    -- David Palmer (palmer@xxxxxxxxxxxxxxxxxx)