[Freeciv-Dev] Re: [RFC] Move cost map interface

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Fri, Apr 12, 2002 at 03:17:08PM +0100, Gregory Berkolaiko wrote:
> On Thu, 11 Apr 2002, Raimar Falke wrote:
> 
> > > If you send me the latest of your path_finding?.h, I'll have a go at it 
> > > tomorrow.
> > 
> > Attached.
> 
> Here is the result of my editing.
> Some changes might be controversial, some plain nasty ;)
> 
> But I believe than in few more iterations we might converge on something 
> acceptable to all.
> 
> G.

> --- path_finding4.h   Thu Apr 11 20:27:19 2002
> +++ path_finding5.h   Sat Apr 13 11:56:25 2002
> @@ -1,5 +1,5 @@
>  /********************************************************************** 
> - Freeciv - Copyright (C) 2002 - Raimar Falke
> + Freeciv - Copyright (C) 2002 - Freeciv Project

;)

>     This program is free software; you can redistribute it and/or modify
>     it under the terms of the GNU General Public License as published by
>     the Free Software Foundation; either version 2, or (at your option)
> @@ -57,7 +57,7 @@
>   * Indexes for the turn array of struct pf_position.
>   */
>  enum num_turn {
> -  MINIMAL_TURN, AVERAGE_TURN, MAXIMAL_TURN, NUM_TURNS;
> +  MINIMAL_TURN = 0, AVERAGE_TURN, MAXIMAL_TURN, NUM_TURN_LAST;
>  };

Isn't needed. See 6.5.2.2 Enumeration specifiers in your C language
definition.

