Freeciv

const char *function, int line)

{

fc_assert_full(file, function, line,

return (struct pf_normal_map *) pfm;

}

#define PF_NORMAL_MAP(pfm) \

node->node_known_type = node_known_type;

/* Establish the tile behavior. */

node->behavior = params->get_TB(ptile, node_known_type, params);

if (TB_IGNORE == node->behavior && params->start_tile != ptile) {

return FALSE;

}

/* Test the possibility to perform an action. */

action = params->get_action(ptile, node_known_type, params);

if (PF_ACTION_IMPOSSIBLE == action) {

/* Maybe overwrite node behavior. */

} else if (PF_MS_TRANSPORT == node->move_scope

&& !can_disembark

&& (params->start_tile != ptile

/* Overwrite node behavior. */

node->behavior = TB_DONT_LEAVE;

}

/* ZOC_MINE means can move unrestricted from/into it, ZOC_ALLIED means

* can move unrestricted into it, but not necessarily from it. */

&& !terrain_has_flag(tile_terrain(ptile), TER_NO_ZOC)

&& !params->get_zoc(params->owner, ptile, params->map)) {

node->zoc_number = (0 < unit_list_size(ptile->units)

}

/* Evaluate the extra cost of the destination */

node->extra_tile = params->get_EC(ptile, node_known_type, params);

#ifdef ZERO_VARIABLES_FOR_SEARCHING

} else {

int i;

#ifdef PF_DEBUG

"Unreached destination (%d, %d).",

TILE_XY(dest_tile));

#endif /* PF_DEBUG */

/* Evaluate the cost of the move. */

if (PF_ACTION_NONE != node1->action) {

&& !params->is_action_possible(tile, scope, tile1, node1->action,

params)) {

continue;

cost += node->cost;

/* Evaluate the extra cost if it's relevant */

extra = node->extra_cost;

/* Add the cached value */

extra += node1->extra_tile;

struct pf_map *pfm = PF_MAP(pfnm);

struct pf_normal_node *node = pfnm->lattice + tile_index(ptile);

/* Start position is handled in every function calling this function. */

if (NS_UNINIT == node->status) {

/* Initialize the node, for doing the following tests. */

} else if (pf_normal_map_iterate_until(pfnm, ptile)) {

return pf_normal_map_construct_path(pfnm, ptile);

} else {

}

}

pfnm->lattice = fc_calloc(MAP_INDEX_SIZE, sizeof(struct pf_normal_node));

pfnm->queue = map_index_pq_new(INITIAL_QUEUE_SIZE);

/* 'get_MC' callback must be set. */

/* 'get_move_scope' callback must be set. */

}

/* Copy parameters. */

base_map->get_move_cost = pf_normal_map_move_cost;

base_map->get_path = pf_normal_map_path;

base_map->get_position = pf_normal_map_position;

