path_finding.c File Reference

#include "bitvector.h"
#include "log.h"
#include "mem.h"
#include "support.h"
#include "game.h"
#include "map.h"
#include "movement.h"
#include "pf_tools.h"
#include "path_finding.h"
#include "specpq.h"
#include "spechash.h"

Go to the source code of this file.

Data Structures
struct	pf_map
struct	pf_normal_node
struct	pf_normal_map
struct	pf_danger_node
struct	pf_danger_node::pf_danger_pos
struct	pf_danger_map
struct	pf_fuel_node
struct	pf_fuel_pos
struct	pf_fuel_map
struct	pf_reverse_map

Macros
#define	SPECPQ_TAG   map_index
#define	SPECPQ_DATA_TYPE   int
#define	SPECPQ_PRIORITY_TYPE   int
#define	INITIAL_QUEUE_SIZE   100
#define	PF_MAP(pfm)   ((struct pf_map *) (pfm))
#define	PF_NORMAL_MAP(pfm)   ((struct pf_normal_map *) (pfm))
#define	PF_DANGER_MAP(pfm)   ((struct pf_danger_map *) (pfm))
#define	PF_FUEL_MAP(pfm)   ((struct pf_fuel_map *) (pfm))
#define	SPECHASH_TAG   pf_pos
#define	SPECHASH_IKEY_TYPE   struct pf_parameter *
#define	SPECHASH_IDATA_TYPE   struct pf_position *
#define	SPECHASH_IKEY_VAL   pf_pos_hash_val
#define	SPECHASH_IKEY_COMP   pf_pos_hash_cmp
#define	SPECHASH_IKEY_FREE   pf_reverse_map_destroy_param
#define	SPECHASH_IDATA_FREE   pf_reverse_map_destroy_pos

Enumerations
enum	pf_node_status {   NS_UNINIT = 0 , NS_INIT , NS_NEW , NS_WAITING ,   NS_PROCESSED }
enum	pf_zoc_type { ZOC_MINE = 0 , ZOC_ALLIED , ZOC_NO }

Functions
static int	pf_moves_left_initially (const struct pf_parameter *param)
static int	pf_move_rate (const struct pf_parameter *param)
static int	pf_turns (const struct pf_parameter *param, int cost)
static int	pf_moves_left (const struct pf_parameter *param, int cost)
static int	pf_total_CC (const struct pf_parameter *param, unsigned cost, unsigned extra)
static void	pf_finalize_position (const struct pf_parameter *param, struct pf_position *pos)
static struct pf_path *	pf_path_new_to_start_tile (const struct pf_parameter *param)
static void	pf_position_fill_start_tile (struct pf_position *pos, const struct pf_parameter *param)
static bool	pf_normal_node_init (struct pf_normal_map *pfnm, struct pf_normal_node *node, struct tile *ptile, enum pf_move_scope previous_scope)
static void	pf_normal_map_fill_position (const struct pf_normal_map *pfnm, struct tile *ptile, struct pf_position *pos)
static struct pf_path *	pf_normal_map_construct_path (const struct pf_normal_map *pfnm, struct tile *dest_tile)
static int	pf_normal_map_adjust_cost (int cost, int moves_left)
static bool	pf_jumbo_map_iterate (struct pf_map *pfm)
static bool	pf_normal_map_iterate (struct pf_map *pfm)
static bool	pf_normal_map_iterate_until (struct pf_normal_map *pfnm, struct tile *ptile)
static int	pf_normal_map_move_cost (struct pf_map *pfm, struct tile *ptile)
static struct pf_path *	pf_normal_map_path (struct pf_map *pfm, struct tile *ptile)
static bool	pf_normal_map_position (struct pf_map *pfm, struct tile *ptile, struct pf_position *pos)
static void	pf_normal_map_destroy (struct pf_map *pfm)
static struct pf_map *	pf_normal_map_new (const struct pf_parameter *parameter)
static bool	pf_danger_node_init (struct pf_danger_map *pfdm, struct pf_danger_node *node, struct tile *ptile, enum pf_move_scope previous_scope)
static void	pf_danger_map_fill_position (const struct pf_danger_map *pfdm, struct tile *ptile, struct pf_position *pos)
static int	pf_danger_map_fill_cost_for_full_moves (const struct pf_parameter *param, int cost)
static struct pf_path *	pf_danger_map_construct_path (const struct pf_danger_map *pfdm, struct tile *ptile)
static void	pf_danger_map_create_segment (struct pf_danger_map *pfdm, struct pf_danger_node *node1)
static int	pf_danger_map_adjust_cost (const struct pf_parameter *params, int cost, bool to_danger, int moves_left)
static bool	pf_danger_map_iterate (struct pf_map *pfm)
static bool	pf_danger_map_iterate_until (struct pf_danger_map *pfdm, struct tile *ptile)
static int	pf_danger_map_move_cost (struct pf_map *pfm, struct tile *ptile)
static struct pf_path *	pf_danger_map_path (struct pf_map *pfm, struct tile *ptile)
static bool	pf_danger_map_position (struct pf_map *pfm, struct tile *ptile, struct pf_position *pos)
static void	pf_danger_map_destroy (struct pf_map *pfm)
static struct pf_map *	pf_danger_map_new (const struct pf_parameter *parameter)
static int	pf_fuel_total_CC (const struct pf_parameter *param, int cost, int extra, int safety)
static int	pf_fuel_waited_total_CC (int cost, int safety)
static bool	pf_fuel_node_init (struct pf_fuel_map *pffm, struct pf_fuel_node *node, struct tile *ptile, enum pf_move_scope previous_scope)
static bool	pf_fuel_node_dangerous (const struct pf_fuel_node *node)
static struct pf_fuel_pos *	pf_fuel_pos_ref (struct pf_fuel_pos *pos)
static void	pf_fuel_pos_unref (struct pf_fuel_pos *pos)
static struct pf_fuel_pos *	pf_fuel_pos_replace (struct pf_fuel_pos *pos, const struct pf_fuel_node *node)
static void	pf_fuel_finalize_position_base (const struct pf_parameter *param, struct pf_position *pos, int cost, int moves_left)
static void	pf_fuel_finalize_position (struct pf_position *pos, const struct pf_parameter *params, const struct pf_fuel_node *node, const struct pf_fuel_pos *head)
static void	pf_fuel_map_fill_position (const struct pf_fuel_map *pffm, struct tile *ptile, struct pf_position *pos)
static int	pf_fuel_map_fill_cost_for_full_moves (const struct pf_parameter *param, int cost, int moves_left)
static struct pf_path *	pf_fuel_map_construct_path (const struct pf_fuel_map *pffm, struct tile *ptile)
static void	pf_fuel_map_create_segment (struct pf_fuel_map *pffm, struct tile *ptile, struct pf_fuel_node *node)
static int	pf_fuel_map_adjust_cost (int cost, int moves_left, int move_rate)
static bool	pf_fuel_map_attack_is_possible (const struct pf_parameter *param, int moves_left, int moves_left_req)
static bool	pf_fuel_map_iterate (struct pf_map *pfm)
static bool	pf_fuel_map_iterate_until (struct pf_fuel_map *pffm, struct tile *ptile)
static int	pf_fuel_map_move_cost (struct pf_map *pfm, struct tile *ptile)
static struct pf_path *	pf_fuel_map_path (struct pf_map *pfm, struct tile *ptile)
static bool	pf_fuel_map_position (struct pf_map *pfm, struct tile *ptile, struct pf_position *pos)
static void	pf_fuel_map_destroy (struct pf_map *pfm)
static struct pf_map *	pf_fuel_map_new (const struct pf_parameter *parameter)
struct pf_map *	pf_map_new (const struct pf_parameter *parameter)
void	pf_map_destroy (struct pf_map *pfm)
int	pf_map_move_cost (struct pf_map *pfm, struct tile *ptile)
struct pf_path *	pf_map_path (struct pf_map *pfm, struct tile *ptile)
bool	pf_map_position (struct pf_map *pfm, struct tile *ptile, struct pf_position *pos)
bool	pf_map_iterate (struct pf_map *pfm)
struct tile *	pf_map_iter (struct pf_map *pfm)
int	pf_map_iter_move_cost (struct pf_map *pfm)
struct pf_path *	pf_map_iter_path (struct pf_map *pfm)
void	pf_map_iter_position (struct pf_map *pfm, struct pf_position *pos)
const struct pf_parameter *	pf_map_parameter (const struct pf_map *pfm)
void	pf_path_destroy (struct pf_path *path)
struct pf_path *	pf_path_concat (struct pf_path *dest_path, const struct pf_path *src_path)
bool	pf_path_advance (struct pf_path *path, struct tile *ptile)
bool	pf_path_backtrack (struct pf_path *path, struct tile *ptile)
const struct pf_position *	pf_path_last_position (const struct pf_path *path)
void	pf_path_print_real (const struct pf_path *path, enum log_level level, const char *file, const char *function, int line)
static genhash_val_t	pf_pos_hash_val (const struct pf_parameter *parameter)
static bool	pf_pos_hash_cmp (const struct pf_parameter *parameter1, const struct pf_parameter *parameter2)
static void	pf_reverse_map_destroy_pos (struct pf_position *pos)
static void	pf_reverse_map_destroy_param (struct pf_parameter *param)
struct pf_reverse_map *	pf_reverse_map_new (const struct civ_map *nmap, const struct player *pplayer, struct tile *target_tile, int max_turns, bool omniscient)
struct pf_reverse_map *	pf_reverse_map_new_for_city (const struct civ_map *nmap, const struct city *pcity, const struct player *attacker, int max_turns, bool omniscient)
void	pf_reverse_map_destroy (struct pf_reverse_map *pfrm)
static const struct pf_position *	pf_reverse_map_pos (struct pf_reverse_map *pfrm, const struct pf_parameter *param)
static const struct pf_position *	pf_reverse_map_unit_pos (struct pf_reverse_map *pfrm, const struct unit *punit)
static const struct pf_position *	pf_reverse_map_utype_pos (struct pf_reverse_map *pfrm, const struct unit_type *punittype, struct tile *ptile)
int	pf_reverse_map_utype_move_cost (struct pf_reverse_map *pfrm, const struct unit_type *punittype, struct tile *ptile)
int	pf_reverse_map_unit_move_cost (struct pf_reverse_map *pfrm, const struct unit *punit)
bool	pf_reverse_map_utype_position (struct pf_reverse_map *pfrm, const struct unit_type *punittype, struct tile *ptile, struct pf_position *pos)
bool	pf_reverse_map_unit_position (struct pf_reverse_map *pfrm, const struct unit *punit, struct pf_position *pos)

