Freeciv-3.4
Loading...
Searching...
No Matches
path_finding.c
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
14#ifdef HAVE_CONFIG_H
15#include <fc_config.h>
16#endif
17
18/* utility */
19#include "bitvector.h"
20#include "log.h"
21#include "mem.h"
22#include "support.h"
23
24/* common */
25#include "game.h"
26#include "map.h"
27#include "movement.h"
28
29/* common/aicore */
30#include "pf_tools.h"
31
32#include "path_finding.h"
33
34/* For explanations on how to use this module, see "path_finding.h". */
35
36#define SPECPQ_TAG map_index
37#define SPECPQ_DATA_TYPE int
38#define SPECPQ_PRIORITY_TYPE int
39#include "specpq.h"
40#define INITIAL_QUEUE_SIZE 100
41
42#ifdef FREECIV_DEBUG
43/* Extra checks for debugging. */
44#define PF_DEBUG
45#endif
46
47/* ======================== Internal structures ========================== */
48
49#ifdef PF_DEBUG
50/* The mode we use the pf_map. Used for cast conversion checks. */
51enum pf_mode {
52 PF_NORMAL = 1, /* Usual goto */
53 PF_DANGER, /* Goto with dangerous positions */
54 PF_FUEL /* Goto for fueled units */
55};
56#endif /* PF_DEBUG */
57
59 NS_UNINIT = 0, /* memory is calloced, hence zero means
60 * uninitialised. */
61 NS_INIT, /* node initialized, but we didn't search a route
62 * yet. */
63 NS_NEW, /* the optimal route isn't found yet. */
64 NS_WAITING, /* the optimal route is found, considering waiting.
65 * Only used for pf_danger_map and pf_fuel_map, it
66 * means we are waiting on a safe place for full
67 * moves before crossing a dangerous area. */
68 NS_PROCESSED /* the optimal route is found. */
69};
70
72 ZOC_MINE = 0, /* My ZoC. */
73 ZOC_ALLIED, /* Allied ZoC. */
74 ZOC_NO /* No ZoC. */
75};
76
77/* Abstract base class for pf_normal_map, pf_danger_map, and pf_fuel_map. */
78struct pf_map {
79#ifdef PF_DEBUG
80 enum pf_mode mode; /* The mode of the map, for conversion checking. */
81#endif /* PF_DEBUG */
82
83 /* "Virtual" function table. */
84 void (*destroy) (struct pf_map *pfm); /* Destructor. */
85 int (*get_move_cost) (struct pf_map *pfm, struct tile *ptile);
86 struct pf_path * (*get_path) (struct pf_map *pfm, struct tile *ptile);
87 bool (*get_position) (struct pf_map *pfm, struct tile *ptile,
88 struct pf_position *pos);
89 bool (*iterate) (struct pf_map *pfm);
90
91 /* Private data. */
92 struct tile *tile; /* The current position (aka iterator). */
93 struct pf_parameter params; /* Initial parameters. */
94};
95
96/* Down-cast macro. */
97#define PF_MAP(pfm) ((struct pf_map *) (pfm))
98
99/* ========================== Common functions =========================== */
100
101/************************************************************************/
109static inline int pf_moves_left_initially(const struct pf_parameter *param)
110{
111 return (param->moves_left_initially
112 + (param->fuel_left_initially - 1) * param->move_rate);
113}
114
115/************************************************************************/
123static inline int pf_move_rate(const struct pf_parameter *param)
124{
125 return param->move_rate * param->fuel;
126}
127
128/************************************************************************/
133static inline int pf_turns(const struct pf_parameter *param, int cost)
134{
135 /* Negative cost can happen when a unit initially has more MP than its
136 * move-rate (due to wonders transfer etc). Although this may be a bug,
137 * we'd better be ready.
138 *
139 * Note that cost == 0 corresponds to the current turn with full MP. */
140 if (param->fuel_left_initially < param->fuel) {
141 cost -= (param->fuel - param->fuel_left_initially) * param->move_rate;
142 }
143 if (cost <= 0) {
144 return 0;
145 } else if (param->move_rate <= 0) {
146 return FC_INFINITY; /* This unit cannot move by itself. */
147 } else {
148 return cost / param->move_rate;
149 }
150}
151
152/************************************************************************/
155static inline int pf_moves_left(const struct pf_parameter *param, int cost)
156{
157 int move_rate = pf_move_rate(param);
158
159 /* Cost may be negative; see pf_turns(). */
160 if (cost <= 0) {
161 return move_rate - cost;
162 } else if (move_rate <= 0) {
163 return 0; /* This unit never have moves left. */
164 } else {
165 return move_rate - (cost % move_rate);
166 }
167}
168
169/************************************************************************/
172static inline int pf_total_CC(const struct pf_parameter *param,
173 unsigned cost, unsigned extra)
174{
175 return PF_TURN_FACTOR * cost + extra * pf_move_rate(param);
176}
177
178/************************************************************************/
184static inline void pf_finalize_position(const struct pf_parameter *param,
185 struct pf_position *pos)
186{
187 int move_rate = param->move_rate;
188
189 if (0 < move_rate) {
190 pos->moves_left %= move_rate;
191 }
192}
193
194static struct pf_path *
195pf_path_new_to_start_tile(const struct pf_parameter *param);
197 const struct pf_parameter *param);
198
199
200/* ================ Specific pf_normal_* mode structures ================= */
201
202/* Normal path-finding maps are used for most of units with standard rules.
203 * See what units make pf_map_new() to pick danger or fuel maps instead. */
204
205/* Node definition. Note we try to have the smallest data as possible. */
207 /* Note that 'short' here would be followed with padding anyway,
208 * for alignment reasons, */
209 signed int cost; /* total_MC. 'cost' may be negative, see comment in
210 * pf_turns(). */
211 unsigned extra_cost; /* total_EC. Can be huge, (higher than 'cost'). */
212 unsigned dir_to_here : 4; /* Direction from which we came. It's
213 * an 'enum direction8' including
214 * possibility of direction8_invalid (so we need
215 * 4 bits) */
216 unsigned status : 3; /* 'enum pf_node_status' really. */
217
218 /* Cached values */
219 unsigned move_scope : 3; /* 'enum pf_move_scope really. */
220 unsigned action : 2; /* 'enum pf_action really. */
221 unsigned node_known_type : 2; /* 'enum known_type' really. */
222 unsigned behavior : 2; /* 'enum tile_behavior' really. */
223 unsigned zoc_number : 2; /* 'enum pf_zoc_type' really. */
224 unsigned short extra_tile; /* EC */
225};
226
227/* Derived structure of struct pf_map. */
229 struct pf_map base_map; /* Base structure, must be the first! */
230
231 struct map_index_pq *queue; /* Queue of nodes we have reached but not
232 * processed yet (NS_NEW), sorted by their
233 * total_CC. */
234 struct pf_normal_node *lattice; /* Lattice of nodes. */
235};
236
237/* Up-cast macro. */
238#ifdef PF_DEBUG
239static inline struct pf_normal_map *
240pf_normal_map_check(struct pf_map *pfm, const char *file,
241 const char *function, int line)
242{
244 pfm != nullptr && PF_NORMAL == pfm->mode,
245 return nullptr, "Wrong pf_map to pf_normal_map conversion.");
246 return (struct pf_normal_map *) pfm;
247}
248#define PF_NORMAL_MAP(pfm) \
249 pf_normal_map_check(pfm, __FILE__, __FUNCTION__, __FC_LINE__)
250#else
251#define PF_NORMAL_MAP(pfm) ((struct pf_normal_map *) (pfm))
252#endif /* PF_DEBUG */
253
254/* ================ Specific pf_normal_* mode functions ================= */
255
256/************************************************************************/
261static inline bool pf_normal_node_init(struct pf_normal_map *pfnm,
262 struct pf_normal_node *node,
263 struct tile *ptile,
265{
266 const struct pf_parameter *params = pf_map_parameter(PF_MAP(pfnm));
267 enum known_type node_known_type;
268 enum pf_action action;
269
270#ifdef PF_DEBUG
271 fc_assert(NS_UNINIT == node->status);
272 /* Else, not a critical problem, but waste of time. */
273#endif
274
275 node->status = NS_INIT;
276
277 /* Establish the "known" status of node. */
278 if (params->omniscience) {
279 node_known_type = TILE_KNOWN_SEEN;
280 } else {
281 node_known_type = tile_get_known(ptile, params->owner);
282 }
283 node->node_known_type = node_known_type;
284
285 /* Establish the tile behavior. */
286 if (params->get_TB != nullptr) {
287 node->behavior = params->get_TB(ptile, node_known_type, params);
288 if (TB_IGNORE == node->behavior && params->start_tile != ptile) {
289 return FALSE;
290 }
291#ifdef ZERO_VARIABLES_FOR_SEARCHING
292 } else {
293 /* The default. */
294 node->behavior = TB_NORMAL;
295#endif
296 }
297
298 if (TILE_UNKNOWN != node_known_type) {
299 bool can_disembark;
300
301 /* Test if we can invade tile. */
302 if (!utype_has_flag(params->utype, UTYF_CIVILIAN)
303 && !player_can_invade_tile(params->owner, ptile)) {
304 /* Maybe overwrite node behavior. */
305 if (params->start_tile != ptile) {
306 node->behavior = TB_IGNORE;
307 return FALSE;
308 } else if (TB_NORMAL == node->behavior) {
309 node->behavior = TB_IGNORE;
310 }
311 }
312
313 /* Test the possibility to perform an action. */
314 if (params->get_action != nullptr) {
315 action = params->get_action(ptile, node_known_type, params);
317 /* Maybe overwrite node behavior. */
318 if (params->start_tile != ptile) {
319 node->behavior = TB_IGNORE;
320 return FALSE;
321 } else if (TB_NORMAL == node->behavior) {
322 node->behavior = TB_IGNORE;
323 }
325 } else if (PF_ACTION_NONE != action
326 && TB_DONT_LEAVE != node->behavior) {
327 /* Overwrite node behavior. */
328 node->behavior = TB_DONT_LEAVE;
329 }
330 node->action = action;
331#ifdef ZERO_VARIABLES_FOR_SEARCHING
332 } else {
333 /* Nodes are allocated by fc_calloc(), so should be already set to
334 * 0. */
335 node->action = PF_ACTION_NONE;
336#endif
337 }
338
339 /* Test the possibility to move from/to 'ptile'. */
340 node->move_scope = params->get_move_scope(ptile, &can_disembark,
341 previous_scope, params);
342 if (PF_MS_NONE == node->move_scope
343 && PF_ACTION_NONE == node->action
344 && params->ignore_none_scopes) {
345 /* Maybe overwrite node behavior. */
346 if (params->start_tile != ptile) {
347 node->behavior = TB_IGNORE;
348 return FALSE;
349 } else if (TB_NORMAL == node->behavior) {
350 node->behavior = TB_IGNORE;
351 }
352 } else if (PF_MS_TRANSPORT == node->move_scope
353 && !can_disembark
354 && (params->start_tile != ptile
355 || params->transported_by_initially == nullptr)) {
356 /* Overwrite node behavior. */
357 node->behavior = TB_DONT_LEAVE;
358 }
359
360 /* ZOC_MINE means can move unrestricted from/into it, ZOC_ALLIED means
361 * can move unrestricted into it, but not necessarily from it. */
362 if (params->get_zoc != nullptr
363 && tile_city(ptile) == nullptr
365 && !params->get_zoc(params->owner, ptile, params->map)) {
366 node->zoc_number = (0 < unit_list_size(ptile->units)
367 ? ZOC_ALLIED : ZOC_NO);
368#ifdef ZERO_VARIABLES_FOR_SEARCHING
369 } else {
370 /* Nodes are allocated by fc_calloc(), so should be already set to
371 * 0. */
372 node->zoc_number = ZOC_MINE;
373#endif
374 }
375 } else {
376 node->move_scope = PF_MS_NATIVE;
377#ifdef ZERO_VARIABLES_FOR_SEARCHING
378 /* Nodes are allocated by fc_calloc(), so should be already set to 0. */
379 node->action = PF_ACTION_NONE;
380 node->zoc_number = ZOC_MINE;
381#endif
382 }
383
384 /* Evaluate the extra cost of the destination */
385 if (params->get_EC != nullptr) {
386 node->extra_tile = params->get_EC(ptile, node_known_type, params);
387#ifdef ZERO_VARIABLES_FOR_SEARCHING
388 } else {
389 /* Nodes are allocated by fc_calloc(), so should be already set to 0. */
390 node->extra_tile = 0;
391#endif
392 }
393
394 return TRUE;
395}
396
397/************************************************************************/
402 struct tile *ptile,
403 struct pf_position *pos)
404{
405 int tindex = tile_index(ptile);
406 struct pf_normal_node *node = pfnm->lattice + tindex;
407 const struct pf_parameter *params = pf_map_parameter(PF_MAP(pfnm));
408
409#ifdef PF_DEBUG
411 "Unreached destination (%d, %d).", TILE_XY(ptile));
412#endif /* PF_DEBUG */
413
414 pos->tile = ptile;
415 pos->total_EC = node->extra_cost;
416 pos->total_MC = (node->cost - pf_move_rate(params)
417 + pf_moves_left_initially(params));
418 pos->turn = pf_turns(params, node->cost);
419 pos->moves_left = pf_moves_left(params, node->cost);
420#ifdef PF_DEBUG
421 fc_assert(params->fuel == 1);
422 fc_assert(params->fuel_left_initially == 1);
423#endif /* PF_DEBUG */
424 pos->fuel_left = 1;
425 pos->dir_to_here = node->dir_to_here;
426 pos->dir_to_next_pos = direction8_invalid(); /* This field does not apply. */
427
428 if (node->cost > 0) {
429 pf_finalize_position(params, pos);
430 }
431}
432
433/************************************************************************/
437static struct pf_path *
439 struct tile *dest_tile)
440{
441 struct pf_normal_node *node = pfnm->lattice + tile_index(dest_tile);
442 const struct pf_parameter *params = pf_map_parameter(PF_MAP(pfnm));
444 struct pf_path *path;
445 struct tile *ptile;
446 int i;
447
448#ifdef PF_DEBUG
449 fc_assert_ret_val_msg(NS_PROCESSED == node->status, nullptr,
450 "Unreached destination (%d, %d).",
451 TILE_XY(dest_tile));
452#endif /* PF_DEBUG */
453
454 ptile = dest_tile;
455 path = fc_malloc(sizeof(*path));
456
457 /* 1: Count the number of steps to get here.
458 * To do it, backtrack until we hit the starting point */
459 for (i = 0; ; i++) {
460 if (ptile == params->start_tile) {
461 /* Ah-ha, reached the starting point! */
462 break;
463 }
464
465 ptile = mapstep(params->map, ptile, DIR_REVERSE(node->dir_to_here));
466 node = pfnm->lattice + tile_index(ptile);
467 }
468
469 /* 2: Allocate the memory */
470 path->length = i + 1;
471 path->positions = fc_malloc((i + 1) * sizeof(*(path->positions)));
472
473 /* 3: Backtrack again and fill the positions this time */
474 ptile = dest_tile;
475 node = pfnm->lattice + tile_index(ptile);
476
477 for (; i >= 0; i--) {
479 /* fill_position doesn't set direction */
481
482 dir_next = node->dir_to_here;
483
484 if (i > 0) {
485 /* Step further back, if we haven't finished yet */
486 ptile = mapstep(params->map, ptile, DIR_REVERSE(dir_next));
487 node = pfnm->lattice + tile_index(ptile);
488 }
489 }
490
491 return path;
492}
493
494/************************************************************************/
497static int pf_normal_map_adjust_cost(int cost, int moves_left)
498{
499 return MIN(cost, moves_left);
500}
501
502/************************************************************************/
519static bool pf_jumbo_map_iterate(struct pf_map *pfm)
520{
522 struct tile *tile = pfm->tile;
523 int tindex = tile_index(tile);
524 struct pf_normal_node *node = pfnm->lattice + tindex;
525 const struct pf_parameter *params = pf_map_parameter(pfm);
526
527 /* Processing Stage */
528
529 /* The previous position is defined by 'tile' (tile pointer), 'node'
530 * (the data of the tile for the pf_map), and index (the index of the
531 * position in the Freeciv map). */
532
533 adjc_dir_iterate(params->map, tile, tile1, dir) {
534 /* Calculate the cost of every adjacent position and set them in the
535 * priority queue for next call to pf_jumbo_map_iterate(). */
536 int tindex1 = tile_index(tile1);
537 struct pf_normal_node *node1 = pfnm->lattice + tindex1;
538 int priority;
539 unsigned cost1;
540 unsigned extra_cost1;
541
542 /* As for the previous position, 'tile1', 'node1' and 'tindex1' are
543 * defining the adjacent position. */
544
545 if (node1->status == NS_PROCESSED) {
546 /* This gives 15% speedup */
547 continue;
548 }
549
550 if (NS_UNINIT == node1->status) {
551 /* Set cost as impossible for initializing, params->get_costs(), will
552 * overwrite with the right value. */
554 extra_cost1 = 0;
555 } else {
556 cost1 = node1->cost;
557 extra_cost1 = node1->extra_cost;
558 }
559
560 /* User-supplied callback 'get_costs' takes care of everything (ZOC,
561 * known, costs etc). See explanations in "path_finding.h". */
562 priority = params->get_costs(tile, dir, tile1, node->cost,
563 node->extra_cost, &cost1,
564 &extra_cost1, params);
565 if (priority >= 0) {
566 /* We found a better route to 'tile1', record it (the costs are
567 * recorded already). Node status step A. to B. */
568 if (NS_NEW == node1->status) {
570 } else {
572 }
573 node1->cost = cost1;
574 node1->extra_cost = extra_cost1;
575 node1->status = NS_NEW;
576 node1->dir_to_here = dir;
577 }
579
580 /* Get the next node (the index with the highest priority). */
581 if (!map_index_pq_remove(pfnm->queue, &tindex)) {
582 /* No more indexes in the priority queue, iteration end. */
583 return FALSE;
584 }
585
586#ifdef PF_DEBUG
587 fc_assert(NS_NEW == pfnm->lattice[tindex].status);
588#endif
589
590 /* Change the pf_map iterator. Node status step B. to C. */
591 pfm->tile = index_to_tile(params->map, tindex);
592 pfnm->lattice[tindex].status = NS_PROCESSED;
593
594 return TRUE;
595}
596
597/************************************************************************/
613static bool pf_normal_map_iterate(struct pf_map *pfm)
614{
616 struct tile *tile = pfm->tile;
617 int tindex = tile_index(tile);
618 struct pf_normal_node *node = pfnm->lattice + tindex;
619 const struct pf_parameter *params = pf_map_parameter(pfm);
620 int cost_of_path;
621 enum pf_move_scope scope = node->move_scope;
622
623 /* There is no exit from DONT_LEAVE tiles! */
624 if (node->behavior != TB_DONT_LEAVE
625 && scope != PF_MS_NONE
626 && (params->move_rate > 0 || node->cost < 0)) {
627 /* Processing Stage */
628
629 /* The previous position is defined by 'tile' (tile pointer), 'node'
630 * (the data of the tile for the pf_map), and index (the index of the
631 * position in the Freeciv map). */
632
633 adjc_dir_iterate(params->map, tile, tile1, dir) {
634 /* Calculate the cost of every adjacent position and set them in the
635 * priority queue for next call to pf_normal_map_iterate(). */
636 int tindex1 = tile_index(tile1);
637 struct pf_normal_node *node1 = pfnm->lattice + tindex1;
638 int cost;
639 unsigned extra = 0;
640
641 /* As for the previous position, 'tile1', 'node1' and 'tindex1' are
642 * defining the adjacent position. */
643
644 if (node1->status == NS_PROCESSED) {
645 /* This gives 15% speedup. Node status already at step D. */
646 continue;
647 }
648
649 /* Initialise target tile if necessary. */
650 if (node1->status == NS_UNINIT) {
651 /* Only initialize once. See comment for pf_normal_node_init().
652 * Node status step A. to B. */
654 continue;
655 }
656 } else if (TB_IGNORE == node1->behavior) {
657 /* We cannot enter this tile at all! */
658 continue;
659 }
660
661 /* Is the move ZOC-ok? */
662 if (node->zoc_number != ZOC_MINE && node1->zoc_number == ZOC_NO) {
663 continue;
664 }
665
666 /* Evaluate the cost of the move. */
667 if (PF_ACTION_NONE != node1->action) {
668 if (params->is_action_possible != nullptr
669 && !params->is_action_possible(tile, scope, tile1, node1->action,
670 params)) {
671 continue;
672 }
673 /* action move cost depends on action and unit type. */
674 if (node1->action == PF_ACTION_ATTACK
677 || utype_can_do_action(params->utype,
679 /* Assume that the attack will be a suicide attack even if a
680 * regular attack may be legal. */
681 cost = params->move_rate;
682 } else {
684 }
685 } else if (node1->node_known_type == TILE_UNKNOWN) {
686 cost = params->utype->unknown_move_cost;
687 } else {
688 cost = params->get_MC(tile, scope, tile1, node1->move_scope, params);
689 }
690 if (cost < 0) {
691 /* e.g. PF_IMPOSSIBLE_MC */
692 continue;
693 }
695 pf_moves_left(params, node->cost));
696
697 /* Total cost at tile1. Cost may be negative; see pf_turns(). */
698 cost += node->cost;
699
700 /* Evaluate the extra cost if it's relevant */
701 if (params->get_EC != nullptr) {
702 extra = node->extra_cost;
703 /* Add the cached value */
704 extra += node1->extra_tile;
705 }
706
707 /* Update costs. */
708 cost_of_path = pf_total_CC(params, cost, extra);
709
710 if (NS_INIT == node1->status) {
711 /* We are reaching this node for the first time. */
712 node1->status = NS_NEW;
713 node1->extra_cost = extra;
714 node1->cost = cost;
715 node1->dir_to_here = dir;
716 /* As we prefer lower costs, let's reverse the cost of the path. */
718 } else if (cost_of_path < pf_total_CC(params, node1->cost,
719 node1->extra_cost)) {
720 /* We found a better route to 'tile1'. Let's register 'tindex1' to
721 * the priority queue. Node status step B. to C. */
722 node1->status = NS_NEW;
723 node1->extra_cost = extra;
724 node1->cost = cost;
725 node1->dir_to_here = dir;
726 /* As we prefer lower costs, let's reverse the cost of the path. */
728 }
730 }
731
732 /* Get the next node (the index with the highest priority). */
733 if (!map_index_pq_remove(pfnm->queue, &tindex)) {
734 /* No more indexes in the priority queue, iteration end. */
735 return FALSE;
736 }
737
738#ifdef PF_DEBUG
739 fc_assert(NS_NEW == pfnm->lattice[tindex].status);
740#endif
741
742 /* Change the pf_map iterator. Node status step C. to D. */
743 pfm->tile = index_to_tile(params->map, tindex);
744 pfnm->lattice[tindex].status = NS_PROCESSED;
745
746 return TRUE;
747}
748
749/************************************************************************/
753 struct tile *ptile)
754{
755 struct pf_map *pfm = PF_MAP(pfnm);
756 struct pf_normal_node *node = pfnm->lattice + tile_index(ptile);
757
758 if (pf_map_parameter(pfm)->get_costs == nullptr) {
759 /* Start position is handled in every function calling this function. */
760 if (NS_UNINIT == node->status) {
761 /* Initialize the node, for doing the following tests. */
762 if (!pf_normal_node_init(pfnm, node, ptile, PF_MS_NONE)) {
763 return FALSE;
764 }
765 } else if (TB_IGNORE == node->behavior) {
766 /* Simpliciation: if we cannot enter this node at all, don't iterate
767 * the whole map. */
768 return FALSE;
769 }
770 } /* Else, this is a jumbo map, not dealing with normal nodes. */
771
772 while (NS_PROCESSED != node->status) {
773 if (!pf_map_iterate(pfm)) {
774 /* All reachable destination have been iterated, 'ptile' is
775 * unreachable. */
776 return FALSE;
777 }
778 }
779
780 return TRUE;
781}
782
783/************************************************************************/
788static int pf_normal_map_move_cost(struct pf_map *pfm, struct tile *ptile)
789{
791
792 if (ptile == pfm->params.start_tile) {
793 return 0;
794 } else if (pf_normal_map_iterate_until(pfnm, ptile)) {
795 return (pfnm->lattice[tile_index(ptile)].cost
798 } else {
799 return PF_IMPOSSIBLE_MC;
800 }
801}
802
803/************************************************************************/
807static struct pf_path *pf_normal_map_path(struct pf_map *pfm,
808 struct tile *ptile)
809{
811
812 if (ptile == pfm->params.start_tile) {
814 } else if (pf_normal_map_iterate_until(pfnm, ptile)) {
815 return pf_normal_map_construct_path(pfnm, ptile);
816 } else {
817 return nullptr;
818 }
819}
820
821/************************************************************************/
826static bool pf_normal_map_position(struct pf_map *pfm, struct tile *ptile,
827 struct pf_position *pos)
828{
830
831 if (ptile == pfm->params.start_tile) {
833 return TRUE;
834 } else if (pf_normal_map_iterate_until(pfnm, ptile)) {
836 return TRUE;
837 } else {
838 return FALSE;
839 }
840}
841
842/************************************************************************/
845static void pf_normal_map_destroy(struct pf_map *pfm)
846{
848
849 free(pfnm->lattice);
851 free(pfnm);
852}
853
854/************************************************************************/
857static struct pf_map *pf_normal_map_new(const struct pf_parameter *parameter)
858{
859 struct pf_normal_map *pfnm;
860 struct pf_map *base_map;
861 struct pf_parameter *params;
862 struct pf_normal_node *node;
863
864 pfnm = fc_malloc(sizeof(*pfnm));
865 base_map = &pfnm->base_map;
866 params = &base_map->params;
867#ifdef PF_DEBUG
868 /* Set the mode, used for cast check. */
869 base_map->mode = PF_NORMAL;
870#endif /* PF_DEBUG */
871
872 /* Allocate the map. */
873 pfnm->lattice = fc_calloc(MAP_INDEX_SIZE, sizeof(struct pf_normal_node));
875
876 if (parameter->get_costs == nullptr) {
877 /* 'get_MC' callback must be set. */
878 fc_assert_ret_val(parameter->get_MC != nullptr, nullptr);
879
880 /* 'get_move_scope' callback must be set. */
881 fc_assert_ret_val(parameter->get_move_scope != nullptr, nullptr);
882 }
883
884 /* Copy parameters. */
885 *params = *parameter;
886
887 /* Initialize virtual function table. */
888 base_map->destroy = pf_normal_map_destroy;
890 base_map->get_path = pf_normal_map_path;
892 if (params->get_costs != nullptr) {
893 base_map->iterate = pf_jumbo_map_iterate;
894 } else {
895 base_map->iterate = pf_normal_map_iterate;
896 }
897
898 /* Initialise starting node. */
899 node = pfnm->lattice + tile_index(params->start_tile);
900 if (params->get_costs == nullptr) {
901 if (!pf_normal_node_init(pfnm, node, params->start_tile, PF_MS_NONE)) {
902 /* Always fails. */
904 PF_MS_NONE));
905 }
906
907 if (params->transported_by_initially != nullptr) {
908 /* Overwrite. It is safe because we cannot return to start tile with
909 * pf_normal_map. */
911 if (!utype_can_freely_unload(params->utype,
913 && tile_city(params->start_tile) == nullptr
915 params->transported_by_initially)) {
916 /* Cannot disembark, don't leave transporter. */
917 node->behavior = TB_DONT_LEAVE;
918 }
919 }
920 }
921
922 /* Initialise the iterator. */
923 base_map->tile = params->start_tile;
924
925 /* This makes calculations of turn/moves_left more convenient, but we
926 * need to subtract this value before we return cost to the user. Note
927 * that cost may be negative if moves_left_initially > move_rate
928 * (see pf_turns()). */
929 node->cost = pf_move_rate(params) - pf_moves_left_initially(params);
930 node->extra_cost = 0;
932 node->status = NS_PROCESSED;
933
934 return PF_MAP(pfnm);
935}
936
937
938/* ================ Specific pf_danger_* mode structures ================= */
939
940/* Danger path-finding maps are used for units which can cross some areas
941 * but not ending their turn there. It used to be used for triremes notably.
942 * But since Freeciv 2.2, units with the "CoastStrict" flag just have
943 * restricted moves, then it is not use anymore. */
944
945/* Node definition. Note we try to have the smallest data as possible. */
947 /* Note that 'short' here would be followed with padding anyway,
948 * for alignment reasons, */
949 signed int cost; /* total_MC. 'cost' may be negative, see comment in
950 * pf_turns(). */
951 unsigned extra_cost; /* total_EC. Can be huge, (higher than 'cost'). */
952 unsigned dir_to_here : 4; /* Direction from which we came. It's
953 * an 'enum direction8' including
954 * possibility of direction8_invalid (so we need
955 * 4 bits) */
956 unsigned status : 3; /* 'enum pf_node_status' really. */
957
958 /* Cached values */
959 unsigned move_scope : 3; /* 'enum pf_move_scope really. */
960 unsigned action : 2; /* 'enum pf_action really. */
961 unsigned node_known_type : 2; /* 'enum known_type' really. */
962 unsigned behavior : 2; /* 'enum tile_behavior' really. */
963 unsigned zoc_number : 2; /* 'enum pf_zoc_type' really. */
964 bool is_dangerous : 1; /* Whether we cannot end the turn there. */
965 bool waited : 1; /* TRUE if waited to get there. */
966 unsigned short extra_tile; /* EC */
967
968 /* Segment leading across the danger area back to the nearest safe node:
969 * need to remember costs and stuff. */
971 signed short cost; /* See comment above. */
972 unsigned extra_cost; /* See comment above. */
973 signed dir_to_here : 4; /* See comment above. */
975};
976
977/* Derived structure of struct pf_map. */
979 struct pf_map base_map; /* Base structure, must be the first! */
980
981 struct map_index_pq *queue; /* Queue of nodes we have reached but not
982 * processed yet (NS_NEW and NS_WAITING),
983 * sorted by their total_CC. */
984 struct map_index_pq *danger_queue; /* Dangerous positions. */
985 struct pf_danger_node *lattice; /* Lattice of nodes. */
986};
987
988/* Up-cast macro. */
989#ifdef PF_DEBUG
990static inline struct pf_danger_map *
991pf_danger_map_check(struct pf_map *pfm, const char *file,
992 const char *function, int line)
993{
995 pfm != nullptr && PF_DANGER == pfm->mode,
996 return nullptr, "Wrong pf_map to pf_danger_map conversion.");
997 return (struct pf_danger_map *) pfm;
998}
999#define PF_DANGER_MAP(pfm) \
1000 pf_danger_map_check(pfm, __FILE__, __FUNCTION__, __FC_LINE__)
1001#else
1002#define PF_DANGER_MAP(pfm) ((struct pf_danger_map *) (pfm))
1003#endif /* PF_DEBUG */
1004
1005/* =============== Specific pf_danger_* mode functions ================== */
1006
1007/************************************************************************/
1012static inline bool pf_danger_node_init(struct pf_danger_map *pfdm,
1013 struct pf_danger_node *node,
1014 struct tile *ptile,
1016{
1017 const struct pf_parameter *params = pf_map_parameter(PF_MAP(pfdm));
1018 enum known_type node_known_type;
1019 enum pf_action action;
1020
1021#ifdef PF_DEBUG
1022 fc_assert(NS_UNINIT == node->status);
1023 /* Else, not a critical problem, but waste of time. */
1024#endif
1025
1026 node->status = NS_INIT;
1027
1028 /* Establish the "known" status of node. */
1029 if (params->omniscience) {
1030 node_known_type = TILE_KNOWN_SEEN;
1031 } else {
1032 node_known_type = tile_get_known(ptile, params->owner);
1033 }
1034 node->node_known_type = node_known_type;
1035
1036 /* Establish the tile behavior. */
1037 if (params->get_TB != nullptr) {
1038 node->behavior = params->get_TB(ptile, node_known_type, params);
1039 if (TB_IGNORE == node->behavior && params->start_tile != ptile) {
1040 return FALSE;
1041 }
1042#ifdef ZERO_VARIABLES_FOR_SEARCHING
1043 } else {
1044 /* The default. */
1045 node->behavior = TB_NORMAL;
1046#endif
1047 }
1048
1049 if (TILE_UNKNOWN != node_known_type) {
1050 bool can_disembark;
1051
1052 /* Test if we can invade tile. */
1053 if (!utype_has_flag(params->utype, UTYF_CIVILIAN)
1054 && !player_can_invade_tile(params->owner, ptile)) {
1055 /* Maybe overwrite node behavior. */
1056 if (params->start_tile != ptile) {
1057 node->behavior = TB_IGNORE;
1058 return FALSE;
1059 } else if (TB_NORMAL == node->behavior) {
1060 node->behavior = TB_IGNORE;
1061 }
1062 }
1063
1064 /* Test the possibility to perform an action. */
1065 if (params->get_action != nullptr) {
1066 action = params->get_action(ptile, node_known_type, params);
1068 /* Maybe overwrite node behavior. */
1069 if (params->start_tile != ptile) {
1070 node->behavior = TB_IGNORE;
1071 return FALSE;
1072 } else if (TB_NORMAL == node->behavior) {
1073 node->behavior = TB_IGNORE;
1074 }
1076 } else if (PF_ACTION_NONE != action
1077 && TB_DONT_LEAVE != node->behavior) {
1078 /* Overwrite node behavior. */
1079 node->behavior = TB_DONT_LEAVE;
1080 }
1081 node->action = action;
1082#ifdef ZERO_VARIABLES_FOR_SEARCHING
1083 } else {
1084 /* Nodes are allocated by fc_calloc(), so should be already set to
1085 * 0. */
1086 node->action = PF_ACTION_NONE;
1087#endif
1088 }
1089
1090 /* Test the possibility to move from/to 'ptile'. */
1091 node->move_scope = params->get_move_scope(ptile, &can_disembark,
1092 previous_scope, params);
1093 if (PF_MS_NONE == node->move_scope
1094 && PF_ACTION_NONE == node->action
1095 && params->ignore_none_scopes) {
1096 /* Maybe overwrite node behavior. */
1097 if (params->start_tile != ptile) {
1098 node->behavior = TB_IGNORE;
1099 return FALSE;
1100 } else if (TB_NORMAL == node->behavior) {
1101 node->behavior = TB_IGNORE;
1102 }
1103 } else if (PF_MS_TRANSPORT == node->move_scope
1104 && !can_disembark
1105 && (params->start_tile != ptile
1106 || params->transported_by_initially == nullptr)) {
1107 /* Overwrite node behavior. */
1108 node->behavior = TB_DONT_LEAVE;
1109 }
1110
1111 /* ZOC_MINE means can move unrestricted from/into it, ZOC_ALLIED means
1112 * can move unrestricted into it, but not necessarily from it. */
1113 if (params->get_zoc != nullptr
1114 && tile_city(ptile) == nullptr
1116 && !params->get_zoc(params->owner, ptile, params->map)) {
1117 node->zoc_number = (0 < unit_list_size(ptile->units)
1118 ? ZOC_ALLIED : ZOC_NO);
1119#ifdef ZERO_VARIABLES_FOR_SEARCHING
1120 } else {
1121 /* Nodes are allocated by fc_calloc(), so should be already set to
1122 * 0. */
1123 node->zoc_number = ZOC_MINE;
1124#endif
1125 }
1126 } else {
1127 node->move_scope = PF_MS_NATIVE;
1128#ifdef ZERO_VARIABLES_FOR_SEARCHING
1129 /* Nodes are allocated by fc_calloc(), so should be already set to 0. */
1130 node->action = PF_ACTION_NONE;
1131 node->zoc_number = ZOC_MINE;
1132#endif
1133 }
1134
1135 /* Evaluate the extra cost of the destination. */
1136 if (params->get_EC != nullptr) {
1137 node->extra_tile = params->get_EC(ptile, node_known_type, params);
1138#ifdef ZERO_VARIABLES_FOR_SEARCHING
1139 } else {
1140 /* Nodes are allocated by fc_calloc(), so should be already set to 0. */
1141 node->extra_tile = 0;
1142#endif
1143 }
1144
1145#ifdef ZERO_VARIABLES_FOR_SEARCHING
1146 /* Nodes are allocated by fc_calloc(), so should be already set to
1147 * FALSE. */
1148 node->waited = FALSE;
1149#endif
1150
1151 node->is_dangerous =
1152 params->is_pos_dangerous(ptile, node_known_type, params);
1153
1154 return TRUE;
1155}
1156
1157/************************************************************************/
1162 struct tile *ptile,
1163 struct pf_position *pos)
1164{
1165 int tindex = tile_index(ptile);
1166 struct pf_danger_node *node = pfdm->lattice + tindex;
1167 const struct pf_parameter *params = pf_map_parameter(PF_MAP(pfdm));
1168
1169#ifdef PF_DEBUG
1171 || NS_WAITING == node->status,
1172 "Unreached destination (%d, %d).", TILE_XY(ptile));
1173#endif /* PF_DEBUG */
1174
1175 pos->tile = ptile;
1176 pos->total_EC = node->extra_cost;
1177 pos->total_MC = (node->cost - pf_move_rate(params)
1178 + pf_moves_left_initially(params));
1179 pos->turn = pf_turns(params, node->cost);
1180 pos->moves_left = pf_moves_left(params, node->cost);
1181#ifdef PF_DEBUG
1182 fc_assert(params->fuel == 1);
1183 fc_assert(params->fuel_left_initially == 1);
1184#endif /* PF_DEBUG */
1185 pos->fuel_left = 1;
1186 pos->dir_to_here = node->dir_to_here;
1187 pos->dir_to_next_pos = direction8_invalid(); /* This field does not apply. */
1188
1189 if (node->cost > 0) {
1190 pf_finalize_position(params, pos);
1191 }
1192}
1193
1194/************************************************************************/
1199static inline int
1201 int cost)
1202{
1203 int moves_left = pf_moves_left(param, cost);
1204
1205 if (moves_left < pf_move_rate(param)) {
1206 return cost + moves_left;
1207 } else {
1208 return cost;
1209 }
1210}
1211
1212/************************************************************************/
1216static struct pf_path *
1218 struct tile *ptile)
1219{
1220 struct pf_path *path = fc_malloc(sizeof(*path));
1222 struct pf_danger_pos *danger_seg = nullptr;
1223 bool waited = FALSE;
1224 struct pf_danger_node *node = pfdm->lattice + tile_index(ptile);
1225 unsigned length = 1;
1226 struct tile *iter_tile = ptile;
1227 const struct pf_parameter *params = pf_map_parameter(PF_MAP(pfdm));
1228 struct pf_position *pos;
1229 int i;
1230
1231#ifdef PF_DEBUG
1233 || NS_WAITING == node->status, nullptr,
1234 "Unreached destination (%d, %d).",
1235 TILE_XY(ptile));
1236#endif /* PF_DEBUG */
1237
1238 /* First iterate to find path length. */
1239 while (iter_tile != params->start_tile) {
1240 if (!node->is_dangerous && node->waited) {
1241 length += 2;
1242 } else {
1243 length++;
1244 }
1245
1246 if (!node->is_dangerous || !danger_seg) {
1247 /* We are in the normal node and dir_to_here field is valid */
1248 dir_next = node->dir_to_here;
1249 /* d_node->danger_segment is the indicator of what lies ahead
1250 * if it's not nullptr, we are entering a danger segment,
1251 * if it's nullptr, we are not on one so danger_seg should be nullptr. */
1252 danger_seg = node->danger_segment;
1253 } else {
1254 /* We are in a danger segment. */
1256 danger_seg++;
1257 }
1258
1259 /* Step backward. */
1261 node = pfdm->lattice + tile_index(iter_tile);
1262 }
1263
1264 /* Allocate memory for path. */
1265 path->positions = fc_malloc(length * sizeof(struct pf_position));
1266 path->length = length;
1267
1268 /* Reset variables for main iteration. */
1269 iter_tile = ptile;
1270 node = pfdm->lattice + tile_index(ptile);
1271 danger_seg = nullptr;
1272 waited = FALSE;
1273
1274 for (i = length - 1; i >= 0; i--) {
1275 bool old_waited = FALSE;
1276
1277 /* 1: Deal with waiting. */
1278 if (!node->is_dangerous) {
1279 if (waited) {
1280 /* Waited at _this_ tile, need to record it twice in the
1281 * path. Here we record our state _after_ waiting (e.g.
1282 * full move points). */
1283 pos = path->positions + i;
1284 pos->tile = iter_tile;
1285 pos->total_EC = node->extra_cost;
1286 pos->turn = pf_turns(params,
1288 pos->moves_left = params->move_rate;
1289 pos->fuel_left = params->fuel;
1290 pos->total_MC = ((pos->turn - 1) * params->move_rate
1291 + params->moves_left_initially);
1292 pos->dir_to_next_pos = dir_next;
1293 pf_finalize_position(params, pos);
1294 /* Set old_waited so that we record direction8_invalid() as a direction at
1295 * the step we were going to wait. */
1296 old_waited = TRUE;
1297 i--;
1298 }
1299 /* Update "waited" (node->waited means "waited to get here"). */
1300 waited = node->waited;
1301 }
1302
1303 /* 2: Fill the current position. */
1304 pos = path->positions + i;
1305 pos->tile = iter_tile;
1306 if (!node->is_dangerous || !danger_seg) {
1307 pos->total_MC = node->cost;
1308 pos->total_EC = node->extra_cost;
1309 } else {
1310 /* When on dangerous tiles, must have a valid danger segment. */
1311 fc_assert_ret_val(danger_seg != nullptr, nullptr);
1312 pos->total_MC = danger_seg->cost;
1313 pos->total_EC = danger_seg->extra_cost;
1314 }
1315 pos->turn = pf_turns(params, pos->total_MC);
1316 pos->moves_left = pf_moves_left(params, pos->total_MC);
1317#ifdef PF_DEBUG
1318 fc_assert(params->fuel == 1);
1319 fc_assert(params->fuel_left_initially == 1);
1320#endif /* PF_DEBUG */
1321 pos->fuel_left = 1;
1322 pos->total_MC -= (pf_move_rate(params)
1323 - pf_moves_left_initially(params));
1324 pos->dir_to_next_pos = (old_waited ? direction8_invalid() : dir_next);
1325 if (node->cost > 0) {
1326 pf_finalize_position(params, pos);
1327 }
1328
1329 /* 3: Check if we finished. */
1330 if (i == 0) {
1331 /* We should be back at the start now! */
1332 fc_assert_ret_val(iter_tile == params->start_tile, nullptr);
1333 return path;
1334 }
1335
1336 /* 4: Calculate the next direction. */
1337 if (!node->is_dangerous || !danger_seg) {
1338 /* We are in the normal node and dir_to_here field is valid. */
1339 dir_next = node->dir_to_here;
1340 /* d_node->danger_segment is the indicator of what lies ahead.
1341 * If it's not nullptr, we are entering a danger segment,
1342 * If it's nullptr, we are not on one so danger_seg should be nullptr. */
1343 danger_seg = node->danger_segment;
1344 } else {
1345 /* We are in a danger segment. */
1347 danger_seg++;
1348 }
1349
1350 /* 5: Step further back. */
1352 node = pfdm->lattice + tile_index(iter_tile);
1353 }
1354
1355 fc_assert_msg(FALSE, "Cannot get to the starting point!");
1356
1357 return nullptr;
1358}
1359
1360/************************************************************************/
1379 struct pf_danger_node *node1)
1380{
1381 struct tile *ptile = PF_MAP(pfdm)->tile;
1382 struct pf_danger_node *node = pfdm->lattice + tile_index(ptile);
1383 struct pf_danger_pos *pos;
1384 unsigned length = 0;
1385 unsigned i;
1386 const struct pf_parameter *params = pf_map_parameter(PF_MAP(pfdm));
1387
1388#ifdef PF_DEBUG
1389 if (node1->danger_segment != nullptr) {
1390 log_error("Possible memory leak in pf_danger_map_create_segment().");
1391 }
1392#endif /* PF_DEBUG */
1393
1394 /* First iteration for determining segment length */
1395 while (node->is_dangerous && direction8_is_valid(node->dir_to_here)) {
1396 length++;
1397 ptile = mapstep(params->map, ptile, DIR_REVERSE(node->dir_to_here));
1398 node = pfdm->lattice + tile_index(ptile);
1399 }
1400
1401 /* Allocate memory for segment */
1402 node1->danger_segment = fc_malloc(length * sizeof(struct pf_danger_pos));
1403
1404 /* Reset tile and node pointers for main iteration */
1405 ptile = PF_MAP(pfdm)->tile;
1406 node = pfdm->lattice + tile_index(ptile);
1407
1408 /* Now fill the positions */
1409 for (i = 0, pos = node1->danger_segment; i < length; i++, pos++) {
1410 /* Record the direction */
1411 pos->dir_to_here = node->dir_to_here;
1412 pos->cost = node->cost;
1413 pos->extra_cost = node->extra_cost;
1414 if (i == length - 1) {
1415 /* The last dangerous node contains "waiting" info */
1416 node1->waited = node->waited;
1417 }
1418
1419 /* Step further down the tree */
1420 ptile = mapstep(params->map, ptile, DIR_REVERSE(node->dir_to_here));
1421 node = pfdm->lattice + tile_index(ptile);
1422 }
1423
1424#ifdef PF_DEBUG
1425 /* Make sure we reached a safe node or the start point */
1427#endif
1428}
1429
1430/************************************************************************/
1433static inline int
1435 int cost, bool to_danger, int moves_left)
1436{
1437 int mr;
1438
1439 if (cost == PF_IMPOSSIBLE_MC) {
1440 return PF_IMPOSSIBLE_MC;
1441 }
1442
1443 mr = pf_move_rate(params);
1444 cost = MIN(cost, mr);
1445
1446 if (to_danger && cost >= moves_left) {
1447 /* We would have to end the turn on a dangerous tile! */
1448 return PF_IMPOSSIBLE_MC;
1449 } else {
1450 return MIN(cost, moves_left);
1451 }
1452}
1453
1454/************************************************************************/
1493{
1494 struct pf_danger_map *const pfdm = PF_DANGER_MAP(pfm);
1495 const struct pf_parameter *const params = pf_map_parameter(pfm);
1496 struct tile *tile = pfm->tile;
1497 int tindex = tile_index(tile);
1498 struct pf_danger_node *node = pfdm->lattice + tindex;
1499 enum pf_move_scope scope = node->move_scope;
1500
1501 /* The previous position is defined by 'tile' (tile pointer), 'node'
1502 * (the data of the tile for the pf_map), and index (the index of the
1503 * position in the Freeciv map). */
1504
1506 && params->transported_by_initially != nullptr) {
1507#ifdef PF_DEBUG
1508 fc_assert(tile == params->start_tile);
1509#endif
1511 if (!utype_can_freely_unload(params->utype,
1513 && tile_city(tile) == nullptr
1515 /* Cannot disembark, don't leave transporter. */
1516 node->behavior = TB_DONT_LEAVE;
1517 }
1518 }
1519
1520 for (;;) {
1521 /* There is no exit from DONT_LEAVE tiles! */
1522 if (node->behavior != TB_DONT_LEAVE
1523 && scope != PF_MS_NONE
1524 && (params->move_rate > 0 || node->cost < 0)) {
1525 /* Cost at tile but taking into account waiting. */
1526 int loc_cost;
1527 if (node->status != NS_WAITING) {
1528 loc_cost = node->cost;
1529 } else {
1530 /* We have waited, so we have full moves. */
1532 node->cost);
1533 }
1534
1535 adjc_dir_iterate(params->map, tile, tile1, dir) {
1536 /* Calculate the cost of every adjacent position and set them in
1537 * the priority queues for next call to pf_danger_map_iterate(). */
1538 int tindex1 = tile_index(tile1);
1539 struct pf_danger_node *node1 = pfdm->lattice + tindex1;
1540 int cost;
1541 int extra = 0;
1542
1543 /* As for the previous position, 'tile1', 'node1' and 'tindex1' are
1544 * defining the adjacent position. */
1545
1546 if (node1->status == NS_PROCESSED || node1->status == NS_WAITING) {
1547 /* This gives 15% speedup. Node status already at step D., E.
1548 * or F. */
1549 continue;
1550 }
1551
1552 /* Initialise target tile if necessary. */
1553 if (node1->status == NS_UNINIT) {
1554 /* Only initialize once. See comment for pf_danger_node_init().
1555 * Node status step A. to B. */
1557 continue;
1558 }
1559 } else if (TB_IGNORE == node1->behavior) {
1560 /* We cannot enter this tile at all! */
1561 continue;
1562 }
1563
1564 /* Is the move ZOC-ok? */
1565 if (node->zoc_number != ZOC_MINE && node1->zoc_number == ZOC_NO) {
1566 continue;
1567 }
1568
1569 /* Evaluate the cost of the move. */
1570 if (PF_ACTION_NONE != node1->action) {
1571 if (params->is_action_possible != nullptr
1572 && !params->is_action_possible(tile, scope, tile1,
1573 node1->action, params)) {
1574 continue;
1575 }
1576 /* action move cost depends on action and unit type. */
1577 if (node1->action == PF_ACTION_ATTACK
1578 && (utype_action_takes_all_mp(params->utype,
1580 || utype_can_do_action(params->utype,
1582 /* Assume that the attack will be a suicide attack even if a
1583 * regular attack may be legal. */
1584 cost = params->move_rate;
1585 } else {
1586 cost = SINGLE_MOVE;
1587 }
1588 } else if (node1->node_known_type == TILE_UNKNOWN) {
1589 cost = params->utype->unknown_move_cost;
1590 } else {
1591 cost = params->get_MC(tile, scope, tile1, node1->move_scope,
1592 params);
1593 }
1594 if (cost == PF_IMPOSSIBLE_MC) {
1595 continue;
1596 }
1597 cost = pf_danger_map_adjust_cost(params, cost, node1->is_dangerous,
1598 pf_moves_left(params, loc_cost));
1599
1600 if (cost == PF_IMPOSSIBLE_MC) {
1601 /* This move is deemed impossible. */
1602 continue;
1603 }
1604
1605 /* Total cost at 'tile1'. */
1606 cost += loc_cost;
1607
1608 /* Evaluate the extra cost of the destination, if it's relevant. */
1609 if (params->get_EC != nullptr) {
1610 extra = node1->extra_tile + node->extra_cost;
1611 }
1612
1613 /* Update costs and add to queue, if this is a better route
1614 * to 'tile1'. */
1615 if (!node1->is_dangerous) {
1616 int cost_of_path = pf_total_CC(params, cost, extra);
1617
1618 if (NS_INIT == node1->status
1619 || (cost_of_path < pf_total_CC(params, node1->cost,
1620 node1->extra_cost))) {
1621 /* We are reaching this node for the first time, or we found a
1622 * better route to 'tile1'. Let's register 'tindex1' to the
1623 * priority queue. Node status step B. to C. */
1624 node1->extra_cost = extra;
1625 node1->cost = cost;
1626 node1->dir_to_here = dir;
1627 if (node1->danger_segment != nullptr) {
1628 /* Clear the previously recorded path back. */
1629 free(node1->danger_segment);
1630 node1->danger_segment = nullptr;
1631 }
1632 if (node->is_dangerous) {
1633 /* We came from a dangerous tile. So we need to record the
1634 * path we came from until the previous safe position is
1635 * found. See comment for pf_danger_map_create_segment(). */
1637 } else {
1638 /* Maybe clear previously "waited" status of the node. */
1639 node1->waited = FALSE;
1640 }
1641 if (NS_INIT == node1->status) {
1642 node1->status = NS_NEW;
1644 } else {
1645#ifdef PF_DEBUG
1646 fc_assert(NS_NEW == node1->status);
1647#endif
1649 }
1650 }
1651 } else {
1652 /* The procedure is slightly different for dangerous nodes.
1653 * We will update costs if:
1654 * 1. we are here for the first time;
1655 * 2. we can possibly go further across dangerous area; or
1656 * 3. we can have lower extra and will not overwrite anything
1657 * useful. Node status step B. to C. */
1658 if (node1->status == NS_INIT) {
1659 /* case 1. */
1660 node1->extra_cost = extra;
1661 node1->cost = cost;
1662 node1->dir_to_here = dir;
1663 node1->status = NS_NEW;
1664 node1->waited = (node->status == NS_WAITING);
1665 /* Extra costs of all nodes in danger_queue are equal! */
1666 map_index_pq_insert(pfdm->danger_queue, tindex1, -cost);
1667 } else if ((pf_moves_left(params, cost)
1668 > pf_moves_left(params, node1->cost))
1669 || (node1->status == NS_PROCESSED
1670 && (pf_total_CC(params, cost, extra)
1671 < pf_total_CC(params, node1->cost,
1672 node1->extra_cost)))) {
1673 /* case 2 or 3. */
1674 node1->extra_cost = extra;
1675 node1->cost = cost;
1676 node1->dir_to_here = dir;
1677 node1->status = NS_NEW;
1678 node1->waited = (node->status == NS_WAITING);
1679 /* Extra costs of all nodes in danger_queue are equal! */
1680 map_index_pq_replace(pfdm->danger_queue, tindex1, -cost);
1681 }
1682 }
1684 }
1685
1686 if (NS_WAITING == node->status) {
1687 /* Node status final step E. to F. */
1688#ifdef PF_DEBUG
1689 fc_assert(!node->is_dangerous);
1690#endif
1691 node->status = NS_PROCESSED;
1692 } else if (!node->is_dangerous
1693 && (pf_moves_left(params, node->cost)
1694 < pf_move_rate(params))) {
1695 int fc, cc;
1696 /* Consider waiting at this node. To do it, put it back into queue.
1697 * Node status final step D. to E. */
1699 cc = pf_total_CC(params, fc, node->extra_cost);
1700 node->status = NS_WAITING;
1701 map_index_pq_insert(pfdm->queue, tindex, -cc);
1702 }
1703
1704 /* Get the next node (the index with the highest priority). First try
1705 * to get it from danger_queue. */
1706 if (map_index_pq_remove(pfdm->danger_queue, &tindex)) {
1707 /* Change the pf_map iterator and reset data. */
1708 tile = index_to_tile(params->map, tindex);
1709 pfm->tile = tile;
1710 node = pfdm->lattice + tindex;
1711 } else {
1712 /* No dangerous nodes to process, go for a safe one. */
1713 if (!map_index_pq_remove(pfdm->queue, &tindex)) {
1714 /* No more indexes in the priority queue, iteration end. */
1715 return FALSE;
1716 }
1717
1718#ifdef PF_DEBUG
1719 fc_assert(NS_PROCESSED != pfdm->lattice[tindex].status);
1720#endif
1721
1722 /* Change the pf_map iterator and reset data. */
1723 tile = index_to_tile(params->map, tindex);
1724 pfm->tile = tile;
1725 node = pfdm->lattice + tindex;
1726 if (NS_WAITING != node->status) {
1727 /* Node status step C. and D. */
1728#ifdef PF_DEBUG
1729 fc_assert(!node->is_dangerous);
1730#endif
1731 node->status = NS_PROCESSED;
1732 return TRUE;
1733 }
1734 }
1735
1736#ifdef PF_DEBUG
1738
1739 if (NS_WAITING == node->status) {
1740 /* We've already returned this node once, skip it. */
1741 log_debug("Considering waiting at (%d, %d)", TILE_XY(tile));
1742 } else if (node->is_dangerous) {
1743 /* We don't return dangerous tiles. */
1744 log_debug("Reached dangerous tile (%d, %d)", TILE_XY(tile));
1745 }
1746#endif
1747
1748 scope = node->move_scope;
1749 }
1750
1751 log_error("%s(): internal error.", __FUNCTION__);
1752 return FALSE;
1753}
1754
1755/************************************************************************/
1759 struct tile *ptile)
1760{
1761 struct pf_map *pfm = PF_MAP(pfdm);
1762 struct pf_danger_node *node = pfdm->lattice + tile_index(ptile);
1763
1764 /* Start position is handled in every function calling this function. */
1765
1766 if (NS_UNINIT == node->status) {
1767 /* Initialize the node, for doing the following tests. */
1768 if (!pf_danger_node_init(pfdm, node, ptile, PF_MS_NONE)
1769 || node->is_dangerous) {
1770 return FALSE;
1771 }
1772 } else if (TB_IGNORE == node->behavior || node->is_dangerous) {
1773 /* Simpliciation: if we cannot enter this node at all, or we cannot
1774 * stay at this position, don't iterate the whole map. */
1775 return FALSE;
1776 }
1777
1778 while (NS_PROCESSED != node->status && NS_WAITING != node->status) {
1779 if (!pf_map_iterate(pfm)) {
1780 /* All reachable destination have been iterated, 'ptile' is
1781 * unreachable. */
1782 return FALSE;
1783 }
1784 }
1785
1786 return TRUE;
1787}
1788
1789/************************************************************************/
1794static int pf_danger_map_move_cost(struct pf_map *pfm, struct tile *ptile)
1795{
1797
1798 if (ptile == pfm->params.start_tile) {
1799 return 0;
1800 } else if (pf_danger_map_iterate_until(pfdm, ptile)) {
1801 return (pfdm->lattice[tile_index(ptile)].cost
1804 } else {
1805 return PF_IMPOSSIBLE_MC;
1806 }
1807}
1808
1809/************************************************************************/
1813static struct pf_path *pf_danger_map_path(struct pf_map *pfm,
1814 struct tile *ptile)
1815{
1817
1818 if (ptile == pfm->params.start_tile) {
1820 } else if (pf_danger_map_iterate_until(pfdm, ptile)) {
1821 return pf_danger_map_construct_path(pfdm, ptile);
1822 } else {
1823 return nullptr;
1824 }
1825}
1826
1827/************************************************************************/
1832static bool pf_danger_map_position(struct pf_map *pfm, struct tile *ptile,
1833 struct pf_position *pos)
1834{
1836
1837 if (ptile == pfm->params.start_tile) {
1839 return TRUE;
1840 } else if (pf_danger_map_iterate_until(pfdm, ptile)) {
1842 return TRUE;
1843 } else {
1844 return FALSE;
1845 }
1846}
1847
1848/************************************************************************/
1852{
1854 struct pf_danger_node *node;
1855 int i;
1856
1857 /* Need to clean up the dangling danger segments. */
1858 for (i = 0, node = pfdm->lattice; i < MAP_INDEX_SIZE; i++, node++) {
1859 if (node->danger_segment) {
1860 free(node->danger_segment);
1861 }
1862 }
1863 free(pfdm->lattice);
1864 map_index_pq_destroy(pfdm->queue);
1865 map_index_pq_destroy(pfdm->danger_queue);
1866 free(pfdm);
1867}
1868
1869/************************************************************************/
1872static struct pf_map *pf_danger_map_new(const struct pf_parameter *parameter)
1873{
1874 struct pf_danger_map *pfdm;
1875 struct pf_map *base_map;
1876 struct pf_parameter *params;
1877 struct pf_danger_node *node;
1878
1879 pfdm = fc_malloc(sizeof(*pfdm));
1880 base_map = &pfdm->base_map;
1881 params = &base_map->params;
1882#ifdef PF_DEBUG
1883 /* Set the mode, used for cast check. */
1884 base_map->mode = PF_DANGER;
1885#endif /* PF_DEBUG */
1886
1887 /* Allocate the map. */
1888 pfdm->lattice = fc_calloc(MAP_INDEX_SIZE, sizeof(struct pf_danger_node));
1890 pfdm->danger_queue = map_index_pq_new(INITIAL_QUEUE_SIZE);
1891
1892 /* 'get_MC' callback must be set. */
1893 fc_assert_ret_val(parameter->get_MC != nullptr, nullptr);
1894
1895 /* 'is_pos_dangerous' callback must be set. */
1896 fc_assert_ret_val(parameter->is_pos_dangerous != nullptr, nullptr);
1897
1898 /* 'get_move_scope' callback must be set. */
1899 fc_assert_ret_val(parameter->get_move_scope != nullptr, nullptr);
1900
1901 /* Copy parameters */
1902 *params = *parameter;
1903
1904 /* Initialize virtual function table. */
1905 base_map->destroy = pf_danger_map_destroy;
1907 base_map->get_path = pf_danger_map_path;
1909 base_map->iterate = pf_danger_map_iterate;
1910
1911 /* Initialise starting node. */
1912 node = pfdm->lattice + tile_index(params->start_tile);
1913 if (!pf_danger_node_init(pfdm, node, params->start_tile, PF_MS_NONE)) {
1914 /* Always fails. */
1916 PF_MS_NONE));
1917 }
1918
1919 /* NB: do not handle params->transported_by_initially because we want to
1920 * handle only at start, not when crossing over the start tile for a
1921 * second time. See pf_danger_map_iterate(). */
1922
1923 /* Initialise the iterator. */
1924 base_map->tile = params->start_tile;
1925
1926 /* This makes calculations of turn/moves_left more convenient, but we
1927 * need to subtract this value before we return cost to the user. Note
1928 * that cost may be negative if moves_left_initially > move_rate
1929 * (see pf_turns()). */
1930 node->cost = pf_move_rate(params) - pf_moves_left_initially(params);
1931 node->extra_cost = 0;
1933 node->status = (node->is_dangerous ? NS_NEW : NS_PROCESSED);
1934
1935 return PF_MAP(pfdm);
1936}
1937
1938
1939/* ================= Specific pf_fuel_* mode structures ================== */
1940
1941/* Fuel path-finding maps are used for units which need to refuel. Usually
1942 * for air units such as planes or missiles.
1943 *
1944 * A big difference with the danger path-finding maps is that the tiles
1945 * which are not refuel points are not considered as dangerous because the
1946 * server uses to move the units at the end of the turn to refuels points. */
1947
1948struct pf_fuel_pos;
1949
1950/* Node definition. Note we try to have the smallest data as possible. */
1952 /* Note that 'short' here would be followed with padding anyway,
1953 * for alignment reasons, */
1954 signed int cost; /* total_MC. 'cost' may be negative, see comment in
1955 * pf_turns(). */
1956 unsigned extra_cost; /* total_EC. Can be huge, (higher than 'cost'). */
1957 unsigned moves_left : 12; /* Moves left at this position. */
1958 unsigned dir_to_here : 4; /* Direction from which we came. It's
1959 * an 'enum direction8' including
1960 * possibility of direction8_invalid (so we need
1961 * 4 bits) */
1962 unsigned status : 3; /* 'enum pf_node_status' really. */
1963
1964 /* Cached values */
1965 unsigned move_scope : 3; /* 'enum pf_move_scope really. */
1966 unsigned action : 2; /* 'enum pf_action really. */
1967 unsigned node_known_type : 2; /* 'enum known_type' really. */
1968 unsigned behavior : 2; /* 'enum tile_behavior' really. */
1969 unsigned zoc_number : 2; /* 'enum pf_zoc_type' really. */
1970 signed moves_left_req : 13; /* The minimum required moves left to reach
1971 * this tile. It the number of moves we need
1972 * to reach the nearest refuel point. A
1973 * value of 0 means this is a refuel point.
1974 * FIXME: this is right only for units with
1975 * constant move costs! */
1976 unsigned short extra_tile; /* EC */
1977 unsigned short cost_to_here[DIR8_MAGIC_MAX]; /* Step cost[dir to here] */
1978
1979 /* Segment leading across the danger area back to the nearest safe node:
1980 * need to remember costs and stuff. */
1982 /* Optimal segment to follow to get there (when node is processed). */
1984};
1985
1986/* We need to remember how we could get to there (until the previous refuel
1987 * point, or start position), because we could re-process the nodes after
1988 * having waiting somewhere. */
1990 signed int cost;
1991 unsigned extra_cost;
1992 unsigned moves_left : 12;
1993 unsigned dir_to_here : 4;
1994 unsigned ref_count : 4;
1996};
1997
1998/* Derived structure of struct pf_map. */
2000 struct pf_map base_map; /* Base structure, must be the first! */
2001
2002 struct map_index_pq *queue; /* Queue of nodes we have reached but not
2003 * processed yet (NS_NEW), sorted by their
2004 * total_CC */
2005 struct map_index_pq *waited_queue; /* Queue of nodes to reach farer
2006 * positions after having refueled. */
2007 struct pf_fuel_node *lattice; /* Lattice of nodes */
2008};
2009
2010/* Up-cast macro. */
2011#ifdef PF_DEBUG
2012static inline struct pf_fuel_map *
2013pf_fuel_map_check(struct pf_map *pfm, const char *file,
2014 const char *function, int line)
2015{
2017 pfm != nullptr && PF_FUEL == pfm->mode,
2018 return nullptr, "Wrong pf_map to pf_fuel_map conversion.");
2019 return (struct pf_fuel_map *) pfm;
2020}
2021#define PF_FUEL_MAP(pfm) \
2022 pf_fuel_map_check(pfm, __FILE__, __FUNCTION__, __FC_LINE__)
2023#else
2024#define PF_FUEL_MAP(pfm) ((struct pf_fuel_map *) (pfm))
2025#endif /* PF_DEBUG */
2026
2027/* ================= Specific pf_fuel_* mode functions ================== */
2028
2029/************************************************************************/
2032static inline int pf_fuel_total_CC(const struct pf_parameter *param,
2033 int cost, int extra, int safety)
2034{
2035 return pf_total_CC(param, cost, extra) - safety;
2036}
2037
2038/************************************************************************/
2041static inline int pf_fuel_waited_total_CC(int cost, int safety)
2042{
2043 return PF_TURN_FACTOR * (cost + 1) - safety - 1;
2044}
2045
2046/************************************************************************/
2051static inline bool pf_fuel_node_init(struct pf_fuel_map *pffm,
2052 struct pf_fuel_node *node,
2053 struct tile *ptile,
2055{
2056 const struct pf_parameter *params = pf_map_parameter(PF_MAP(pffm));
2057 enum known_type node_known_type;
2058 enum pf_action action;
2059
2060#ifdef PF_DEBUG
2061 fc_assert(NS_UNINIT == node->status);
2062 /* Else, not a critical problem, but waste of time. */
2063#endif
2064
2065 node->status = NS_INIT;
2066
2067 /* Establish the "known" status of node. */
2068 if (params->omniscience) {
2069 node_known_type = TILE_KNOWN_SEEN;
2070 } else {
2071 node_known_type = tile_get_known(ptile, params->owner);
2072 }
2073 node->node_known_type = node_known_type;
2074
2075 /* Establish the tile behavior. */
2076 if (params->get_TB != nullptr) {
2077 node->behavior = params->get_TB(ptile, node_known_type, params);
2078 if (TB_IGNORE == node->behavior && params->start_tile != ptile) {
2079 return FALSE;
2080 }
2081#ifdef ZERO_VARIABLES_FOR_SEARCHING
2082 } else {
2083 /* The default. */
2084 node->behavior = TB_NORMAL;
2085#endif
2086 }
2087
2088 if (TILE_UNKNOWN != node_known_type) {
2089 bool can_disembark;
2090
2091 /* Test if we can invade tile. */
2092 if (!utype_has_flag(params->utype, UTYF_CIVILIAN)
2093 && !player_can_invade_tile(params->owner, ptile)) {
2094 /* Maybe overwrite node behavior. */
2095 if (params->start_tile != ptile) {
2096 node->behavior = TB_IGNORE;
2097 return FALSE;
2098 } else if (TB_NORMAL == node->behavior) {
2099 node->behavior = TB_IGNORE;
2100 }
2101 }
2102
2103 /* Test the possibility to perform an action. */
2104 if (params->get_action != nullptr
2105 && PF_ACTION_NONE != (action =
2106 params->get_action(ptile, node_known_type,
2107 params))) {
2109 /* Maybe overwrite node behavior. */
2110 if (params->start_tile != ptile) {
2111 node->behavior = TB_IGNORE;
2112 return FALSE;
2113 } else if (TB_NORMAL == node->behavior) {
2114 node->behavior = TB_IGNORE;
2115 }
2117 } else if (TB_DONT_LEAVE != node->behavior) {
2118 /* Overwrite node behavior. */
2119 node->behavior = TB_DONT_LEAVE;
2120 }
2121 node->action = action;
2122#ifdef ZERO_VARIABLES_FOR_SEARCHING
2123 node->moves_left_req = 0; /* Attack is always possible theoretically. */
2124#endif
2125 } else {
2126#ifdef ZERO_VARIABLES_FOR_SEARCHING
2127 /* Nodes are allocated by fc_calloc(), so should be already set to
2128 * 0. */
2129 node->action = PF_ACTION_NONE;
2130#endif
2131 node->moves_left_req =
2132 params->get_moves_left_req(ptile, node_known_type, params);
2133 if (PF_IMPOSSIBLE_MC == node->moves_left_req) {
2134 /* Overwrite node behavior. */
2135 if (params->start_tile == ptile) {
2136 node->behavior = TB_DONT_LEAVE;
2137 } else {
2138 node->behavior = TB_IGNORE;
2139 return FALSE;
2140 }
2141 }
2142 }
2143
2144 /* Test the possibility to move from/to 'ptile'. */
2145 node->move_scope = params->get_move_scope(ptile, &can_disembark,
2146 previous_scope, params);
2147 if (PF_MS_NONE == node->move_scope
2148 && PF_ACTION_NONE == node->action
2149 && params->ignore_none_scopes) {
2150 /* Maybe overwrite node behavior. */
2151 if (params->start_tile != ptile) {
2152 node->behavior = TB_IGNORE;
2153 return FALSE;
2154 } else if (TB_NORMAL == node->behavior) {
2155 node->behavior = TB_IGNORE;
2156 }
2157 } else if (PF_MS_TRANSPORT == node->move_scope
2158 && !can_disembark
2159 && (params->start_tile != ptile
2160 || params->transported_by_initially == nullptr)) {
2161 /* Overwrite node behavior. */
2162 node->behavior = TB_DONT_LEAVE;
2163 }
2164
2165 /* ZOC_MINE means can move unrestricted from/into it, ZOC_ALLIED means
2166 * can move unrestricted into it, but not necessarily from it. */
2167 if (params->get_zoc != nullptr
2168 && tile_city(ptile) == nullptr
2170 && !params->get_zoc(params->owner, ptile, params->map)) {
2171 node->zoc_number = (0 < unit_list_size(ptile->units)
2172 ? ZOC_ALLIED : ZOC_NO);
2173#ifdef ZERO_VARIABLES_FOR_SEARCHING
2174 } else {
2175 /* Nodes are allocated by fc_calloc(), so should be already set to
2176 * 0. */
2177 node->zoc_number = ZOC_MINE;
2178#endif
2179 }
2180 } else {
2181 node->moves_left_req =
2182 params->get_moves_left_req(ptile, node_known_type, params);
2183 if (PF_IMPOSSIBLE_MC == node->moves_left_req) {
2184 /* Overwrite node behavior. */
2185 if (params->start_tile == ptile) {
2186 node->behavior = TB_DONT_LEAVE;
2187 } else {
2188 node->behavior = TB_IGNORE;
2189 return FALSE;
2190 }
2191 }
2192
2193 node->move_scope = PF_MS_NATIVE;
2194#ifdef ZERO_VARIABLES_FOR_SEARCHING
2195 /* Nodes are allocated by fc_calloc(), so should be already set to 0. */
2196 node->action = PF_ACTION_NONE;
2197 node->zoc_number = ZOC_MINE;
2198#endif
2199 }
2200
2201 /* Evaluate the extra cost of the destination. */
2202 if (params->get_EC != nullptr) {
2203 node->extra_tile = params->get_EC(ptile, node_known_type, params);
2204#ifdef ZERO_VARIABLES_FOR_SEARCHING
2205 } else {
2206 /* Nodes are allocated by fc_calloc(), so should be already set to 0. */
2207 node->extra_tile = 0;
2208#endif
2209 }
2210
2211#ifdef ZERO_VARIABLES_FOR_SEARCHING
2212 /* Nodes are allocated by fc_calloc(), so should be already set to 0. */
2213 node->pos = nullptr;
2214 node->segment = nullptr;
2215#endif
2216
2217 return TRUE;
2218}
2219
2220/************************************************************************/
2223static inline bool pf_fuel_node_dangerous(const struct pf_fuel_node *node)
2224{
2225 return (node->pos == nullptr
2226 || (node->pos->moves_left < node->moves_left_req
2227 && PF_ACTION_NONE == node->action));
2228}
2229
2230/************************************************************************/
2233static inline struct pf_fuel_pos *pf_fuel_pos_ref(struct pf_fuel_pos *pos)
2234{
2235#ifdef PF_DEBUG
2236 /* Assert we have enough space to store the new count. Maximum is 10
2237 * (node->pos, node->segment, and 8 for other_pos->prev). */
2238 fc_assert(15 > pos->ref_count);
2239#endif
2240 pos->ref_count++;
2241
2242 return pos;
2243}
2244
2245/************************************************************************/
2249static inline void pf_fuel_pos_unref(struct pf_fuel_pos *pos)
2250{
2251 while (pos != nullptr && 0 == --pos->ref_count) {
2252 struct pf_fuel_pos *prev = pos->prev;
2253
2254 free(pos);
2255 pos = prev;
2256 }
2257}
2258
2259/************************************************************************/
2265static inline struct pf_fuel_pos *
2267{
2268 if (pos == nullptr) {
2269 pos = fc_malloc(sizeof(*pos));
2270 pos->ref_count = 1;
2271 } else if (1 < pos->ref_count) {
2272 pos->ref_count--;
2273 pos = fc_malloc(sizeof(*pos));
2274 pos->ref_count = 1;
2275 } else {
2276#ifdef PF_DEBUG
2277 fc_assert(1 == pos->ref_count);
2278#endif
2279 pf_fuel_pos_unref(pos->prev);
2280 }
2281 pos->cost = node->cost;
2282 pos->extra_cost = node->extra_cost;
2283 pos->moves_left = node->moves_left;
2284 pos->dir_to_here = node->dir_to_here;
2285 pos->prev = nullptr;
2286
2287 return pos;
2288}
2289
2290/************************************************************************/
2293static inline void
2295 struct pf_position *pos,
2296 int cost, int moves_left)
2297{
2298 int move_rate = param->move_rate;
2299
2300 pos->turn = pf_turns(param, cost);
2301 if (move_rate > 0 && param->start_tile != pos->tile) {
2302 pos->fuel_left = moves_left / move_rate;
2303 pos->moves_left = moves_left % move_rate;
2304 } else if (param->start_tile == pos->tile) {
2305 pos->fuel_left = param->fuel_left_initially;
2306 pos->moves_left = param->moves_left_initially;
2307 } else {
2308 pos->fuel_left = param->fuel_left_initially;
2309 pos->moves_left = moves_left;
2310 }
2311}
2312
2313/************************************************************************/
2316static inline void
2318 const struct pf_parameter *params,
2319 const struct pf_fuel_node *node,
2320 const struct pf_fuel_pos *head)
2321{
2322 if (head) {
2324 head->cost, head->moves_left);
2325 } else {
2327 node->cost, node->moves_left);
2328 }
2329}
2330
2331/************************************************************************/
2336 struct tile *ptile,
2337 struct pf_position *pos)
2338{
2339 int tindex = tile_index(ptile);
2340 struct pf_fuel_node *node = pffm->lattice + tindex;
2341 struct pf_fuel_pos *head = node->segment;
2342 const struct pf_parameter *params = pf_map_parameter(PF_MAP(pffm));
2343
2344#ifdef PF_DEBUG
2345 fc_assert_ret_msg(head != nullptr,
2346 "Unreached destination (%d, %d).", TILE_XY(ptile));
2347#endif /* PF_DEBUG */
2348
2349 pos->tile = ptile;
2350 pos->total_EC = head->extra_cost;
2351 pos->total_MC = (head->cost - pf_move_rate(params)
2352 + pf_moves_left_initially(params));
2353 pos->dir_to_here = head->dir_to_here;
2354 pos->dir_to_next_pos = direction8_invalid(); /* This field does not apply. */
2355 pf_fuel_finalize_position(pos, params, node, head);
2356}
2357
2358/************************************************************************/
2363static inline int
2365 int cost, int moves_left)
2366{
2367#ifdef PF_DEBUG
2368 fc_assert(0 < param->move_rate);
2369#endif /* PF_DEBUG */
2370 return cost + moves_left % param->move_rate;
2371}
2372
2373/************************************************************************/
2376static struct pf_path *
2378 struct tile *ptile)
2379{
2380 struct pf_path *path = fc_malloc(sizeof(*path));
2382 struct pf_fuel_node *node = pffm->lattice + tile_index(ptile);
2383 struct pf_fuel_pos *segment = node->segment;
2384 unsigned length = 1;
2385 struct tile *iter_tile = ptile;
2386 const struct pf_parameter *params = pf_map_parameter(PF_MAP(pffm));
2387 struct pf_position *pos;
2388 int i;
2389
2390#ifdef PF_DEBUG
2391 fc_assert_ret_val_msg(segment != nullptr, nullptr,
2392 "Unreached destination (%d, %d).",
2393 TILE_XY(ptile));
2394#endif /* PF_DEBUG */
2395
2396 /* First iterate to find path length. */
2397 /* NB: the start point could be reached in the middle of a segment.
2398 * See comment for pf_fuel_map_create_segment(). */
2399 while (direction8_is_valid(segment->dir_to_here)) {
2400 if (node->moves_left_req == 0) {
2401 /* A refuel point. */
2402 if (segment != node->segment) {
2403 length += 2;
2404 segment = node->segment;
2405 } else {
2406 length++;
2407 }
2408 } else {
2409 length++;
2410 }
2411
2412 /* Step backward. */
2413 iter_tile = mapstep(params->map, iter_tile,
2414 DIR_REVERSE(segment->dir_to_here));
2415 node = pffm->lattice + tile_index(iter_tile);
2416 segment = segment->prev;
2417#ifdef PF_DEBUG
2418 fc_assert(segment != nullptr);
2419#endif /* PF_DEBUG */
2420 }
2421 if (node->moves_left_req == 0 && segment != node->segment) {
2422 /* We wait at the start point */
2423 length++;
2424 }
2425
2426 /* Allocate memory for path. */
2427 path->positions = fc_malloc(length * sizeof(struct pf_position));
2428 path->length = length;
2429
2430 /* Reset variables for main iteration. */
2431 iter_tile = ptile;
2432 node = pffm->lattice + tile_index(ptile);
2433 segment = node->segment;
2434
2435 for (i = length - 1; i >= 0; i--) {
2436 /* 1: Deal with waiting. */
2437 if (node->moves_left_req == 0 && segment != node->segment) {
2438 /* Waited at _this_ tile, need to record it twice in the
2439 * path. Here we record our state _after_ waiting (e.g.
2440 * full move points). */
2441 pos = path->positions + i;
2442 pos->tile = iter_tile;
2443 pos->total_EC = segment->extra_cost;
2444 pos->turn = pf_turns(params, segment->cost);
2445 pos->total_MC = ((pos->turn - 1) * params->move_rate
2446 + params->moves_left_initially);
2447 pos->moves_left = params->move_rate;
2448 pos->fuel_left = params->fuel;
2449 pos->dir_to_next_pos = dir_next;
2451 segment = node->segment;
2452 i--;
2453 if (segment == nullptr) {
2454 /* We waited at start tile, then 'node->segment' is not set. */
2455#ifdef PF_DEBUG
2456 fc_assert(iter_tile == params->start_tile);
2457 fc_assert(0 == i);
2458#endif /* PF_DEBUG */
2460 return path;
2461 }
2462 }
2463
2464 /* 2: Fill the current position. */
2465 pos = path->positions + i;
2466 pos->tile = iter_tile;
2467 pos->total_MC = (pf_moves_left_initially(params)
2468 - pf_move_rate(params) + segment->cost);
2469 pos->total_EC = segment->extra_cost;
2470 pos->dir_to_next_pos = dir_next;
2471 pf_fuel_finalize_position(pos, params, node, segment);
2472
2473 /* 3: Check if we finished. */
2474 if (i == 0) {
2475 /* We should be back at the start now! */
2476 fc_assert_ret_val(iter_tile == params->start_tile, nullptr);
2477 return path;
2478 }
2479
2480 /* 4: Calculate the next direction. */
2481 dir_next = segment->dir_to_here;
2482
2483 /* 5: Step further back. */
2485 node = pffm->lattice + tile_index(iter_tile);
2486 segment = segment->prev;
2487#ifdef PF_DEBUG
2488 fc_assert(segment != nullptr);
2489#endif /* PF_DEBUG */
2490 }
2491
2492 fc_assert_msg(FALSE, "Cannot get to the starting point!");
2493
2494 return nullptr;
2495}
2496
2497/************************************************************************/
2515 struct tile *ptile,
2516 struct pf_fuel_node *node)
2517{
2518 struct pf_fuel_pos *pos, *next;
2519 const struct pf_parameter *params = pf_map_parameter(PF_MAP(pffm));
2520
2521 pos = pf_fuel_pos_replace(node->pos, node);
2522 node->pos = pos;
2523
2524 /* Iterate until we reach any built segment. */
2525 do {
2526 next = pos;
2527 ptile = mapstep(params->map, ptile, DIR_REVERSE(node->dir_to_here));
2528 node = pffm->lattice + tile_index(ptile);
2529 pos = node->pos;
2530 if (pos != nullptr) {
2531 if (pos->cost == node->cost
2532 && pos->dir_to_here == node->dir_to_here
2533 && pos->extra_cost == node->extra_cost
2534 && pos->moves_left == node->moves_left) {
2535 /* Reached an usable segment. */
2536 next->prev = pf_fuel_pos_ref(pos);
2537 break;
2538 }
2539 }
2540 /* Update position. */
2541 pos = pf_fuel_pos_replace(pos, node);
2542 node->pos = pos;
2543 next->prev = pf_fuel_pos_ref(pos);
2544 } while (0 != node->moves_left_req && direction8_is_valid(node->dir_to_here));
2545}
2546
2547/************************************************************************/
2550static inline int pf_fuel_map_adjust_cost(int cost, int moves_left,
2551 int move_rate)
2552{
2553 if (move_rate > 0) {
2554 int remaining_moves = moves_left % move_rate;
2555
2556 if (remaining_moves == 0) {
2558 }
2559
2560 return MIN(cost, remaining_moves);
2561 } else {
2562 return MIN(cost, moves_left);
2563 }
2564}
2565
2566/************************************************************************/
2572static inline bool
2574 int moves_left, int moves_left_req)
2575{
2577 /* Case missile */
2578 return TRUE;
2579 } else if (utype_action_takes_all_mp(param->utype,
2581 /* Case Bombers */
2583 /* We are in the last turn of fuel, don't attack */
2584 return FALSE;
2585 } else {
2586 return TRUE;
2587 }
2588 } else {
2589 /* Case fighters */
2590 if (moves_left - SINGLE_MOVE < moves_left_req) {
2591 return FALSE;
2592 } else {
2593 return TRUE;
2594 }
2595 }
2596}
2597
2598/************************************************************************/
2633static bool pf_fuel_map_iterate(struct pf_map *pfm)
2634{
2635 struct pf_fuel_map *const pffm = PF_FUEL_MAP(pfm);
2636 const struct pf_parameter *const params = pf_map_parameter(pfm);
2637 struct tile *tile = pfm->tile;
2638 int tindex = tile_index(tile);
2639 struct pf_fuel_node *node = pffm->lattice + tindex;
2640 enum pf_move_scope scope = node->move_scope;
2642 bool waited = FALSE;
2643
2644 /* The previous position is defined by 'tile' (tile pointer), 'node'
2645 * (the data of the tile for the pf_map), and index (the index of the
2646 * position in the Freeciv map). */
2647
2649 && params->transported_by_initially != nullptr) {
2650#ifdef PF_DEBUG
2651 fc_assert(tile == params->start_tile);
2652#endif
2654 if (!utype_can_freely_unload(params->utype,
2656 && tile_city(tile) == nullptr
2658 /* Cannot disembark, don't leave transporter. */
2659 node->behavior = TB_DONT_LEAVE;
2660 }
2661 }
2662
2663 for (;;) {
2664 /* There is no exit from DONT_LEAVE tiles! */
2665 if (node->behavior != TB_DONT_LEAVE
2666 && scope != PF_MS_NONE
2667 && (params->move_rate > 0 || node->cost < 0)) {
2668 int loc_cost = node->cost;
2669 int loc_moves_left = node->moves_left;
2670
2671 if (0 == node->moves_left_req
2672 && 0 < params->move_rate
2673 && 0 == loc_moves_left % params->move_rate
2674 && loc_cost >= params->moves_left_initially) {
2675 /* We have implicitly refueled at the end of the turn. Update also
2676 * 'node->moves_left' to ensure to wait there in paths. */
2677 loc_moves_left = pf_move_rate(params);
2678 node->moves_left = loc_moves_left;
2679 }
2680
2681 adjc_dir_iterate(params->map, tile, tile1, dir) {
2682 /* Calculate the cost of every adjacent position and set them in
2683 * the priority queues for next call to pf_fuel_map_iterate(). */
2684 int tindex1 = tile_index(tile1);
2685 struct pf_fuel_node *node1 = pffm->lattice + tindex1;
2686 int cost, extra = 0;
2687 int moves_left;
2689 struct pf_fuel_pos *pos;
2690
2691 /* As for the previous position, 'tile1', 'node1' and 'tindex1' are
2692 * defining the adjacent position. */
2693
2694 /* Non-full fuel tiles can be updated even after being processed. */
2695 if ((NS_PROCESSED == node1->status || NS_WAITING == node1->status)
2696 && 0 == node1->moves_left_req) {
2697 /* This gives 15% speedup. */
2698 continue;
2699 }
2700
2701 /* Initialise target tile if necessary */
2702 if (node1->status == NS_UNINIT) {
2703 /* Only initialize once. See comment for pf_fuel_node_init().
2704 * Node status step A. to B. */
2706 continue;
2707 }
2708 } else if (TB_IGNORE == node1->behavior) {
2709 /* We cannot enter this tile at all! */
2710 continue;
2711 }
2712
2713 /* Is the move ZOC-ok? */
2714 if (node->zoc_number != ZOC_MINE && node1->zoc_number == ZOC_NO) {
2715 continue;
2716 }
2717
2718 cost = node1->cost_to_here[dir];
2719 if (0 == cost) {
2720 /* Evaluate the cost of the move. */
2721 if (PF_ACTION_NONE != node1->action) {
2722 if (params->is_action_possible != nullptr
2723 && !params->is_action_possible(tile, scope, tile1,
2724 node1->action, params)) {
2725 node1->cost_to_here[dir] = PF_IMPOSSIBLE_MC + 2;
2726 continue;
2727 }
2728 /* action move cost depends on action and unit type. */
2729 if (node1->action == PF_ACTION_ATTACK
2730 && (utype_action_takes_all_mp(params->utype,
2733 || utype_can_do_action(params->utype,
2735 /* Assume that the attack will be a suicide attack even if a
2736 * regular attack may be legal. */
2737 cost = params->move_rate;
2738 } else {
2739 cost = SINGLE_MOVE;
2740 }
2741 } else if (node1->node_known_type == TILE_UNKNOWN) {
2742 cost = params->utype->unknown_move_cost;
2743 } else {
2744 cost = params->get_MC(tile, scope, tile1, node1->move_scope,
2745 params);
2746 }
2747
2748 if (cost == FC_INFINITY) {
2749 /* tile_move_cost_ptrs() uses FC_INFINITY to flag that all
2750 * movement is spent, e.g., when disembarking from transport. */
2751 cost = params->move_rate;
2752 }
2753
2754#ifdef PF_DEBUG
2755 fc_assert(1 << (8 * sizeof(node1->cost_to_here[dir])) > cost + 2);
2756 fc_assert(0 < cost + 2);
2757#endif /* PF_DEBUG */
2758
2759 node1->cost_to_here[dir] = cost + 2;
2760 if (cost == PF_IMPOSSIBLE_MC) {
2761 continue;
2762 }
2763 } else if (cost == PF_IMPOSSIBLE_MC + 2) {
2764 continue;
2765 } else {
2766 cost -= 2;
2767 }
2768
2770 params->move_rate);
2771
2773 if (moves_left < node1->moves_left_req
2775 || 0 > moves_left)) {
2776 /* We don't have enough moves left, but missiles
2777 * can do suicidal attacks. */
2778 continue;
2779 }
2780
2781 if (PF_ACTION_ATTACK == node1->action
2783 node->moves_left_req)) {
2784 /* We wouldn't have enough moves left after attacking. */
2785 continue;
2786 }
2787
2788 /* Total cost at 'tile1' */
2789 cost += loc_cost;
2790
2791 /* Evaluate the extra cost of the destination, if it's relevant. */
2792 if (params->get_EC != nullptr) {
2793 extra = node1->extra_tile + node->extra_cost;
2794 }
2795
2796 /* Update costs and add to queue, if this is a better route
2797 * to tile1. Case safe tiles or reached directly without waiting. */
2798 pos = node1->segment;
2799 cost_of_path = pf_fuel_total_CC(params, cost, extra,
2800 moves_left - node1->moves_left_req);
2801 if (node1->status == NS_INIT) {
2802 /* Not calculated yet. */
2803 old_cost_of_path = 0;
2804 } else if (pos) {
2805 /* We have a path to this tile. The default values could have been
2806 * overwritten if we had more moves left to deal with waiting.
2807 * Then, we have to get back the value of this node to calculate
2808 * the cost. */
2810 pf_fuel_total_CC(params, pos->cost, pos->extra_cost,
2811 pos->moves_left - node1->moves_left_req);
2812 } else {
2813 /* Default cost */
2815 pf_fuel_total_CC(params, node1->cost, node1->extra_cost,
2816 node1->moves_left - node1->moves_left_req);
2817 }
2818
2819 /* Step 1: We test if this route is the best to this tile, by a
2820 * direct way, not taking in account waiting. */
2821
2822 if (NS_INIT == node1->status
2823 || (node1->status == NS_NEW && cost_of_path < old_cost_of_path)) {
2824 /* We are reaching this node for the first time, or we found a
2825 * better route to 'tile1', or we would have more moves lefts
2826 * at previous position. Let's register 'tindex1' to the
2827 * priority queue. */
2828 node1->extra_cost = extra;
2829 node1->cost = cost;
2831 node1->dir_to_here = dir;
2832 /* Always record the segment, including when it is not dangerous
2833 * to move there. */
2835 if (NS_INIT == node1->status) {
2836 /* Node status B. to C. */
2837 node1->status = NS_NEW;
2839 } else {
2840 /* else staying at D. */
2841#ifdef PF_DEBUG
2842 fc_assert(NS_NEW == node1->status);
2843#endif
2846 }
2847 }
2848 continue; /* adjc_dir_iterate() */
2849 }
2850
2851 /* Step 2: We test if this route could open better routes for other
2852 * tiles, if we waited somewhere. */
2853
2854 if (!waited
2855 || NS_NEW == node1->status
2856 || 0 == node1->moves_left_req) {
2857 /* Stops there if:
2858 * 1. we didn't wait to get there ;
2859 * 2. we didn't process yet the node ;
2860 * 3. this is a refuel point. */
2861 continue; /* adjc_dir_iterate() */
2862 }
2863
2864#ifdef PF_DEBUG
2865 fc_assert(NS_PROCESSED == node1->status);
2866#endif
2867
2868 if (moves_left > node1->moves_left
2869 || (moves_left == node1->moves_left
2871 /* We will update costs if:
2872 * 1. we would have more moves left than previously on this node.
2873 * 2. we can have lower extra and will not overwrite anything
2874 * useful. */
2875 node1->extra_cost = extra;
2876 node1->cost = cost;
2878 node1->dir_to_here = dir;
2879 map_index_pq_insert(pffm->waited_queue, tindex1,
2881 moves_left - node1->moves_left_req));
2882 }
2884 }
2885
2886 if (NS_WAITING == node->status) {
2887 /* Node status final step E. to F. */
2888#ifdef PF_DEBUG
2889 fc_assert(0 == node->moves_left_req);
2890#endif
2891 node->status = NS_PROCESSED;
2892 } else if (0 == node->moves_left_req
2893 && PF_ACTION_NONE == node->action
2894 && node->moves_left < pf_move_rate(params)
2896 && (fc_assert(0 < params->move_rate), 0 < params->move_rate)
2897#endif
2898 && (0 != node->moves_left % params->move_rate
2899 || node->cost < params->moves_left_initially)) {
2900 /* Consider waiting at this node. To do it, put it back into queue.
2901 * Node status final step D. to E. */
2902 node->status = NS_WAITING;
2903 /* The values we use now to calculate waited total_CC
2904 * will be applied to the node after we get it back from the queue
2905 * to get passing-by segments before it without waiting */
2906 map_index_pq_insert(pffm->queue, tindex,
2909 node->cost,
2910 node->moves_left),
2911 pf_move_rate(params)));
2912 }
2913
2914 /* Get the next node (the index with the highest priority). First try
2915 * to get it from waited_queue. */
2916 if (!map_index_pq_priority(pffm->queue, &priority)
2917 || (map_index_pq_priority(pffm->waited_queue, &waited_priority)
2918 && priority < waited_priority)) {
2919 if (!map_index_pq_remove(pffm->waited_queue, &tindex)) {
2920 /* End of the iteration. */
2921 return FALSE;
2922 }
2923
2924 /* Change the pf_map iterator and reset data. */
2925 tile = index_to_tile(params->map, tindex);
2926 pfm->tile = tile;
2927 node = pffm->lattice + tindex;
2928 waited = TRUE;
2929#ifdef PF_DEBUG
2930 fc_assert(0 < node->moves_left_req);
2931 fc_assert(NS_PROCESSED == node->status);
2932#endif
2933 } else {
2934#ifdef PF_DEBUG
2935#ifndef FREECIV_NDEBUG
2936 bool success =
2937#endif
2938 map_index_pq_remove(pffm->queue, &tindex);
2939
2941#else
2942 map_index_pq_remove(pffm->queue, &tindex);
2943#endif
2944
2945 /* Change the pf_map iterator and reset data. */
2946 tile = index_to_tile(params->map, tindex);
2947 pfm->tile = tile;
2948 node = pffm->lattice + tindex;
2949
2950#ifdef PF_DEBUG
2951 fc_assert(NS_PROCESSED != node->status);
2952#endif /* PF_DEBUG */
2953
2954 waited = (NS_WAITING == node->status);
2955 if (waited) {
2956 /* Arrange waiting at the node */
2957 node->cost = pf_fuel_map_fill_cost_for_full_moves(params, node->cost,
2958 node->moves_left);
2959 node->moves_left = pf_move_rate(params);
2960 } else if (!pf_fuel_node_dangerous(node)) {
2961 /* Node status step C. and D. */
2962 node->status = NS_PROCESSED;
2963 node->segment = pf_fuel_pos_ref(node->pos);
2964 return TRUE;
2965 }
2966 }
2967
2968#ifdef PF_DEBUG
2970
2971 if (NS_WAITING == node->status) {
2972 /* We've already returned this node once, skip it. */
2973 log_debug("Considering waiting at (%d, %d)", TILE_XY(tile));
2974 } else if (NS_PROCESSED == node->status) {
2975 /* We've already returned this node once, skip it. */
2976 log_debug("Reprocessing tile (%d, %d)", TILE_XY(tile));
2977 } else if (pf_fuel_node_dangerous(node)) {
2978 /* We don't return dangerous tiles. */
2979 log_debug("Reached dangerous tile (%d, %d)", TILE_XY(tile));
2980 }
2981#endif /* PF_DEBUG */
2982
2983 scope = node->move_scope;
2984 }
2985
2986 log_error("%s(): internal error.", __FUNCTION__);
2987 return FALSE;
2988}
2989
2990/************************************************************************/
2993static inline bool pf_fuel_map_iterate_until(struct pf_fuel_map *pffm,
2994 struct tile *ptile)
2995{
2996 struct pf_map *pfm = PF_MAP(pffm);
2997 struct pf_fuel_node *node = pffm->lattice + tile_index(ptile);
2998
2999 /* Start position is handled in every function calling this function. */
3000
3001 if (NS_UNINIT == node->status) {
3002 /* Initialize the node, for doing the following tests. */
3003 if (!pf_fuel_node_init(pffm, node, ptile, PF_MS_NONE)) {
3004 return FALSE;
3005 }
3006 } else if (TB_IGNORE == node->behavior) {
3007 /* Simpliciation: if we cannot enter this node at all, don't iterate the
3008 * whole map. */
3009 return FALSE;
3010 }
3011
3012 while (node->segment == nullptr) {
3013 if (!pf_map_iterate(pfm)) {
3014 /* All reachable destination have been iterated, 'ptile' is
3015 * unreachable. */
3016 return FALSE;
3017 }
3018 }
3019
3020 return TRUE;
3021}
3022
3023/************************************************************************/
3028static int pf_fuel_map_move_cost(struct pf_map *pfm, struct tile *ptile)
3029{
3030 struct pf_fuel_map *pffm = PF_FUEL_MAP(pfm);
3031
3032 if (ptile == pfm->params.start_tile) {
3033 return 0;
3034 } else if (pf_fuel_map_iterate_until(pffm, ptile)) {
3035 const struct pf_fuel_node *node = pffm->lattice + tile_index(ptile);
3036
3037 return (node->segment->cost
3040 } else {
3041 return PF_IMPOSSIBLE_MC;
3042 }
3043}
3044
3045/************************************************************************/
3049static struct pf_path *pf_fuel_map_path(struct pf_map *pfm,
3050 struct tile *ptile)
3051{
3052 struct pf_fuel_map *pffm = PF_FUEL_MAP(pfm);
3053
3054 if (ptile == pfm->params.start_tile) {
3056 } else if (pf_fuel_map_iterate_until(pffm, ptile)) {
3057 return pf_fuel_map_construct_path(pffm, ptile);
3058 } else {
3059 return nullptr;
3060 }
3061}
3062
3063/************************************************************************/
3068static bool pf_fuel_map_position(struct pf_map *pfm, struct tile *ptile,
3069 struct pf_position *pos)
3070{
3071 struct pf_fuel_map *pffm = PF_FUEL_MAP(pfm);
3072
3073 if (ptile == pfm->params.start_tile) {
3075 return TRUE;
3076 } else if (pf_fuel_map_iterate_until(pffm, ptile)) {
3078 return TRUE;
3079 } else {
3080 return FALSE;
3081 }
3082}
3083
3084/************************************************************************/
3087static void pf_fuel_map_destroy(struct pf_map *pfm)
3088{
3089 struct pf_fuel_map *pffm = PF_FUEL_MAP(pfm);
3090 struct pf_fuel_node *node;
3091 int i;
3092
3093 /* Need to clean up the dangling fuel segments. */
3094 for (i = 0, node = pffm->lattice; i < MAP_INDEX_SIZE; i++, node++) {
3095 pf_fuel_pos_unref(node->pos);
3097 }
3098 free(pffm->lattice);
3099 map_index_pq_destroy(pffm->queue);
3100 map_index_pq_destroy(pffm->waited_queue);
3101 free(pffm);
3102}
3103
3104/************************************************************************/
3107static struct pf_map *pf_fuel_map_new(const struct pf_parameter *parameter)
3108{
3109 struct pf_fuel_map *pffm;
3110 struct pf_map *base_map;
3111 struct pf_parameter *params;
3112 struct pf_fuel_node *node;
3113
3114 pffm = fc_malloc(sizeof(*pffm));
3115 base_map = &pffm->base_map;
3116 params = &base_map->params;
3117#ifdef PF_DEBUG
3118 /* Set the mode, used for cast check. */
3119 base_map->mode = PF_FUEL;
3120#endif /* PF_DEBUG */
3121
3122 /* Allocate the map. */
3123 pffm->lattice = fc_calloc(MAP_INDEX_SIZE, sizeof(struct pf_fuel_node));
3125 pffm->waited_queue = map_index_pq_new(INITIAL_QUEUE_SIZE);
3126
3127 /* 'get_MC' callback must be set. */
3128 fc_assert_ret_val(parameter->get_MC != nullptr, nullptr);
3129
3130 /* 'get_moves_left_req' callback must be set. */
3131 fc_assert_ret_val(parameter->get_moves_left_req != nullptr, nullptr);
3132
3133 /* 'get_move_scope' callback must be set. */
3134 fc_assert_ret_val(parameter->get_move_scope != nullptr, nullptr);
3135
3136 /* Copy parameters. */
3137 *params = *parameter;
3138
3139 /* Initialize virtual function table. */
3140 base_map->destroy = pf_fuel_map_destroy;
3142 base_map->get_path = pf_fuel_map_path;
3144 base_map->iterate = pf_fuel_map_iterate;
3145
3146 /* Initialise starting node. */
3147 node = pffm->lattice + tile_index(params->start_tile);
3148 if (!pf_fuel_node_init(pffm, node, params->start_tile, PF_MS_NONE)) {
3149 /* Always fails. */
3151 PF_MS_NONE));
3152 }
3153
3154 /* NB: do not handle params->transported_by_initially because we want to
3155 * handle only at start, not when crossing over the start tile for a
3156 * second time. See pf_danger_map_iterate(). */
3157
3158 /* Initialise the iterator. */
3159 base_map->tile = params->start_tile;
3160
3161 /* This makes calculations of turn/moves_left more convenient, but we
3162 * need to subtract this value before we return cost to the user. Note
3163 * that cost may be negative if moves_left_initially > move_rate
3164 * (see pf_turns()). */
3165 node->moves_left = pf_moves_left_initially(params);
3166 node->cost = pf_move_rate(params) - node->moves_left;
3167 node->extra_cost = 0;
3169 /* Record a segment. We need it for correct paths. */
3170 node->segment
3171 = pf_fuel_pos_ref(node->pos = pf_fuel_pos_replace(nullptr, node));
3172 node->status = NS_PROCESSED;
3173
3174 return PF_MAP(pffm);
3175}
3176
3177
3178/* ====================== pf_map public functions ======================= */
3179
3180/************************************************************************/
3184struct pf_map *pf_map_new(const struct pf_parameter *parameter)
3185{
3186 if (parameter->is_pos_dangerous) {
3187 if (parameter->get_moves_left_req) {
3188 log_error("path finding code cannot deal with dangers "
3189 "and fuel together.");
3190 }
3191 if (parameter->get_costs) {
3192 log_error("jumbo callbacks for danger maps are not yet implemented.");
3193 }
3194 return pf_danger_map_new(parameter);
3195 } else if (parameter->get_moves_left_req) {
3196 if (parameter->get_costs) {
3197 log_error("jumbo callbacks for fuel maps are not yet implemented.");
3198 }
3199 return pf_fuel_map_new(parameter);
3200 }
3201
3202 return pf_normal_map_new(parameter);
3203}
3204
3205/************************************************************************/
3209{
3210#ifdef PF_DEBUG
3211 fc_assert_ret(pfm != nullptr);
3212#endif
3213 pfm->destroy(pfm);
3214}
3215
3216/************************************************************************/
3221int pf_map_move_cost(struct pf_map *pfm, struct tile *ptile)
3222{
3223#ifdef PF_DEBUG
3225 fc_assert_ret_val(ptile != nullptr, PF_IMPOSSIBLE_MC);
3226#endif
3227 return pfm->get_move_cost(pfm, ptile);
3228}
3229
3230/************************************************************************/
3237struct pf_path *pf_map_path(struct pf_map *pfm, struct tile *ptile)
3238{
3239#ifdef PF_DEBUG
3240 struct pf_path *path;
3241
3242 fc_assert_ret_val(pfm != nullptr, nullptr);
3243 fc_assert_ret_val(ptile != nullptr, nullptr);
3244 path = pfm->get_path(pfm, ptile);
3245
3246 if (path != nullptr) {
3247#ifndef FREECIV_NDEBUG
3248 const struct pf_parameter *param = pf_map_parameter(pfm);
3249 const struct pf_position *pos = &path->positions[0];
3250
3251 fc_assert(path->length >= 1);
3252 fc_assert(pos->tile == param->start_tile);
3253 fc_assert(pos->moves_left == param->moves_left_initially);
3254 fc_assert(pos->fuel_left == param->fuel_left_initially);
3255#endif /* FREECIV_NDEBUG */
3256 }
3257
3258 return path;
3259#else
3260 return pfm->get_path(pfm, ptile);
3261#endif
3262}
3263
3264/************************************************************************/
3269bool pf_map_position(struct pf_map *pfm, struct tile *ptile,
3270 struct pf_position *pos)
3271{
3272#ifdef PF_DEBUG
3273 fc_assert_ret_val(pfm != nullptr, FALSE);
3274 fc_assert_ret_val(ptile != nullptr, FALSE);
3275#endif
3276 return pfm->get_position(pfm, ptile, pos);
3277}
3278
3279/************************************************************************/
3291{
3292#ifdef PF_DEBUG
3293 fc_assert_ret_val(pfm != nullptr, FALSE);
3294#endif
3295
3296 if (pfm->tile == nullptr) {
3297 /* The end of the iteration was already reached. Don't try to iterate
3298 * again. */
3299 return FALSE;
3300 }
3301
3302 if (!pfm->iterate(pfm)) {
3303 /* End of iteration. */
3304 pfm->tile = nullptr;
3305 return FALSE;
3306 }
3307
3308 return TRUE;
3309}
3310
3311/************************************************************************/
3314struct tile *pf_map_iter(struct pf_map *pfm)
3315{
3316#ifdef PF_DEBUG
3317 fc_assert_ret_val(pfm != nullptr, nullptr);
3318#endif
3319 return pfm->tile;
3320}
3321
3322/************************************************************************/
3327{
3328#ifdef PF_DEBUG
3330 fc_assert_ret_val(pfm->tile != nullptr, PF_IMPOSSIBLE_MC);
3331#endif
3332 return pfm->get_move_cost(pfm, pfm->tile);
3333}
3334
3335/************************************************************************/
3340{
3341#ifdef PF_DEBUG
3342 fc_assert_ret_val(pfm != nullptr, nullptr);
3343 fc_assert_ret_val(pfm->tile != nullptr, nullptr);
3344#endif
3345 return pfm->get_path(pfm, pfm->tile);
3346}
3347
3348/************************************************************************/
3353{
3354#ifdef PF_DEBUG
3355 fc_assert_ret(pfm != nullptr);
3356 fc_assert_ret(pfm->tile != nullptr);
3357#endif
3358 if (!pfm->get_position(pfm, pfm->tile, pos)) {
3359 /* Always fails. */
3360 fc_assert(pfm->get_position(pfm, pfm->tile, pos));
3361 }
3362}
3363
3364/************************************************************************/
3367const struct pf_parameter *pf_map_parameter(const struct pf_map *pfm)
3368{
3369#ifdef PF_DEBUG
3370 fc_assert_ret_val(pfm != nullptr, nullptr);
3371#endif
3372 return &pfm->params;
3373}
3374
3375
3376/* ====================== pf_path public functions ======================= */
3377
3378/************************************************************************/
3382 const struct pf_parameter *param)
3383{
3384 pos->tile = param->start_tile;
3385 pos->turn = 0;
3386 pos->moves_left = param->moves_left_initially;
3387 pos->fuel_left = param->fuel_left_initially;
3388 pos->total_MC = 0;
3389 pos->total_EC = 0;
3390 pos->dir_to_next_pos = direction8_invalid();
3391 pos->dir_to_here = direction8_invalid();
3392}
3393
3394/************************************************************************/
3397static struct pf_path *
3399{
3400 struct pf_path *path = fc_malloc(sizeof(*path));
3401 struct pf_position *pos = fc_malloc(sizeof(*pos));
3402
3403 path->length = 1;
3405 path->positions = pos;
3406 return path;
3407}
3408
3409/************************************************************************/
3413void pf_path_destroy(struct pf_path *path)
3414{
3415 if (path != nullptr) {
3416 free(path->positions);
3417 free(path);
3418 }
3419}
3420
3421/************************************************************************/
3429 const struct pf_path *src_path)
3430{
3431 int dest_end;
3432
3433 fc_assert_ret_val(src_path != nullptr, nullptr);
3434
3435 if (dest_path == nullptr) {
3436 /* Just copy path. */
3437 dest_path = fc_malloc(sizeof(*dest_path));
3438 dest_path->length = src_path->length;
3439 dest_path->positions = fc_malloc(sizeof(*dest_path->positions)
3440 * dest_path->length);
3441 memcpy(dest_path->positions, src_path->positions,
3442 sizeof(*dest_path->positions) * dest_path->length);
3443 return dest_path;
3444 }
3445
3446 dest_end = dest_path->length - 1;
3447 fc_assert(dest_path->positions[dest_end].tile
3448 == src_path->positions[0].tile);
3449 fc_assert(dest_path->positions[dest_end].moves_left
3450 == src_path->positions[0].moves_left);
3451 fc_assert(dest_path->positions[dest_end].fuel_left
3452 == src_path->positions[0].fuel_left);
3453
3454 if (src_path->length == 1) {
3455 return dest_path;
3456 }
3457
3458 dest_path->length = dest_end + src_path->length;
3459 dest_path->positions = fc_realloc(dest_path->positions,
3460 sizeof(*dest_path->positions)
3461 * dest_path->length);
3462 /* Be careful to include the first position of src_path, it contains
3463 * the direction (it is undefined in the last position of dest_path) */
3464 memcpy(dest_path->positions + dest_end, src_path->positions,
3465 sizeof(*dest_path->positions) * src_path->length);
3466
3467 return dest_path;
3468}
3469
3470/************************************************************************/
3477bool pf_path_advance(struct pf_path *path, struct tile *ptile)
3478{
3479 unsigned i;
3480 struct pf_position *new_positions;
3481
3482 for (i = 0; path->positions[i].tile != ptile; i++) {
3483 if (i >= path->length) {
3484 return FALSE;
3485 }
3486 }
3488 path->length -= i;
3489 new_positions = fc_malloc(sizeof(*path->positions) * path->length);
3491 path->length * sizeof(*path->positions));
3492 free(path->positions);
3493 path->positions = new_positions;
3494
3495 return TRUE;
3496}
3497
3498/************************************************************************/
3505bool pf_path_backtrack(struct pf_path *path, struct tile *ptile)
3506{
3507 int i;
3508 struct pf_position *new_positions;
3509
3510 fc_assert_ret_val(path->length > 0, FALSE);
3511
3512 for (i = path->length - 1; path->positions[i].tile != ptile; i--) {
3513 if (i <= 0) {
3514 return FALSE;
3515 }
3516 }
3517
3518 fc_assert_ret_val(i >= 0, FALSE);
3519
3520 path->length = i + 1;
3521 new_positions = fc_malloc(sizeof(*path->positions) * path->length);
3523 path->length * sizeof(*path->positions));
3524 free(path->positions);
3525 path->positions = new_positions;
3526
3527 return TRUE;
3528}
3529
3530/************************************************************************/
3533const struct pf_position *pf_path_last_position(const struct pf_path *path)
3534{
3535 return path->positions + (path->length - 1);
3536}
3537
3538/************************************************************************/
3542void pf_path_print_real(const struct pf_path *path, enum log_level level,
3543 const char *file, const char *function, int line)
3544{
3545 struct pf_position *pos;
3546 int i;
3547
3548 if (path != nullptr) {
3549 do_log(file, function, line, TRUE, level,
3550 "PF: path (at %p) consists of %d positions:",
3551 (void *) path, path->length);
3552 } else {
3553 do_log(file, function, line, TRUE, level, "PF: path is nullptr");
3554 return;
3555 }
3556
3557 for (i = 0, pos = path->positions; i < path->length; i++, pos++) {
3558 do_log(file, function, line, FALSE, level,
3559 "PF: %2d/%2d: (%2d,%2d) dir=%-2s cost=%2d (%2d, %d) EC=%d",
3560 i + 1, path->length, TILE_XY(pos->tile),
3561 dir_get_name(pos->dir_to_next_pos), pos->total_MC,
3562 pos->turn, pos->moves_left, pos->total_EC);
3563 }
3564}
3565
3566
3567/* ===================== pf_reverse_map functions ======================== */
3568
3569/* The path-finding reverse maps are used check the move costs that the
3570 * units needs to reach the start tile. It stores a pf_map for every unit
3571 * type. */
3572
3573static genhash_val_t pf_pos_hash_val(const struct pf_parameter *parameter);
3574static bool pf_pos_hash_cmp(const struct pf_parameter *parameter1,
3575 const struct pf_parameter *parameter2);
3576static void pf_reverse_map_destroy_pos(struct pf_position *pos);
3577static void pf_reverse_map_destroy_param(struct pf_parameter *param);
3578
3579#define SPECHASH_TAG pf_pos
3580#define SPECHASH_IKEY_TYPE struct pf_parameter *
3581#define SPECHASH_IDATA_TYPE struct pf_position *
3582#define SPECHASH_IKEY_VAL pf_pos_hash_val
3583#define SPECHASH_IKEY_COMP pf_pos_hash_cmp
3584#define SPECHASH_IKEY_FREE pf_reverse_map_destroy_param
3585#define SPECHASH_IDATA_FREE pf_reverse_map_destroy_pos
3586#include "spechash.h"
3587
3588/* The reverse map structure. */
3590 struct tile *target_tile; /* Where we want to go. */
3591 int max_turns; /* The maximum of turns. */
3592 struct pf_parameter template; /* Keep a parameter ready for usage. */
3593 struct pf_pos_hash *hash; /* A hash where pf_position are stored. */
3594};
3595
3596/* Here goes all unit type flags which affect the move rules handled by
3597 * the reverse map. */
3602
3603/************************************************************************/
3606static genhash_val_t pf_pos_hash_val(const struct pf_parameter *parameter)
3607{
3608 genhash_val_t result = 0;
3609 size_t b, i;
3610
3611 for (i = 0, b = sizeof(result) * 8 - 1; i < signifiant_flags_num;
3612 i++, b--) {
3613 if (utype_has_flag(parameter->utype, signifiant_flags[i])) {
3614 result |= (1u << b);
3615 }
3616 }
3617
3618 result += (uclass_number(utype_class(parameter->utype))
3619 + (parameter->move_rate << 5)
3620 + (tile_index(parameter->start_tile) << 11));
3621 if (!parameter->omniscience) {
3622 result += parameter->utype->unknown_move_cost << 23;
3623 }
3624
3625 return result;
3626}
3627
3628/************************************************************************/
3631static bool pf_pos_hash_cmp(const struct pf_parameter *parameter1,
3632 const struct pf_parameter *parameter2)
3633{
3634 size_t i;
3635
3636 if (parameter1->start_tile != parameter2->start_tile
3637 || parameter1->move_rate != parameter2->move_rate) {
3638 return FALSE;
3639 }
3640
3641 if (parameter1->utype == parameter2->utype) {
3642 /* Short test. */
3643 return TRUE;
3644 }
3645
3646 if (utype_class(parameter1->utype) != utype_class(parameter2->utype)) {
3647 return FALSE;
3648 }
3649
3650 if (!parameter1->omniscience) {
3651#ifdef PF_DEBUG
3652 fc_assert(!parameter2->omniscience);
3653#endif
3654 if (parameter1->utype->unknown_move_cost
3655 != parameter2->utype->unknown_move_cost) {
3656 return FALSE;
3657 }
3658 }
3659
3660 for (i = 0; i < signifiant_flags_num; i++) {
3663 return FALSE;
3664 }
3665 }
3666
3667 return TRUE;
3668}
3669
3670/************************************************************************/
3674{
3675 free(pos);
3676}
3677
3678/************************************************************************/
3682{
3683 free(param);
3684}
3685
3686/************************************************************************/
3691 const struct player *pplayer,
3692 struct tile *target_tile,
3693 int max_turns, bool omniscient)
3694{
3695 struct pf_reverse_map *pfrm = fc_malloc(sizeof(struct pf_reverse_map));
3696 struct pf_parameter *param = &pfrm->template;
3697
3698 pfrm->target_tile = target_tile;
3699 pfrm->max_turns = max_turns;
3700
3701 /* Initialize the parameter. */
3703 param->owner = pplayer;
3704 param->omniscience = omniscient;
3705 param->map = nmap;
3706
3707 /* Initialize the map hash. */
3708 pfrm->hash = pf_pos_hash_new();
3709
3710 return pfrm;
3711}
3712
3713/************************************************************************/
3718 const struct city *pcity,
3719 const struct player *attacker,
3720 int max_turns, bool omniscient)
3721{
3723}
3724
3725/************************************************************************/
3729{
3730 fc_assert_ret(pfrm != nullptr);
3731
3733 free(pfrm);
3734}
3735
3736/************************************************************************/
3740static const struct pf_position *
3742 const struct pf_parameter *param)
3743{
3744 struct pf_position *pos;
3745 struct pf_map *pfm;
3746 struct pf_parameter *copy;
3747 struct tile *target_tile;
3748 const struct pf_normal_node *lattice;
3749 int max_cost;
3750
3751 /* Check if we already processed something similar. */
3752 if (pf_pos_hash_lookup(pfrm->hash, param, &pos)) {
3753 return pos;
3754 }
3755
3756 /* We didn't. Build map and iterate. */
3757 pfm = pf_normal_map_new(param);
3758 lattice = PF_NORMAL_MAP(pfm)->lattice;
3759 target_tile = pfrm->target_tile;
3760 if (pfrm->max_turns >= 0) {
3761 max_cost = param->move_rate * (pfrm->max_turns + 1);
3762 do {
3763 if (lattice[tile_index(pfm->tile)].cost >= max_cost) {
3764 break;
3765 } else if (pfm->tile == target_tile) {
3766 /* Found our position. Insert in hash, destroy map, and return. */
3767 pos = fc_malloc(sizeof(*pos));
3769 copy = fc_malloc(sizeof(*copy));
3770 *copy = *param;
3771 pf_pos_hash_insert(pfrm->hash, copy, pos);
3773 return pos;
3774 }
3775 } while (pfm->iterate(pfm));
3776 } else {
3777 /* No limit for iteration. */
3778 do {
3779 if (pfm->tile == target_tile) {
3780 /* Found our position. Insert in hash, destroy map, and return. */
3781 pos = fc_malloc(sizeof(*pos));
3783 copy = fc_malloc(sizeof(*copy));
3784 *copy = *param;
3785 pf_pos_hash_insert(pfrm->hash, copy, pos);
3787 return pos;
3788 }
3789 } while (pfm->iterate(pfm));
3790 }
3792
3793 /* Position not found. Let's insert nullptr as position to avoid to iterate
3794 * the map again. */
3795 copy = fc_malloc(sizeof(*copy));
3796 *copy = *param;
3797 pf_pos_hash_insert(pfrm->hash, copy, nullptr);
3798
3799 return nullptr;
3800}
3801
3802/************************************************************************/
3806static inline const struct pf_position *
3808 const struct unit *punit)
3809{
3810 struct pf_parameter *param = &pfrm->template;
3811
3812 /* Fill parameter. */
3813 param->start_tile = unit_tile(punit);
3814 param->move_rate = unit_move_rate(punit);
3815 /* Do not consider punit->moves_left, because this value is usually
3816 * not restored when calling this function. Let's assume the unit will
3817 * have its whole move rate. */
3818 param->moves_left_initially = param->move_rate;
3819 param->utype = unit_type_get(punit);
3820 return pf_reverse_map_pos(pfrm, param);
3821}
3822
3823/************************************************************************/
3827static inline const struct pf_position *
3829 const struct unit_type *punittype,
3830 struct tile *ptile)
3831{
3832 struct pf_parameter *param = &pfrm->template;
3833 const struct player *pplayer = param->owner;
3834 int veteran_level = get_unittype_bonus(pplayer, ptile, punittype,
3835 nullptr, EFT_VETERAN_BUILD);
3836
3839 }
3840
3841 /* Fill parameter. */
3842 param->start_tile = ptile;
3843 param->move_rate = utype_move_rate(punittype, ptile, pplayer,
3845 param->moves_left_initially = param->move_rate;
3846 param->utype = punittype;
3847 return pf_reverse_map_pos(pfrm, param);
3848}
3849
3850/************************************************************************/
3855 const struct unit_type *punittype,
3856 struct tile *ptile)
3857{
3859 ptile);
3860
3861 return (pos != nullptr ? pos->total_MC : PF_IMPOSSIBLE_MC);
3862}
3863
3864/************************************************************************/
3869 const struct unit *punit)
3870{
3872
3873 return (pos != nullptr ? pos->total_MC : PF_IMPOSSIBLE_MC);
3874}
3875
3876/************************************************************************/
3880 const struct unit_type *punittype,
3881 struct tile *ptile,
3882 struct pf_position *pos)
3883{
3885 ptile);
3886
3887 if (mypos != nullptr) {
3888 *pos = *mypos;
3889 return TRUE;
3890 } else {
3891 return FALSE;
3892 }
3893}
3894
3895/************************************************************************/
3899 const struct unit *punit,
3900 struct pf_position *pos)
3901{
3903
3904 if (mypos != nullptr) {
3905 *pos = *mypos;
3906 return TRUE;
3907 } else {
3908 return FALSE;
3909 }
3910}
static struct action * action_by_number(action_id act_id)
Definition actions.h:400
#define city_tile(_pcity_)
Definition city.h:564
char * incite_cost
Definition comments.c:76
struct unit struct city struct unit struct tile * target_tile
Definition dialogs_g.h:57
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
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 cost
Definition dialogs_g.h:74
int get_unittype_bonus(const struct player *pplayer, const struct tile *ptile, const struct unit_type *punittype, const struct action *paction, enum effect_type effect_type)
Definition effects.c:1031
#define DIR8_MAGIC_MAX
Definition fc_types.h:329
unsigned int genhash_val_t
Definition genhash.h:32
static struct tile * pos
Definition finddlg.c:53
void do_log(const char *file, const char *function, int line, bool print_from_where, enum log_level level, const char *message,...)
Definition log.c:514
#define fc_assert_msg(condition, message,...)
Definition log.h:182
#define fc_assert_ret(condition)
Definition log.h:192
#define fc_assert(condition)
Definition log.h:177
#define fc_assert_full(file, function, line, condition, action, message,...)
Definition log.h:154
#define fc_assert_ret_msg(condition, message,...)
Definition log.h:206
#define fc_assert_ret_val(condition, val)
Definition log.h:195
#define log_debug(message,...)
Definition log.h:116
log_level
Definition log.h:29
#define log_error(message,...)
Definition log.h:104
#define fc_assert_ret_val_msg(condition, val, message,...)
Definition log.h:209
const char * dir_get_name(enum direction8 dir)
Definition map.c:1287
struct tile * index_to_tile(const struct civ_map *imap, int mindex)
Definition map.c:471
struct tile * mapstep(const struct civ_map *nmap, const struct tile *ptile, enum direction8 dir)
Definition map.c:384
#define adjc_dir_iterate(nmap, center_tile, itr_tile, dir_itr)
Definition map.h:435
#define DIR_REVERSE(dir)
Definition map.h:589
#define adjc_dir_iterate_end
Definition map.h:439
#define fc_calloc(n, esz)
Definition mem.h:38
#define fc_realloc(ptr, sz)
Definition mem.h:36
#define fc_malloc(sz)
Definition mem.h:34
int unit_move_rate(const struct unit *punit)
Definition movement.c:89
int utype_move_rate(const struct unit_type *utype, const struct tile *ptile, const struct player *pplayer, int veteran_level, int hitpoints)
Definition movement.c:47
#define SINGLE_MOVE
Definition movement.h:26
static struct pf_path * pf_fuel_map_path(struct pf_map *pfm, struct tile *ptile)
bool pf_reverse_map_unit_position(struct pf_reverse_map *pfrm, const struct unit *punit, struct pf_position *pos)
static void pf_danger_map_fill_position(const struct pf_danger_map *pfdm, struct tile *ptile, struct pf_position *pos)
struct pf_path * pf_path_concat(struct pf_path *dest_path, const struct pf_path *src_path)
static bool pf_fuel_map_iterate(struct pf_map *pfm)
static const struct pf_position * pf_reverse_map_pos(struct pf_reverse_map *pfrm, const struct pf_parameter *param)
static struct pf_map * pf_danger_map_new(const struct pf_parameter *parameter)
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)
const struct pf_position * pf_path_last_position(const struct pf_path *path)
void pf_path_destroy(struct pf_path *path)
#define PF_DANGER_MAP(pfm)
static bool pf_normal_node_init(struct pf_normal_map *pfnm, struct pf_normal_node *node, struct tile *ptile, enum pf_move_scope previous_scope)
static struct pf_path * pf_danger_map_construct_path(const struct pf_danger_map *pfdm, struct tile *ptile)
static bool pf_danger_node_init(struct pf_danger_map *pfdm, struct pf_danger_node *node, struct tile *ptile, enum pf_move_scope previous_scope)
static const size_t signifiant_flags_num
bool pf_path_backtrack(struct pf_path *path, struct tile *ptile)
static void pf_fuel_finalize_position_base(const struct pf_parameter *param, struct pf_position *pos, int cost, int moves_left)
static int pf_normal_map_move_cost(struct pf_map *pfm, struct tile *ptile)
static int pf_fuel_map_fill_cost_for_full_moves(const struct pf_parameter *param, int cost, int moves_left)
struct pf_map * pf_map_new(const struct pf_parameter *parameter)
static const struct pf_position * pf_reverse_map_unit_pos(struct pf_reverse_map *pfrm, const struct unit *punit)
static bool pf_fuel_map_position(struct pf_map *pfm, struct tile *ptile, struct pf_position *pos)
static void pf_fuel_map_fill_position(const struct pf_fuel_map *pffm, struct tile *ptile, struct pf_position *pos)
struct pf_path * pf_map_path(struct pf_map *pfm, struct tile *ptile)
bool pf_map_iterate(struct pf_map *pfm)
static void pf_fuel_map_create_segment(struct pf_fuel_map *pffm, struct tile *ptile, struct pf_fuel_node *node)
#define PF_MAP(pfm)
static bool pf_pos_hash_cmp(const struct pf_parameter *parameter1, const struct pf_parameter *parameter2)
bool pf_map_position(struct pf_map *pfm, struct tile *ptile, struct pf_position *pos)
static int pf_move_rate(const struct pf_parameter *param)
void pf_map_iter_position(struct pf_map *pfm, struct pf_position *pos)
int pf_map_iter_move_cost(struct pf_map *pfm)
static bool pf_jumbo_map_iterate(struct pf_map *pfm)
static int pf_normal_map_adjust_cost(int cost, int moves_left)
static bool pf_normal_map_iterate_until(struct pf_normal_map *pfnm, struct tile *ptile)
static bool pf_fuel_node_init(struct pf_fuel_map *pffm, struct pf_fuel_node *node, struct tile *ptile, enum pf_move_scope previous_scope)
static struct pf_path * pf_danger_map_path(struct pf_map *pfm, struct tile *ptile)
static genhash_val_t pf_pos_hash_val(const struct pf_parameter *parameter)
pf_zoc_type
@ ZOC_MINE
@ ZOC_ALLIED
@ ZOC_NO
static struct pf_map * pf_normal_map_new(const struct pf_parameter *parameter)
static struct pf_path * pf_normal_map_path(struct pf_map *pfm, struct tile *ptile)
static struct pf_fuel_pos * pf_fuel_pos_replace(struct pf_fuel_pos *pos, const struct pf_fuel_node *node)
static struct pf_path * pf_normal_map_construct_path(const struct pf_normal_map *pfnm, struct tile *dest_tile)
static bool pf_danger_map_position(struct pf_map *pfm, struct tile *ptile, struct pf_position *pos)
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)
static int pf_moves_left_initially(const struct pf_parameter *param)
static void pf_reverse_map_destroy_pos(struct pf_position *pos)
static struct pf_fuel_pos * pf_fuel_pos_ref(struct pf_fuel_pos *pos)
static int pf_danger_map_move_cost(struct pf_map *pfm, struct tile *ptile)
static bool pf_fuel_map_attack_is_possible(const struct pf_parameter *param, int moves_left, int moves_left_req)
static enum unit_type_flag_id signifiant_flags[]
static void pf_finalize_position(const struct pf_parameter *param, struct pf_position *pos)
void pf_reverse_map_destroy(struct pf_reverse_map *pfrm)
struct pf_path * pf_map_iter_path(struct pf_map *pfm)
static void pf_fuel_finalize_position(struct pf_position *pos, const struct pf_parameter *params, const struct pf_fuel_node *node, const struct pf_fuel_pos *head)
static void pf_normal_map_fill_position(const struct pf_normal_map *pfnm, struct tile *ptile, struct pf_position *pos)
#define PF_FUEL_MAP(pfm)
static int pf_fuel_map_adjust_cost(int cost, int moves_left, int move_rate)
static bool pf_danger_map_iterate(struct pf_map *pfm)
static int pf_fuel_map_move_cost(struct pf_map *pfm, struct tile *ptile)
static void pf_position_fill_start_tile(struct pf_position *pos, const struct pf_parameter *param)
static void pf_fuel_pos_unref(struct pf_fuel_pos *pos)
int pf_reverse_map_unit_move_cost(struct pf_reverse_map *pfrm, const struct unit *punit)
static bool pf_normal_map_position(struct pf_map *pfm, struct tile *ptile, struct pf_position *pos)
static struct pf_path * pf_path_new_to_start_tile(const struct pf_parameter *param)
static int pf_total_CC(const struct pf_parameter *param, unsigned cost, unsigned extra)
static bool pf_fuel_node_dangerous(const struct pf_fuel_node *node)
static void pf_danger_map_destroy(struct pf_map *pfm)
pf_node_status
@ NS_INIT
@ NS_UNINIT
@ NS_PROCESSED
@ NS_WAITING
@ NS_NEW
static bool pf_normal_map_iterate(struct pf_map *pfm)
void pf_map_destroy(struct pf_map *pfm)
static int pf_moves_left(const struct pf_parameter *param, int cost)
struct tile * pf_map_iter(struct pf_map *pfm)
static int pf_danger_map_adjust_cost(const struct pf_parameter *params, int cost, bool to_danger, int moves_left)
struct pf_reverse_map * pf_reverse_map_new(const struct civ_map *nmap, const struct player *pplayer, struct tile *target_tile, int max_turns, bool omniscient)
static const struct pf_position * pf_reverse_map_utype_pos(struct pf_reverse_map *pfrm, const struct unit_type *punittype, struct tile *ptile)
static bool pf_fuel_map_iterate_until(struct pf_fuel_map *pffm, struct tile *ptile)
static void pf_normal_map_destroy(struct pf_map *pfm)
int pf_map_move_cost(struct pf_map *pfm, struct tile *ptile)
bool pf_path_advance(struct pf_path *path, struct tile *ptile)
static int pf_fuel_total_CC(const struct pf_parameter *param, int cost, int extra, int safety)
static void pf_fuel_map_destroy(struct pf_map *pfm)
int pf_reverse_map_utype_move_cost(struct pf_reverse_map *pfrm, const struct unit_type *punittype, struct tile *ptile)
static struct pf_map * pf_fuel_map_new(const struct pf_parameter *parameter)
static struct pf_path * pf_fuel_map_construct_path(const struct pf_fuel_map *pffm, struct tile *ptile)
static bool pf_danger_map_iterate_until(struct pf_danger_map *pfdm, struct tile *ptile)
bool pf_reverse_map_utype_position(struct pf_reverse_map *pfrm, const struct unit_type *punittype, struct tile *ptile, struct pf_position *pos)
#define INITIAL_QUEUE_SIZE
static int pf_danger_map_fill_cost_for_full_moves(const struct pf_parameter *param, int cost)
#define PF_NORMAL_MAP(pfm)
static int pf_turns(const struct pf_parameter *param, int cost)
static int pf_fuel_waited_total_CC(int cost, int safety)
static void pf_reverse_map_destroy_param(struct pf_parameter *param)
static void pf_danger_map_create_segment(struct pf_danger_map *pfdm, struct pf_danger_node *node1)
#define PF_IMPOSSIBLE_MC
pf_action
@ PF_ACTION_ATTACK
@ PF_ACTION_IMPOSSIBLE
@ PF_ACTION_NONE
pf_move_scope
@ PF_MS_TRANSPORT
@ PF_MS_NATIVE
@ PF_MS_NONE
#define PF_TURN_FACTOR
@ TB_NORMAL
@ TB_DONT_LEAVE
@ TB_IGNORE
void pft_fill_reverse_parameter(const struct civ_map *nmap, struct pf_parameter *parameter, struct tile *target_tile)
Definition pf_tools.c:963
bool player_can_invade_tile(const struct player *pplayer, const struct tile *ptile)
Definition player.c:270
struct setting_list * level[OLEVELS_NUM]
Definition settings.c:190
#define ARRAY_SIZE(x)
Definition shared.h:85
#define MIN(x, y)
Definition shared.h:55
#define FC_INFINITY
Definition shared.h:36
SPECPQ_PRIORITY_TYPE priority
Definition specpq.h:86
Definition city.h:318
struct map_index_pq * danger_queue
struct pf_danger_node * lattice
struct map_index_pq * queue
struct pf_map base_map
struct pf_danger_node::pf_danger_pos * danger_segment
unsigned node_known_type
unsigned move_scope
unsigned zoc_number
signed int cost
unsigned short extra_tile
unsigned extra_cost
unsigned behavior
unsigned dir_to_here
struct map_index_pq * waited_queue
struct pf_map base_map
struct map_index_pq * queue
struct pf_fuel_node * lattice
struct pf_fuel_pos * segment
unsigned zoc_number
unsigned extra_cost
unsigned status
unsigned behavior
unsigned node_known_type
unsigned short cost_to_here[DIR8_MAGIC_MAX]
unsigned move_scope
struct pf_fuel_pos * pos
unsigned moves_left
signed int cost
unsigned dir_to_here
unsigned short extra_tile
unsigned action
signed moves_left_req
unsigned dir_to_here
unsigned extra_cost
signed int cost
struct pf_fuel_pos * prev
unsigned moves_left
unsigned ref_count
bool(* get_position)(struct pf_map *pfm, struct tile *ptile, struct pf_position *pos)
int(* get_move_cost)(struct pf_map *pfm, struct tile *ptile)
struct tile * tile
struct pf_path *(* get_path)(struct pf_map *pfm, struct tile *ptile)
bool(* iterate)(struct pf_map *pfm)
void(* destroy)(struct pf_map *pfm)
struct pf_parameter params
struct pf_map base_map
struct pf_normal_node * lattice
struct map_index_pq * queue
unsigned dir_to_here
unsigned zoc_number
unsigned extra_cost
unsigned short extra_tile
unsigned node_known_type
unsigned move_scope
signed int cost
unsigned behavior
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)
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)
struct tile * start_tile
unsigned length
struct pf_position * positions
enum direction8 dir_to_next_pos
struct tile * tile
struct pf_parameter template
struct pf_pos_hash * hash
struct tile * target_tile
Definition tile.h:50
struct unit_list * units
Definition tile.h:58
int unknown_move_cost
Definition unittype.h:525
Definition unit.h:140
int moves_left
Definition unit.h:152
#define TRUE
Definition support.h:46
#define FALSE
Definition support.h:47
#define bool
Definition support.h:71
#define terrain_has_flag(terr, flag)
Definition terrain.h:176
bool tile_has_native_base(const struct tile *ptile, const struct unit_type *punittype)
Definition tile.c:325
enum known_type tile_get_known(const struct tile *ptile, const struct player *pplayer)
Definition tile.c:393
struct city * tile_city(const struct tile *ptile)
Definition tile.c:83
#define tile_index(_pt_)
Definition tile.h:89
known_type
Definition tile.h:35
@ TILE_UNKNOWN
Definition tile.h:36
@ TILE_KNOWN_SEEN
Definition tile.h:38
#define tile_terrain(_tile)
Definition tile.h:115
#define TILE_XY(ptile)
Definition tile.h:43
#define unit_tile(_pu)
Definition unit.h:407
bool utype_action_takes_all_mp(const struct unit_type *putype, struct action *paction)
Definition unittype.c:1216
const struct unit_type * unit_type_get(const struct unit *punit)
Definition unittype.c:126
bool utype_can_freely_unload(const struct unit_type *pcargotype, const struct unit_type *ptranstype)
Definition unittype.c:325
int utype_veteran_levels(const struct unit_type *punittype)
Definition unittype.c:2657
Unit_Class_id uclass_number(const struct unit_class *pclass)
Definition unittype.c:2497
bool utype_can_do_action(const struct unit_type *putype, const action_id act_id)
Definition unittype.c:396
#define utype_class(_t_)
Definition unittype.h:756
static bool utype_has_flag(const struct unit_type *punittype, int flag)
Definition unittype.h:624
#define MAP_INDEX_SIZE