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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

Quoting Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>:

> The diplomat code has nothing to do with the PF. It is _one_ user. It
> should be separately committed.

ok

> > + Freeciv - Copyright (C) 2002 - The Freeciv Project
> 
> 2003

ok

> > + *  - move cost (MC): move cost of a _single_ step.  Note that the BMC of
> a
> 
> Use of BMC.

ok

> > + *  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)
> 
> I don't know what "in TM" means here.

TM was defined earlier and a reference to a more detailed explanation was given

> > +/* 
> > + * Maximal MC. If exceeded, tile is randed unreachable.
> > + */
> > +#define PF_MAXCOST 2000
> 
> This wasn't there the last time. It should go.

No.

> > + * Specifies how total_MC, turn and moves_left are computed (for deatils
> 
> Spelling.

Yes.

> > +enum turn_mode {
> > +  /* 
> > +   * No turn numbers or moves_left are used at all. The fields "turn"
> > +   * and "moves_left" will always be -1. 
> > +   */
> > +  TM_NONE,
> > +
> > +  /* 
> > +   * Similar to TM_NONE. The MC, however, is capped at the move_rate.
> 
> Add The fields "turn" and "moves_left" will always be -1. 

It says "similar" and lists the only exception.  "DRY", you told me.  But I am
for clarifying it as you suggest now.

> > +/* 
> > + * Full specification of a position and time to reach it.
> > + */
> > +struct pf_position {
> > +  int x, y;                        /* Coordinates of the position */
> > +  int turn, moves_left;            /* See definitions above */
> > +  int MC_of_next_step;             /* MC of the next step */
> > +
> > +  int total_MC;                    /* Total MC to reach this point */
> > +  int total_EC;                    /* Total EC to reach this point */
> > +
> > +  enum direction8 dir_to_next_pos; /* Unsed only in struct_path */
> 
> > +  enum direction8 dir_to_here;     /* Where did we come from */
> 
> This wasn't there the last time. It introduces redundancy. But it can
> stay.

You are mistaken, there is no redundancy.  It should definitely stay.
It was introduced as it was needed in the AI.

> > +  /* 
> > +   * Callback to get MC of a move from (from_x, from_y) to
> 
> > +   * (to_x, to_y) and inthe direction dir.
> 
> Spelling.

Yes.

> > +   */
> > +  int (*get_MC) (int from_x, int from_y, enum direction8 dir,
> > +            int to_x, int to_y, void *);
> 
> We should also supply "known".

When any user code needs it, it will be added.

> > +  void *get_MC_data;               /* Passed as last parameter to get_cost 
> > */
> 
> get_MC

Right.

> > +  /*
> > +   * Callback which determines the behavior of a tile. If NULL
> > +   * TB_NORMAL is assumed. Parameters are x, y, known and
> > +   * get_TB_data. It can be assumed that the implementation of
> > +   * path_finding.h will cache this value.
> > +   */
> > +  enum tile_behavior (*get_TB) (int, int, enum known_type, void *);
> 
> > +  void *get_TB_data;               /* Passed as last parameter to get_cost 
> > */
> 
> get_TB.

Right.

> > +  /*
> > +   * Callback which can be used to provide extra costs depending on
> > +   * the tile. Can be NULL. Parameters are x, y, known and
> > +   * get_EC_data. It can be assumed that the implementation of
> > +   * path_finding.h will cache this value.
> > +   */
> > +  int (*get_EC) (int, int, enum known_type, void *);
> 
> > +  void *get_EC_data;               /* Passed as last parameter to get_cost 
> > */
> 
> get_EC.

Cutting and pasting... :(

> > +  /*
> > +   * If this callback is non-NULL and returns TRUE this position is
> > +   * dangerous. The unit will never end a turn at a dangerous
> > +   * position. Can be NULL. Parameter are x, y and
> 
> > +   * is_position_dangerous_data.
> 
> is_pos_dangerous.

Yes.

> > +   */
> > +   bool(*is_pos_dangerous) (int, int, void *);
> 
> > +  void *is_pos_dangerous_data;     /* Passed as last parameter to get_cost
> */
> 
> is_pos_dangerous.

Yes.

> > +/* 
> > + * Iterates the map until it reaches (x, y).  Then fills the info about
> > + * it into pos.
> > + * Returns FALSE if position is unreachable.  Contents of pos in this
> case
> > + * is not defined.
> > + */
> > +bool pf_get_position(pf_map_t pf_map, int x, int y, struct pf_position
> *pos);
> 
> We should provide the same way to test for unreachable target. Either
> add "is_valid" to position or change return type of pf_get_path to
> bool. Since the first is ugly I'm for the second. ppath->is_valid will
> then go.

I am for the second too as you can gather from me putting it there.

> Why did you remove get_known? It is required to handicap handling.

Please explain.

> > +static int single_seamove(int x, int y, enum direction8 dir,
> > +                     int x1, int y1, void *data)
> > +{
> > +  /* MOVE_COST_FOR_VALID_SEA_STEP means ships can move between */
> > +  if (map_get_tile(x, y)->move_cost[dir]
> > +      == MOVE_COST_FOR_VALID_SEA_STEP) {
> > +    return SINGLE_MOVE;
> > +  } else {
> > +    return PF_MAXCOST;
> > +  }
> > +}
> 
> Now I see why you need PF_MAXCOST. This should be changed. get_MC
> should look like this:
> 
>   bool (*get_MC) (int *dest_MC, int from_x, int from_y, enum direction8
> dir,
>                 int to_x, int to_y, void *);

This is ugly.  PF_MAXCOST is a well-defined special value and it should stay.
I will have no cruft in the function signature, it's big enough as it is.

> > +  Must put owner into *data.
> 
> What about also giving the parameters to all callbacks?

They can be supplied through *data fields if needed.

> > +  Alternatively,we can change the flow to
> > +  if (ptile->terrain == T_OCEAN) {
> > +    move_cost = PF_MAXCOST;
> > +  } else if (terrain1 == T_OCEAN) {
> > +    move_cost = SINGLE_MOVE;
> > +  } else {
> > +    move_cost = ptile->move_cost[dir];
> > +  }
> > +  which will achieve thesame without call-back.
> 
> Why didn't you done this?

For educational purposes.

> > +/************************************************************ 
> > +  Reversed LAND_MOVE cost function for a unit.
> 
> > +  Will be used. DO NOT REMOVE you pricks.
> 
> When will it be used?

After path-finding gets committed.

> > +/**********************************************************************
> 
> > +  Switch on one tile overlapping into the sea 
> 
> False since it also handles SEA_MOVING.

Yes.

> Why do we need pf_next_{x,y,cost} now that the main AI user of the PF
> uses pf_next_get_position?

Ok.

> I still think that the above two macros should be prefixed with "ai",
> "plain", "simple", "basic" or similar since there are the most plain
> use of PF. There is no EC handling in them. Either users of PF want
> this.

I have no opinion on that.  The name must not exceed 77 characters in total,
however.

G.