base_map->iterate = pf_jumbo_map_iterate;

} else {

base_map->iterate = pf_normal_map_iterate;

/* Initialise starting node. */

node = pfnm->lattice + tile_index(params->start_tile);

if (!pf_normal_node_init(pfnm, node, params->start_tile, PF_MS_NONE)) {

/* Always fails. */

fc_assert(pf_normal_node_init(pfnm, node, params->start_tile,

PF_MS_NONE));

}

/* Overwrite. It is safe because we cannot return to start tile with

* pf_normal_map. */

node->move_scope |= PF_MS_TRANSPORT;

if (!utype_can_freely_unload(params->utype,

params->transported_by_initially)

&& !tile_has_native_base(params->start_tile,

params->transported_by_initially)) {

/* Cannot disembark, don't leave transporter. */

const char *function, int line)

{

fc_assert_full(file, function, line,

return (struct pf_danger_map *) pfm;

}

#define PF_DANGER_MAP(pfm) \

node->node_known_type = node_known_type;

/* Establish the tile behavior. */

node->behavior = params->get_TB(ptile, node_known_type, params);

if (TB_IGNORE == node->behavior && params->start_tile != ptile) {

return FALSE;

}

/* Test the possibility to perform an action. */

action = params->get_action(ptile, node_known_type, params);

if (PF_ACTION_IMPOSSIBLE == action) {

/* Maybe overwrite node behavior. */

} else if (PF_MS_TRANSPORT == node->move_scope

&& !can_disembark

&& (params->start_tile != ptile

/* Overwrite node behavior. */

node->behavior = TB_DONT_LEAVE;

}

/* ZOC_MINE means can move unrestricted from/into it, ZOC_ALLIED means

* can move unrestricted into it, but not necessarily from it. */

&& !terrain_has_flag(tile_terrain(ptile), TER_NO_ZOC)

&& !params->get_zoc(params->owner, ptile, params->map)) {

node->zoc_number = (0 < unit_list_size(ptile->units)

}

/* Evaluate the extra cost of the destination. */

node->extra_tile = params->get_EC(ptile, node_known_type, params);

#ifdef ZERO_VARIABLES_FOR_SEARCHING

} else {

{

struct pf_path *path = fc_malloc(sizeof(*path));

enum direction8 dir_next = direction8_invalid();

bool waited = FALSE;

struct pf_danger_node *node = pfdm->lattice + tile_index(ptile);

unsigned length = 1;

#ifdef PF_DEBUG

fc_assert_ret_val_msg(NS_PROCESSED == node->status

"Unreached destination (%d, %d).",

TILE_XY(ptile));

#endif /* PF_DEBUG */

/* We are in the normal node and dir_to_here field is valid */

dir_next = node->dir_to_here;

/* d_node->danger_segment is the indicator of what lies ahead

danger_seg = node->danger_segment;

} else {

/* We are in a danger segment. */

/* Reset variables for main iteration. */

iter_tile = ptile;

node = pfdm->lattice + tile_index(ptile);

waited = FALSE;

for (i = length - 1; i >= 0; i--) {

pos->total_EC = node->extra_cost;

} else {

/* When on dangerous tiles, must have a valid danger segment. */

pos->total_MC = danger_seg->cost;

pos->total_EC = danger_seg->extra_cost;

}

/* 3: Check if we finished. */

if (i == 0) {

/* We should be back at the start now! */

return path;

}

/* We are in the normal node and dir_to_here field is valid. */

dir_next = node->dir_to_here;

/* d_node->danger_segment is the indicator of what lies ahead.

danger_seg = node->danger_segment;

} else {

/* We are in a danger segment. */

}

fc_assert_msg(FALSE, "Cannot get to the starting point!");

}

/************************************************************************//**

const struct pf_parameter *params = pf_map_parameter(PF_MAP(pfdm));

#ifdef PF_DEBUG

log_error("Possible memory leak in pf_danger_map_create_segment().");

}

#endif /* PF_DEBUG */

* position in the Freeciv map). */

if (!direction8_is_valid(node->dir_to_here)

#ifdef PF_DEBUG

fc_assert(tile == params->start_tile);

#endif

scope |= PF_MS_TRANSPORT;

if (!utype_can_freely_unload(params->utype,

params->transported_by_initially)

&& !tile_has_native_base(tile, params->transported_by_initially)) {

/* Cannot disembark, don't leave transporter. */

node->behavior = TB_DONT_LEAVE;

/* Evaluate the cost of the move. */

if (PF_ACTION_NONE != node1->action) {

&& !params->is_action_possible(tile, scope, tile1,

node1->action, params)) {

continue;

cost += loc_cost;

/* Evaluate the extra cost of the destination, if it's relevant. */

extra = node1->extra_tile + node->extra_cost;

}

node1->extra_cost = extra;

node1->cost = cost;

node1->dir_to_here = dir;

/* Clear the previously recorded path back. */

free(node1->danger_segment);

}

if (node->is_dangerous) {

/* We came from a dangerous tile. So we need to record the

} else if (pf_danger_map_iterate_until(pfdm, ptile)) {

return pf_danger_map_construct_path(pfdm, ptile);

} else {

}

}

pfdm->danger_queue = map_index_pq_new(INITIAL_QUEUE_SIZE);

/* 'get_MC' callback must be set. */

/* 'is_pos_dangerous' callback must be set. */

/* 'get_move_scope' callback must be set. */

/* Copy parameters */

*params = *parameter;

const char *function, int line)

{

fc_assert_full(file, function, line,

return (struct pf_fuel_map *) pfm;

}

#define PF_FUEL_MAP(pfm) \

node->node_known_type = node_known_type;

/* Establish the tile behavior. */

node->behavior = params->get_TB(ptile, node_known_type, params);

if (TB_IGNORE == node->behavior && params->start_tile != ptile) {

return FALSE;

}

/* Test the possibility to perform an action. */

&& PF_ACTION_NONE != (action =

params->get_action(ptile, node_known_type,

params))) {

} else if (PF_MS_TRANSPORT == node->move_scope

&& !can_disembark

&& (params->start_tile != ptile

/* Overwrite node behavior. */

node->behavior = TB_DONT_LEAVE;

}

/* ZOC_MINE means can move unrestricted from/into it, ZOC_ALLIED means

* can move unrestricted into it, but not necessarily from it. */

&& !terrain_has_flag(tile_terrain(ptile), TER_NO_ZOC)

&& !params->get_zoc(params->owner, ptile, params->map)) {

node->zoc_number = (0 < unit_list_size(ptile->units)

}

/* Evaluate the extra cost of the destination. */

node->extra_tile = params->get_EC(ptile, node_known_type, params);

#ifdef ZERO_VARIABLES_FOR_SEARCHING

} else {

#ifdef ZERO_VARIABLES_FOR_SEARCHING

/* Nodes are allocated by fc_calloc(), so should be already set to 0. */

#endif

return TRUE;

****************************************************************************/

static inline bool pf_fuel_node_dangerous(const struct pf_fuel_node *node)

{

|| (node->pos->moves_left < node->moves_left_req

&& PF_ACTION_NONE == node->action));

}

****************************************************************************/

static inline void pf_fuel_pos_unref(struct pf_fuel_pos *pos)

{

struct pf_fuel_pos *prev = pos->prev;

free(pos);

static inline struct pf_fuel_pos *

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

{

pos = fc_malloc(sizeof(*pos));

pos->ref_count = 1;

} else if (1 < pos->ref_count) {

pos->extra_cost = node->extra_cost;

pos->moves_left = node->moves_left;

pos->dir_to_here = node->dir_to_here;

return pos;

}

const struct pf_parameter *params = pf_map_parameter(PF_MAP(pffm));

#ifdef PF_DEBUG

"Unreached destination (%d, %d).", TILE_XY(ptile));

#endif /* PF_DEBUG */

int i;

#ifdef PF_DEBUG

"Unreached destination (%d, %d).",

TILE_XY(ptile));

#endif /* PF_DEBUG */

node = pffm->lattice + tile_index(iter_tile);

segment = segment->prev;

#ifdef PF_DEBUG

#endif /* PF_DEBUG */

}

