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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

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.

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

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

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

Not a bad idea.  Yes.  Again won't suit everyone, but it's interesting.

G.