[Freeciv-Dev] Re: [RFC] Path finding interface #9

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Sat, Apr 27, 2002 at 05:34:52PM +0100, Gregory Berkolaiko wrote:
> On Sat, 27 Apr 2002, Raimar Falke wrote:
> 
> > On Mon, Apr 08, 2002 at 09:08:43AM +0200, Raimar Falke wrote:
> > 
> > And a new version 9. This one is backed up with an
> > implementation. Changes:
> >  - add missing includes
> >  - remove syntax errors
> >  - rename the parameter map to pf_map
> >  - add some more costs (TC, COP)
> >  - change definition of best path
> >  - change enum turn_mode since now they can't be ORed together anymore
> >  - added turn_cost_factor, move_cost_factor to the parameter (these
> >  are required for TC)
> >  - removed extra_cost2 (since we take care of the tireme case using
> >  is_position_safe)
> >  - correct pf_position: move_expended is not an array and is split
> >  into BMC_of_next_step and total_BMC
> >  - make remaining_move_points an array
> >  - rename pf_get_next_position to pf_get_next_location
> >  - various comment changes
> 
> I guess if you don't want to rename "position", we can rename "location".  
> Please change all occurences of "location" to "node".

What about iterator?

> > Big picture: the previous definition of the term "best path" was flawed:
> >  Best path is a path which has the minimal FC. If two paths have
> >  equal FC, the path with the minimal turns and if these are equal
> >  too the maximum remaining points at the destination is choosen.
> > 
> > It turns out that definition is not the one I want/need for the
> > agents. If we leave extra costs out at the moment I don't want the
> > path which has total_BMC=9 and needs 2 turns before another one which
> > has total_BMC=10 but only takes 1 turn. So the number of turns needs
> > get into the final value. The answer is turn cost (TC). See the header
> > file for the details. Also the sort criteria isn't FC anymore but cost
> > of path (COP). turn_mode now defines which case (best/worst/average)
> > is used to calculate the TC. If you only want sort by to raw BMC you
> > can specify TC_NONE.
> 
> This problem could and should be solved, IMO, by differentiating between 
> BMC in MINIMAL, AVERAGE and MAXIMAL modes.  But your definition is fine 
> too.

But the BMC is the same for all modes. You have to take care of a case
like this: two paths with the same total BMC and different turns and
different safety (by having different extra_cost1). You then have to
give the caller the possibility how much safety he wants to trade to
arrive one turn earlier.

> > pf_construct_path and pf_get_path will now fill out all elements of
> > the turn and remaining_move_points arrays. If this isn't desired and
> > costs too much performance (I doubt this but anyway) I would add a
> > flag to these to methods and not to the parameter.
> 
> Since the above functions are not going to be used by the AI much, the 
> extra performace cost (if any) will be born by the client.
> 
> > Open issues: how is the average case defined? My current
> > implementation:
> >   turns = (min_turns + max_turns) / 2;
> >   points_left = (min_points_left + max_points_left) / 2;
> > is obviously wrong.
> 
> As it is defined in the current warmap / turns_to_whatever implementation:
> (BMC(in AVERAGE mode) - initial_moves_left) / speed.
> 
> which should be near your  turns = (min_turns + max_turns) / 2;

> obviously, there isn't much sense in talking about points_left in AVERAGE 
> mode.

Ack. But it has to set to something.

> > The implementation doesn't handle is_position_safe and air units yet
> > so there may be further changes.
> 
> Unfortunately I am unlikely to be able to have a go at the implementation 
> until end of May.  I would like to ask you not to hurry with the inclusion 
> of yours.

The inclusion will not happen for some time.

        Raimar

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