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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Mon, 1 Jul 2002, Raimar Falke wrote:

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

The last thing I want is a new flag in the parameter struct already
plagued by a multitude of flags.  

What I want however is a possibility to extend the BMC functions to cover
any such task.  In your code it would amount to adding some ifs in 
claculate_costs_for_move.  In my code it would amount to correctly setting 
up an internal call-back at the time of map initialization.  I think the 
latter approach is better.

Another question is to how let the code know which type of BMC function 
you want to use.  You want to use flags which I think is not too elegant 
as you have to set all the flags at any time, even though you won't use 
them.  Another way is to enumerate all available choices of BMC and let 
the user select the appropriate one (e.g BMC_IGTER) or at least specify 
the unittype and then the BMC (most) appropriate for that unittype will be 
selected.  Then the extension will go in three stages:
1. Write the call-back.
2. Add a new entry to enum available_callbacks
3. Make sure initialization code understands this new entry (something 
like adding new case to a switch).

Then 4 entries in the parameter struct, 
  enum unit_move_type move_type;
  enum unit_flag_id flags;
  bool move_backward;
  enum goto_move_restriction restriction;

will be replaced with:
  enum unit_type type;
  enum available_callbacks callbackname;

plus probably 
  bool ignore_ZOC

The reason I want to separate zoc is because in some cases you want the
simplest possible map to just estimate some distances without going into
too much detail.  Then you don't care for zoc that much.  This is
applicaple to the city-warmap case in the current AI, when such map is
used to estimate distances from enemy cities belonging to
_different_players_ to the city you want to protect.  

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

Yes, but do you intend to write such a thing from scrap?  It can be easily 
made using pf_iterate_map and a slightly modified BMC.  So this function 
for units meeting will just be a wrapper on the existing path_finding 
structure.

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

I'll send you the code later.

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

No.  Full stop.  If you break the 
        turn*move_rate - moves_left + const
relationship between turn and moves_left, your path-finding will get 
screwed, it won't give you best paths anymore.  And I definitely described 
it in detail before.

The cop you included in your code,

+static int my_get_cop(int BMC, int EC, int turns, int moves_left,
+                     void *user_data)
+{
+    return BMC*100+EC+turns+(move_rate-moves_left);
+}

is plain wrong if you use a turn mode other than TC_NONE.

Example:
assume TC_MAXIMUM and move_rate=6, full moves initially, EC=0.

1 - 1 - 6 - 1  (2turns, 5moves left)

6 - 1 - 1 - 1  (1turns, 3moves left)

the first path will be selected, while the second one is obviously 
shorter.

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

Well, there are some tasks that you cannot trust to anyone, let alone 
computer.  I won't waste my time trying to come up with an explorer mode 
which is perfect for all tastes, just because it will involve so many 
parameters that noone will ever use it.

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

Don't worry, be happy!

G.