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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Thu, Feb 20, 2003 at 01:32:32PM +0000, Gregory Berkolaiko wrote:
> > > > > 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?

You mean get_BMC and get_TB get merged? Or how do we remove get_TB?

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

Historical reasons.

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

I like it. Really.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "At the beginning of the week, we sealed ten BSD programmers
  into a computer room with a single distribution of BSD Unix.
  Upon opening the room after seven days, we found all ten programmers 
  dead, clutching each other's throats, and thirteen new flavors of BSD."