/********************************************************************** 
 Freeciv - Copyright (C) 2002 - The 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, AVERAGE_TURN, MAXIMAL_TURN, NUM_TURNS;
};

struct pf_parameter {
  /*
   * Definition of the state of a virtual unit unit at the start.
   */
  int start_x, start_y;
  int moves_left_initially;
  struct player *owner;

  enum unit_move_type move_type;
  /* only F_IGZOC and F_IGTER are used currently */
  enum unit_flag_id flags;
  int move_rate;

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

  /*
   * GOTO_MOVE_STRAIGHTEST will set the BMC to constant 1. Even for
   * unknown tiles.
   */
  enum goto_move_restriction restriction;

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

  /*
   * 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.
   */
  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_a_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];
};

/*
 * Opaque type.
 */
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. The path will be written in the given struct
 * pf_path. The caller should test path->found_a_valid.
 */
void pf_get_path(pf_map_t map, int dest_x, int dest_y, struct pf_path *path);

/*
 * Construct the whole path to the given position and write it into
 * the given path. The position has to be obtained from
 * pf_get_next_position.
 */
void pf_construct_path(pf_map_t map, const struct pf_position *position,
		       struct pf_path *path);

/*
 * The last position of the next best path is written in the given
 * struct pf_position. Only the fields int x, y and
 * remaining_move_points are set. Returns FALSE if no more positions
 * are available in this map. Behavior is undefined after pf_get_path
 * was called.
 */
bool pf_get_next_position(pf_map_t map, struct pf_position *path);

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

 /*
  * Returns the last position of the given path.
  */
struct pf_position *last_position_on_path(struct pf_path *);

#endif