Freeciv-3.3
Loading...
Searching...
No Matches
path_finding.h
Go to the documentation of this file.
1/***********************************************************************
2 Freeciv - Copyright (C) 2003 - The Freeciv Project
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation; either version 2, or (at your option)
6 any later version.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12***********************************************************************/
13#ifndef FC__PATH_FINDING_H
14#define FC__PATH_FINDING_H
15
16#ifdef __cplusplus
17extern "C" {
18#endif /* __cplusplus */
19
20
21/* utility */
22#include "log.h" /* enum log_level */
23
24/* common */
25#include "map.h"
26#include "tile.h"
27#include "unit.h"
28#include "unittype.h"
29
30/* ========================== Explanations =============================== */
31
32/*
33 * Functions in this file help to find a path from A to B.
34 *
35 * DEFINITIONS:
36 * step: one movement step which brings us from one tile to an
37 * adjacent one
38 *
39 * turn: turns spent to reach a tile. Since movement rules involve
40 * randomness, we use different "turn modes" to get an estimate of
41 * this number
42 *
43 * moves left: move points left upon reaching a tile.
44 *
45 * path: a list of steps which leads from the start to the end
46 *
47 * move cost (MC): move cost of a _single_ step. MC is always positive.
48 * [The parameter can specify what the MC of a step into the unknown is
49 * to be (this is a constant for each map). This defaults to a
50 * slightly large value meaning unknown tiles are avoided slightly.
51 * It's also possible to use 0 here and use TB or EC to control
52 * movement through unknown tiles, or to use PF_IMPOSSIBLE_MC to
53 * easily avoid unknown tiles.]
54 *
55 * extra cost (EC): extra cost of a _single_ tile. EC is always positive.
56 * The intended meaning for EC is "how much we want to avoid this tile",
57 * see DISCUSSION below for more.
58 *
59 * tile behaviour (TB): the extra information about a tile which
60 * tells us whether we can enter and leave tile as normal (see enum
61 * tile_behavior).
62 *
63 * total_MC: (effective) move cost of the whole path.
64 *
65 * total_EC: extra cost of the whole path (just sum of ECs of all
66 * tiles).
67 *
68 * total_CC: combined cost of the whole path (see below).
69 *
70 * best path: a path which has the minimal total_CC. If two paths
71 * have equal total_CC the behavior is undefined.
72 *
73 *
74 * DISCUSSION:
75 * First of all it should be noted that path-finding is not about finding
76 * shortest paths but about finding the "best" paths. Now, each path has
77 * two major characteristics:
78 * (1) How long it is (or how much does it cost in terms of time)
79 * and
80 * (2) How dangerous it is (or how much does it cost in terms of resources).
81 *
82 * We use MC (and total_MC) to describe (1) and use EC (and total_EC) to
83 * describe (2). Of course, when it comes to selecting the "best" path,
84 * we need to compromise between taking the shortest road and taking the
85 * safest road. To that end, we use the "combined cost", calculated as
86 * total_CC = PF_TURN_FACTOR * total_MC + move_rate * total_EC,
87 * where PF_TURN_FACTOR is a large constant. This means that each EC
88 * point is equivalent to 1/PF_TURN_FACTOR-th of one turn, or,
89 * equivalently, we are willing to spend one more turn on the road to
90 * avoid PF_TURN_FACTOR worth of danger. Note that if ECs are kept
91 * significantly lower than PF_TURN_FACTOR, the total_EC will only act as a
92 * tie-breaker between equally long paths.
93 *
94 * Note, that the user is expected to ask "So this best path, how long will
95 * it take me to walk it?". For that reason we keep our accounts of MCs and
96 * ECs separately, as one cannot answer the above question basing on
97 * total_CC alone.
98 *
99 * The above setup allows us to find elegant solutions to rather involved
100 * questions. A good example would be designing a road from A to B:
101 * ================
102 * The future road should be as short as possible, but out of many
103 * shortest roads we want to select the one which is fastest to
104 * construct. For example:
105 * the initial conditions ("-"s mark existing road, "."s mark plains)
106 * A.....B
107 * .....
108 * .---.
109 * a possible solution
110 * A-----B
111 * .....
112 * .---.
113 * the best solution (utilize existing road)
114 * A.....B
115 * \.../
116 * .---.
117 *
118 * To solve the problem we simply declare that
119 * MC between any two tiles shall be MOVE_COST_ROAD
120 * EC of any tile shall be the time to construct a road there
121 * =================
122 *
123 * In some cases we would like to impose extra restrictions on the
124 * paths/tiles we want to consider. For example, a trireme might want to
125 * never enter deep sea. A chariot, would like to find paths going to
126 * enemy cities but not going _through_ them. This can be achieved
127 * through an additional tile_behaviour callback, which would return
128 * TB_IGNORE for tiles we don't want to visit and TB_DONT_LEAVE for tiles
129 * we won't be able to leave (at least alive).
130 *
131 * Dangerous tiles are those on which we don't want to end a turn. If the
132 * danger callback is specified it is used to determine which tiles are
133 * dangerous; no path that ends a turn on such a tile will ever be
134 * considered.
135 *
136 * There is also support for fuel, and thus indirectly for air units. If
137 * the fuel parameters are provided then the unit is considered to have
138 * that much fuel. The net effect is that if a unit has N fuel then only
139 * every Nth turn will be considered a stopping point. To support air
140 * units, then, all tiles that don't have airfields (or cities/carriers)
141 * should be returned as dangerous (see danger, above). Setting fuel == 1
142 * in the pf_parameter disables fuel support.
143 *
144 * There are few other options in the path-finding. For further info about
145 * them, see comment for the pf_parameter structure below.
146 *
147 *
148 * FORMULAE:
149 * For calculating total_MC (given particular tile_behaviour)
150 * total_MC = ((turn + 1) * move_rate - moves_left)
151 *
152 * For calculating total_CC:
153 * total_CC = PF_TURN_FACTOR * total_MC + move_rate * total_EC
154 *
155 *
156 * EXAMPLES:
157 * The path-finding can be used in two major modes:
158 * (A) We know where we want to go and need the best path there
159 * How many miles to Dublin?
160 * Three score and ten, sir.
161 * Will we be there by candlelight?
162 * (B) We know what we want and need the nearest one
163 * Where is the nearest pub, gov?
164 *
165 * In the first case we use pf_map_move_cost(), pf_map_path(), and
166 * pf_map_position() (the latter will only tell us the distance but not the
167 * path to take). In the second case we use pf_map_iterate() to iterate
168 * through all tiles in the order of increased distance and break when we
169 * found what we were looking for. In this case we use pf_map_iter_*() to
170 * get information about the "closest tile".
171 *
172 * A) the caller knows the map position of the goal and wants to know the
173 * path:
174 *
175 * struct pf_parameter parameter;
176 * struct pf_map *pfm;
177 * struct pf_path *path;
178 *
179 * // fill parameter (see below)
180 *
181 * // create the map: the main path-finding object.
182 * pfm = pf_map_new(&parameter);
183 *
184 * // create the path to the tile 'ptile'.
185 * if ((path = pf_map_path(pfm, ptile))) {
186 * // success, use path
187 * pf_path_destroy(path);
188 * } else {
189 * // no path could be found
190 * }
191 *
192 * // don't forget to destroy the map after usage.
193 * pf_map_destroy(pfm);
194 *
195 * You may call pf_map_path() multiple times with the same pfm.
196 *
197 * B) the caller doesn't know the map position of the goal yet (but knows
198 * what they are looking for, e.g. a port) and wants to iterate over
199 * all paths in order of increasing costs (total_CC):
200 *
201 * struct pf_parameter parameter;
202 * struct pf_map *pfm;
203 *
204 * // fill parameter (see below)
205 *
206 * // create the map: the main path-finding object.
207 * pfm = pf_map_new(&parameter);
208 *
209 * // iterate the map, using macros defined on this header.
210 * pf_map_*_iterate(pfm, something, TRUE) {
211 * // do something
212 * } pf_map_*_iterate_end;
213 *
214 * // don't forget to destroy the map after usage.
215 * pf_map_destroy(pfm);
216 *
217 * Depending on the kind of information required, the iteration macro
218 * should be:
219 *
220 * 1) tile iteration:
221 * pf_map_tiles_iterate(pfm, ptile, TRUE) {
222 * // do something
223 * } pf_map_tiles_iterate_end;
224 *
225 * 2) move cost iteration on the nearest position:
226 * pf_map_move_costs_iterate(pfm, ptile, move_cost, TRUE) {
227 * // do something
228 * } pf_map_move_costs_iterate_end;
229 *
230 * 3) information (for example the total MC and the number of turns) on the
231 * next nearest position:
232 * pf_map_positions_iterate(pfm, pos, TRUE) {
233 * // do something
234 * } pf_map_positions_iterate_end;
235 *
236 * 4) information about the whole path (leading to the next nearest
237 * position):
238 * pf_map_paths_iterate(pfm, path, TRUE) {
239 * // do something
240 * pf_path_destroy(path);
241 * } pf_map_paths_iterate_end;
242 *
243 * The third argument passed to the iteration macros is a condition that
244 * controls if the start tile of the pf_parameter should iterated or not.
245 *
246 *
247 * FILLING the struct pf_parameter:
248 * This can either be done by hand or using the pft_* functions from
249 * "common/aicore/pf_tools.h" or a mix of these.
250 *
251 * Hints:
252 * 1. It is useful to limit the expansion of unknown tiles with a get_TB
253 * callback. In this case you might set the unknown_MC to be 0.
254 * 2. If there are two paths of the same cost to a tile, you are
255 * not guaranteed to get the one with the least steps in it. If you care,
256 * specifying EC to be 1 will do the job.
257 * 3. To prevent AI from thinking that it can pass through "chokepoints"
258 * controlled by enemy cities, you can specify tile behaviour of each
259 * occupied enemy city to be TB_DONT_LEAVE.
260 */
261
262/* MC for an impossible step. If this value is returned by get_MC it
263 * is treated like TB_IGNORE for this step. This won't change the TB
264 * for any other step to this tile. This is assumed to be negative,
265 * i.e., to be caught by "if (cost < 0)" */
266#define PF_IMPOSSIBLE_MC -1
267
268/* The factor which is used to multiple total_EC in the total_CC
269 * calculation. See definition of total_CC above.
270 * The number is chosen to be much larger than 0 and much smaller
271 * than MAX_INT (and a power of 2 for easy multiplication). */
272#define PF_TURN_FACTOR 65536
273
274/* Debugging control if we arrange waits sanely in advisor paths
275 * value & 1 means checking move costs
276 * value & 2 means checking fuel left
277 * value & 4 means checking health */
278#ifndef PF_WAIT_DEBUG
279#ifdef FREECIV_DEBUG
280/* Disabled by default - the assert enabled can be overzealous with some rulesets */
281/* #define PF_WAIT_DEBUG 3 */
282#endif
283#endif
284/* =========================== Structures ================================ */
285
286/* Specifies the type of the action. */
294
295/* Specifies the actions to consider. */
299 /* When this option is turned on, the move to a city will be considered
300 * as attacking a unit, even if we ignore if there is a unit in the city.
301 * This does not mean we are considering taking over a city! */
304 PF_AA_TRADE_ROUTE = 1 << 3
306
307/* Specifies the way path-finding will treat a tile. */
309 TB_NORMAL = 0, /* Well, normal .*/
310 TB_IGNORE, /* This one will be ignored. */
311 TB_DONT_LEAVE /* Paths can lead _to_ such tile, but are not
312 * allowed to go _through_. This move cost is
313 * always evaluated to a constant single move cost,
314 * preferring straight paths because we don't need
315 * moves left to leave this tile. */
317
318/* Specifies the possibility to move from/to a tile. */
325
326/* Full specification of a position and time to reach it. */
328 struct tile *tile; /* The tile. */
329 int turn; /* The number of turns to the target. */
330 int moves_left; /* The number of moves left the unit would have when
331 * reaching the tile. */
332 int fuel_left; /* The number of turns of fuel left the unit would
333 * have when reaching the tile. It is always set to
334 * 1 when unit types are not fueled. */
335
336 unsigned total_MC; /* Total MC to reach this point */
337 unsigned total_EC; /* Total EC to reach this point */
338
339 enum direction8 dir_to_next_pos; /* Used only in 'struct pf_path'. */
340 enum direction8 dir_to_here; /* Where did we come from. */
341};
342
343/* Full specification of a path. */
344struct pf_path {
345 unsigned length; /* Number of steps in the path */
347};
348
349/* Initial data for the path-finding. Normally should use functions
350 * from "pf_tools.[ch]" to fill the parameter.
351 *
352 * All callbacks get the parameter passed to pf_map_new() as the last
353 * argument.
354 *
355 * Examples of callbacks can be found in "pf_tools.c"
356 * NB: It should be safe to struct copy pf_parameter. */
358 const struct civ_map *map;
359 struct tile *start_tile; /* Initial position */
360
362 int fuel_left_initially; /* Ignored for non-air units. */
363 /* Set if the unit is transported. */
365 /* See unit_cargo_depth(). */
367 /* All cargo unit types. */
369
370 int move_rate; /* Move rate of the virtual unit */
371 int fuel; /* Should be 1 for units without fuel. */
372
373 const struct unit_type *utype;
374 const struct player *owner;
375
376 bool omniscience; /* Do we care if the tile is visible? */
377
378 /* Callback to get MC of a move from 'from_tile' to 'to_tile' and in the
379 * direction 'dir'. Note that the callback can calculate 'to_tile' by
380 * itself based on 'from_tile' and 'dir'. Excessive information 'to_tile'
381 * is provided to ease the implementation of the callback. */
382 unsigned (*get_MC) (const struct tile *from_tile,
384 const struct tile *to_tile,
386 const struct pf_parameter *param);
387
388 /* Callback which determines if we can move from/to 'ptile'. */
389 enum pf_move_scope (*get_move_scope) (const struct tile *ptile,
390 bool *can_disembark,
392 const struct pf_parameter *param);
394
395 /* Callback which determines the behavior of a tile. If NULL
396 * TB_NORMAL is assumed. It can be assumed that the implementation
397 * of "path_finding.h" will cache this value. */
398 enum tile_behavior (*get_TB) (const struct tile *ptile,
399 enum known_type known,
400 const struct pf_parameter *param);
401
402 /* Callback which can be used to provide extra costs depending on the
403 * tile. Can be NULL. It can be assumed that the implementation of
404 * "path_finding.h" will cache this value. */
405 unsigned (*get_EC) (const struct tile *ptile, enum known_type known,
406 const struct pf_parameter *param);
407
408 /* Callback which determines whether an action would be performed at
409 * 'ptile' instead of moving to it. */
410 enum pf_action (*get_action) (const struct tile *ptile,
411 enum known_type known,
412 const struct pf_parameter *param);
414
415 /* Callback which determines whether the action from 'from_tile' to
416 * 'to_tile' is effectively possible. */
419 const struct tile *to_tile,
420 enum pf_action action,
421 const struct pf_parameter *param);
422
423 /* Although the rules governing ZoC are universal, the amount of
424 * information available at server and client is different. To
425 * compensate for it, we might need to supply our own version
426 * of "common" is_my_zoc. Also AI might need to partially ignore
427 * ZoC for strategic planning purposes (take into account enemy cities
428 * but not units for example).
429 * If this callback is NULL, ZoC are ignored. */
430 bool (*get_zoc) (const struct player *pplayer, const struct tile *ptile,
431 const struct civ_map *zmap);
432
433 /* If this callback is non-NULL and returns TRUE this position is
434 * dangerous. The unit will never end a turn at a dangerous
435 * position. Can be NULL. */
436 bool (*is_pos_dangerous) (const struct tile *ptile, enum known_type,
437 const struct pf_parameter *param);
438
439 /* If this callback is non-NULL and returns the required moves left to
440 * move to this tile and to leave the position safely. Can be NULL. */
441 int (*get_moves_left_req) (const struct tile *ptile, enum known_type,
442 const struct pf_parameter *param);
443
444 /* This is a jumbo callback which overrides all previous ones. It takes
445 * care of everything (ZOC, known, costs etc).
446 * Variables:
447 * from_tile -- the source tile
448 * from_cost, from_extra -- costs of the source tile
449 * to_tile -- the dest tile
450 * to_cost, to_extra -- costs of the dest tile
451 * dir -- direction from source to dest
452 * param -- a pointer to this struct
453 * If the dest tile hasn't been reached before, to_cost is -1.
454 *
455 * The callback should:
456 * - evaluate the costs of the move
457 * - calculate the cost of the whole path
458 * - compare it to the ones recorded at dest tile
459 * - if new cost are not better, return -1
460 * - if new costs are better, record them in to_cost/to_extra and return
461 * the cost-of-the-path which is the overall measure of goodness of the
462 * path (less is better) and used to order newly discovered locations. */
463 int (*get_costs) (const struct tile *from_tile,
464 enum direction8 dir,
465 const struct tile *to_tile,
466 int from_cost, int from_extra,
467 unsigned *to_cost, unsigned *to_extra,
468 const struct pf_parameter *param);
469
470 /* User provided data. Can be used to attach arbitrary information
471 * to the map. */
472 void *data;
473};
474
475/* The map itself. Opaque type. */
476struct pf_map;
477
478/* The reverse map structure. Opaque type. */
479struct pf_reverse_map;
480
481
482/* ========================= Public Interface ============================ */
483
484/* Create and free. */
485struct pf_map *pf_map_new(const struct pf_parameter *parameter)
487void pf_map_destroy(struct pf_map *pfm);
488
489/* Method A) functions. */
490int pf_map_move_cost(struct pf_map *pfm, struct tile *ptile);
491struct pf_path *pf_map_path(struct pf_map *pfm, struct tile *ptile)
493bool pf_map_position(struct pf_map *pfm, struct tile *ptile,
494 struct pf_position *pos)
496
497/* Method B) functions. */
498bool pf_map_iterate(struct pf_map *pfm);
499struct tile *pf_map_iter(struct pf_map *pfm);
500int pf_map_iter_move_cost(struct pf_map *pfm);
501struct pf_path *pf_map_iter_path(struct pf_map *pfm)
503void pf_map_iter_position(struct pf_map *pfm, struct pf_position *pos);
504
505/* Other related functions. */
506const struct pf_parameter *pf_map_parameter(const struct pf_map *pfm);
507
508
509/* Paths functions. */
510void pf_path_destroy(struct pf_path *path);
512 const struct pf_path *src_path);
513bool pf_path_advance(struct pf_path *path, struct tile *ptile);
514bool pf_path_backtrack(struct pf_path *path, struct tile *ptile);
515const struct pf_position *pf_path_last_position(const struct pf_path *path);
516void pf_path_print_real(const struct pf_path *path, enum log_level level,
517 const char *file, const char *function, int line);
518#define pf_path_print(path, level) \
519 if (log_do_output_for_level(level)) { \
520 pf_path_print_real(path, level, __FILE__, __FUNCTION__, __FC_LINE__); \
521 }
522
523
524/* Reverse map functions (Costs to go to start tile). */
525struct pf_reverse_map *pf_reverse_map_new(const struct civ_map *nmap,
526 const struct player *pplayer,
527 struct tile *start_tile,
528 int max_turns, bool omniscient)
531 const struct city *pcity,
532 const struct player *attacker,
533 int max_turns, bool omniscient)
536
538 const struct unit_type *punittype,
539 struct tile *ptile);
541 const struct unit *punit);
543 const struct unit_type *punittype,
544 struct tile *ptile,
545 struct pf_position *pos);
547 const struct unit *punit,
548 struct pf_position *pos);
549
550
551
552/* This macro iterates all reachable tiles.
553 *
554 * ARG_pfm - A pf_map structure pointer.
555 * NAME_tile - The name of the iterator to use (type struct tile *). This
556 * is defined inside the macro.
557 * COND_from_start - A boolean value (or equivalent, it can be a function)
558 * which indicate if the start tile should be iterated or
559 * not. */
560#define pf_map_tiles_iterate(ARG_pfm, NAME_tile, COND_from_start) \
561if (COND_from_start || pf_map_iterate((ARG_pfm))) { \
562 struct pf_map *_MY_pf_map_ = (ARG_pfm); \
563 struct tile *NAME_tile; \
564 do { \
565 NAME_tile = pf_map_iter(_MY_pf_map_);
566
567#define pf_map_tiles_iterate_end \
568 } while (pf_map_iterate(_MY_pf_map_)); \
569}
570
571/* This macro iterates all reachable tiles and their move costs.
572 *
573 * ARG_pfm - A pf_map structure pointer.
574 * NAME_tile - The name of the iterator to use (type struct tile *). This
575 * is defined inside the macro.
576 * NAME_cost - The name of the variable containing the move cost info (type
577 * integer). This is defined inside the macro.
578 * COND_from_start - A boolean value (or equivalent, it can be a function)
579 * which indicate if the start tile should be iterated or
580 * not. */
581#define pf_map_move_costs_iterate(ARG_pfm, NAME_tile, NAME_cost, \
582 COND_from_start) \
583if (COND_from_start || pf_map_iterate((ARG_pfm))) { \
584 struct pf_map *_MY_pf_map_ = (ARG_pfm); \
585 struct tile *NAME_tile; \
586 int NAME_cost; \
587 do { \
588 NAME_tile = pf_map_iter(_MY_pf_map_); \
589 NAME_cost = pf_map_iter_move_cost(_MY_pf_map_);
590
591#define pf_map_move_costs_iterate_end \
592 } while (pf_map_iterate(_MY_pf_map_)); \
593}
594
595/* This macro iterates all reachable tiles and fill a pf_position structure.
596 * structure as info.
597 *
598 * ARG_pfm - A pf_map structure pointer.
599 * NAME_pos - The name of the iterator to use (type struct pf_position).
600 * This is defined inside the macro.
601 * COND_from_start - A boolean value (or equivalent, it can be a function)
602 * which indicate if the start tile should be iterated or
603 * not. */
604#define pf_map_positions_iterate(ARG_pfm, NAME_pos, COND_from_start) \
605if (COND_from_start || pf_map_iterate((ARG_pfm))) { \
606 struct pf_map *_MY_pf_map_ = (ARG_pfm); \
607 struct pf_position NAME_pos; \
608 do { \
609 pf_map_iter_position(_MY_pf_map_, &NAME_pos);
610
611#define pf_map_positions_iterate_end \
612 } while (pf_map_iterate(_MY_pf_map_)); \
613}
614
615/* This macro iterates all possible paths.
616 * NB: you need to free the paths with pf_path_destroy(path_iter).
617 *
618 * ARG_pfm - A pf_map structure pointer.
619 * NAME_path - The name of the iterator to use (type struct pf_path *).
620 * This is defined inside the macro.
621 * COND_from_start - A boolean value (or equivalent, it can be a function)
622 * which indicate if the start tile should be iterated or
623 * not. */
624#define pf_map_paths_iterate(ARG_pfm, NAME_path, COND_from_start) \
625if (COND_from_start || pf_map_iterate((ARG_pfm))) { \
626 struct pf_map *_MY_pf_map_ = (ARG_pfm); \
627 struct pf_path *NAME_path;\
628 do {\
629 NAME_path = pf_map_iter_path(_MY_pf_map_);
630
631#define pf_map_paths_iterate_end \
632 } while (pf_map_iterate(_MY_pf_map_)); \
633}
634
635#ifdef __cplusplus
636}
637#endif /* __cplusplus */
638
639#endif /* FC__PATH_FINDING_H */
char * incite_cost
Definition comments.c:76
struct unit struct city struct unit struct tile struct extra_type const struct act_prob *act_probs int actor_unit_id struct unit struct unit * punit
Definition dialogs_g.h:74
struct unit struct city struct unit struct tile struct extra_type const struct act_prob *act_probs int actor_unit_id struct unit struct unit int const struct action *paction struct unit struct city * pcity
Definition dialogs_g.h:78
static struct tile * pos
Definition finddlg.c:53
log_level
Definition log.h:29
bool pf_reverse_map_unit_position(struct pf_reverse_map *pfrm, const struct unit *punit, struct pf_position *pos)
struct pf_path * pf_path_concat(struct pf_path *dest_path, const struct pf_path *src_path)
bool pf_map_position(struct pf_map *pfm, struct tile *ptile, struct pf_position *pos) fc__warn_unused_result
const struct pf_parameter * pf_map_parameter(const struct pf_map *pfm)
void pf_path_print_real(const struct pf_path *path, enum log_level level, const char *file, const char *function, int line)
struct pf_path * pf_map_path(struct pf_map *pfm, struct tile *ptile) fc__warn_unused_result
const struct pf_position * pf_path_last_position(const struct pf_path *path)
void pf_path_destroy(struct pf_path *path)
bool pf_path_backtrack(struct pf_path *path, struct tile *ptile)
bool pf_map_iterate(struct pf_map *pfm)
pf_action
@ PF_ACTION_ATTACK
@ PF_ACTION_DIPLOMAT
@ PF_ACTION_TRADE_ROUTE
@ PF_ACTION_IMPOSSIBLE
@ PF_ACTION_NONE
void pf_map_iter_position(struct pf_map *pfm, struct pf_position *pos)
int pf_map_iter_move_cost(struct pf_map *pfm)
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
pf_move_scope
@ PF_MS_TRANSPORT
@ PF_MS_CITY
@ PF_MS_NATIVE
@ PF_MS_NONE
struct pf_map * pf_map_new(const struct pf_parameter *parameter) 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_unit_move_cost(struct pf_reverse_map *pfrm, const struct unit *punit)
void pf_map_destroy(struct pf_map *pfm)
struct tile * pf_map_iter(struct pf_map *pfm)
struct pf_path * pf_map_iter_path(struct pf_map *pfm) fc__warn_unused_result
pf_action_account
@ PF_AA_CITY_ATTACK
@ PF_AA_UNIT_ATTACK
@ PF_AA_NONE
@ PF_AA_DIPLOMAT
@ PF_AA_TRADE_ROUTE
int pf_map_move_cost(struct pf_map *pfm, struct tile *ptile)
bool pf_path_advance(struct pf_path *path, struct tile *ptile)
int pf_reverse_map_utype_move_cost(struct pf_reverse_map *pfrm, const struct unit_type *punittype, struct tile *ptile)
tile_behavior
@ TB_NORMAL
@ TB_DONT_LEAVE
@ TB_IGNORE
bool pf_reverse_map_utype_position(struct pf_reverse_map *pfrm, const struct unit_type *punittype, struct tile *ptile, struct pf_position *pos)
struct setting_list * level[OLEVELS_NUM]
Definition settings.c:190
Definition city.h:317
int fuel_left_initially
const struct unit_type * transported_by_initially
enum pf_action(* get_action)(const struct tile *ptile, enum known_type known, const struct pf_parameter *param)
enum pf_move_scope(* get_move_scope)(const struct tile *ptile, bool *can_disembark, enum pf_move_scope previous_scope, const struct pf_parameter *param)
bool ignore_none_scopes
const struct civ_map * map
enum tile_behavior(* get_TB)(const struct tile *ptile, enum known_type known, const struct pf_parameter *param)
enum pf_action_account actions
const struct player * owner
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)
int moves_left_initially
bool(* get_zoc)(const struct player *pplayer, const struct tile *ptile, const struct civ_map *zmap)
unsigned(* get_MC)(const struct tile *from_tile, enum pf_move_scope src_move_scope, const struct tile *to_tile, enum pf_move_scope dst_move_scope, const struct pf_parameter *param)
int(* get_costs)(const struct tile *from_tile, enum direction8 dir, const struct tile *to_tile, int from_cost, int from_extra, unsigned *to_cost, unsigned *to_extra, const struct pf_parameter *param)
unsigned(* get_EC)(const struct tile *ptile, enum known_type known, const struct pf_parameter *param)
const struct unit_type * utype
bool(* is_action_possible)(const struct tile *from_tile, enum pf_move_scope src_move_scope, const struct tile *to_tile, enum pf_action action, const struct pf_parameter *param)
bv_unit_types cargo_types
struct tile * start_tile
unsigned length
struct pf_position * positions
unsigned total_MC
enum direction8 dir_to_here
unsigned total_EC
enum direction8 dir_to_next_pos
struct tile * tile
Definition tile.h:50
Definition unit.h:140
#define fc__warn_unused_result
Definition support.h:109
#define bool
Definition support.h:71
known_type
Definition tile.h:35