Freeciv-3.3: /fast/freeciv/nightly/main/common/aicore/path_finding.h File Reference

Freeciv-3.3

Loading...
Searching...
No Matches
Data Structures | Macros | Enumerations | Functions
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 player *pplayer, struct tile *start_tile, int max_turns, bool omniscient, const struct civ_map *nmap) fc__warn_unused_result
struct pf_reverse_map * | pf_reverse_map_new_for_city (const struct city *pcity, const struct player *attacker, int max_turns, bool omniscient, const struct civ_map *nmap) 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_);
incite_cost
char * incite_cost
Definition comments.c:74
pf_map_iterate
bool pf_map_iterate(struct pf_map *pfm)
Definition path_finding.c:3288
pf_map_iter_move_cost
int pf_map_iter_move_cost(struct pf_map *pfm)
Definition path_finding.c:3324
pf_map_iter
struct tile * pf_map_iter(struct pf_map *pfm)
Definition path_finding.c:3312
pf_map
Definition path_finding.c:78
tile
Definition tile.h:50

Definition at line 582 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 592 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_);
pf_map_iter_path
struct pf_path * pf_map_iter_path(struct pf_map *pfm) fc__warn_unused_result
Definition path_finding.c:3337
pf_path
Definition path_finding.h:344

Definition at line 625 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 632 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);
pf_position
Definition path_finding.h:327

Definition at line 605 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 612 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 561 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 568 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__); \
}
__FC_LINE__
#define __FC_LINE__
Definition log.h:40
log_do_output_for_level
#define log_do_output_for_level(level)
Definition log.h:89
level
struct setting_list * level[OLEVELS_NUM]
Definition settings.c:190

Definition at line 519 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 3727 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 player * | pplayer,
|  | struct tile * | target_tile,
|  | int | max_turns,
|  | bool | omniscient,
|  | const struct civ_map * | nmap
| ) |  |

'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 city * | pcity,
|  | const struct player * | attacker,
|  | int | max_turns,
|  | bool | omniscient,
|  | const struct civ_map * | nmap
| ) |  |

'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 3866 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 3896 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 3852 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 3877 of file path_finding.c.