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

#include "map.h"
#include "unit.h"
#include "unittype.h"
#include "terrain.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) (of a step): the basic movement 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 of (EC) (of a tile): sum of various extra costs
 *  (which all have to be >=0)
 *  - final cost (FC) (of a step): FC = BMC * PF_BMC_FACTOR + ECTT
 *  Where ECTT is the EC of the target tile.
 *  - turn cost (TC): TC = turn_cost_factor * turns_needed +
 *  move_cost_factor * (move_rate - moves_left)
 *  How turns_needed and moves_left are calculated depend on turn_mode.
 *  - cost of a path (COP): COP = sum of FC for all steps + TCF
 *  Where TCF is the TC of the final position.
 *  - best path: a path which has the minimal COP. If two paths have
 *  equal COP the behavior is undefined.
 */

/*
 * 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 and remaining_move_points are used to
 * calculate TC. TC_NONE will set turn to 0 and remaining_move_points
 * to the move_rate so that TC is constant 0.
 */
enum turn_mode {
  TC_NONE, TC_MINIMUM, TC_AVERAGE, TC_MAXIMUM
};

/*
 * Indexes for the turn and remaining_move_points array of struct
 * pf_position.
 */
enum turn_index {
  MINIMAL_TURN, AVERAGE_TURN, MAXIMAL_TURN, NUM_TURNS
};

/*
 * Opaque types.
 */
typedef struct pf_map *pf_map_t;
typedef void *pf_location_t;

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;

  /* 
   * Only affects the BMC. If set the FALSE the BMC is calculated to
   * simulate a path from (start_x, start_y) to the location (which is
   * returned by pf_get_next_position or passed to pf_get_path). If
   * set to TRUE the BMC will be calculated to simulate a path from
   * the location to the starting map position (start_x,start_y).
   */
  bool move_backward;

  /*
   * Determines how the TC is calculated.
   */
  enum turn_mode turn_mode;
  int turn_cost_factor, move_cost_factor;

  /*
   * 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 is_position_safe.
   */
  void *user_data2;

  /*
   * 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_data2.
   */
  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;
    int turn[NUM_TURNS], remaining_move_points[NUM_TURNS];
    int BMC_of_next_step;

    /* Total BMC required to reach this position. */
    int total_BMC;

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

/*
 * 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 pf_map, int end_x, int end_y, struct pf_path *path);

/*
 * Construct the whole path to the given location and write it into
 * the given path. The location has to be obtained from
 * pf_get_next_location.
 */
void pf_construct_path(pf_map_t pf_map, struct pf_path *path,
		       const pf_location_t location);

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

/*
 * Return the position of the given location.
 */
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);

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

void pf_print_path(const struct pf_path *path);

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

#endif