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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

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

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.

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.

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.

The implementation doesn't handle is_position_safe and air units yet
so there may be further changes.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "There are three ways to get something done. Do it yourself, hire someone
  to do it for you or forbid your kids to do it."

path_finding9.h
Description: Text document