if (node->moves_left_req == 0 && segment != node->segment) {

dir_next = direction8_invalid();

segment = node->segment;

i--;

/* We waited at start tile, then 'node->segment' is not set. */

#ifdef PF_DEBUG

fc_assert(iter_tile == params->start_tile);

/* 3: Check if we finished. */

if (i == 0) {

/* We should be back at the start now! */

return path;

}

node = pffm->lattice + tile_index(iter_tile);

segment = segment->prev;

#ifdef PF_DEBUG

#endif /* PF_DEBUG */

}

fc_assert_msg(FALSE, "Cannot get to the starting point!");

}

/************************************************************************//**

ptile = mapstep(params->map, ptile, DIR_REVERSE(node->dir_to_here));

node = pffm->lattice + tile_index(ptile);

pos = node->pos;

if (pos->cost == node->cost

&& pos->dir_to_here == node->dir_to_here

&& pos->extra_cost == node->extra_cost

* position in the Freeciv map). */

if (!direction8_is_valid(node->dir_to_here)

#ifdef PF_DEBUG

fc_assert(tile == params->start_tile);

#endif

scope |= PF_MS_TRANSPORT;

if (!utype_can_freely_unload(params->utype,

params->transported_by_initially)

&& !tile_has_native_base(tile, params->transported_by_initially)) {

/* Cannot disembark, don't leave transporter. */

node->behavior = TB_DONT_LEAVE;

if (0 == cost) {

/* Evaluate the cost of the move. */

if (PF_ACTION_NONE != node1->action) {

&& !params->is_action_possible(tile, scope, tile1,

node1->action, params)) {

node1->cost_to_here[dir] = PF_IMPOSSIBLE_MC + 2;

cost += loc_cost;

/* Evaluate the extra cost of the destination, if it's relevant. */

extra = node1->extra_tile + node->extra_cost;

}

return FALSE;

}

if (!pf_map_iterate(pfm)) {

/* All reachable destination have been iterated, 'ptile' is

* unreachable. */

} else if (pf_fuel_map_iterate_until(pffm, ptile)) {

return pf_fuel_map_construct_path(pffm, ptile);

} else {

}

}

pffm->waited_queue = map_index_pq_new(INITIAL_QUEUE_SIZE);

/* 'get_MC' callback must be set. */

/* 'get_moves_left_req' callback must be set. */

/* 'get_move_scope' callback must be set. */

/* Copy parameters. */

*params = *parameter;

node->dir_to_here = direction8_invalid();

/* Record a segment. We need it for correct paths. */

node->segment

node->status = NS_PROCESSED;

return PF_MAP(pffm);

void pf_map_destroy(struct pf_map *pfm)

{

#ifdef PF_DEBUG

#endif

pfm->destroy(pfm);

}

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

{

#ifdef PF_DEBUG

#endif

return pfm->get_move_cost(pfm, ptile);

}

/************************************************************************//**

Tries to find the best path in the given map to the position ptile.

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.

#ifdef PF_DEBUG

struct pf_path *path;

path = pfm->get_path(pfm, ptile);

#ifndef FREECIV_NDEBUG

const struct pf_parameter *param = pf_map_parameter(pfm);

const struct pf_position *pos = &path->positions[0];

struct pf_position *pos)

{

#ifdef PF_DEBUG

#endif

return pfm->get_position(pfm, ptile, pos);

}

bool pf_map_iterate(struct pf_map *pfm)

{

#ifdef PF_DEBUG

#endif

/* The end of the iteration was already reached. Don't try to iterate

* again. */

return FALSE;

if (!pfm->iterate(pfm)) {

/* End of iteration. */

return FALSE;

}

struct tile *pf_map_iter(struct pf_map *pfm)

{

#ifdef PF_DEBUG

#endif

return pfm->tile;

}

int pf_map_iter_move_cost(struct pf_map *pfm)

{

#ifdef PF_DEBUG

#endif

return pfm->get_move_cost(pfm, pfm->tile);

}

struct pf_path *pf_map_iter_path(struct pf_map *pfm)

{

#ifdef PF_DEBUG

#endif

return pfm->get_path(pfm, pfm->tile);

}

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

{

#ifdef PF_DEBUG

#endif

if (!pfm->get_position(pfm, pfm->tile, pos)) {

/* Always fails. */

const struct pf_parameter *pf_map_parameter(const struct pf_map *pfm)

{

#ifdef PF_DEBUG

#endif

return &pfm->params;

}

}

/************************************************************************//**

argument.

****************************************************************************/

void pf_path_destroy(struct pf_path *path)

{

free(path->positions);

free(path);

}

should start where the initial segment 'dest_path' stops. The

overlapping position is removed.

****************************************************************************/

struct pf_path *pf_path_concat(struct pf_path *dest_path,

const struct pf_path *src_path)

{

int dest_end;

/* Just copy path. */

dest_path = fc_malloc(sizeof(*dest_path));

dest_path->length = src_path->length;

struct pf_position *pos;

int i;

do_log(file, function, line, TRUE, level,

"PF: path (at %p) consists of %d positions:",

(void *) path, path->length);

} else {

return;

}

}

/************************************************************************//**

****************************************************************************/

static void pf_reverse_map_destroy_pos(struct pf_position *pos)

{

****************************************************************************/

void pf_reverse_map_destroy(struct pf_reverse_map *pfrm)

{

pf_pos_hash_destroy(pfrm->hash);

free(pfrm);

}

/************************************************************************//**

'target_tile' is unreachable.

****************************************************************************/

static const struct pf_position *

}

pf_map_destroy(pfm);

* the map again. */

copy = fc_malloc(sizeof(*copy));

*copy = *param;

}