Variables
static enum unit_type_flag_id	signifiant_flags []
static const size_t	signifiant_flags_num = ARRAY_SIZE(signifiant_flags)

Macro Definition Documentation

INITIAL_QUEUE_SIZE

#define INITIAL_QUEUE_SIZE   100

Definition at line 40 of file path_finding.c.

PF_DANGER_MAP

#define PF_DANGER_MAP

(

pfm

)

((struct pf_danger_map *) (pfm))

Definition at line 1002 of file path_finding.c.

PF_FUEL_MAP

#define PF_FUEL_MAP

(

pfm

)

((struct pf_fuel_map *) (pfm))

Definition at line 2023 of file path_finding.c.

PF_MAP

#define PF_MAP

(

pfm

)

((struct pf_map *) (pfm))

Definition at line 97 of file path_finding.c.

PF_NORMAL_MAP

#define PF_NORMAL_MAP

(

pfm

)

((struct pf_normal_map *) (pfm))

Definition at line 251 of file path_finding.c.

SPECHASH_IDATA_FREE

#define SPECHASH_IDATA_FREE   pf_reverse_map_destroy_pos

Definition at line 3583 of file path_finding.c.

SPECHASH_IDATA_TYPE

#define SPECHASH_IDATA_TYPE   struct pf_position *

Definition at line 3579 of file path_finding.c.

SPECHASH_IKEY_COMP

#define SPECHASH_IKEY_COMP   pf_pos_hash_cmp

Definition at line 3581 of file path_finding.c.

SPECHASH_IKEY_FREE

#define SPECHASH_IKEY_FREE   pf_reverse_map_destroy_param

Definition at line 3582 of file path_finding.c.

SPECHASH_IKEY_TYPE

#define SPECHASH_IKEY_TYPE   struct pf_parameter *

Definition at line 3578 of file path_finding.c.

SPECHASH_IKEY_VAL

#define SPECHASH_IKEY_VAL   pf_pos_hash_val

Definition at line 3580 of file path_finding.c.

SPECHASH_TAG

#define SPECHASH_TAG   pf_pos

Definition at line 3577 of file path_finding.c.

SPECPQ_DATA_TYPE

#define SPECPQ_DATA_TYPE   int

Definition at line 37 of file path_finding.c.

SPECPQ_PRIORITY_TYPE

#define SPECPQ_PRIORITY_TYPE   int

Definition at line 38 of file path_finding.c.

SPECPQ_TAG

#define SPECPQ_TAG   map_index

Definition at line 36 of file path_finding.c.

Enumeration Type Documentation

pf_node_status

enum pf_node_status

Enumerator
NS_UNINIT
NS_INIT
NS_NEW
NS_WAITING
NS_PROCESSED

Definition at line 58 of file path_finding.c.

pf_zoc_type

enum pf_zoc_type

Enumerator
ZOC_MINE
ZOC_ALLIED
ZOC_NO

Definition at line 71 of file path_finding.c.

Function Documentation

pf_danger_map_adjust_cost()

