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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

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

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

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

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

Best,
G.