/********************************************************************** 
 Freeciv - Copyright (C) 2002 - Raimar Falke
   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

struct pf_parameter {
    /*
     * Definition of the state of the unit at the start.
     */
    int start_x, start_y;
    Unit_Type_id unittype;
    int moves_left;
    struct player *owner;

    /*
     * Callback to query the known state of a tile for the given
     * player.
     */
    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_cost_1)(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_cost_2)(int, int, enum known_type, int, void *);
};

struct pf_path {
    /*
     * Is this path a 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, turn and remaining_move_points describe a position in
       * place and time.
       */
    int x, y, turn, remaining_move_points;
    enum direction8 direction_for_next_position;
  } positions[MAX_PATH_LENGTH + 1];
};

/*
 * Takes a "struct pf_path *" and returns the last position as a
 * "struct pf_position *".
 */
#define LAST_POSITION(m_p) (&((m_p)->positions[(m_p)->positions_used-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.
 */
pf_map_t pf_get_map(const struct pf_parameter *const parameter);

/*
 * Tries to find a path in the given map to the given destination
 * position. The path will be written in the given struct pf_path.
 * Caller should test path->found_a_valid.
 */
void pf_get_path_from_map(pf_map_t map, int dest_x, int dest_y,
			  struct pf_path *path);

/*
 * The next path with the lowest FC is written in the given struct
 * pf_path.  Caller should test path->found_a_valid. Behavior 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);

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