static int pf_danger_map_adjust_cost ( const struct pf_parameter *  params, int  cost, bool  to_danger, int  moves_left  )

inlinestatic

Adjust cost taking into account possibility of making the move.

Definition at line 1433 of file path_finding.c.

Referenced by pf_danger_map_iterate().

pf_danger_map_construct_path()

static struct pf_path * pf_danger_map_construct_path ( const struct pf_danger_map *  pfdm, struct tile *  ptile  )

static

Read off the path to the node 'ptile', but with dangers. NB: will only find paths to safe tiles!

Definition at line 1217 of file path_finding.c.

Referenced by pf_danger_map_path().

pf_danger_map_create_segment()

static void pf_danger_map_create_segment ( struct pf_danger_map *  pfdm, struct pf_danger_node *  node1  )

static

Creating path segment going back from node1 to a safe tile. We need to remember the whole segment because any node can be crossed by many danger segments.

Example: be A, B, C and D points safe positions, E a dangerous one. A B E C D We have found dangerous path from A to D, and later one from C to B: A B A B \ / C D C D If we didn't save the segment from A to D when a new segment passing by E is found, then finding the path from A to D will produce an error. (The path is always done in reverse order.) D->dir_to_here will point to E, which is correct, but E->dir_to_here will point to C.

Definition at line 1377 of file path_finding.c.

Referenced by pf_danger_map_iterate().

pf_danger_map_destroy()

static void pf_danger_map_destroy ( struct pf_map *  pfm )

static

'pf_danger_map' destructor.

Definition at line 1850 of file path_finding.c.

Referenced by pf_danger_map_new().

pf_danger_map_fill_cost_for_full_moves()

static int pf_danger_map_fill_cost_for_full_moves ( const struct pf_parameter *  param, int  cost  )

inlinestatic

This function returns the fills the cost needed for a position, to get full moves at the next turn. This would be called only when the status is NS_WAITING.

Definition at line 1200 of file path_finding.c.

Referenced by pf_danger_map_construct_path(), and pf_danger_map_iterate().

pf_danger_map_fill_position()

static void pf_danger_map_fill_position ( const struct pf_danger_map *  pfdm, struct tile *  ptile, struct pf_position *  pos  )

static

Fill in the position which must be discovered already. A helper for pf_danger_map_position(). This also "finalizes" the position.

Definition at line 1161 of file path_finding.c.

Referenced by pf_danger_map_position().

pf_danger_map_iterate()

static bool pf_danger_map_iterate ( struct pf_map *  pfm )

static

Primary method for iterative path-finding in presence of danger Notes:

1. Whenever the path-finding stumbles upon a dangerous location, it goes into a sub-Dijkstra which processes only dangerous locations, by means of a separate queue. When this sub-Dijkstra reaches a safe location, it records the segment of the path going across the dangerous tiles. Hence danger_segment is an extended (and reversed) version of the dir_to_here field (see comment for pf_danger_map_create_segment()). It can be re-recorded multiple times as we find shorter and shorter routes.
2. Waiting is realised by inserting the (safe) tile back into the queue with a lower priority P. This tile might pop back sooner than P, because there might be several copies of it in the queue already. But that does not seem to present any problems.
3. For some purposes, NS_WAITING is just another flavour of NS_PROCESSED, since the path to a NS_WAITING tile has already been found.
4. This algorithm cannot guarantee the best safe segments across dangerous region. However it will find a safe segment if there is one. To guarantee the best (in terms of total_CC) safe segments across danger, supply 'get_EC' which returns small extra on dangerous tiles.

During the iteration, the node status will be changed: A. NS_UNINIT: The node is not initialized, we didn't reach it at all. B. NS_INIT: We have initialized the cached values, however, we failed to reach this node. C. NS_NEW: We have reached this node, but we are not sure it was the best path. Dangerous tiles never get upper status. D. NS_PROCESSED: Now, we are sure we have the best path. E. NS_WAITING: The safe node (never the dangerous ones) is re-inserted in the priority queue, as explained above (2.). We need to consider if waiting for full moves open or not new possibilities for moving across dangerous areas. F. NS_PROCESSED: When finished to consider waiting at the node, revert the status to NS_PROCESSED. In points D., E., and F., the best path to the node can be considered as found (only safe nodes).

Definition at line 1491 of file path_finding.c.

Referenced by pf_danger_map_new().

pf_danger_map_iterate_until()

static bool pf_danger_map_iterate_until ( struct pf_danger_map *  pfdm, struct tile *  ptile  )

inlinestatic

Iterate the map until 'ptile' is reached.

Definition at line 1757 of file path_finding.c.

Referenced by pf_danger_map_move_cost(), pf_danger_map_path(), and pf_danger_map_position().

pf_danger_map_move_cost()

static int pf_danger_map_move_cost ( struct pf_map *  pfm, struct tile *  ptile  )

static

Return the move cost at ptile. If ptile has not been reached yet, iterate the map until we reach it or run out of map. This function returns PF_IMPOSSIBLE_MC on unreachable positions.

Definition at line 1793 of file path_finding.c.

Referenced by pf_danger_map_new().

pf_danger_map_new()

static struct pf_map * pf_danger_map_new ( const struct pf_parameter *  parameter )

static

'pf_danger_map' constructor.

Definition at line 1871 of file path_finding.c.

Referenced by pf_map_new().

pf_danger_map_path()

static struct pf_path * pf_danger_map_path ( struct pf_map *  pfm, struct tile *  ptile  )

static

Return the path to ptile. If ptile has not been reached yet, iterate the map until we reach it or run out of map.

Definition at line 1812 of file path_finding.c.

Referenced by pf_danger_map_new().

pf_danger_map_position()

static bool pf_danger_map_position ( struct pf_map *  pfm, struct tile *  ptile, struct pf_position *  pos  )

static

Get info about position at ptile and put it in pos . If ptile has not been reached yet, iterate the map until we reach it. Should always check the return value, for the position might be unreachable.

Definition at line 1831 of file path_finding.c.

Referenced by pf_danger_map_new().

pf_danger_node_init()

static bool pf_danger_node_init ( struct pf_danger_map *  pfdm, struct pf_danger_node *  node, struct tile *  ptile, enum pf_move_scope  previous_scope  )

inlinestatic

Calculates cached values of the target node. Set the node status to NS_INIT to avoid recalculating all values. Returns FALSE if we cannot enter node (in this case, most of the cached values are not set).

Definition at line 1012 of file path_finding.c.

Referenced by pf_danger_map_iterate(), pf_danger_map_iterate_until(), and pf_danger_map_new().

pf_finalize_position()

static void pf_finalize_position ( const struct pf_parameter *  param, struct pf_position *  pos  )

inlinestatic

Take a position previously filled out (as by fill_position) and "finalize" it by reversing all fuel multipliers.

See pf_moves_left_initially() and pf_move_rate().

