/********************************************************************** 
 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)
   any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
***********************************************************************/
#ifndef FC__PATH_FINDING_H
#define FC__PATH_FINDING_H

/*
 * Functions in this file help to find a path from A to B.
 *
 * Terms used:
 *  - step: one movement step which brings us from one tile to an adjacent one
 *  - turn: obvious
 *  - path: a list of steps which leads from the start to the end
 *  - basic movement cost (BMC): the basic movements costs of the step
 *    as returned by map_move_cost. Note that the BMC of a step is 0
 *    if the target is unknown.
 *  - extra cost (EC): sum of various extra costs (which all have to be >=0)
 *  - final cost (FC): FC = BMC * PF_BMC_FACTOR + EC
 *  - best path: a path which has the minimal FC. If two paths have
 *  equal FC, the path with the minimal turns and if these are equal
 *  too the maximum remaining points at the destination is choosen.
 */

/*
 * Scaling factor for the BMC.
 */
#define PF_BMC_FACTOR	100

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

/*
 * Maximal number of steps in a path.
 */
#define MAX_PATH_LENGTH	100

/*
 * Specify which turn numbers should be calculated.
 */
enum num_turn_mode {
  NTM_NONE = 0, NTM_MINIMAL = 1, NTM_AVERAGE = 2, NTM_MAXIMUM = 4;
};

/*
 * Indexes for the turn array of struct pf_position.
 */
enum num_turn {
  MINIMAL_TURN = 0, AVERAGE_TURN, MAXIMAL_TURN, NUM_TURN_LAST;
};

struct pf_parameter {
  /*
   * Definition of the state of a virtual unit unit at the start.
   */
  int start_x, start_y;
  /* 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;
  int moves_left_initially;
  int move_rate;
  struct player *owner;
  
  /*
   * Some NTM_ constants ORed together. Does affect the turn field
   * of struct pf_position.
   */
  enum num_turn_mode turn_mode;
  
  /*
   * Callback to query the known state of a tile for the given
   * player.  Should take into account the handicaps.
   */
  enum known_type (*get_known)(int, int, struct player *);
  
  /*
   * Callback to query the ZOC state of a tile for the given
   * player.
   * If == NULL, than assume IG_ZOC.
   */
  bool (*get_zoc_permission)(int, int, struct player *);

  /*
   * Passed as last parameter to extra_cost1.
   */
  void *user_data1;
  
  /*
   * Callback which can be used to provide extra costs depending on
   * the tile. Can be NULL. Parameters are x, y, known and
   * user_data1. It can be assumed that the implementation of
   * path_finding.h will cache this value.
   */
  int (*extra_cost1)(int, int, enum known_type, void *);
  
  /*
   * Passed as last parameter to extra_cost2.
   */
  void *user_data2;
  
  /*
   * Another extra_cost callback, see above for comments.
   */
  int (*extra_cost2)(int, int, enum known_type, int, void *);
  
  /*
   * Passed as last parameter to is_position_safe.
   */
  void *user_data3;
  
  /*
   * If this callback is non-NULL and returns TRUE this position is
   * safe. A safe position splits the simulated path of the
   * simulated unit: it will move on as normal and it will wait a
   * turn to get full move points. Can be NULL. Parameter are x, y,
   * known and user_data3.
   */
  int (*is_position_safe)(int, int, enum known_type, void *);    
};

struct pf_path {
  /*
   * Is this path valid? Is set to FALSE if there was no path found.
   */
  bool found_valid;
  
  /*
   * Number of positions used in the array "positions".
   */
  int positions_used;
  struct pf_position positions[MAX_PATH_LENGTH + 1];
};

/*
 * 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 *);

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

/*
 * 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.
 */
void pf_get_turn_info_of_position(int *turns, int *moves_left, 
                                  enum num_turn turn_mode,
                                  pf_map_t map,
                                  struct pf_position *);

/*
 * Opaque types.
 */
struct pf_position;
typedef struct pf_map *pf_map_t;

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

/*
 * Returns a map which can be used to query for paths or to iterate
 * 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.  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 "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);
/*
 * 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.
 */
const struct pf_position *pf_get_next_position_from_map(pf_map_t map);

/*
 * After usage the map should be destroyed.
 */
void pf_destroy_map(pf_map_t map);

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;
};

/*
 * Anything else goes here?
 */
struct pf_map {
  struct pf_position *the_map;
  struct pf_parameter *parameters;
  struct pf_queue *queue;
}

/*
 * Need to agree upon
 */
struct pf_queue;