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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Tue, Jul 02, 2002 at 09:38:07PM +0100, Gregory Berkolaiko wrote:
> On Tue, 2 Jul 2002, Raimar Falke wrote:
> 
> > 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.
> 
> I agree.  But in my opinion it is more elegant to extend one enum than to 
> add more and more flags.

So we both have our opinions.

> > > > > 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
> 
> Exactly.  But if fast is boat and slow is chariot, pos_s will always be 
> NULL (with the exception of ports).  So we need a slightly different BMC 
> for chariot here, which woul allow one overlap into the ocean.

Than change it:

while pos_f=get_next_pos(map_f):
  for i in square_iterate(pos_f, 1)
    pos_s=end_pos(get_path_from_map(map_s, i))
    if not pos_s:
      continue
    turn=MAX(pos_f.turn, pos_s.turn)
    if i!=pos_f:
      adjust turn to take care of (un)loading
    if turn<best_turn:
      best_pos=pos_s
      best_turn=turn

> > > > > > 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",...
> 
> okay.  different wording is fine.  but the only cop which will produce 
> anything useful is the one I mentioned earlier.  So why do you want to 
> allow cops that will not do anything useful?
> 
> > > 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.
> 
> I don't think this callback is any better than cop-callback.  I'll give it 
> a think though
> 
> Here is a summary of my position anyway:
> 1. In TM_NONE turn and moves_left are useless.
> 2. In TM_MIN or MAX, BMC is useless and the only combination of turns and 
> moves_left that is good for anything is
>       moves_spent = (turns+1)*move_rate - moves_left
> 3. Thus we can define a universal quantity
>       cost = (tm == TM_NONE ? BMC : (turns+1)*move_rate - moves_left)
> which is the only sensible quantity there is.
> 4. cost + EC is your cop

Ok if we also have the adjust_numbers callback.

> > 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.
> 
> Whatever.  By the way, why "TC" ??

I believe it was TurnCost. TM for TurnMode and then a TM_SAFE and
TM_LUCK?!

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Despite all the medical advances of the 20th century, the mortality 
  rate remains unchanged at 1 death per person."