Definition at line 184 of file path_finding.c.

Referenced by pf_danger_map_construct_path(), pf_danger_map_fill_position(), and pf_normal_map_fill_position().

pf_fuel_finalize_position()

static void pf_fuel_finalize_position ( struct pf_position *  pos, const struct pf_parameter *  params, const struct pf_fuel_node *  node, const struct pf_fuel_pos *  head  )

inlinestatic

Finalize the fuel position. If we have a fuel segment, then use it.

Definition at line 2316 of file path_finding.c.

Referenced by pf_fuel_map_construct_path(), and pf_fuel_map_fill_position().

pf_fuel_finalize_position_base()

static void pf_fuel_finalize_position_base ( const struct pf_parameter *  param, struct pf_position *  pos, int  cost, int  moves_left  )

inlinestatic

Finalize the fuel position.

Definition at line 2293 of file path_finding.c.

Referenced by pf_fuel_finalize_position().

pf_fuel_map_adjust_cost()

static int pf_fuel_map_adjust_cost ( int  cost, int  moves_left, int  move_rate  )

inlinestatic

Adjust cost for move_rate and fuel usage.

Definition at line 2548 of file path_finding.c.

Referenced by pf_fuel_map_iterate().

pf_fuel_map_attack_is_possible()

static bool pf_fuel_map_attack_is_possible ( const struct pf_parameter *  param, int  moves_left, int  moves_left_req  )

inlinestatic

This function returns whether a unit with or without fuel can attack.

moves_left: moves left before the attack. moves_left_req: required moves left to hold on the tile after attacking.

Definition at line 2571 of file path_finding.c.

Referenced by pf_fuel_map_iterate().

pf_fuel_map_construct_path()

static struct pf_path * pf_fuel_map_construct_path ( const struct pf_fuel_map *  pffm, struct tile *  ptile  )

static

Read off the path to the node 'ptile', but with fuel danger.

Definition at line 2376 of file path_finding.c.

Referenced by pf_fuel_map_path().

pf_fuel_map_create_segment()

static void pf_fuel_map_create_segment ( struct pf_fuel_map *  pffm, struct tile *  ptile, struct pf_fuel_node *  node  )

inlinestatic

Creating path segment going back from node1 to a safe tile. We need to remember the whole segment because any node can be crossed by many fuel segments.

Example: be A, a refuel point, B and C not. We start the path from B and have only (3 * SINGLE_MOVE) moves lefts: A B C B cannot move to C because we would have only (1 * SINGLE_MOVE) move left reaching it, and the refuel point is too far. So C->moves_left_req = (4 * SINGLE_MOVE). The path would be to return to A, wait the end of turn to get full moves, and go to C. In a single line: B A B C. So, the point B would be reached twice. but, it needs to stores different data for B->cost, B->extra_cost, B->moves_left, and B->dir_to_here. That's why we need to record every path to unsafe nodes (not for refuel points).

Definition at line 2512 of file path_finding.c.

Referenced by pf_fuel_map_iterate().

pf_fuel_map_destroy()

static void pf_fuel_map_destroy ( struct pf_map *  pfm )

static

'pf_fuel_map' destructor.

Definition at line 3085 of file path_finding.c.

Referenced by pf_fuel_map_new().

pf_fuel_map_fill_cost_for_full_moves()

static int pf_fuel_map_fill_cost_for_full_moves ( const struct pf_parameter *  param, int  cost, int  moves_left  )

inlinestatic

This function returns the fill cost needed for a position, to get full moves at the next turn. This would be called only when the status is NS_WAITING.

Definition at line 2363 of file path_finding.c.

Referenced by pf_fuel_map_iterate().

pf_fuel_map_fill_position()

static void pf_fuel_map_fill_position ( const struct pf_fuel_map *  pffm, struct tile *  ptile, struct pf_position *  pos  )

static

Fill in the position which must be discovered already. A helper for pf_fuel_map_position(). This also "finalizes" the position.

Definition at line 2334 of file path_finding.c.

Referenced by pf_fuel_map_position().

pf_fuel_map_iterate()

static bool pf_fuel_map_iterate ( struct pf_map *  pfm )

static

Primary method for iterative path-finding for fuel units. Notes:

1. We process nodes in the main queue, like for normal maps. Because we process in a different queue common tiles (!= refuel points), we needed to register every path to any tile from a refuel point or the start tile (see comment for pf_fuel_map_create_segment()).
2. Waiting is realised by inserting the refuel point back into the main queue with a lower priority P. Because this tile might pop back sooner than P, because there might be several copies of it in the queue already, we must delete all these copies, to preserve the priority of the process.
3. For some purposes, NS_WAITING is just another flavour of NS_PROCESSED, since the path to a NS_WAITING tile has already been found.
4. This algorithm cannot guarantee the best safe segments across dangerous region. However it will find a safe segment if there is one. To guarantee the best (in terms of total_CC) safe segments across danger, supply 'get_EC' which returns small extra on dangerous tiles.

During the iteration, the node status will be changed: A. NS_UNINIT: The node is not initialized, we didn't reach it at all. B. NS_INIT: We have initialized the cached values, however, we failed to reach this node. C. NS_NEW: We have reached this node, but we are not sure it was the best path. D. NS_PROCESSED: Now, we are sure we have the best path. Not refuel node can even be processed. E. NS_WAITING: The refuel node is re-inserted in the priority queue, as explained above (2.). We need to consider if waiting for full moves open or not new possibilities for moving. F. NS_PROCESSED: When finished to consider waiting at the node, revert the status to NS_PROCESSED. In points D., E., and F., the best path to the node can be considered as found.

Definition at line 2631 of file path_finding.c.

Referenced by pf_fuel_map_new().

pf_fuel_map_iterate_until()

static bool pf_fuel_map_iterate_until ( struct pf_fuel_map *  pffm, struct tile *  ptile  )

inlinestatic

Iterate the map until 'ptile' is reached.

Definition at line 2991 of file path_finding.c.

Referenced by pf_fuel_map_move_cost(), pf_fuel_map_path(), and pf_fuel_map_position().

pf_fuel_map_move_cost()

static int pf_fuel_map_move_cost ( struct pf_map *  pfm, struct tile *  ptile  )

static

Return the move cost at ptile. If 'ptile' has not been reached yet, iterate the map until we reach it or run out of map. This function returns PF_IMPOSSIBLE_MC on unreachable positions.

Definition at line 3026 of file path_finding.c.

Referenced by pf_fuel_map_new().

pf_fuel_map_new()

static struct pf_map * pf_fuel_map_new ( const struct pf_parameter *  parameter )

static

'pf_fuel_map' constructor.

Definition at line 3105 of file path_finding.c.

Referenced by pf_map_new().

pf_fuel_map_path()

static struct pf_path * pf_fuel_map_path ( struct pf_map *  pfm, struct tile *  ptile  )

