/********************************************************************** 
 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.  BMC does not depend on the 
 *  condition of the unit.
 *  - adjusted movement cost (AMC): BMC adjusted to take into account the
 *  move_rate of the unit and the turn_mode (see below).
 *  - extra cost of a step (ECS): sum of various extra costs at the target
 *  tile (all cost have to be >=0)
 *  - cost of a path (COP): 
 *        COP = (sum of AMCs) * PF_AMC_FACTOR + (sum of ECs),
 *  where the sum is over all step of the path.
 *  - best path: a path which has the minimal COP. If two paths have
 *  equal COP the behavior is undefined.
 */

/*
 * Opaque type(s).
 */
typedef struct pf_map *pf_map_t;

/*
 * The step is ignored completely if the sum EC is larger or equal 
 * PF_MAX_EXTRA.
 */
#define PF_MAX_EXTRA    63
/*
 * Scaling factor for the BMC.
 */
#define PF_BMC_FACTOR	PF_MAX_EXTRA
#define PF_AMC_FACTOR	PF_MAX_EXTRA

/* MAXCOST is (uchar_t)(-1) - some initializations depend on this */
#define PF_MAXCOST 255

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

/*
 * If unit has less than full movepoints and tries to undertake a move 
 * which costs more than the unit has, the move succeeds with probability
 * (current_move_points / BMC).  This probabilistic nature of the
 * movement means that we are generally unable to predict the number of 
 * turns needed to reach the destination.  We can, however, find the 
 * minimum, maximum and some sort of average time to the destination.
 * In MINIMUM mode we assume that if current_move_points > 0, 
 * the move will always succeed.
 * In MAXIMUM mode we assume that if current_move_points < full_move_points
 * and current_move_points < BMC, the move will always fail.
 * In AVERAGE mode we just add up all the BMC and divide by 
 * full_move_points.
 * Note: In CivIII the movement is no longer random, it is done according to
 * the MINIMUM mode.
 */
enum turn_mode {
  TM_NONE, TM_MINIMUM, TM_AVERAGE, TM_MAXIMUM
};

/* 
 * Creates and initializes the map 
 */
pf_map_t pf_init_map(struct unit *punit);

/* 
 * Performs one iteration on the map.  The current posistion and 
 * the costs can be read using following utility functions 
 */
bool pf_iterate_map(pf_map_t pf_map);

/*
 * Provide info about current position of the map iteration.
 */
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);

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




/* -------------------------------------------------------------- */
/* --------- From here down nothing is used / implemented ------- */
/* -------------------------------------------------------------- */




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

/*
 * Indexes for the turn and remaining_move_points array of struct
 * pf_position.
 */
enum turn_index {
  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;

  /*--- The following 5 vars are to determine BMC ---*/
  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 node (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 node to the starting map position (start_x,start_y).
   */
  bool move_backward;

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

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

  /*
   * 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 current position of the map iteration 
 * and write it into the given path.
 */
void pf_construct_path(pf_map_t pf_map, struct pf_path *path);

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