73
70
* First of all it should be noted that path-finding is not about finding
74
* shortest paths but about finding the "best" paths. Now, each path
75
* has two major characteristics:
71
* shortest paths but about finding the "best" paths. Now, each path has
72
* two major characteristics:
76
73
* (1) How long it is (or how much does it cost in terms of time)
78
* (2) How dangerous it is (or how much does it cost in terms of
75
* (2) How dangerous it is (or how much does it cost in terms of resources).
81
77
* We use MC (and total_MC) to describe (1) and use EC (and total_EC) to
82
* describe (2). Of course, when it comes to selecting the "best" path,
78
* describe (2). Of course, when it comes to selecting the "best" path,
83
79
* we need to compromise between taking the shortest road and taking the
84
* safest road. To that end, we use the "combined cost", calculated as
80
* safest road. To that end, we use the "combined cost", calculated as
85
81
* total_CC = PF_TURN_FACTOR * total_MC + move_rate * total_EC,
86
* where PF_TURN_FACTOR is a large constant. This means that each EC
82
* where PF_TURN_FACTOR is a large constant. This means that each EC
87
83
* point is equivalent to 1/PF_TURN_FACTOR-th of one turn, or,
88
84
* equivalently, we are willing to spend one more turn on the road to
89
* avoid PF_TURN_FACTOR worth of danger. Note that if ECs are kept
85
* avoid PF_TURN_FACTOR worth of danger. Note that if ECs are kept
90
86
* significantly lower than PF_TURN_FACTOR, the total_EC will only act as a
91
87
* tie-breaker between equally long paths.
93
* Note, that the user is expected to ask "So this best path, how long will
94
* it take me to walk it?". For that reason we keep our accounts of MCs and
89
* Note, that the user is expected to ask "So this best path, how long will
90
* it take me to walk it?". For that reason we keep our accounts of MCs and
95
91
* ECs separately, as one cannot answer the above question basing on
98
94
* The above setup allows us to find elegant solutions to rather involved
99
* questions. A good example would be designing a road from A to B:
95
* questions. A good example would be designing a road from A to B:
100
96
* ================
101
97
* The future road should be as short as possible, but out of many
102
98
* shortest roads we want to select the one which is fastest to
103
* construct. For example:
99
* construct. For example:
104
100
* the initial conditions ("-"s mark existing road, "."s mark plains)
108
104
* a possible solution
112
108
* the best solution (utilize existing road)
117
113
* To solve the problem we simply declare that
118
114
* MC between any two tiles shall be MOVE_COST_ROAD
119
115
* EC of any tile shall be the time to construct a road there
120
116
* =================
122
118
* In some cases we would like to impose extra restrictions on the
123
* paths/tiles we want to consider. For example, a trireme might want to
124
* never enter deep sea. A chariot, would like to find paths going to
125
* enemy cities but not going _through_ them. This can be achieved
126
* through an additional tile_behaviour callback, which would return
119
* paths/tiles we want to consider. For example, a trireme might want to
120
* never enter deep sea. A chariot, would like to find paths going to
121
* enemy cities but not going _through_ them. This can be achieved
122
* through an additional tile_behaviour callback, which would return
127
123
* TB_IGNORE for tiles we don't want to visit and TB_DONT_LEAVE for tiles
128
124
* we won't be able to leave (at least alive).
130
* Dangerous tiles are those on which we don't want to end a turn. If
131
* the danger callback is specified it is used to determine which tiles are
126
* Dangerous tiles are those on which we don't want to end a turn. If the
127
* danger callback is specified it is used to determine which tiles are
132
128
* dangerous; no path that ends a turn on such a tile will ever be
135
* There is also support for fuel, and thus indirectly for air units. If
131
* There is also support for fuel, and thus indirectly for air units. If
136
132
* the fuel parameters are provided then the unit is considered to have
137
* that much fuel. The net effect is that if a unit has N fuel then only
138
* every Nth turn will be considered a stopping point. To support air
133
* that much fuel. The net effect is that if a unit has N fuel then only
134
* every Nth turn will be considered a stopping point. To support air
139
135
* units, then, all tiles that don't have airfields (or cities/carriers)
140
* should be returned as dangerous (see danger, above). Note: fuel support
141
* will only work if all moves have equal MC. Support for fuel is
142
* experimental at this time (Jun 2005) and should not be used in the
143
* server. Setting fuel==1 in the pf_parameter disables fuel support.
145
* There are few other options in the path-finding, including "omniscience"
146
* (if true, all tiles are assumed to be KNOWN) and "get_zoc" callback (if
147
* not NULL, we will consider restrictions imposed upon our movements by
136
* should be returned as dangerous (see danger, above). Setting fuel == 1
137
* in the pf_parameter disables fuel support.
139
* There are few other options in the path-finding. For further info about
140
* them, see comment for the pf_parameter structure below.
152
144
* For calculating total_MC (given particular tile_behaviour)
153
* - TM_NONE: total_MC = sum of MC
154
* - TM_CAPPED: total_MC = sum of MIN(MC, move_rate)
155
* - TM_*_TIME: total_MC = ((turn + 1) * move_rate - moves_left)
145
* total_MC = ((turn + 1) * move_rate - moves_left)
157
147
* For calculating total_CC:
158
148
* total_CC = PF_TURN_FACTOR * total_MC + move_rate * total_EC
167
157
* (B) We know what we want and need the nearest one
168
158
* Where is the nearest pub, gov?
170
* In the first case we use pf_get_path and pf_get_position (the latter
171
* will only tell us the distance but not the path to take). In the
172
* second case we use pf_next to iterate through all tiles in the order
173
* of increased distance and break when we found what we were looking
174
* for. In this case we use pf_next_get_* to get information about the
175
* "next closest tile".
160
* In the first case we use pf_map_move_cost(), pf_map_path(), and
161
* pf_map_position() (the latter will only tell us the distance but not the
162
* path to take). In the second case we use pf_map_iterate() to iterate
163
* through all tiles in the order of increased distance and break when we
164
* found what we were looking for. In this case we use pf_map_iter_*() to
165
* get information about the "closest tile".
177
* A) the caller knows the map position of the goal and wants to know the
167
* A) the caller knows the map position of the goal and wants to know the
180
* struct pf_parameter parameter;
181
* struct pf_map *pfm;
182
* struct pf_path *path;
184
* // fill parameter (see below)
186
* pfm = pf_map_new(¶meter);
188
* if ((path = pf_map_get_path(pfm, ptile))) {
189
* // success, use path
190
* pf_path_destroy(path);
192
* // no path could be found
195
* pf_map_destroy(pfm);
197
* You may call pf_map_get_path multiple times with the same pfm.
199
* B) the caller doesn't know the map position of the goal yet (but knows
170
* struct pf_parameter parameter;
171
* struct pf_map *pfm;
172
* struct pf_path *path;
174
* // fill parameter (see below)
176
* // create the map: the main path-finding object.
177
* pfm = pf_map_new(¶meter);
179
* // create the path to the tile 'ptile'.
180
* if ((path = pf_map_path(pfm, ptile))) {
181
* // success, use path
182
* pf_path_destroy(path);
184
* // no path could be found
187
* // don't forget to destroy the map after usage.
188
* pf_map_destroy(pfm);
190
* You may call pf_map_path() multiple times with the same pfm.
192
* B) the caller doesn't know the map position of the goal yet (but knows
200
193
* what he is looking for, e.g. a port) and wants to iterate over
201
194
* all paths in order of increasing costs (total_CC):
203
* struct pf_parameter parameter;
204
* struct pf_map *pfm;
206
* // fill parameter (see below)
208
* pfm = pf_map_new(¶meter);
210
* pf_map_iterate_*(pfm, something, TRUE) {
212
* } pf_map_iterate_*_end;
214
* pf_map_destroy(pfm);
196
* struct pf_parameter parameter;
197
* struct pf_map *pfm;
199
* // fill parameter (see below)
201
* // create the map: the main path-finding object.
202
* pfm = pf_map_new(¶meter);
204
* // iterate the map, using macros defined on this header.
205
* pf_map_*_iterate(pfm, something, TRUE) {
207
* } pf_map_*_iterate_end;
209
* // don't forget to destroy the map after usage.
210
* pf_map_destroy(pfm);
216
212
* Depending on the kind of information required, the iteration macro
219
215
* 1) tile iteration:
220
* pf_map_iterate_tiles(pfm, ptile, TRUE) {
216
* pf_map_tiles_iterate(pfm, ptile, TRUE) {
221
217
* // do something
222
* } pf_map_iterate_tiles_end;
218
* } pf_map_tiles_iterate_end;
224
220
* 2) move cost iteration on the nearest position:
225
* pf_map_iterate_move_costs(pfm, ptile, move_cost, TRUE) {
221
* pf_map_move_costs_iterate(pfm, ptile, move_cost, TRUE) {
226
222
* // do something
227
* } pf_map_iterate_move_costs_end;
223
* } pf_map_move_costs_iterate_end;
229
* 3) information (for example the total MC and the number of turns) on the
225
* 3) information (for example the total MC and the number of turns) on the
230
226
* next nearest position:
231
* pf_map_iterate_positions(pfm, pos, TRUE) {
227
* pf_map_positions_iterate(pfm, pos, TRUE) {
232
228
* // do something
233
* } pf_map_iterate_positions_end;
229
* } pf_map_positions_iterate_end;
235
* 4) information about the whole path (leading to the next nearest position):
236
* pf_map_iterate_pathes(pfm, path, TRUE) {
231
* 4) information about the whole path (leading to the next nearest
233
* pf_map_paths_iterate(pfm, path, TRUE) {
237
234
* // do something
238
235
* pf_path_destroy(path);
239
* } pf_map_iterate_pathes_end;
236
* } pf_map_paths_iterate_end;
241
238
* The third argument passed to the iteration macros is a condition that
242
239
* controls if the start tile of the pf_parameter should iterated or not.
265
262
/* The factor which is used to multiple total_EC in the total_CC
266
263
* calculation. See definition of total_CC above.
267
* The number is chosen to be much larger than 0 and much smaller
264
* The number is chosen to be much larger than 0 and much smaller
268
265
* than MAX_INT (and a power of 2 for easy multiplication). */
269
266
#define PF_TURN_FACTOR 65536
271
/* ========================= Structures =============================== */
268
/* =========================== Structures ================================ */
273
270
/* Specifies the way path-finding will treat a tile. */
274
271
enum tile_behavior {
275
TB_IGNORE, /* This one will be ignored */
276
TB_DONT_LEAVE, /* Paths can lead _to_ such tile,
277
* but are not allowed to go _through_ */
278
TB_NORMAL /* Well, normal */
281
/* Specifies how total_MC, turn and moves_left fields in the positions
282
* (struct pf_position) are computed. */
284
/* No turn numbers or moves_left are used at all. The fields "turn"
285
* and "moves_left" of struct pf_position will always be set to -1 in
289
/* Similar to TM_NONE. The MC, however, is capped at the
290
* move_rate. The fields "turn" and "moves_left" will always be -1. */
293
/* Assumes that the unit is always lucky in the random rulings and
294
* so yields the best travel time. */
297
/* Assumes that the unit is never lucky in the random rulings and so
298
* yields the worst travel time. */
272
TB_IGNORE = 0, /* This one will be ignored. */
273
TB_DONT_LEAVE, /* Paths can lead _to_ such tile, but are not
274
* allowed to go _through_. */
275
TB_NORMAL /* Well, normal .*/
302
278
/* Full specification of a position and time to reach it. */
303
279
struct pf_position {
305
int turn, moves_left, fuel_left; /* See definitions above */
307
int total_MC; /* Total MC to reach this point */
308
int total_EC; /* Total EC to reach this point */
310
enum direction8 dir_to_next_pos; /* Unsed only in struct_path */
311
enum direction8 dir_to_here; /* Where did we come from */
280
struct tile *tile; /* The tile. */
281
int turn; /* The number of turns to the target. */
282
int moves_left; /* The number of moves left the unit would have when
283
* reaching the tile. */
284
int fuel_left; /* The number of turns of fuel left the unit would
285
* have when reaching the tile. It is always set to
286
* 1 when unit types are not fueled. */
288
int total_MC; /* Total MC to reach this point */
289
int total_EC; /* Total EC to reach this point */
291
enum direction8 dir_to_next_pos; /* Used only in 'struct pf_path'. */
292
enum direction8 dir_to_here; /* Where did we come from. */
314
295
/* Full specification of a path. */
316
int length; /* Number of steps in the path */
297
int length; /* Number of steps in the path */
317
298
struct pf_position *positions;
320
/* Initial data for the path-finding. Normally should use functions
321
* from pf_tools.[ch] to fill the parameter.
323
* All callbacks get the parameter passed to pf_create_map as the last
326
* Examples of callbacks can be found in pf_tools.c
301
/* Initial data for the path-finding. Normally should use functions
302
* from "pf_tools.[ch]" to fill the parameter.
304
* All callbacks get the parameter passed to pf_map_new() as the last
307
* Examples of callbacks can be found in "pf_tools.c"
327
308
* NB: It should be safe to struct copy pf_parameter. */
328
309
struct pf_parameter {
329
struct tile *start_tile; /* Initial position */
310
struct tile *start_tile; /* Initial position */
331
312
int moves_left_initially;
332
313
int fuel_left_initially; /* Ignored for non-air units. */
334
int move_rate; /* Move rate of the virtual unit */
315
int move_rate; /* Move rate of the virtual unit */
335
316
int fuel; /* Should be 1 for units without fuel. */
337
318
struct player *owner;
338
319
const struct unit_class *uclass;
340
bv_flags unit_flags; /* Like F_MARINE and F_TRIREME */
341
bool omniscience; /* Do we care if the tile is visible? */
343
enum turn_mode turn_mode; /* See definitions. */
345
/* Callback to get MC of a move from (from_x, from_y) to (to_x,
346
* to_y) and in the direction dir. Note that the callback can
347
* calculate (to_x, to_y) by itself based on (from_x, from_y) and
348
* dir. Excessive information (to_x, to_y) is provided to ease the
349
* implementation of the callback. */
321
bv_unit_type_flags unit_flags; /* Like F_MARINE and F_TRIREME */
322
bool omniscience; /* Do we care if the tile is visible? */
324
/* Callback to get MC of a move from 'from_tile' to 'to_tile' and in the
325
* direction 'dir'. Note that the callback can calculate 'to_tile' by
326
* itself based on 'from_tile' and 'dir'. Excessive information 'to_tile'
327
* is provided to ease the implementation of the callback. */
350
328
int (*get_MC) (const struct tile *from_tile, enum direction8 dir,
351
329
const struct tile *to_tile,
352
330
const struct pf_parameter *param);
353
int unknown_MC; /* Move cost into unknown - very large by default */
331
int unknown_MC; /* Move cost into unknown - very large by default. */
355
333
/* Callback which determines the behavior of a tile. If NULL
356
334
* TB_NORMAL is assumed. It can be assumed that the implementation
357
* of path_finding.h will cache this value. */
335
* of "path_finding.h" will cache this value. */
358
336
enum tile_behavior (*get_TB) (const struct tile *ptile,
359
337
enum known_type known,
360
338
const struct pf_parameter *param);
362
/* Callback which can be used to provide extra costs depending on
363
* the tile. Can be NULL. It can be assumed that the implementation
364
* of path_finding.h will cache this value. */
340
/* Callback which can be used to provide extra costs depending on the
341
* tile. Can be NULL. It can be assumed that the implementation of
342
* "path_finding.h" will cache this value. */
365
343
int (*get_EC) (const struct tile *ptile, enum known_type known,
366
344
const struct pf_parameter *param);
368
/* Callback to determines if we could invade the tile. Returns TRUE
369
* if we can enter in the territory of the tile owner. */
346
/* Callback to determines if we could invade the tile. Returns TRUE if we
347
* can enter in the territory of the tile owner. */
370
348
bool (*can_invade_tile) (const struct player *pplayer,
371
349
const struct tile *ptile);
373
351
/* Although the rules governing ZoC are universal, the amount of
374
* information available at server and client is different. To
375
* compensate for it, we might need to supply our own version
376
* of "common" is_my_zoc. Also AI might need to partially ignore
377
* ZoC for strategic planning purposes (take into account enemy cities
352
* information available at server and client is different. To
353
* compensate for it, we might need to supply our own version
354
* of "common" is_my_zoc. Also AI might need to partially ignore
355
* ZoC for strategic planning purposes (take into account enemy cities
378
356
* but not units for example).
379
* If this callback is NULL, ZoC are ignored.*/
357
* If this callback is NULL, ZoC are ignored. */
380
358
bool (*get_zoc) (const struct player *pplayer, const struct tile *ptile);
382
360
/* If this callback is non-NULL and returns TRUE this position is
424
/* The map itself. Opaque type. */
402
/* The map itself. Opaque type. */
427
/* The city map strucure. Opaque type. */
432
/* ======================== Public Interface =========================== */
434
/* Returns a map which can be used to query for paths or to iterate
435
* over all paths. Does not perform any computations itself, just sets
437
struct pf_map *pf_map_new(const struct pf_parameter *parameter);
439
/* After usage the map should be destroyed. */
405
/* The reverse map strucure. Opaque type. */
406
struct pf_reverse_map;
410
/* ========================= Public Interface ============================ */
412
/* Create and free. */
413
struct pf_map *pf_map_new(const struct pf_parameter *parameter)
414
fc__warn_unused_result;
440
415
void pf_map_destroy(struct pf_map *pfm);
442
/* Tries to find the best path in the given map to the position ptile.
443
* If NULL is returned no path could be found. The pf_path_get_last_position
444
* of such path would be the same (almost) as the result of the call to
445
* pf_map_get_position(pfm, ptile, &pos) */
446
struct pf_path *pf_map_get_path(struct pf_map *pfm, struct tile *ptile);
448
/* Iterates the map until it reaches ptile. Then fills the info
449
* about it into pos. Returns FALSE if position is unreachable.
450
* Contents of pos in this case is not defined. */
451
bool pf_map_get_position(struct pf_map *pfm, struct tile *ptile,
452
struct pf_position *pos);
454
/* Iterates the path-finding algorithm one step further, to the next
455
* nearest position. This full info on this position and the best path to
456
* it can be obtained using pf_map_iterator_get_position and
457
* pf_map_iteratir_get_path, correspondingly. Returns FALSE if no
458
* further positions are available in this map. If pf_map_get_path(pfm, ptile)
459
* or pf_map_get_position(pfm, ptile, &pos) has been called before the call
460
* to pf_map_iterate(pfm), the iteration will resume from ptile. */
417
/* Method A) functions. */
418
int pf_map_move_cost(struct pf_map *pfm, struct tile *ptile);
419
struct pf_path *pf_map_path(struct pf_map *pfm, struct tile *ptile)
420
fc__warn_unused_result;
421
bool pf_map_position(struct pf_map *pfm, struct tile *ptile,
422
struct pf_position *pos)
423
fc__warn_unused_result;
425
/* Method B) functions. */
461
426
bool pf_map_iterate(struct pf_map *pfm);
463
/* Return the map iterator tile. */
464
struct tile *pf_map_iterator_get_tile(struct pf_map *pfm);
466
/* Return the move cost at the map iterator tile. */
467
int pf_map_iterator_get_move_cost(struct pf_map *pfm);
469
/* Return the map iterator position. This is equivalent to
470
* pf_map_get_position(pfm, pf_map_iterator_get_tile(pfm), &pos). */
471
void pf_map_iterator_get_position(struct pf_map *pfm,
472
struct pf_position *pos);
474
/* Return the map iterator path. This is equivalent to
475
* pf_map_get_path(pfm, pf_map_iterator_get_tile(pfm)). */
476
struct pf_path *pf_map_iterator_get_path(struct pf_map *pfm);
478
/* Return the current parameters for the given map. */
479
const struct pf_parameter *pf_map_get_parameter(const struct pf_map *pfm);
483
/* Print the path via freelog and the given log-level. For
484
* debugging purposes. Make sure the path is valid (if you
485
* got it from pf_map_get_path()). */
486
void pf_path_print(const struct pf_path *path, int log_level);
488
/* After use, a path must be destroyed. pf_destroy_path will also
489
* accept NULL (which is returned by pf_map_get_path in error case). */
427
struct tile *pf_map_iter(struct pf_map *pfm);
428
int pf_map_iter_move_cost(struct pf_map *pfm);
429
struct pf_path *pf_map_iter_path(struct pf_map *pfm)
430
fc__warn_unused_result;
431
void pf_map_iter_position(struct pf_map *pfm, struct pf_position *pos);
433
/* Other related functions. */
434
const struct pf_parameter *pf_map_parameter(const struct pf_map *pfm);
437
/* Paths functions. */
490
438
void pf_path_destroy(struct pf_path *path);
492
/* Returns the last position of the given path. */
493
const struct pf_position *pf_path_get_last_position(const struct pf_path *path);
497
/* Create a city cost map. It is used to calculate the cost units may
498
* need to reach the city. */
499
struct pf_city_map *pf_city_map_new(const struct city *pcity);
501
/* Destroy a city cost map. */
502
void pf_city_map_destroy(struct pf_city_map *pfcm);
504
/* Get the move cost needed by the unit to reach the city. */
505
int pf_city_map_get_move_cost(struct pf_city_map *pfcm,
506
const struct unit_type *punittype,
512
* This macro iterates all reachable tiles.
514
* - pfm: A pf_map structure pointer.
515
* - tile_iter: The name of the iterator to use (type struct tile *).
516
* - from_start_tile: A boolean value which indicate if the start_tile
517
* should be iterated or not.
519
#define pf_map_iterate_tiles(pfm, tile_iter, from_start_tile)\
520
if ((from_start_tile) || pf_map_iterate((pfm))) {\
521
struct pf_map *__pf_map = (pfm);\
522
struct tile *tile_iter;\
524
tile_iter = pf_map_iterator_get_tile(__pf_map);
525
#define pf_map_iterate_tiles_end\
526
} while (pf_map_iterate(__pf_map));\
530
* This macro iterates all reachable tiles and their move costs.
532
* - pfm: A pf_map structure pointer.
533
* - tile_iter: The name of the iterator to use (type struct tile *).
534
* - move_cost: The name of the variable containing the move cost info.
535
* - from_start_tile: A boolean value which indicate if the start_tile
536
* should be iterated or not.
538
#define pf_map_iterate_move_costs(pfm, tile_iter, move_cost, from_start_tile)\
539
if ((from_start_tile) || pf_map_iterate((pfm))) {\
540
struct pf_map *__pf_map = (pfm);\
541
struct tile *tile_iter;\
544
tile_iter = pf_map_iterator_get_tile(__pf_map);\
545
move_cost = pf_map_iterator_get_move_cost(__pf_map);
546
#define pf_map_iterate_move_costs_end\
547
} while (pf_map_iterate(__pf_map));\
551
* This macro iterates all reachable tiles and fill a pf_position
439
const struct pf_position *pf_path_last_position(const struct pf_path *path);
440
void pf_path_print_real(const struct pf_path *path, enum log_level level,
441
const char *file, const char *function, int line);
442
#define pf_path_print(path, level) \
443
if (log_do_output_for_level(level)) { \
444
pf_path_print_real(path, level, __FILE__, __FUNCTION__, __LINE__); \
448
/* Reverse map functions (Costs to go to start tile). */
449
struct pf_reverse_map *pf_reverse_map_new(struct player *pplayer,
450
struct tile *start_tile,
452
fc__warn_unused_result;
453
struct pf_reverse_map *pf_reverse_map_new_for_city(const struct city *pcity,
455
fc__warn_unused_result;
456
struct pf_reverse_map *pf_reverse_map_new_for_unit(const struct unit *punit,
458
fc__warn_unused_result;
459
void pf_reverse_map_destroy(struct pf_reverse_map *prfm);
461
int pf_reverse_map_utype_move_cost(struct pf_reverse_map *pfrm,
462
const struct unit_type *punittype,
464
int pf_reverse_map_unit_move_cost(struct pf_reverse_map *pfrm,
465
const struct unit *punit);
466
struct pf_path *pf_reverse_map_utype_path(struct pf_reverse_map *pfrm,
467
const struct unit_type *punittype,
469
struct pf_path *pf_reverse_map_unit_path(struct pf_reverse_map *pfrm,
470
const struct unit *punit);
471
bool pf_reverse_map_utype_position(struct pf_reverse_map *pfrm,
472
const struct unit_type *punittype,
474
struct pf_position *pos);
475
bool pf_reverse_map_unit_position(struct pf_reverse_map *pfrm,
476
const struct unit *punit,
477
struct pf_position *pos);
481
/* This macro iterates all reachable tiles.
483
* ARG_pfm - A pf_map structure pointer.
484
* NAME_tile - The name of the iterator to use (type struct tile *). This
485
* is defined inside the macro.
486
* COND_from_start - A boolean value (or equivalent, it can be a function)
487
* which indicate if the start tile should be iterated or
489
#define pf_map_tiles_iterate(ARG_pfm, NAME_tile, COND_from_start) \
490
if ((COND_from_start) || pf_map_iterate((ARG_pfm))) { \
491
struct pf_map *_MY_pf_map_ = (ARG_pfm); \
492
struct tile *NAME_tile; \
494
NAME_tile = pf_map_iter(_MY_pf_map_);
495
#define pf_map_tiles_iterate_end \
496
} while (pf_map_iterate(_MY_pf_map_)); \
499
/* This macro iterates all reachable tiles and their move costs.
501
* ARG_pfm - A pf_map structure pointer.
502
* NAME_tile - The name of the iterator to use (type struct tile *). This
503
* is defined inside the macro.
504
* NAME_cost - The name of the variable containing the move cost info (type
505
* integer). This is defined inside the macro.
506
* COND_from_start - A boolean value (or equivalent, it can be a function)
507
* which indicate if the start tile should be iterated or
509
#define pf_map_move_costs_iterate(ARG_pfm, NAME_tile, NAME_cost, \
511
if ((COND_from_start) || pf_map_iterate((ARG_pfm))) { \
512
struct pf_map *_MY_pf_map_ = (ARG_pfm); \
513
struct tile *NAME_tile; \
516
NAME_tile = pf_map_iter(_MY_pf_map_); \
517
NAME_cost = pf_map_iter_move_cost(_MY_pf_map_);
518
#define pf_map_move_costs_iterate_end \
519
} while (pf_map_iterate(_MY_pf_map_)); \
522
/* This macro iterates all reachable tiles and fill a pf_position structure.
552
523
* structure as info.
554
* - pfm: A pf_map structure pointer.
555
* - pos_iter: The name of the iterator to use (type struct pf_position).
556
* - from_start_tile: A boolean value which indicate if the start_tile
557
* should be iterated or not.
559
#define pf_map_iterate_positions(pfm, pos_iter, from_start_tile)\
560
if ((from_start_tile) || pf_map_iterate((pfm))) {\
561
struct pf_map *__pf_map = (pfm);\
562
struct pf_position pos_iter;\
564
pf_map_iterator_get_position(__pf_map, &pos_iter);
565
#define pf_map_iterate_positions_end\
566
} while (pf_map_iterate(__pf_map));\
525
* ARG_pfm - A pf_map structure pointer.
526
* NAME_pos - The name of the iterator to use (type struct pf_position).
527
* This is defined inside the macro.
528
* COND_from_start - A boolean value (or equivalent, it can be a function)
529
* which indicate if the start tile should be iterated or
531
#define pf_map_positions_iterate(ARG_pfm, NAME_pos, COND_from_start) \
532
if ((COND_from_start) || pf_map_iterate((ARG_pfm))) { \
533
struct pf_map *_MY_pf_map_ = (ARG_pfm); \
534
struct pf_position NAME_pos; \
536
pf_map_iter_position(_MY_pf_map_, &NAME_pos);
537
#define pf_map_positions_iterate_end \
538
} while (pf_map_iterate(_MY_pf_map_)); \
570
* This macro iterates all possible pathes.
541
/* This macro iterates all possible pathes.
571
542
* NB: you need to free the pathes with pf_path_destroy(path_iter).
573
* - pfm: A pf_map structure pointer.
574
* - path_iter: The name of the iterator to use (type struct pf_path *).
575
* - from_start_tile: A boolean value which indicate if the start_tile
576
* should be iterated or not.
578
#define pf_map_iterate_pathes(pfm, path_iter, from_start_tile)\
579
if ((from_start_tile) || pf_map_iterate((pfm))) {\
580
struct pf_map *__pf_map = (pfm);\
581
struct pf_path *path_iter;\
544
* ARG_pfm - A pf_map structure pointer.
545
* NAME_path - The name of the iterator to use (type struct pf_path *). This
546
* is defined inside the macro.
547
* COND_from_start - A boolean value (or equivalent, it can be a function)
548
* which indicate if the start tile should be iterated or
550
#define pf_map_paths_iterate(ARG_pfm, NAME_path, COND_from_start) \
551
if ((COND_from_start) || pf_map_iterate((ARG_pfm))) { \
552
struct pf_map *_MY_pf_map_ = (ARG_pfm); \
553
struct pf_path *NAME_path;\
583
path_iter = pf_map_iterator_get_path(__pf_map);
584
#define pf_map_iterate_pathes_end\
585
} while (pf_map_iterate(__pf_map));\
555
NAME_path = pf_map_iter_path(_MY_pf_map_);
556
#define pf_map_paths_iterate_end \
557
} while (pf_map_iterate(_MY_pf_map_)); \
588
560
#endif /* FC__PATH_FINDING_H */
added
removed
common/aicore/path_finding.h