static

Return the path to ptile. If 'ptile' has not been reached yet, iterate the map until we reach it or run out of map.

Definition at line 3047 of file path_finding.c.

Referenced by pf_fuel_map_new().

pf_fuel_map_position()

static bool pf_fuel_map_position ( struct pf_map *  pfm, struct tile *  ptile, struct pf_position *  pos  )

static

Get info about position at ptile and put it in pos. If 'ptile' has not been reached yet, iterate the map until we reach it. Should always check the return value, for the position might be unreachable.

Definition at line 3066 of file path_finding.c.

Referenced by pf_fuel_map_new().

pf_fuel_node_dangerous()

static bool pf_fuel_node_dangerous ( const struct pf_fuel_node *  node )

inlinestatic

Returns whether this node is dangerous or not.

Definition at line 2222 of file path_finding.c.

Referenced by pf_fuel_map_iterate().

pf_fuel_node_init()

static bool pf_fuel_node_init ( struct pf_fuel_map *  pffm, struct pf_fuel_node *  node, struct tile *  ptile, enum pf_move_scope  previous_scope  )

inlinestatic

Calculates cached values of the target node. Set the node status to NS_INIT to avoid recalculating all values. Returns FALSE if we cannot enter node (in this case, most of the cached values are not set).

Definition at line 2050 of file path_finding.c.

Referenced by pf_fuel_map_iterate(), pf_fuel_map_iterate_until(), and pf_fuel_map_new().

pf_fuel_pos_ref()

static struct pf_fuel_pos * pf_fuel_pos_ref ( struct pf_fuel_pos *  pos )

inlinestatic

Increase ref count of the information how we can get to that position.

Definition at line 2232 of file path_finding.c.

Referenced by pf_fuel_map_create_segment(), pf_fuel_map_iterate(), and pf_fuel_map_new().

pf_fuel_pos_replace()

static struct pf_fuel_pos * pf_fuel_pos_replace ( struct pf_fuel_pos *  pos, const struct pf_fuel_node *  node  )

inlinestatic

Replace the position. Reference count of the old pos is reduced by one, but it likely lives on via other references. If reference count goes to zero, reuse the memory instead of freeing and allocating again.

Definition at line 2265 of file path_finding.c.

Referenced by pf_fuel_map_create_segment(), and pf_fuel_map_new().

pf_fuel_pos_unref()

static void pf_fuel_pos_unref ( struct pf_fuel_pos *  pos )

inlinestatic

Forget how we went to position. Maybe destroy the position, and previous ones.

Definition at line 2248 of file path_finding.c.

Referenced by pf_fuel_map_destroy(), and pf_fuel_pos_replace().

pf_fuel_total_CC()

static int pf_fuel_total_CC ( const struct pf_parameter *  param, int  cost, int  extra, int  safety  )

inlinestatic

Obtain cost-of-path from pure cost, extra cost and safety.

Definition at line 2031 of file path_finding.c.

Referenced by pf_fuel_map_iterate().

pf_fuel_waited_total_CC()

static int pf_fuel_waited_total_CC ( int  cost, int  safety  )

inlinestatic

Obtain cost-of-path for constant extra cost (used for node after waited).

Definition at line 2040 of file path_finding.c.

Referenced by pf_fuel_map_iterate().

pf_jumbo_map_iterate()

static bool pf_jumbo_map_iterate ( struct pf_map *  pfm )

static

Bare-bones PF iterator. All Freeciv rules logic is hidden in 'get_costs' callback (compare to pf_normal_map_iterate function). This function is called when the pf_map was created with a 'get_cost' callback.

Plan: 1. Process previous position.

1. Get new nearest position and return it.

During the iteration, the node status will be changed: A. NS_UNINIT: The node is not initialized, we didn't reach it at all. (NS_INIT not used here) B. NS_NEW: We have reached this node, but we are not sure it was the best path. (NS_WAITING not used here) C. NS_PROCESSED: Now, we are sure we have the best path. Then, we won't do anything more with this node.

Definition at line 519 of file path_finding.c.

Referenced by pf_normal_map_new().

pf_map_destroy()

void pf_map_destroy

(

struct pf_map *

pfm

)

After usage the map must be destroyed.

Definition at line 3206 of file path_finding.c.

Referenced by auto_settler_setup_work(), calculate_city_clusters(), caravan_search_from(), dai_choose_diplomat_offensive(), dai_find_strategic_airbase(), dai_hunter_manage(), dai_hunter_try_launch(), dai_manage_airunit(), dai_manage_barbarian_leader(), dai_manage_diplomat(), dai_unit_can_strike_my_unit(), dai_unit_goto_constrained(), dai_wonder_city_distance(), explorer_goto(), find_nearest_airbase(), find_nearest_safe_city(), find_rampage_target(), find_something_to_bomb(), find_something_to_kill(), goto_is_sane(), immediate_destination(), kill_something_with(), look_for_charge(), manage_auto_explorer(), path_to_nearest_allied_city(), pf_reverse_map_pos(), player_restore_units(), process_attacker_want(), remove_last_part(), send_attack_tile(), send_goto_tile(), send_rally_tile(), settler_evaluate_city_requests(), settler_evaluate_improvements(), settler_map_iterate(), tile_before_end_path(), and update_last_part().

pf_map_iter()

struct tile * pf_map_iter

(

struct pf_map *

pfm

)

Return the current tile.

Definition at line 3312 of file path_finding.c.

pf_map_iter_move_cost()

int pf_map_iter_move_cost

(

struct pf_map *

pfm

)

Return the move cost at the current position. This is equivalent to pf_map_move_cost(pfm, pf_map_iter(pfm)).

Definition at line 3324 of file path_finding.c.

pf_map_iter_path()

struct pf_path * pf_map_iter_path

(

struct pf_map *

pfm

)

Return the path to our current position.This is equivalent to pf_map_path(pfm, pf_map_iter(pfm)).

Definition at line 3337 of file path_finding.c.

pf_map_iter_position()

void pf_map_iter_position	(	struct pf_map *	pfm,
		struct pf_position *	pos
	)

Read all info about the current position into pos. This is equivalent to pf_map_position(pfm, pf_map_iter(pfm), &pos).

Definition at line 3350 of file path_finding.c.

Referenced by process_attacker_want().

pf_map_iterate()

bool pf_map_iterate

(

struct pf_map *

pfm

)

Iterates the path-finding algorithm one step further, to the next nearest position. This full info on this position and the best path to it can be obtained using pf_map_iter_move_cost(), pf_map_iter_path(), and pf_map_iter_position() correspondingly. Returns FALSE if no further positions are available in this map.

NB: If pf_map_move_cost(pfm, ptile), pf_map_path(pfm, ptile), or pf_map_position(pfm, ptile) has been called before the call to pf_map_iterate(), the iteration will resume from 'ptile'.

Definition at line 3288 of file path_finding.c.

