[Freeciv-Dev] Re: [RFC] Path finding implementation.

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

> Ok here is the version 11 with a sample implementation. Changes to the
> interface:
>  - remove enum turn_index
>  - rename the user data arguments
>  - make the arrays turn and remaining_move_points scalar values
> 
> Changes in the implementation: 
>  - exchange the hash with a 2D array
>  - exchange the list with a heap
>  - cache tile pointer
>  - add ptile->move_cost2

Random comments:

1. Why not use move_cost?

2. I think railroad isn't really needed.  If you really want a 
tie-breaker, use turns.

3. Inside the main loop, neighbour->type != IS_KNOWN should be an assert 
really.  If it's broken, your Dijkstra is broken too.

4. Instead of rebuilding the heap, I just pile everything in.  To keep 
integrity I have to store priorities in the heap as well.  I am not sure 
what is faster.

5. About definition of ZOC: a tile occupied by your ally is not your 
ZOC?  Very weird.

> I would like that we agree upon an interface and let the two
> implementations run in parallel to catch the remaining bugs. Parallel
> to this I would implement the famous is_position_dangerous if I get
> the time. I expect that this will require some work to get right.

Yes, interface. 

The most important thing:  I really want the BMC as a call-back.  The more 
I think about it, the more I like it.  It gives you flexibility, cleans up 
the main loop, can be made aware of client vs server specifics etc.

Now, let's load the header file...
Comments rated 1->5 reflecting strength of my feeling about them.

>  *  (which all have to be >=0)
>  *  - cost of a path (COP) as returns by get_cop.
>  *  - best path: a path which has the minimal COP. If two paths have
>  *  equal COP the behavior is undefined.

(4) I don't like cops, but I can live with it, if you absolutely insist.
I think 
        time_to_dest * PF_IGNORE_COST + extra_cost_to_dest
should be the universal cop.

> /*
>  * The step is ignored completely if any extra cost or the sum EC is
>  * larger than or equal to PF_IGNORE_COST.
>  */
> #define PF_IGNORE_COST        FC_INFINITY

(5) I'd like it to be finite.  You are using 100 in your_cop anyways.

> struct pf_path {
>   bool found_a_valid;

(1) "is_valid" is a better sounding name IMO

>   struct pf_position {
>     int x, y;
>     int turn, remaining_move_points;
>     int BMC_of_next_step;
> 
>     /* Total BMC required to reach this position. */
>     int total_BMC;

(3) Do you really need the total_BMC ?  Isn't turn + remaining_points 
enough?  Causes some unnecessary problems with my implementation...

>     enum direction8 direction_for_next_position;
>   } positions[MAX_PATH_LENGTH + 1];
> };

Now the most important bit,

> struct pf_parameter {
>   int start_x, start_y;
>   int moves_left_initially;
>   struct player *owner;

(5+) Most of the below can go if we do BMC call-back

>   enum unit_move_type move_type;

die!

>   /* only F_IGZOC and F_IGTER are used currently */
>   enum unit_flag_id flags;

die!

>   int move_rate;
>   bool move_backward;

die!

>
>   enum turn_mode turn_mode;
>
>   enum known_type (*get_known) (int, int, struct player *);
>
>   enum goto_move_restriction restriction;

die!

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

(4) I would prefer the following form for the call-backs:

/* 
 * Generic move cost function:
 * (x,y) is the target tile, dir is the direction to the target tile.
 */
typedef int (COSTFN)(pf_map_t the_map, int x, int y, int dir);
/* 
 * Generic extra cost function:
 * (x,y) is the target tile.
 */
typedef int (EXTRAFN)(pf_map_t the_map, int x, int y);

Do you plan any parameters to extra_cost that are not contained in pf_map?

>  void *extra_cost2_data;
>
>  /*
>   * Callback which can be used to provide extra costs depending on
>   * the path to this tile. Can be NULL. Parameters are path and
>   * extra_cost2_data.
>   */
>  int (*extra_cost2) (const struct pf_path *, void *);

(2) A cost depending on the whole path ?!?!  That's quite exotic.  Please 
justify.

>   void *is_position_dangerous_data;
>   bool(*is_position_dangerous) (int, int, enum known_type, void *);

not implemented -> no comment.  but passing the map instead of the last 
two args is preferable.

>  void *get_cop_data;
>  int (*get_cop) (int, int, int, int, void *);
>};

See above.

> /*
>  * Called only once per executable start.
>  */
> void pf_init(void);

Very useful function.  But hard to implement ;)

> pf_map_t pf_get_map(const struct pf_parameter *const parameter);
> void pf_get_path(pf_map_t pf_map, int end_x, int end_y,
>                struct pf_path *path);
> void pf_construct_path(pf_map_t pf_map, struct pf_path *path,
                       const pf_location_t location);

Fine.

> /*
>  * The last position of the next best path is written in the given
>  * location. Returns FALSE if no more positions are available in this
>  * map. Behavior is undefined after pf_get_path was called.
>  */
> bool pf_get_next_location(pf_map_t pf_map, pf_location_t * location);

(3) Scrap returning the location.  See below

> int pf_get_location_x(pf_map_t pf_map, const pf_location_t location);
> int pf_get_location_y(pf_map_t pf_map, const pf_location_t location);

(3) I prefer my:
int pf_get_current_x(const pf_map_t);
int pf_get_current_y(const pf_map_t);
int pf_get_current_cost(const pf_map_t);
int pf_get_current_extra_cost(const pf_map_t);

Also should add:
int pf_get(_extra)_cost(const pf_map, int x, int y);

> /*
>  * After usage the map should be destroyed.
>  */

Burnt and then eaten!

> void pf_destroy_map(pf_map_t pf_map);
> 
> void pf_print_path(const struct pf_path *path);


Our positions becoming closer! ;)

G.