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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Tue, Jul 02, 2002 at 03:35:11PM +0100, Gregory Berkolaiko wrote:
> 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.  

You can model ignore_ZOC in my model quite easy by just adding
F_IGZOC to the flags.

If we talk about the interface and not the implementation (callbacks)
the difference is that the user in model just copies the values from
the unit struct and the unit type struct and be done with it. The path
finding will use the exact correct numbers not the "(most)
appropriate". If the user wants them backwards: flip a flag. If the
user wants to be informed about attackes (note that this doesn't have
to do something with BMC) flip a flag. In your model you give the same
information using a new enum which the user has to choose.

So in both models you can express the same and in both models you have
to change the code if you want something new.

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

This is correct. The implementation is simple:

fast = choose the faster unit
slow = is the other

map_f=get_map(fast)
map_s=get_map(slow)

best_pos=NULL
best_turn=9999999

while pos_f=get_next_pos(map_f):
  pos_s=end_pos(get_path_from_map(map_s, pos_f))
  if not pos_s:
    continue
  turn=MAX(pos_f.turn, pos_s.turn)
  if turn<best_turn:
    best_pos=pos_s
    best_turn=turn

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

We have to distinguish between two problems:
 - the uniform cost search (the general form of Dijkstra) only wants
 that after a step your cost didn't decreased (it can stay
 constant). This is the reason for this line:
  assert(dest->COP > 0 && dest->COP >= src->COP);

 - while the uniform cost search will search you the path with the
 minimal cost it is up to the user (of the uniform cost search) to
 decide what is the cost function.

So the statement "is plain wrong" is plain wrong ;) It is more a
"doesn't do anything useful", "may produce not the results you
expected at first sight",...

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

Ok I should have written in large letters a comment above my_get_cop:
"This is sample code. Don't use it in production. This code performs
useless operation."

But this still leaves the original problem. I suggest another
solution: a call back in the form:

 void adjust_numbers(int *BMC, int *EC, int *turns, int *moves_left)

it can be NULL. It is called before the COP is calculated. Then we
only need two user supplied factors and fix the COP calculation.

BTW: we should rename TC_MAXIMUM to TC_SAFE or TC_UPPER_BOUND or
similar. I already have a hard time remembering what it means.

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

It really is quite easy. You just have to circle one point (the
capital for example or the center of known tiles at this island).

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "When C++ is your hammer, everything looks like a thumb."
    -- Steven M. Haflich