Referenced by pf_danger_map_iterate_until(), pf_fuel_map_iterate_until(), and pf_normal_map_iterate_until().

pf_map_move_cost()

int pf_map_move_cost	(	struct pf_map *	pfm,
		struct tile *	ptile
	)

Tries to find the minimal move cost to reach ptile. Returns PF_IMPOSSIBLE_MC if not reachable. If ptile has not been reached yet, iterate the map until we reach it or run out of map.

Definition at line 3219 of file path_finding.c.

Referenced by dai_manage_barbarian_leader(), find_beachhead(), and goto_is_sane().

pf_map_new()

struct pf_map * pf_map_new

(

const struct pf_parameter *

parameter

)

Factory function to create a new map according to the parameter. Does not do any iterations.

Definition at line 3182 of file path_finding.c.

Referenced by add_part(), auto_settler_setup_work(), calculate_city_clusters(), caravan_search_from(), dai_choose_diplomat_offensive(), dai_find_strategic_airbase(), dai_hunter_manage(), dai_hunter_try_launch(), dai_manage_airunit(), dai_manage_barbarian_leader(), dai_manage_diplomat(), dai_unit_can_strike_my_unit(), dai_unit_goto_constrained(), dai_wonder_city_distance(), explorer_goto(), find_nearest_airbase(), find_nearest_safe_city(), find_rampage_target(), find_something_to_bomb(), find_something_to_kill(), goto_is_sane(), immediate_destination(), look_for_charge(), manage_auto_explorer(), path_to_nearest_allied_city(), player_restore_units(), process_attacker_want(), send_attack_tile(), send_goto_tile(), send_rally_tile(), settler_evaluate_city_requests(), settler_evaluate_improvements(), settler_map_iterate(), tile_before_end_path(), and update_last_part().

pf_map_parameter()

const struct pf_parameter * pf_map_parameter

(

const struct pf_map *

pfm

)

Return the pf_parameter for given pf_map.

Definition at line 3365 of file path_finding.c.

Referenced by pf_danger_map_construct_path(), pf_danger_map_create_segment(), pf_danger_map_fill_position(), pf_danger_map_iterate(), pf_danger_map_move_cost(), pf_danger_map_path(), pf_danger_map_position(), pf_danger_node_init(), pf_fuel_map_construct_path(), pf_fuel_map_create_segment(), pf_fuel_map_fill_position(), pf_fuel_map_iterate(), pf_fuel_map_move_cost(), pf_fuel_map_path(), pf_fuel_map_position(), pf_fuel_node_init(), pf_jumbo_map_iterate(), pf_map_path(), pf_normal_map_construct_path(), pf_normal_map_fill_position(), pf_normal_map_iterate(), pf_normal_map_iterate_until(), pf_normal_map_move_cost(), pf_normal_map_path(), pf_normal_map_position(), pf_normal_node_init(), and process_attacker_want().

pf_map_path()

struct pf_path * pf_map_path	(	struct pf_map *	pfm,
		struct tile *	ptile
	)

Tries to find the best path in the given map to the position ptile. If NULL is returned no path could be found. The pf_path_last_position() of such path would be the same (almost) as the result of the call to pf_map_position(). If ptile has not been reached yet, iterate the map until we reach it or run out of map.

Definition at line 3235 of file path_finding.c.

Referenced by auto_settler_setup_work(), dai_diplomat_bribe_nearby(), dai_find_strategic_airbase(), dai_hunter_manage(), dai_manage_airunit(), dai_manage_barbarian_leader(), dai_manage_diplomat(), dai_unit_goto_constrained(), explorer_goto(), find_nearest_airbase(), find_rampage_target(), find_something_to_bomb(), find_something_to_kill(), immediate_destination(), path_to_nearest_allied_city(), player_restore_units(), send_attack_tile(), send_goto_tile(), send_rally_tile(), settler_evaluate_city_requests(), settler_evaluate_improvements(), tile_before_end_path(), and update_last_part().

pf_map_position()

bool pf_map_position	(	struct pf_map *	pfm,
		struct tile *	ptile,
		struct pf_position *	pos
	)

Get info about position at ptile and put it in pos. If ptile has not been reached yet, iterate the map until we reach it. Should always check the return value, for the position might be unreachable.

Definition at line 3267 of file path_finding.c.

Referenced by dai_manage_diplomat(), find_something_to_kill(), process_attacker_want(), settler_evaluate_city_requests(), and settler_evaluate_improvements().

pf_move_rate()

static int pf_move_rate ( const struct pf_parameter *  param )

inlinestatic

Return the "move rate".

This is different from the parameter's move_rate because of fuel. For units with fuel > 1 all moves on the same tank of fuel are considered to be one turn. Thus the rest of the PF code doesn't actually know that the unit has fuel, it just thinks it has that many more MP.

Definition at line 123 of file path_finding.c.

Referenced by pf_danger_map_adjust_cost(), pf_danger_map_construct_path(), pf_danger_map_fill_cost_for_full_moves(), pf_danger_map_fill_position(), pf_danger_map_iterate(), pf_danger_map_move_cost(), pf_danger_map_new(), pf_fuel_map_construct_path(), pf_fuel_map_fill_position(), pf_fuel_map_iterate(), pf_fuel_map_move_cost(), pf_fuel_map_new(), pf_moves_left(), pf_normal_map_fill_position(), pf_normal_map_move_cost(), pf_normal_map_new(), and pf_total_CC().

pf_moves_left()

static int pf_moves_left ( const struct pf_parameter *  param, int  cost  )

inlinestatic

Moves left after node is reached.

Definition at line 155 of file path_finding.c.

Referenced by pf_danger_map_construct_path(), pf_danger_map_fill_cost_for_full_moves(), pf_danger_map_fill_position(), pf_danger_map_iterate(), pf_normal_map_fill_position(), and pf_normal_map_iterate().

pf_moves_left_initially()

static int pf_moves_left_initially ( const struct pf_parameter *  param )

inlinestatic

Return the number of "moves" started with.

This is different from the moves_left_initially because of fuel. For units with fuel > 1 all moves on the same tank of fuel are considered to be one turn. Thus the rest of the PF code doesn't actually know that the unit has fuel, it just thinks it has that many more MP.

Definition at line 109 of file path_finding.c.

Referenced by pf_danger_map_construct_path(), pf_danger_map_fill_position(), pf_danger_map_move_cost(), pf_danger_map_new(), pf_fuel_map_construct_path(), pf_fuel_map_fill_position(), pf_fuel_map_move_cost(), pf_fuel_map_new(), pf_normal_map_fill_position(), pf_normal_map_move_cost(), and pf_normal_map_new().

pf_normal_map_adjust_cost()

static int pf_normal_map_adjust_cost ( int  cost, int  moves_left  )

static

Adjust MC to reflect the move_rate.

Definition at line 497 of file path_finding.c.