/************************************************************************//**

'target_tile' is unreachable.

****************************************************************************/

static inline const struct pf_position *

}

/************************************************************************//**

****************************************************************************/

static inline const struct pf_position *

pf_reverse_map_utype_pos(struct pf_reverse_map *pfrm,

struct pf_parameter *param = &pfrm->template;

const struct player *pplayer = param->owner;

int veteran_level = get_unittype_bonus(pplayer, ptile, punittype,

if (veteran_level >= utype_veteran_levels(punittype)) {

veteran_level = utype_veteran_levels(punittype) - 1;

const struct pf_position *pos = pf_reverse_map_utype_pos(pfrm, punittype,

ptile);

}

/************************************************************************//**

{

const struct pf_position *pos = pf_reverse_map_unit_pos(pfrm, punit);

}

/************************************************************************//**

const struct pf_position *mypos = pf_reverse_map_utype_pos(pfrm, punittype,

ptile);

*pos = *mypos;

return TRUE;

} else {

{

const struct pf_position *mypos = pf_reverse_map_unit_pos(pfrm, punit);

*pos = *mypos;

return TRUE;

} else {

const struct pf_parameter *param);

bool ignore_none_scopes;

* TB_NORMAL is assumed. It can be assumed that the implementation

* of "path_finding.h" will cache this value. */

enum tile_behavior (*get_TB) (const struct tile *ptile,

const struct pf_parameter *param);

/* Callback which can be used to provide extra costs depending on the

* "path_finding.h" will cache this value. */

unsigned (*get_EC) (const struct tile *ptile, enum known_type known,

const struct pf_parameter *param);

* of "common" is_my_zoc. Also AI might need to partially ignore

* ZoC for strategic planning purposes (take into account enemy cities

* but not units for example).

bool (*get_zoc) (const struct player *pplayer, const struct tile *ptile,

const struct civ_map *zmap);

* dangerous. The unit will never end a turn at a dangerous

bool (*is_pos_dangerous) (const struct tile *ptile, enum known_type,

const struct pf_parameter *param);

int (*get_moves_left_req) (const struct tile *ptile, enum known_type,

const struct pf_parameter *param);