[Freeciv-Dev] Re: (PR#2370) Path finding

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Wed, 19 Feb 2003, Gregory Berkolaiko wrote:

> > > > +    node->behavior =
> > > > +        params->get_TB(x, y, node->node_known_type, 
> > > > params->get_TB_data);
> > > > 
> > > > +    node->extra_tile =
> > > > +        params->get_ECOT(x, y, node->node_known_type,
> > > > +                         params->get_ECOT_data);
> > > > 
> > > > Both can be done in the callbacks.
> > > 
> > > You mean both requests for the known type?  I agree.
> > 
> > The known parameter is removed from the signatures and the called
> > functions query the known state by itself if required.
> 
> Yes.
> 
> > > ZoC cannot be done in get_TB, because move_ZoC_allowed is a two-tile 
> > > function and TB is one-tile function
> > 
> > Correct. Than we could add ZoC handling to get_BMC.
> 
> Ok.
> 
> > > > About the known-management: if we remove it from the core code:
> > > >  - it will reduce the number of parameters
> > > >  - it will reduce the size of the cell/node
> > > 
> > > true.  Less memory -- faster.
> > > 
> > > >  - it will increase run-time because of extra function calls to
> > > >  map_get_known by the user functions.
> > 
> > > mind you, caching can still be done through void *data parameter.
> > > We can pass pointer to caching map.

I am really in two minds about it.  On one hand, yes, it's possible to do 
it all in the callbacks.  On the other hand the callbacks will get 
excessively ugly, especially if they do their own caching...

I think we should go for a compromise.  Remove get_TB, leave known and ZoC 
treatment.  What do you think?

About naming.  The current abbreviations are messy:

 *  - basic movement cost (BMC) (of a step): the basic movement costs
 *  of the step as returned by map_move_cost. Note that the BMC of a
 *  step is 0 if the target is unknown.  The idea is that the user
 *  sets the unknown move cost via EC
 *  - capped basic movement cost: (CBMC): MIN(BMC, move_rate)
 *  - extra cost of a tile (ECOT): a user supplied value which is >=0
 *  - total extra cost (TEC): the sum of all ECOT of all tiles which
 *  are used
 *  - cost of a path (COP):
 *    # TC_NONE: COP = PF_TURN_FACTOR * BMC  +  move_rate * TEC
 *    # TC_CAPPED: COP = PF_TURN_FACTOR * CBMC  +  move_rate * TEC
 *    # TC_*_TIME: COP = PF_TURN_FACTOR * ((turn + 1) * move_rate - 
moves_left)
 *                       + move_rate * TEC
 *  - best path: a path which has the minimal COP. If two paths have
 *  equal COP the behavior is undefined.

1. Qualifier "basic" does not clarify anything.  It is applied only to 
move-cost and no other move-cost is there to be distinguished.  We should 
abolish it.  Same as OT qualifier of the extra cost.
So I propose:
MC - move cost of a single move
EC - extra cost of a single tile
total_MC - (effective) move cost of the whole path
total_EC - extra cost of the whole path
total_CC - combined cost of the whole path (formerly COP)

Formulae:
in TM_NONE
  total_MC = sum of MC
in TM_CAPPED 
  total_MC = sum of MIN(MC, move_rate)
in TM_*_TIME
  total_MC = ((turn + 1) * move_rate - moves_left)

total_CC = PF_TURN_FACTOR * total_MC + move_rate * total_EC


This naming scheme is also full of abbreviations but it is more ordered:
total_ means it referes to the whole path.  No total_ means it's of one 
step/tile.

G.