Referenced by pf_normal_map_iterate().

pf_normal_map_construct_path()

static struct pf_path * pf_normal_map_construct_path ( const struct pf_normal_map *  pfnm, struct tile *  dest_tile  )

static

Read off the path to the node dest_tile, which must already be discovered. A helper for pf_normal_map_path functions.

Definition at line 438 of file path_finding.c.

Referenced by pf_normal_map_path().

pf_normal_map_destroy()

static void pf_normal_map_destroy ( struct pf_map *  pfm )

static

'pf_normal_map' destructor.

Definition at line 845 of file path_finding.c.

Referenced by pf_normal_map_new().

pf_normal_map_fill_position()

static void pf_normal_map_fill_position ( const struct pf_normal_map *  pfnm, struct tile *  ptile, struct pf_position *  pos  )

static

Fill in the position which must be discovered already. A helper for pf_normal_map_position(). This also "finalizes" the position.

Definition at line 401 of file path_finding.c.

Referenced by pf_normal_map_construct_path(), pf_normal_map_position(), and pf_reverse_map_pos().

pf_normal_map_iterate()

static bool pf_normal_map_iterate ( struct pf_map *  pfm )

static

Primary method for iterative path-finding.

Plan: 1. Process previous position.

1. Get new nearest position and return it.

During the iteration, the node status will be changed: A. NS_UNINIT: The node is not initialized, we didn't reach it at all. B. NS_INIT: We have initialized the cached values, however, we failed to reach this node. C. NS_NEW: We have reached this node, but we are not sure it was the best path. (NS_WAITING not used here) D. NS_PROCESSED: Now, we are sure we have the best path. Then, we won't do anything more with this node.

Definition at line 613 of file path_finding.c.

Referenced by pf_normal_map_new().

pf_normal_map_iterate_until()

static bool pf_normal_map_iterate_until ( struct pf_normal_map *  pfnm, struct tile *  ptile  )

inlinestatic

Iterate the map until 'ptile' is reached.

Definition at line 752 of file path_finding.c.

Referenced by pf_normal_map_move_cost(), pf_normal_map_path(), and pf_normal_map_position().

pf_normal_map_move_cost()

static int pf_normal_map_move_cost ( struct pf_map *  pfm, struct tile *  ptile  )

static

Return the move cost at ptile. If ptile has not been reached yet, iterate the map until we reach it or run out of map. This function returns PF_IMPOSSIBLE_MC on unreachable positions.

Definition at line 788 of file path_finding.c.

Referenced by pf_normal_map_new().

pf_normal_map_new()

static struct pf_map * pf_normal_map_new ( const struct pf_parameter *  parameter )

static

'pf_normal_map' constructor.

Definition at line 857 of file path_finding.c.

Referenced by pf_map_new(), and pf_reverse_map_pos().

pf_normal_map_path()

static struct pf_path * pf_normal_map_path ( struct pf_map *  pfm, struct tile *  ptile  )

static

Return the path to ptile. If ptile has not been reached yet, iterate the map until we reach it or run out of map.

Definition at line 807 of file path_finding.c.

Referenced by pf_normal_map_new().

pf_normal_map_position()

static bool pf_normal_map_position ( struct pf_map *  pfm, struct tile *  ptile, struct pf_position *  pos  )

static

Get info about position at ptile and put it in pos. If ptile has not been reached yet, iterate the map until we reach it. Should always check the return value, for the position might be unreachable.

Definition at line 826 of file path_finding.c.

Referenced by pf_normal_map_new().

pf_normal_node_init()

static bool pf_normal_node_init ( struct pf_normal_map *  pfnm, struct pf_normal_node *  node, struct tile *  ptile, enum pf_move_scope  previous_scope  )

inlinestatic

Calculates cached values of the target node. Set the node status to NS_INIT to avoid recalculating all values. Returns FALSE if we cannot enter node (in this case, most of the cached values are not set).

Definition at line 261 of file path_finding.c.

Referenced by pf_normal_map_iterate(), pf_normal_map_iterate_until(), and pf_normal_map_new().

pf_path_advance()

bool pf_path_advance	(	struct pf_path *	path,
		struct tile *	ptile
	)

Remove the part of a path leading up to a given tile. If given tile is on the path more than once then the first occurrence will be the one used. If tile is not on the path at all, returns FALSE and path is not changed at all.

Definition at line 3475 of file path_finding.c.

pf_path_backtrack()

bool pf_path_backtrack	(	struct pf_path *	path,
		struct tile *	ptile
	)

Remove the part of a path following a given tile. If given tile is on the path more than once then the last occurrence will be the one used. If tile is not on the path at all, returns FALSE and path is not changed at all.

Definition at line 3503 of file path_finding.c.

Referenced by send_goto_route().

pf_path_concat()

struct pf_path * pf_path_concat	(	struct pf_path *	dest_path,
		const struct pf_path *	src_path
	)

Concatenate two paths together. The additional segment 'src_path' should start where the initial segment 'dest_path' stops. The overlapping position is removed.

If 'dest_path' == NULL, we just copy the src_path and nothing else.

Definition at line 3426 of file path_finding.c.

Referenced by send_connect_route(), send_goto_route(), and send_patrol_route().

pf_path_destroy()

void pf_path_destroy

(

struct pf_path *

path

)

After use, a path must be destroyed. Note this function accept NULL as argument.

Definition at line 3411 of file path_finding.c.

Referenced by auto_settler_findwork(), dai_auto_settler_run(), dai_diplomat_bribe_nearby(), dai_find_boat_for_unit(), dai_hunter_manage(), dai_manage_airunit(), dai_manage_barbarian_leader(), dai_manage_diplomat(), dai_military_attack(), dai_military_rampage(), dai_unit_goto_constrained(), explorer_goto(), goto_map_free(), immediate_destination(), player_restore_units(), remove_last_part(), request_unit_return(), send_attack_tile(), send_goto_route(), send_goto_tile(), send_patrol_route(), send_rally_tile(), and update_last_part().

pf_path_last_position()

const struct pf_position * pf_path_last_position

(

const struct pf_path *

path

)

Get the last position of the path.

Definition at line 3531 of file path_finding.c.

Referenced by auto_settler_findwork(), dai_auto_settler_run(), dai_log_path(), goto_get_turns(), request_unit_return(), send_goto_route(), and update_last_part().

pf_path_new_to_start_tile()

static struct pf_path * pf_path_new_to_start_tile ( const struct pf_parameter *  param )

static

Create a path to the start tile of a parameter.

Definition at line 3396 of file path_finding.c.

Referenced by pf_danger_map_path(), pf_fuel_map_path(), and pf_normal_map_path().

pf_path_print_real()

void pf_path_print_real	(	const struct pf_path *	path,
		enum log_level	level,
		const char *	file,
		const char *	function,
		int	line
	)