>  struct pf_parameter {
> @@ -65,10 +65,11 @@
>       * Definition of the state of a virtual unit unit at the start.
>       */
>      int start_x, start_y;
> -    enum unit_move_type move_type;
> -    /* only F_IGZOC and F_IGTER are used */
> -    enum unit_flag_id flags;
> -    int moves_left;

> +  /* Indicates which built-in BMC-function should be used */
> +  enum pf_move_mode {
> +    LAND_MODE, SEA_MODE, CITY_MODE, IGTER_MODE, CARDINAL_MOVE
> +  } move_mode;

I'm against this. Why should we add another enum when the same can be
expressed with enum unit_move_type, enum unit_flag_id and enum
goto_move_restriction which are used throughout the code?

> +  int moves_left_initially;
>      int move_rate;
>      struct player *owner;
>  
> @@ -80,15 +81,16 @@
>  
>      /*
>       * Callback to query the known state of a tile for the given
> -     * player.
> +   * player.  Should take into account the handicaps.
>       */
> -    enum known_type (*get_known)(int , int, struct player *);
> +  enum known_type (*get_known)(int, int, struct player *);
>  
>      /*
> -     * GOTO_MOVE_STRAIGHTEST will set the BMC to constant 1. Even for
> -     * unknown tiles.
> +   * Callback to query the ZOC state of a tile for the given
> +   * player.
> +   * If == NULL, than assume IG_ZOC.
>       */
> -    enum goto_move_restriction restriction;

> +  bool (*get_zoc_permission)(int, int, struct player *);

Reminds me that I haven't thought about ZOC yet.

>      /*
>       * Passed as last parameter to extra_cost1.
> @@ -109,10 +111,7 @@
>      void *user_data2;
>  
>      /*
> -     * Callback which can be used to provide extra costs depending on
> -     * the tile and the moves left of the unit. Can be NULL. Parameter
> -     * are x, y, known, moves left and user_data2. An implementation
> -     * of path_finding.h may or may not cache this value.
> +   * Another extra_cost callback, see above for comments.
>       */

Why have you removed the comment? What is the extra int?

>      int (*extra_cost2)(int, int, enum known_type, int, void *);
>  
> @@ -133,35 +132,44 @@
>  
>  struct pf_path {
>      /*
> -     * Is this path a valid? Is set to FALSE if there was no path found.
> +   * Is this path valid? Is set to FALSE if there was no path found.
>       */
> -    bool found_a_valid;
> +  bool found_valid;
>  
>      /*
>       * Number of positions used in the array "positions".
>       */
>    int positions_used;
> -
> -  struct pf_position {
> -      /*
> -       * x, y, remaining_move_points and turn describe a position in
> -       * space and time.
> -       */
> -    int x, y, remaining_move_points;
> -    int turn[NUM_TURNS];
> -    enum direction8 direction_for_next_position;
> -  } positions[MAX_PATH_LENGTH + 1];
> +  struct pf_position positions[MAX_PATH_LENGTH + 1];

No you misunderstood. pf_position isn't an opaque type. Where should
the caller else gets these informations? There is probably another
internal type which is used to fill the pf_positions. The internal
type for example will also have an extra field to avoid rail road
loops.

>  };
>  
>  /*
>   * Takes a "struct pf_path *" and returns the last position as a
>   * "struct pf_position *".
> + * Should not be needed -- GB.
> + */
> +struct pf_position *last_position_on_path(struct pf_path *);

Macro -> function: ok. The comment: no. Trust me this saves some writing.

> +/*
> + * Returns coordinates of the position in the supplied variables.
> + */
> +void pf_get_coords_of_position(int *x, int *y, struct pf_position *);

Obsolete if pf_position is public.

> +/*
> + * Returns number of turns used and number of moves left after reaching
> + * the position according to the turn_mode.  
> + * NB: No ORing of turn_mode allowed!
> + * map should be provided for it contains the parameters.
>   */
> -#define LAST_POSITION(m_p) (&((m_p)->positions[(m_p)->positions_used-1]))
> +void pf_get_turn_info_of_position(int *turns, int *moves_left, 
> +                                  enum num_turn turn_mode,
> +                                  pf_map_t map,
> +                                  struct pf_position *);

Obsolete if pf_position is public.

>  /*
> - * Opaque type.
> + * Opaque types.
>   */
> +struct pf_position;
>  typedef struct pf_map *pf_map_t;
>  
>  /*
> @@ -171,24 +179,37 @@
>  
>  /*
>   * Returns a map which can be used to query for paths or to iterate
> - * over all paths.
> + * 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);
>  
>  /*
>   * Tries to find the best path in the given map to the given
> - * destination position. The path will be written in the given struct
> - * pf_path. The caller should test path->found_a_valid.
> + * destination position.  If the path is "ready", returns it, if the path 
> + * is not ready, iterates the path finding algorithm until the best path is 
> + * found or until all possible destinations are exhausted.
> + * The path will be written in the given struct
> + * pf_path. The caller should test path->found_valid.
>   */
>  void pf_get_path_from_map(pf_map_t map, int dest_x, int dest_y,
>                         struct pf_path *path);
>  
>  /*
> - * The next best path is written in the given struct pf_path. Caller
> - * should test path->found_a_valid. Behavior is undefined after
> + * The "non-destructive" version of the previous function.  Will not perform
> + * any computations but if the path is ready, it will return it.
> + * The path will be written in the given struct
> + * pf_path. The caller should test path->found_valid.
> + */
> +void pf_get_path_from_map_if_ready(pf_map_t map, int dest_x, int dest_y,
> +                                   struct pf_path *path);

As I pointed out we don't need these two versions. And even if we do
we want to add a bool arg instead of another function.

> +/*
> + * Returns the next nearest destination. 
> + * Performs one iteration of the path-finding algorithm.  Returns NULL if 
> + * the search is exhausted.  Behaviour is undefined after
>   * pf_get_path_from_map was called.
>   */
> -void pf_get_next_path_from_map(pf_map_t map, struct pf_path *path);
> +const struct pf_position *pf_get_next_position_from_map(pf_map_t map);

>  
>  /*
>   * After usage the map should be destroyed.
> @@ -197,3 +218,29 @@
>  
>  void pf_print_path(const struct pf_path *const path);
>  #endif
> +
> +
> +/*======================================================================*/
> +/*===================== Hidden structures ==============================*/
> +/*======================================================================*/
> +
> +struct pf_position {
> +  int x, y;
> +  int moves_used[NUM_TURNS];
> +  enum direction8 came_from;

> +  enum direction8 went_to;

You can't do this.

> +};
> +
> +/*
> + * Anything else goes here?
> + */
> +struct pf_map {
> +  struct pf_position *the_map;
> +  struct pf_parameter *parameters;
> +  struct pf_queue *queue;
> +}
> +
> +/*
> + * Need to agree upon

No. All of this section should get removed.

> + */
> +struct pf_queue;

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "We've all heard that a million monkeys banging on a million typewriters
  will eventually reproduce the entire works of Shakespeare.
  Now, thanks to the Internet, we know this is not true."