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

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

At 11:20 AM 02/04/27 +0200, 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

Most of these changes reflect the basic mistake in the approach and
anal attention to unimportant details.

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

Best path is what the developer wants at the time his code is being
developed, not what you think was important because of your agents 
special case needs.

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

As long as others are free to implement a completely different system
for their needs that is flexible and extensible, the performance issues 
or added performance penalties and constraints imposed by all these 
decisions are only an issue to the agent code.

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

All these complications etc. are only necessary in the one-size-fits-all
model which is generally the wrong way to go for this sort of thing. But
you have been warned about this many times, so carry on gaining personal
experiences until you learn your lessons :-).

>       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."
>
>Attachment Converted: "c:\program files\eudora\attach\path_finding9.h"

Cheers,
RossW
=====