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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Sat, Feb 22, 2003 at 05:55:04PM -0600, Mike Kaufman wrote:
> here's a list of issues before I got tired and/or bored:
> 
> -mike

> 
> 
> path_finding.h:
> 
>  * DEFINITIONS:
>  *  - step: one movement step which brings us from one tile to an adjacent one
>  *  - turn: turns spent to reach a tile.  Since movement rules involve 
>  *  randomness, we use different "turn modes" to get an estimate of this 
>  *  number
> should be rewritten thusly:

>  * DEFINITIONS:
>  * step: one movement step which brings us from one tile to an adjacent one
>  * turn: turns spent to reach a tile.  Since movement rules involve 
>  *       randomness, we use different "turn modes" to get an estimate of 
>  *       this number

The first can be formatted with emacs but the second can't.

> sp.
>  *  - extra cost (EC): extra cost of a _sinlge_ tile.  A user supplied value 
>  *  which is >=0
> this is also nonsensical.

Why?

>  *  FORMULAE:  
>  *  - calculating total_MC
>  *  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
> this makes no sense.

Do you understand

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

>  *  - calculating total combined cost
>  *     total_CC = PF_TURN_FACTOR * total_MC + move_rate * tot
> used PF_TURN_FACTOR before defining

Yes.

>  * A) the caller knows the goal position and wants to know the path:
>  * 
>  * struct pf_parameter parameter;
>  * pf_map_t pf_map;
>  * struct pf_path path;
>  * 
>  * // fill parameter
>  *
>  * pf_map = pf_get_map(&parameter);
>  *
>  * pf_get_path(pf_map, goal_x, goal_y, &path);
>  *
>  * if(path.is_valid) {
>  *   // success
>  * } else {
>  *   // no path could be found
>  * }

> why is pf_map even here?

Because you can't/don't want to integrate it with pf_get_path _and_
pf_next. These functions are the one which get called after
pf_get_map.

> why isn't goal_x and goal_y in pf_parameter?

These are useless for the pf_next usage of pf.

>  * // fill parameter
>  *
> should be explained what you're filling this with.

This is explained below.

> I really need some examples for the cost functions or where to find such 
> animals.

pf_tools.c has some. Not sure what can be said.

>  * 1. It is useful to limit the expansion of unknown tiles with
>  * the get_TB callback because the MC of unknown tiles is 0.
> not understandable.
>  * 2. If there are two paths of the same cost to a tile (x,y), you are
>  * not guaranteed to get the one with the least steps in it.  If you care,
>  * specifying EC to be 1 will do the job.
> why not for either point?

> EC is not explained at all.

EC was explained above.

>  * 3. To prevent AI from thinking that it can pass through "chokepoints"
>  * controlled by enemy cities, you should specify TB of each enemy city to 
>  * be TB_DONT_LEAVE.
> 'checkpoints' or 'waypoints' would be better here.
> also s/TB/the tile behavior/
> 
> 
>  * Maximal MC. If exceeded, tile is randed unreachable.
>                                     ^branded
> sp.

> /*
>  * Maximal number of steps in a path.
>  */
> #define MAX_PATH_LENGTH 200
> 
> this should be 363 (or dynamic which would be ideal)

Yes it is arbitrary. Yes dynamic would be ideal. No one bother to do
till now.

> /*
>  * The factor which is used to multiple TEC in the total_CC calculation. See
>  * definition of total_CC above.
>  */
> #define PF_TURN_FACTOR  65536
> 
> this is a circular definition
> 

>   TB_DONT_LEAVE,                /* Paths can lead _to_ such tile, 
>                                  * but are not allowed to go _through_ */
> better to be named TB_CANT_LEAVE

The callback returns this value to say "don't leave".

>    * No turn numbers or moves_left are used at all. The fields "turn"
>    * and "moves_left" will always be -1. 
>    */
>   TM_NONE,
> "moves_left" being -1 means nothing to me in this context.
> 
> 
>   /* 
>    * Callback to get MC of a move from (from_x, from_y) to
>    * (to_x, to_y) and inthe direction dir.
>    */
>   int (*get_MC) (int from_x, int from_y, enum direction8 dir,
>                  int to_x, int to_y, void *);
> 
> sp. 'inthe'
> also enum direction8 dir as a parameter is confusing. It seems that either 
> this is not needed, or two such parameters are. more explanation in the
> comment is certainly required.
> 
> 
>   void *get_TB_data;            /* Passed as last parameter to get_cost */
> all three have this comment, are you sure?

This is wrong and obsoleted.

> typedef struct pf_map *pf_map_t;
> I don't like this at all. It's very confusing, but considering...

I have no problem removing this typedef. A lot of the other freeciv
code also uses structs directly.

>  * over all paths. Does not perform any computations itself, just sets
>  * everything up.
>  */
> pf_map_t pf_get_map(const struct pf_parameter *const parameter);
> hmm, don't like the name here. You're allocating memory, but the
> name of the function doesn't lead you to believe it. Better
> pf_create_map() and rename the internal function something else.

I agree.

> the bevy of pf_next_*: the definitions of these are worrisome. I
> think it's because 'next' and 'last' aren't being used
> precisely. 'internal buffer' should be explained briefly as well.

Yes.

I leave the other comments to Gregory.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "I do feel kind of sorry for Microsoft. Their attornies and marketing
  force must have tons of ulcers trying to figure out how to beat (not
  just co-exist with) a product that has no clearly defined (read
  suable) human owner, and that changes on an hourly basis like the
  sea changes the layout of the sand on a beach. Severely tough to
  fight something like that."
    -- David D.W. Downey at linux-kernel