Debug a path. This function shouldn't be called directly, see pf_path_print() defined in "path_finding.h".

Definition at line 3540 of file path_finding.c.

pf_pos_hash_cmp()

static bool pf_pos_hash_cmp ( const struct pf_parameter *  parameter1, const struct pf_parameter *  parameter2  )

static

Comparison function for pf_parameter hash key.

Definition at line 3629 of file path_finding.c.

pf_pos_hash_val()

static genhash_val_t pf_pos_hash_val ( const struct pf_parameter *  parameter )

static

Hash function for pf_parameter key.

Definition at line 3604 of file path_finding.c.

pf_position_fill_start_tile()

static void pf_position_fill_start_tile ( struct pf_position *  pos, const struct pf_parameter *  param  )

static

Fill the position for the start tile of a parameter.

Definition at line 3379 of file path_finding.c.

Referenced by pf_danger_map_position(), pf_fuel_map_construct_path(), pf_fuel_map_position(), pf_normal_map_position(), and pf_path_new_to_start_tile().

pf_reverse_map_destroy()

void pf_reverse_map_destroy

(

struct pf_reverse_map *

pfrm

)

'pf_reverse_map' destructor.

Definition at line 3726 of file path_finding.c.

Referenced by assess_danger(), and dai_manage_barbarian_leader().

pf_reverse_map_destroy_param()

static void pf_reverse_map_destroy_param ( struct pf_parameter *  param )

static

Destroy the parameter.

Definition at line 3679 of file path_finding.c.

pf_reverse_map_destroy_pos()

static void pf_reverse_map_destroy_pos ( struct pf_position *  pos )

static

Destroy the position if not NULL.

Definition at line 3671 of file path_finding.c.

pf_reverse_map_new()

struct pf_reverse_map * pf_reverse_map_new	(	const struct civ_map *	nmap,
		const struct player *	pplayer,
		struct tile *	target_tile,
		int	max_turns,
		bool	omniscient
	)

'pf_reverse_map' constructor. If 'max_turns' is positive, then it won't try to iterate the maps beyond this number of turns.

Definition at line 3688 of file path_finding.c.

Referenced by dai_manage_barbarian_leader(), and pf_reverse_map_new_for_city().

pf_reverse_map_new_for_city()

struct pf_reverse_map * pf_reverse_map_new_for_city	(	const struct civ_map *	nmap,
		const struct city *	pcity,
		const struct player *	attacker,
		int	max_turns,
		bool	omniscient
	)

'pf_reverse_map' constructor for city. If 'max_turns' is positive, then it won't try to iterate the maps beyond this number of turns.

Definition at line 3715 of file path_finding.c.

Referenced by assess_danger().

pf_reverse_map_pos()

static const struct pf_position * pf_reverse_map_pos ( struct pf_reverse_map *  pfrm, const struct pf_parameter *  param  )

static

Returns the map for the unit type. Creates it if needed. Returns NULL if 'target_tile' is unreachable.

Definition at line 3739 of file path_finding.c.

Referenced by pf_reverse_map_unit_pos(), and pf_reverse_map_utype_pos().

pf_reverse_map_unit_move_cost()

int pf_reverse_map_unit_move_cost	(	struct pf_reverse_map *	pfrm,
		const struct unit *	punit
	)

Get the move costs that a unit needs to reach the start tile. Returns PF_IMPOSSIBLE_MC if the tile is unreachable.

Definition at line 3865 of file path_finding.c.

Referenced by dai_manage_barbarian_leader().

pf_reverse_map_unit_pos()

static const struct pf_position * pf_reverse_map_unit_pos ( struct pf_reverse_map *  pfrm, const struct unit *  punit  )

inlinestatic

Returns the position for the unit. Creates it if needed. Returns NULL if 'target_tile' is unreachable.

Definition at line 3804 of file path_finding.c.

Referenced by pf_reverse_map_unit_move_cost(), and pf_reverse_map_unit_position().

pf_reverse_map_unit_position()

bool pf_reverse_map_unit_position	(	struct pf_reverse_map *	pfrm,
		const struct unit *	punit,
		struct pf_position *	pos
	)

Fill the position. Return TRUE if the tile is reachable.

Definition at line 3895 of file path_finding.c.

Referenced by assess_danger_unit().

pf_reverse_map_utype_move_cost()

int pf_reverse_map_utype_move_cost	(	struct pf_reverse_map *	pfrm,
		const struct unit_type *	punittype,
		struct tile *	ptile
	)

Get the move costs that a unit type needs to reach the start tile. Returns PF_IMPOSSIBLE_MC if the tile is unreachable.

Definition at line 3851 of file path_finding.c.

pf_reverse_map_utype_pos()

static const struct pf_position * pf_reverse_map_utype_pos ( struct pf_reverse_map *  pfrm, const struct unit_type *  punittype, struct tile *  ptile  )

inlinestatic

Returns the position for the unit type. Creates it if needed. Returns NULL if 'target_tile' is unreachable.

Definition at line 3825 of file path_finding.c.

Referenced by pf_reverse_map_utype_move_cost(), and pf_reverse_map_utype_position().

pf_reverse_map_utype_position()

bool pf_reverse_map_utype_position	(	struct pf_reverse_map *	pfrm,
		const struct unit_type *	punittype,
		struct tile *	ptile,
		struct pf_position *	pos
	)

Fill the position. Return TRUE if the tile is reachable.

Definition at line 3876 of file path_finding.c.

pf_total_CC()

static int pf_total_CC ( const struct pf_parameter *  param, unsigned  cost, unsigned  extra  )

inlinestatic

Obtain cost-of-path from pure cost and extra cost

Definition at line 172 of file path_finding.c.

Referenced by pf_danger_map_iterate(), pf_fuel_total_CC(), and pf_normal_map_iterate().

pf_turns()

static int pf_turns ( const struct pf_parameter *  param, int  cost  )

inlinestatic

Number of turns required to reach node. See comment in the body of pf_normal_map_new(), pf_danger_map_new(), and pf_fuel_map_new() functions about the usage of moves_left_initially().

Definition at line 133 of file path_finding.c.

Referenced by pf_danger_map_construct_path(), pf_danger_map_fill_position(), pf_fuel_finalize_position_base(), pf_fuel_map_construct_path(), and pf_normal_map_fill_position().

Variable Documentation

signifiant_flags

enum unit_type_flag_id signifiant_flags[]

static

Initial value:

= {
  UTYF_IGTER, UTYF_CIVILIAN, UTYF_COAST_STRICT
}

Definition at line 3596 of file path_finding.c.

Referenced by pf_pos_hash_cmp(), and pf_pos_hash_val().

signifiant_flags_num

const size_t signifiant_flags_num = ARRAY_SIZE(signifiant_flags)

static

Definition at line 3599 of file path_finding.c.

Referenced by pf_pos_hash_cmp(), and pf_pos_hash_val().