Freeciv-3.1: /fast/freeciv/nightly/S3_1/common/aicore/path_finding.h Source File

Freeciv-3.1

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 catched 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. */
287 enum pf_action {
288 PF_ACTION_NONE = 0,
289 PF_ACTION_ATTACK,
290 PF_ACTION_DIPLOMAT,
291 PF_ACTION_TRADE_ROUTE,
292 PF_ACTION_IMPOSSIBLE = -1
293};
294
295/* Specifies the actions to consider. */
296 enum pf_action_account {
297 PF_AA_NONE = 0,
298 PF_AA_UNIT_ATTACK = 1 << 0,
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! */
302 PF_AA_CITY_ATTACK = 1 << 1,
303 PF_AA_DIPLOMAT = 1 << 2,
304 PF_AA_TRADE_ROUTE = 1 << 3
305};
306
307/* Specifies the way path-finding will treat a tile. */
308 enum tile_behavior {
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. */
316};
317
318/* Specifies the possibility to move from/to a tile. */
319 enum pf_move_scope {
320 PF_MS_NONE = 0,
321 PF_MS_NATIVE = 1 << 0,
322 PF_MS_CITY = 1 << 1,
323 PF_MS_TRANSPORT = 1 << 2
324};
325
326/* Full specification of a position and time to reach it. */
327 struct pf_position {
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. */
344 struct pf_path {
345 unsigned length; /* Number of steps in the path */
346 struct pf_position *positions;
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. */
357 struct pf_parameter {
358 const struct civ_map *map;
359 struct tile *start_tile; /* Initial position */
360
361 int moves_left_initially;
362 int fuel_left_initially; /* Ignored for non-air units. */
363 /* Set if the unit is transported. */
364 const struct unit_type *transported_by_initially;
365 /* See unit_cargo_depth(). */
366 int cargo_depth;
367 /* All cargo unit types. */
368 bv_unit_types cargo_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,
383 enum pf_move_scope src_move_scope,
384 const struct tile *to_tile,
385 enum pf_move_scope dst_move_scope,
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,
391 enum pf_move_scope previous_scope,
392 const struct pf_parameter *param);
393 bool ignore_none_scopes;
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);
413 enum pf_action_account actions;
414
415 /* Callback which determines whether the action from 'from_tile' to
416 * 'to_tile' is effectively possible. */
417 bool (*is_action_possible) (const struct tile *from_tile,
418 enum pf_move_scope src_move_scope,
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 strucure. Opaque type. */
479struct pf_reverse_map;
480
481
482
483/* ========================= Public Interface ============================ */
484
485/* Create and free. */
486struct pf_map *pf_map_new(const struct pf_parameter *parameter)
487 fc__warn_unused_result;
488void pf_map_destroy(struct pf_map *pfm);
489
490/* Method A) functions. */
491int pf_map_move_cost(struct pf_map *pfm, struct tile *ptile);
492struct pf_path *pf_map_path(struct pf_map *pfm, struct tile *ptile)
493 fc__warn_unused_result;
494bool pf_map_position(struct pf_map *pfm, struct tile *ptile,
495 struct pf_position *pos)
496 fc__warn_unused_result;
497
498/* Method B) functions. */
499bool pf_map_iterate(struct pf_map *pfm);
500struct tile *pf_map_iter(struct pf_map *pfm);
501int pf_map_iter_move_cost(struct pf_map *pfm);
502struct pf_path *pf_map_iter_path(struct pf_map *pfm)
503 fc__warn_unused_result;
504void pf_map_iter_position(struct pf_map *pfm, struct pf_position *pos);
505
506/* Other related functions. */
507const struct pf_parameter *pf_map_parameter(const struct pf_map *pfm);
508
509
510/* Paths functions. */
511void pf_path_destroy(struct pf_path *path);
512struct pf_path *pf_path_concat(struct pf_path *dest_path,
513 const struct pf_path *src_path);
514bool pf_path_advance(struct pf_path *path, struct tile *ptile);
515bool pf_path_backtrack(struct pf_path *path, struct tile *ptile);
516const struct pf_position *pf_path_last_position(const struct pf_path *path);
517void pf_path_print_real(const struct pf_path *path, enum log_level level,
518 const char *file, const char *function, int line);
519#define pf_path_print(path, level) \
520 if (log_do_output_for_level(level)) { \
521 pf_path_print_real(path, level, __FILE__, __FUNCTION__, __FC_LINE__); \
522 }
523
524
525/* Reverse map functions (Costs to go to start tile). */
526struct pf_reverse_map *pf_reverse_map_new(const struct player *pplayer,
527 struct tile *start_tile,
528 int max_turns, bool omniscient,
529 const struct civ_map *nmap)
530 fc__warn_unused_result;
531struct pf_reverse_map *pf_reverse_map_new_for_city(const struct city *pcity,
532 const struct player *attacker,
533 int max_turns, bool omniscient,
534 const struct civ_map *nmap)
535 fc__warn_unused_result;
536void pf_reverse_map_destroy(struct pf_reverse_map *prfm);
537
538int pf_reverse_map_utype_move_cost(struct pf_reverse_map *pfrm,
539 const struct unit_type *punittype,
540 struct tile *ptile);
541int pf_reverse_map_unit_move_cost(struct pf_reverse_map *pfrm,
542 const struct unit *punit);
543bool pf_reverse_map_utype_position(struct pf_reverse_map *pfrm,
544 const struct unit_type *punittype,
545 struct tile *ptile,
546 struct pf_position *pos);
547bool pf_reverse_map_unit_position(struct pf_reverse_map *pfrm,
548 const struct unit *punit,
549 struct pf_position *pos);
550
551
552
553/* This macro iterates all reachable tiles.
554 *
555 * ARG_pfm - A pf_map structure pointer.
556 * NAME_tile - The name of the iterator to use (type struct tile *). This
557 * is defined inside the macro.
558 * COND_from_start - A boolean value (or equivalent, it can be a function)
559 * which indicate if the start tile should be iterated or
560 * not. */
561#define pf_map_tiles_iterate(ARG_pfm, NAME_tile, COND_from_start) \
562if (COND_from_start || pf_map_iterate((ARG_pfm))) { \
563 struct pf_map *_MY_pf_map_ = (ARG_pfm); \
564 struct tile *NAME_tile; \
565 do { \
566 NAME_tile = pf_map_iter(_MY_pf_map_);
567
568#define pf_map_tiles_iterate_end \
569 } while (pf_map_iterate(_MY_pf_map_)); \
570}
571
572/* This macro iterates all reachable tiles and their move costs.
573 *
574 * ARG_pfm - A pf_map structure pointer.
575 * NAME_tile - The name of the iterator to use (type struct tile *). This
576 * is defined inside the macro.
577 * NAME_cost - The name of the variable containing the move cost info (type
578 * integer). This is defined inside the macro.
579 * COND_from_start - A boolean value (or equivalent, it can be a function)
580 * which indicate if the start tile should be iterated or
581 * not. */
582#define pf_map_move_costs_iterate(ARG_pfm, NAME_tile, NAME_cost, \
583 COND_from_start) \
584if (COND_from_start || pf_map_iterate((ARG_pfm))) { \
585 struct pf_map *_MY_pf_map_ = (ARG_pfm); \
586 struct tile *NAME_tile; \
587 int NAME_cost; \
588 do { \
589 NAME_tile = pf_map_iter(_MY_pf_map_); \
590 NAME_cost = pf_map_iter_move_cost(_MY_pf_map_);
591
592#define pf_map_move_costs_iterate_end \
593 } while (pf_map_iterate(_MY_pf_map_)); \
594}
595
596/* This macro iterates all reachable tiles and fill a pf_position structure.
597 * structure as info.
598 *
599 * ARG_pfm - A pf_map structure pointer.
600 * NAME_pos - The name of the iterator to use (type struct pf_position).
601 * This is defined inside the macro.
602 * COND_from_start - A boolean value (or equivalent, it can be a function)
603 * which indicate if the start tile should be iterated or
604 * not. */
605#define pf_map_positions_iterate(ARG_pfm, NAME_pos, COND_from_start) \
606if (COND_from_start || pf_map_iterate((ARG_pfm))) { \
607 struct pf_map *_MY_pf_map_ = (ARG_pfm); \
608 struct pf_position NAME_pos; \
609 do { \
610 pf_map_iter_position(_MY_pf_map_, &NAME_pos);
611
612#define pf_map_positions_iterate_end \
613 } while (pf_map_iterate(_MY_pf_map_)); \
614}
615
616/* This macro iterates all possible paths.
617 * NB: you need to free the paths with pf_path_destroy(path_iter).
618 *
619 * ARG_pfm - A pf_map structure pointer.
620 * NAME_path - The name of the iterator to use (type struct pf_path *).
621 * This is defined inside the macro.
622 * COND_from_start - A boolean value (or equivalent, it can be a function)
623 * which indicate if the start tile should be iterated or
624 * not. */
625#define pf_map_paths_iterate(ARG_pfm, NAME_path, COND_from_start) \
626if (COND_from_start || pf_map_iterate((ARG_pfm))) { \
627 struct pf_map *_MY_pf_map_ = (ARG_pfm); \
628 struct pf_path *NAME_path;\
629 do {\
630 NAME_path = pf_map_iter_path(_MY_pf_map_);
631
632#define pf_map_paths_iterate_end \
633 } while (pf_map_iterate(_MY_pf_map_)); \
634}
635
636#ifdef __cplusplus
637}
638#endif /* __cplusplus */
639
640#endif /* FC__PATH_FINDING_H */
punit
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:73
pos
static struct tile * pos
Definition finddlg.c:53
log.h
log_level
log_level
Definition log.h:28
map.h
pf_reverse_map_unit_position
bool pf_reverse_map_unit_position(struct pf_reverse_map *pfrm, const struct unit *punit, struct pf_position *pos)
Definition path_finding.c:3896
pf_path_concat
struct pf_path * pf_path_concat(struct pf_path *dest_path, const struct pf_path *src_path)
Definition path_finding.c:3426
pf_map_position
bool pf_map_position(struct pf_map *pfm, struct tile *ptile, struct pf_position *pos) fc__warn_unused_result
Definition path_finding.c:3267
pf_map_parameter
const struct pf_parameter * pf_map_parameter(const struct pf_map *pfm)
Definition path_finding.c:3365
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)
Definition path_finding.c:3540
pf_map_path
struct pf_path * pf_map_path(struct pf_map *pfm, struct tile *ptile) fc__warn_unused_result
Definition path_finding.c:3235
pf_path_last_position
const struct pf_position * pf_path_last_position(const struct pf_path *path)
Definition path_finding.c:3531
pf_path_destroy
void pf_path_destroy(struct pf_path *path)
Definition path_finding.c:3411
pf_path_backtrack
bool pf_path_backtrack(struct pf_path *path, struct tile *ptile)
Definition path_finding.c:3503
pf_map_iterate
bool pf_map_iterate(struct pf_map *pfm)
Definition path_finding.c:3288
pf_action
pf_action
Definition path_finding.h:287
PF_ACTION_ATTACK
@ PF_ACTION_ATTACK
Definition path_finding.h:289
PF_ACTION_DIPLOMAT
@ PF_ACTION_DIPLOMAT
Definition path_finding.h:290
PF_ACTION_TRADE_ROUTE
@ PF_ACTION_TRADE_ROUTE
Definition path_finding.h:291
PF_ACTION_IMPOSSIBLE
@ PF_ACTION_IMPOSSIBLE
Definition path_finding.h:292
PF_ACTION_NONE
@ PF_ACTION_NONE
Definition path_finding.h:288
pf_map_iter_position
void pf_map_iter_position(struct pf_map *pfm, struct pf_position *pos)
Definition path_finding.c:3350
pf_map_iter_move_cost
int pf_map_iter_move_cost(struct pf_map *pfm)
Definition path_finding.c:3324
pf_move_scope
pf_move_scope
Definition path_finding.h:319
PF_MS_TRANSPORT
@ PF_MS_TRANSPORT
Definition path_finding.h:323
PF_MS_CITY
@ PF_MS_CITY
Definition path_finding.h:322
PF_MS_NATIVE
@ PF_MS_NATIVE
Definition path_finding.h:321
PF_MS_NONE
@ PF_MS_NONE
Definition path_finding.h:320
pf_map_new
struct pf_map * pf_map_new(const struct pf_parameter *parameter) fc__warn_unused_result
Definition path_finding.c:3182
pf_reverse_map_destroy
void pf_reverse_map_destroy(struct pf_reverse_map *prfm)
Definition path_finding.c:3727
pf_reverse_map_unit_move_cost
int pf_reverse_map_unit_move_cost(struct pf_reverse_map *pfrm, const struct unit *punit)
Definition path_finding.c:3866
pf_map_destroy
void pf_map_destroy(struct pf_map *pfm)
Definition path_finding.c:3206
pf_map_iter
struct tile * pf_map_iter(struct pf_map *pfm)
Definition path_finding.c:3312
pf_reverse_map_new
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
Definition path_finding.c:3688
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_action_account
pf_action_account
Definition path_finding.h:296
PF_AA_CITY_ATTACK
@ PF_AA_CITY_ATTACK
Definition path_finding.h:302
PF_AA_UNIT_ATTACK
@ PF_AA_UNIT_ATTACK
Definition path_finding.h:298
PF_AA_NONE
@ PF_AA_NONE
Definition path_finding.h:297
PF_AA_DIPLOMAT
@ PF_AA_DIPLOMAT
Definition path_finding.h:303
PF_AA_TRADE_ROUTE
@ PF_AA_TRADE_ROUTE
Definition path_finding.h:304
pf_map_move_cost
int pf_map_move_cost(struct pf_map *pfm, struct tile *ptile)
Definition path_finding.c:3219
pf_path_advance
bool pf_path_advance(struct pf_path *path, struct tile *ptile)
Definition path_finding.c:3475
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)
Definition path_finding.c:3852
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) fc__warn_unused_result
Definition path_finding.c:3715
tile_behavior
tile_behavior
Definition path_finding.h:308
TB_NORMAL
@ TB_NORMAL
Definition path_finding.h:309
TB_DONT_LEAVE
@ TB_DONT_LEAVE
Definition path_finding.h:311
TB_IGNORE
@ TB_IGNORE
Definition path_finding.h:310
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)
Definition path_finding.c:3877
level
struct setting_list * level[OLEVELS_NUM]
Definition settings.c:183
action
Definition actions.h:379
city
Definition city.h:309
civ_map
Definition map_types.h:71
pf_map
Definition path_finding.c:78
pf_parameter
Definition path_finding.h:357
pf_parameter::fuel_left_initially
int fuel_left_initially
Definition path_finding.h:362
pf_parameter::transported_by_initially
const struct unit_type * transported_by_initially
Definition path_finding.h:364
pf_parameter::get_action
enum pf_action(* get_action)(const struct tile *ptile, enum known_type known, const struct pf_parameter *param)
Definition path_finding.h:410
pf_parameter::get_move_scope
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)
Definition path_finding.h:389
pf_parameter::ignore_none_scopes
bool ignore_none_scopes
Definition path_finding.h:393
pf_parameter::map
const struct civ_map * map
Definition path_finding.h:358
pf_parameter::get_TB
enum tile_behavior(* get_TB)(const struct tile *ptile, enum known_type known, const struct pf_parameter *param)
Definition path_finding.h:398
pf_parameter::actions
enum pf_action_account actions
Definition path_finding.h:413
pf_parameter::owner
const struct player * owner
Definition path_finding.h:374
pf_parameter::is_pos_dangerous
bool(* is_pos_dangerous)(const struct tile *ptile, enum known_type, const struct pf_parameter *param)
Definition path_finding.h:436
pf_parameter::get_moves_left_req
int(* get_moves_left_req)(const struct tile *ptile, enum known_type, const struct pf_parameter *param)
Definition path_finding.h:441
pf_parameter::moves_left_initially
int moves_left_initially
Definition path_finding.h:361
pf_parameter::cargo_depth
int cargo_depth
Definition path_finding.h:366
pf_parameter::move_rate
int move_rate
Definition path_finding.h:370
pf_parameter::get_zoc
bool(* get_zoc)(const struct player *pplayer, const struct tile *ptile, const struct civ_map *zmap)
Definition path_finding.h:430
pf_parameter::get_MC
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)
Definition path_finding.h:382
pf_parameter::get_costs
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)
Definition path_finding.h:463
pf_parameter::get_EC
unsigned(* get_EC)(const struct tile *ptile, enum known_type known, const struct pf_parameter *param)
Definition path_finding.h:405
pf_parameter::data
void * data
Definition path_finding.h:472
pf_parameter::fuel
int fuel
Definition path_finding.h:371
pf_parameter::utype
const struct unit_type * utype
Definition path_finding.h:373
pf_parameter::is_action_possible
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)
Definition path_finding.h:417
pf_parameter::cargo_types
bv_unit_types cargo_types
Definition path_finding.h:368
pf_parameter::omniscience
bool omniscience
Definition path_finding.h:376
pf_parameter::start_tile
struct tile * start_tile
Definition path_finding.h:359
pf_path
Definition path_finding.h:344
pf_path::length
unsigned length
Definition path_finding.h:345
pf_path::positions
struct pf_position * positions
Definition path_finding.h:346
pf_position
Definition path_finding.h:327
pf_position::total_MC
unsigned total_MC
Definition path_finding.h:336
pf_position::moves_left
int moves_left
Definition path_finding.h:330
pf_position::fuel_left
int fuel_left
Definition path_finding.h:332
pf_position::dir_to_here
enum direction8 dir_to_here
Definition path_finding.h:340
pf_position::total_EC
unsigned total_EC
Definition path_finding.h:337
pf_position::dir_to_next_pos
enum direction8 dir_to_next_pos
Definition path_finding.h:339
pf_position::tile
struct tile * tile
Definition path_finding.h:328
pf_position::turn
int turn
Definition path_finding.h:329
pf_reverse_map
Definition path_finding.c:3587
pf_reverse_map::max_turns
int max_turns
Definition path_finding.c:3589
player
Definition player.h:249
tile
Definition tile.h:49
unit_type
Definition unittype.h:481
unit
Definition unit.h:138
fc__warn_unused_result
#define fc__warn_unused_result
Definition support.h:99
bool
#define bool
Definition support.h:61
tile.h
known_type
known_type
Definition tile.h:34
unit.h
unittype.h