path_finding.h File Reference

#include "log.h"
#include "map.h"
#include "tile.h"
#include "unit.h"
#include "unittype.h"

Go to the source code of this file.

Data Structures
struct	pf_position
struct	pf_path
struct	pf_parameter

Macros
#define	PF_IMPOSSIBLE_MC   -1
#define	PF_TURN_FACTOR   65536
#define	pf_path_print(path, level)
#define	pf_map_tiles_iterate(ARG_pfm, NAME_tile, COND_from_start)
#define	pf_map_tiles_iterate_end
#define	pf_map_move_costs_iterate(ARG_pfm, NAME_tile, NAME_cost, COND_from_start)
#define	pf_map_move_costs_iterate_end
#define	pf_map_positions_iterate(ARG_pfm, NAME_pos, COND_from_start)
#define	pf_map_positions_iterate_end
#define	pf_map_paths_iterate(ARG_pfm, NAME_path, COND_from_start)
#define	pf_map_paths_iterate_end

Enumerations
enum	pf_action {   PF_ACTION_NONE = 0 , PF_ACTION_ATTACK , PF_ACTION_DIPLOMAT , PF_ACTION_TRADE_ROUTE ,   PF_ACTION_IMPOSSIBLE = -1 }
enum	pf_action_account {   PF_AA_NONE = 0 , PF_AA_UNIT_ATTACK = 1 << 0 , PF_AA_CITY_ATTACK = 1 << 1 , PF_AA_DIPLOMAT = 1 << 2 ,   PF_AA_TRADE_ROUTE = 1 << 3 }
enum	tile_behavior { TB_NORMAL = 0 , TB_IGNORE , TB_DONT_LEAVE }
enum	pf_move_scope { PF_MS_NONE = 0 , PF_MS_NATIVE = 1 << 0 , PF_MS_CITY = 1 << 1 , PF_MS_TRANSPORT = 1 << 2 }

Functions
struct pf_map *	pf_map_new (const struct pf_parameter *parameter) fc__warn_unused_result
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) fc__warn_unused_result
bool	pf_map_position (struct pf_map *pfm, struct tile *ptile, struct pf_position *pos) fc__warn_unused_result
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) fc__warn_unused_result
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)
struct pf_reverse_map *	pf_reverse_map_new (const struct civ_map *nmap, const struct player *pplayer, struct tile *start_tile, int max_turns, bool omniscient) fc__warn_unused_result
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) fc__warn_unused_result
void	pf_reverse_map_destroy (struct pf_reverse_map *prfm)
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)

Macro Definition Documentation

PF_IMPOSSIBLE_MC

#define PF_IMPOSSIBLE_MC   -1

Definition at line 266 of file path_finding.h.

pf_map_move_costs_iterate

#define pf_map_move_costs_iterate	(		ARG_pfm,
			NAME_tile,
			NAME_cost,
			COND_from_start
	)

Value:

if (COND_from_start || pf_map_iterate((ARG_pfm))) {                         \
  struct pf_map *_MY_pf_map_ = (ARG_pfm);                                   \
  struct tile *NAME_tile;                                                   \
  int NAME_cost;                                                            \
  do {                                                                      \
    NAME_tile = pf_map_iter(_MY_pf_map_);                                   \
    NAME_cost = pf_map_iter_move_cost(_MY_pf_map_);

Definition at line 581 of file path_finding.h.

pf_map_move_costs_iterate_end

#define pf_map_move_costs_iterate_end

Value:

  } while (pf_map_iterate(_MY_pf_map_));                                    \
}

Definition at line 591 of file path_finding.h.

pf_map_paths_iterate

#define pf_map_paths_iterate	(		ARG_pfm,
			NAME_path,
			COND_from_start
	)

Value:

if (COND_from_start || pf_map_iterate((ARG_pfm))) {                         \
  struct pf_map *_MY_pf_map_ = (ARG_pfm);                                   \
  struct pf_path *NAME_path;\
  do {\
    NAME_path = pf_map_iter_path(_MY_pf_map_);

Definition at line 624 of file path_finding.h.

pf_map_paths_iterate_end

#define pf_map_paths_iterate_end

Value:

  } while (pf_map_iterate(_MY_pf_map_));                                    \
}

Definition at line 631 of file path_finding.h.

pf_map_positions_iterate

#define pf_map_positions_iterate	(		ARG_pfm,
			NAME_pos,
			COND_from_start
	)

Value:

if (COND_from_start || pf_map_iterate((ARG_pfm))) {                         \
  struct pf_map *_MY_pf_map_ = (ARG_pfm);                                   \
  struct pf_position NAME_pos;                                              \
  do {                                                                      \
    pf_map_iter_position(_MY_pf_map_, &NAME_pos);

Definition at line 604 of file path_finding.h.

pf_map_positions_iterate_end

#define pf_map_positions_iterate_end

Value:

  } while (pf_map_iterate(_MY_pf_map_));                                    \
}

Definition at line 611 of file path_finding.h.

pf_map_tiles_iterate

#define pf_map_tiles_iterate	(		ARG_pfm,
			NAME_tile,
			COND_from_start
	)

Value:

if (COND_from_start || pf_map_iterate((ARG_pfm))) {                         \
  struct pf_map *_MY_pf_map_ = (ARG_pfm);                                   \
  struct tile *NAME_tile;                                                   \
  do {                                                                      \
    NAME_tile = pf_map_iter(_MY_pf_map_);

Definition at line 560 of file path_finding.h.

pf_map_tiles_iterate_end

#define pf_map_tiles_iterate_end

Value:

  } while (pf_map_iterate(_MY_pf_map_));                                    \
}

Definition at line 567 of file path_finding.h.

pf_path_print

#define pf_path_print	(		path,
			level
	)

Value:

  if (log_do_output_for_level(level)) {                                     \
    pf_path_print_real(path, level, __FILE__, __FUNCTION__, __FC_LINE__);   \
  }

Definition at line 518 of file path_finding.h.

PF_TURN_FACTOR

#define PF_TURN_FACTOR   65536

Definition at line 272 of file path_finding.h.

Enumeration Type Documentation

pf_action

enum pf_action

Enumerator
PF_ACTION_NONE
PF_ACTION_ATTACK
PF_ACTION_DIPLOMAT
PF_ACTION_TRADE_ROUTE
PF_ACTION_IMPOSSIBLE

Definition at line 287 of file path_finding.h.

pf_action_account

enum pf_action_account

Enumerator
PF_AA_NONE
PF_AA_UNIT_ATTACK
PF_AA_CITY_ATTACK
PF_AA_DIPLOMAT
PF_AA_TRADE_ROUTE

Definition at line 296 of file path_finding.h.

pf_move_scope

enum pf_move_scope

Enumerator
PF_MS_NONE
PF_MS_NATIVE
PF_MS_CITY
PF_MS_TRANSPORT

Definition at line 319 of file path_finding.h.

tile_behavior

enum tile_behavior

Enumerator
TB_NORMAL
TB_IGNORE
TB_DONT_LEAVE

Definition at line 308 of file path_finding.h.

Function Documentation

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_worker_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_map_iterate(), tile_before_end_path(), update_last_part(), worker_evaluate_city_requests(), and worker_evaluate_improvements().

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_worker_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_map_iterate(), tile_before_end_path(), update_last_part(), worker_evaluate_city_requests(), and worker_evaluate_improvements().

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_worker_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(), tile_before_end_path(), update_last_part(), worker_evaluate_city_requests(), and worker_evaluate_improvements().

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(), worker_evaluate_city_requests(), and worker_evaluate_improvements().

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_worker_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_worker_findwork(), dai_auto_settler_run(), dai_log_path(), goto_get_turns(), request_unit_return(), send_goto_route(), and update_last_part().

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_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_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_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_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_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.