Freeciv-3.2: /fast/freeciv/nightly/S3_2/common/aicore/path_finding.c Source File

Freeciv-3.2

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 converion 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
58 enum pf_node_status {
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
71 enum pf_zoc_type {
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. */
78 struct 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/************************************************************************/
109 static 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/************************************************************************/
123 static inline int pf_move_rate(const struct pf_parameter *param)
124{
125 return param->move_rate * param->fuel;
126}
127
128/************************************************************************/
133 static 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/************************************************************************/
155 static 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/************************************************************************/
172 static 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/************************************************************************/
184 static 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 *
195 pf_path_new_to_start_tile(const struct pf_parameter *param);
196static void pf_position_fill_start_tile(struct pf_position *pos,
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. */
206 struct pf_normal_node {
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. */
228 struct pf_normal_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 *
240 pf_normal_map_check(struct pf_map *pfm, const char *file,
241 const char *function, int line)
242{
243 fc_assert_full(file, function, line,
244 NULL != pfm && PF_NORMAL == pfm->mode,
245 return NULL, "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/************************************************************************/
261 static inline bool pf_normal_node_init(struct pf_normal_map *pfnm,
262 struct pf_normal_node *node,
263 struct tile *ptile,
264 enum pf_move_scope previous_scope)
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 (NULL != params->get_TB) {
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 (NULL != params->get_action) {
315 action = params->get_action(ptile, node_known_type, params);
316 if (PF_ACTION_IMPOSSIBLE == action) {
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 }
324 action = PF_ACTION_NONE;
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 || NULL == params->transported_by_initially)) {
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 (NULL != params->get_zoc
363 && NULL == tile_city(ptile)
364 && !terrain_has_flag(tile_terrain(ptile), TER_NO_ZOC)
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 (NULL != params->get_EC) {
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/************************************************************************/
401 static void pf_normal_map_fill_position(const struct pf_normal_map *pfnm,
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
410 fc_assert_ret_msg(NS_PROCESSED == node->status,
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 *
438pf_normal_map_construct_path(const struct pf_normal_map *pfnm,
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));
443 enum direction8 dir_next = direction8_invalid();
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, NULL,
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--) {
478 pf_normal_map_fill_position(pfnm, ptile, &path->positions[i]);
479 /* fill_position doesn't set direction */
480 path->positions[i].dir_to_next_pos = dir_next;
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/************************************************************************/
497 static int pf_normal_map_adjust_cost(int cost, int moves_left)
498{
499 return MIN(cost, moves_left);
500}
501
502/************************************************************************/
519 static bool pf_jumbo_map_iterate(struct pf_map *pfm)
520{
521 struct pf_normal_map *pfnm = PF_NORMAL_MAP(pfm);
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. */
553 cost1 = PF_IMPOSSIBLE_MC;
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) {
569 map_index_pq_replace(pfnm->queue, tindex1, -priority);
570 } else {
571 map_index_pq_insert(pfnm->queue, tindex1, -priority);
572 }
573 node1->cost = cost1;
574 node1->extra_cost = extra_cost1;
575 node1->status = NS_NEW;
576 node1->dir_to_here = dir;
577 }
578 } adjc_dir_iterate_end;
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/************************************************************************/
613 static bool pf_normal_map_iterate(struct pf_map *pfm)
614{
615 struct pf_normal_map *pfnm = PF_NORMAL_MAP(pfm);
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. */
653 if (!pf_normal_node_init(pfnm, node1, tile1, scope)) {
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 (NULL != params->is_action_possible
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
675 && (utype_action_takes_all_mp(params->utype,
676 action_by_number(ACTION_ATTACK))
677 || utype_can_do_action(params->utype,
678 ACTION_SUICIDE_ATTACK))) {
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 {
683 cost = SINGLE_MOVE;
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 }
694 cost = pf_normal_map_adjust_cost(cost,
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 (NULL != params->get_EC) {
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. */
717 map_index_pq_insert(pfnm->queue, tindex1, -cost_of_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. */
727 map_index_pq_replace(pfnm->queue, tindex1, -cost_of_path);
728 }
729 } adjc_dir_iterate_end;
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/************************************************************************/
752 static inline bool pf_normal_map_iterate_until(struct pf_normal_map *pfnm,
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 (NULL == pf_map_parameter(pfm)->get_costs) {
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/************************************************************************/
788 static int pf_normal_map_move_cost(struct pf_map *pfm, struct tile *ptile)
789{
790 struct pf_normal_map *pfnm = PF_NORMAL_MAP(pfm);
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
796 - pf_move_rate(pf_map_parameter(pfm))
797 + pf_moves_left_initially(pf_map_parameter(pfm)));
798 } else {
799 return PF_IMPOSSIBLE_MC;
800 }
801}
802
803/************************************************************************/
807 static struct pf_path *pf_normal_map_path(struct pf_map *pfm,
808 struct tile *ptile)
809{
810 struct pf_normal_map *pfnm = PF_NORMAL_MAP(pfm);
811
812 if (ptile == pfm->params.start_tile) {
813 return pf_path_new_to_start_tile(pf_map_parameter(pfm));
814 } else if (pf_normal_map_iterate_until(pfnm, ptile)) {
815 return pf_normal_map_construct_path(pfnm, ptile);
816 } else {
817 return NULL;
818 }
819}
820
821/************************************************************************/
826 static bool pf_normal_map_position(struct pf_map *pfm, struct tile *ptile,
827 struct pf_position *pos)
828{
829 struct pf_normal_map *pfnm = PF_NORMAL_MAP(pfm);
830
831 if (ptile == pfm->params.start_tile) {
832 pf_position_fill_start_tile(pos, pf_map_parameter(pfm));
833 return TRUE;
834 } else if (pf_normal_map_iterate_until(pfnm, ptile)) {
835 pf_normal_map_fill_position(pfnm, ptile, pos);
836 return TRUE;
837 } else {
838 return FALSE;
839 }
840}
841
842/************************************************************************/
845 static void pf_normal_map_destroy(struct pf_map *pfm)
846{
847 struct pf_normal_map *pfnm = PF_NORMAL_MAP(pfm);
848
849 free(pfnm->lattice);
850 map_index_pq_destroy(pfnm->queue);
851 free(pfnm);
852}
853
854/************************************************************************/
857 static 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));
874 pfnm->queue = map_index_pq_new(INITIAL_QUEUE_SIZE);
875
876 if (NULL == parameter->get_costs) {
877 /* 'get_MC' callback must be set. */
878 fc_assert_ret_val(NULL != parameter->get_MC, NULL);
879
880 /* 'get_move_scope' callback must be set. */
881 fc_assert_ret_val(parameter->get_move_scope != NULL, NULL);
882 }
883
884 /* Copy parameters. */
885 *params = *parameter;
886
887 /* Initialize virtual function table. */
888 base_map->destroy = pf_normal_map_destroy;
889 base_map->get_move_cost = pf_normal_map_move_cost;
890 base_map->get_path = pf_normal_map_path;
891 base_map->get_position = pf_normal_map_position;
892 if (NULL != params->get_costs) {
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 (NULL == params->get_costs) {
901 if (!pf_normal_node_init(pfnm, node, params->start_tile, PF_MS_NONE)) {
902 /* Always fails. */
903 fc_assert(pf_normal_node_init(pfnm, node, params->start_tile,
904 PF_MS_NONE));
905 }
906
907 if (NULL != params->transported_by_initially) {
908 /* Overwrite. It is safe because we cannot return to start tile with
909 * pf_normal_map. */
910 node->move_scope |= PF_MS_TRANSPORT;
911 if (!utype_can_freely_unload(params->utype,
912 params->transported_by_initially)
913 && NULL == tile_city(params->start_tile)
914 && !tile_has_native_base(params->start_tile,
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;
931 node->dir_to_here = direction8_invalid();
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. */
946 struct pf_danger_node {
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 remeber costs and stuff. */
970 struct pf_danger_pos {
971 signed short cost; /* See comment above. */
972 unsigned extra_cost; /* See comment above. */
973 signed dir_to_here : 4; /* See comment above. */
974 } *danger_segment;
975};
976
977/* Derived structure of struct pf_map. */
978 struct pf_danger_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 *
991 pf_danger_map_check(struct pf_map *pfm, const char *file,
992 const char *function, int line)
993{
994 fc_assert_full(file, function, line,
995 NULL != pfm && PF_DANGER == pfm->mode,
996 return NULL, "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/************************************************************************/
1012 static inline bool pf_danger_node_init(struct pf_danger_map *pfdm,
1013 struct pf_danger_node *node,
1014 struct tile *ptile,
1015 enum pf_move_scope previous_scope)
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 (NULL != params->get_TB) {
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 (NULL != params->get_action) {
1066 action = params->get_action(ptile, node_known_type, params);
1067 if (PF_ACTION_IMPOSSIBLE == action) {
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 }
1075 action = PF_ACTION_NONE;
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 || NULL == params->transported_by_initially)) {
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 (NULL != params->get_zoc
1114 && NULL == tile_city(ptile)
1115 && !terrain_has_flag(tile_terrain(ptile), TER_NO_ZOC)
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 (NULL != params->get_EC) {
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/************************************************************************/
1161 static void pf_danger_map_fill_position(const struct pf_danger_map *pfdm,
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
1170 fc_assert_ret_msg(NS_PROCESSED == node->status
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
1200pf_danger_map_fill_cost_for_full_moves(const struct pf_parameter *param,
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 *
1217pf_danger_map_construct_path(const struct pf_danger_map *pfdm,
1218 struct tile *ptile)
1219{
1220 struct pf_path *path = fc_malloc(sizeof(*path));
1221 enum direction8 dir_next = direction8_invalid();
1222 struct pf_danger_pos *danger_seg = NULL;
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
1232 fc_assert_ret_val_msg(NS_PROCESSED == node->status
1233 || NS_WAITING == node->status, NULL,
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 non-NULL, we are entering a danger segment,
1251 * if it's NULL, we are not on one so danger_seg should be NULL. */
1252 danger_seg = node->danger_segment;
1253 } else {
1254 /* We are in a danger segment. */
1255 dir_next = danger_seg->dir_to_here;
1256 danger_seg++;
1257 }
1258
1259 /* Step backward. */
1260 iter_tile = mapstep(params->map, iter_tile, DIR_REVERSE(dir_next));
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 = NULL;
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,
1287 pf_danger_map_fill_cost_for_full_moves(params, node->cost));
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 != NULL, NULL);
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, NULL);
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 non-NULL, we are entering a danger segment,
1342 * If it's NULL, we are not on one so danger_seg should be NULL. */
1343 danger_seg = node->danger_segment;
1344 } else {
1345 /* We are in a danger segment. */
1346 dir_next = danger_seg->dir_to_here;
1347 danger_seg++;
1348 }
1349
1350 /* 5: Step further back. */
1351 iter_tile = mapstep(params->map, iter_tile, DIR_REVERSE(dir_next));
1352 node = pfdm->lattice + tile_index(iter_tile);
1353 }
1354
1355 fc_assert_msg(FALSE, "Cannot get to the starting point!");
1356 return NULL;
1357}
1358
1359/************************************************************************/
1377 static void pf_danger_map_create_segment(struct pf_danger_map *pfdm,
1378 struct pf_danger_node *node1)
1379{
1380 struct tile *ptile = PF_MAP(pfdm)->tile;
1381 struct pf_danger_node *node = pfdm->lattice + tile_index(ptile);
1382 struct pf_danger_pos *pos;
1383 unsigned length = 0;
1384 unsigned i;
1385 const struct pf_parameter *params = pf_map_parameter(PF_MAP(pfdm));
1386
1387#ifdef PF_DEBUG
1388 if (NULL != node1->danger_segment) {
1389 log_error("Possible memory leak in pf_danger_map_create_segment().");
1390 }
1391#endif /* PF_DEBUG */
1392
1393 /* First iteration for determining segment length */
1394 while (node->is_dangerous && direction8_is_valid(node->dir_to_here)) {
1395 length++;
1396 ptile = mapstep(params->map, ptile, DIR_REVERSE(node->dir_to_here));
1397 node = pfdm->lattice + tile_index(ptile);
1398 }
1399
1400 /* Allocate memory for segment */
1401 node1->danger_segment = fc_malloc(length * sizeof(struct pf_danger_pos));
1402
1403 /* Reset tile and node pointers for main iteration */
1404 ptile = PF_MAP(pfdm)->tile;
1405 node = pfdm->lattice + tile_index(ptile);
1406
1407 /* Now fill the positions */
1408 for (i = 0, pos = node1->danger_segment; i < length; i++, pos++) {
1409 /* Record the direction */
1410 pos->dir_to_here = node->dir_to_here;
1411 pos->cost = node->cost;
1412 pos->extra_cost = node->extra_cost;
1413 if (i == length - 1) {
1414 /* The last dangerous node contains "waiting" info */
1415 node1->waited = node->waited;
1416 }
1417
1418 /* Step further down the tree */
1419 ptile = mapstep(params->map, ptile, DIR_REVERSE(node->dir_to_here));
1420 node = pfdm->lattice + tile_index(ptile);
1421 }
1422
1423#ifdef PF_DEBUG
1424 /* Make sure we reached a safe node or the start point */
1425 fc_assert_ret(!node->is_dangerous || !direction8_is_valid(node->dir_to_here));
1426#endif
1427}
1428
1429/************************************************************************/
1432static inline int
1433pf_danger_map_adjust_cost(const struct pf_parameter *params,
1434 int cost, bool to_danger, int moves_left)
1435{
1436 int mr;
1437
1438 if (cost == PF_IMPOSSIBLE_MC) {
1439 return PF_IMPOSSIBLE_MC;
1440 }
1441
1442 mr = pf_move_rate(params);
1443 cost = MIN(cost, mr);
1444
1445 if (to_danger && cost >= moves_left) {
1446 /* We would have to end the turn on a dangerous tile! */
1447 return PF_IMPOSSIBLE_MC;
1448 } else {
1449 return MIN(cost, moves_left);
1450 }
1451}
1452
1453/************************************************************************/
1491 static bool pf_danger_map_iterate(struct pf_map *pfm)
1492{
1493 struct pf_danger_map *const pfdm = PF_DANGER_MAP(pfm);
1494 const struct pf_parameter *const params = pf_map_parameter(pfm);
1495 struct tile *tile = pfm->tile;
1496 int tindex = tile_index(tile);
1497 struct pf_danger_node *node = pfdm->lattice + tindex;
1498 enum pf_move_scope scope = node->move_scope;
1499
1500 /* The previous position is defined by 'tile' (tile pointer), 'node'
1501 * (the data of the tile for the pf_map), and index (the index of the
1502 * position in the Freeciv map). */
1503
1504 if (!direction8_is_valid(node->dir_to_here)
1505 && NULL != params->transported_by_initially) {
1506#ifdef PF_DEBUG
1507 fc_assert(tile == params->start_tile);
1508#endif
1509 scope |= PF_MS_TRANSPORT;
1510 if (!utype_can_freely_unload(params->utype,
1511 params->transported_by_initially)
1512 && NULL == tile_city(tile)
1513 && !tile_has_native_base(tile, params->transported_by_initially)) {
1514 /* Cannot disembark, don't leave transporter. */
1515 node->behavior = TB_DONT_LEAVE;
1516 }
1517 }
1518
1519 for (;;) {
1520 /* There is no exit from DONT_LEAVE tiles! */
1521 if (node->behavior != TB_DONT_LEAVE
1522 && scope != PF_MS_NONE
1523 && (params->move_rate > 0 || node->cost < 0)) {
1524 /* Cost at tile but taking into account waiting. */
1525 int loc_cost;
1526 if (node->status != NS_WAITING) {
1527 loc_cost = node->cost;
1528 } else {
1529 /* We have waited, so we have full moves. */
1530 loc_cost = pf_danger_map_fill_cost_for_full_moves(params,
1531 node->cost);
1532 }
1533
1534 adjc_dir_iterate(params->map, tile, tile1, dir) {
1535 /* Calculate the cost of every adjacent position and set them in
1536 * the priority queues for next call to pf_danger_map_iterate(). */
1537 int tindex1 = tile_index(tile1);
1538 struct pf_danger_node *node1 = pfdm->lattice + tindex1;
1539 int cost;
1540 int extra = 0;
1541
1542 /* As for the previous position, 'tile1', 'node1' and 'tindex1' are
1543 * defining the adjacent position. */
1544
1545 if (node1->status == NS_PROCESSED || node1->status == NS_WAITING) {
1546 /* This gives 15% speedup. Node status already at step D., E.
1547 * or F. */
1548 continue;
1549 }
1550
1551 /* Initialise target tile if necessary. */
1552 if (node1->status == NS_UNINIT) {
1553 /* Only initialize once. See comment for pf_danger_node_init().
1554 * Node status step A. to B. */
1555 if (!pf_danger_node_init(pfdm, node1, tile1, scope)) {
1556 continue;
1557 }
1558 } else if (TB_IGNORE == node1->behavior) {
1559 /* We cannot enter this tile at all! */
1560 continue;
1561 }
1562
1563 /* Is the move ZOC-ok? */
1564 if (node->zoc_number != ZOC_MINE && node1->zoc_number == ZOC_NO) {
1565 continue;
1566 }
1567
1568 /* Evaluate the cost of the move. */
1569 if (PF_ACTION_NONE != node1->action) {
1570 if (NULL != params->is_action_possible
1571 && !params->is_action_possible(tile, scope, tile1,
1572 node1->action, params)) {
1573 continue;
1574 }
1575 /* action move cost depends on action and unit type. */
1576 if (node1->action == PF_ACTION_ATTACK
1577 && (utype_action_takes_all_mp(params->utype,
1578 action_by_number(ACTION_ATTACK))
1579 || utype_can_do_action(params->utype,
1580 ACTION_SUICIDE_ATTACK))) {
1581 /* Assume that the attack will be a suicide attack even if a
1582 * regular attack may be legal. */
1583 cost = params->move_rate;
1584 } else {
1585 cost = SINGLE_MOVE;
1586 }
1587 } else if (node1->node_known_type == TILE_UNKNOWN) {
1588 cost = params->utype->unknown_move_cost;
1589 } else {
1590 cost = params->get_MC(tile, scope, tile1, node1->move_scope,
1591 params);
1592 }
1593 if (cost == PF_IMPOSSIBLE_MC) {
1594 continue;
1595 }
1596 cost = pf_danger_map_adjust_cost(params, cost, node1->is_dangerous,
1597 pf_moves_left(params, loc_cost));
1598
1599 if (cost == PF_IMPOSSIBLE_MC) {
1600 /* This move is deemed impossible. */
1601 continue;
1602 }
1603
1604 /* Total cost at 'tile1'. */
1605 cost += loc_cost;
1606
1607 /* Evaluate the extra cost of the destination, if it's relevant. */
1608 if (NULL != params->get_EC) {
1609 extra = node1->extra_tile + node->extra_cost;
1610 }
1611
1612 /* Update costs and add to queue, if this is a better route
1613 * to 'tile1'. */
1614 if (!node1->is_dangerous) {
1615 int cost_of_path = pf_total_CC(params, cost, extra);
1616
1617 if (NS_INIT == node1->status
1618 || (cost_of_path < pf_total_CC(params, node1->cost,
1619 node1->extra_cost))) {
1620 /* We are reaching this node for the first time, or we found a
1621 * better route to 'tile1'. Let's register 'tindex1' to the
1622 * priority queue. Node status step B. to C. */
1623 node1->extra_cost = extra;
1624 node1->cost = cost;
1625 node1->dir_to_here = dir;
1626 if (NULL != node1->danger_segment) {
1627 /* Clear the previously recorded path back. */
1628 free(node1->danger_segment);
1629 node1->danger_segment = NULL;
1630 }
1631 if (node->is_dangerous) {
1632 /* We came from a dangerous tile. So we need to record the
1633 * path we came from until the previous safe position is
1634 * found. See comment for pf_danger_map_create_segment(). */
1635 pf_danger_map_create_segment(pfdm, node1);
1636 } else {
1637 /* Maybe clear previously "waited" status of the node. */
1638 node1->waited = FALSE;
1639 }
1640 if (NS_INIT == node1->status) {
1641 node1->status = NS_NEW;
1642 map_index_pq_insert(pfdm->queue, tindex1, -cost_of_path);
1643 } else {
1644#ifdef PF_DEBUG
1645 fc_assert(NS_NEW == node1->status);
1646#endif
1647 map_index_pq_replace(pfdm->queue, tindex1, -cost_of_path);
1648 }
1649 }
1650 } else {
1651 /* The procedure is slightly different for dangerous nodes.
1652 * We will update costs if:
1653 * 1. we are here for the first time;
1654 * 2. we can possibly go further across dangerous area; or
1655 * 3. we can have lower extra and will not overwrite anything
1656 * useful. Node status step B. to C. */
1657 if (node1->status == NS_INIT) {
1658 /* case 1. */
1659 node1->extra_cost = extra;
1660 node1->cost = cost;
1661 node1->dir_to_here = dir;
1662 node1->status = NS_NEW;
1663 node1->waited = (node->status == NS_WAITING);
1664 /* Extra costs of all nodes in danger_queue are equal! */
1665 map_index_pq_insert(pfdm->danger_queue, tindex1, -cost);
1666 } else if ((pf_moves_left(params, cost)
1667 > pf_moves_left(params, node1->cost))
1668 || (node1->status == NS_PROCESSED
1669 && (pf_total_CC(params, cost, extra)
1670 < pf_total_CC(params, node1->cost,
1671 node1->extra_cost)))) {
1672 /* case 2 or 3. */
1673 node1->extra_cost = extra;
1674 node1->cost = cost;
1675 node1->dir_to_here = dir;
1676 node1->status = NS_NEW;
1677 node1->waited = (node->status == NS_WAITING);
1678 /* Extra costs of all nodes in danger_queue are equal! */
1679 map_index_pq_replace(pfdm->danger_queue, tindex1, -cost);
1680 }
1681 }
1682 } adjc_dir_iterate_end;
1683 }
1684
1685 if (NS_WAITING == node->status) {
1686 /* Node status final step E. to F. */
1687#ifdef PF_DEBUG
1688 fc_assert(!node->is_dangerous);
1689#endif
1690 node->status = NS_PROCESSED;
1691 } else if (!node->is_dangerous
1692 && (pf_moves_left(params, node->cost)
1693 < pf_move_rate(params))) {
1694 int fc, cc;
1695 /* Consider waiting at this node. To do it, put it back into queue.
1696 * Node status final step D. to E. */
1697 fc = pf_danger_map_fill_cost_for_full_moves(params, node->cost);
1698 cc = pf_total_CC(params, fc, node->extra_cost);
1699 node->status = NS_WAITING;
1700 map_index_pq_insert(pfdm->queue, tindex, -cc);
1701 }
1702
1703 /* Get the next node (the index with the highest priority). First try
1704 * to get it from danger_queue. */
1705 if (map_index_pq_remove(pfdm->danger_queue, &tindex)) {
1706 /* Change the pf_map iterator and reset data. */
1707 tile = index_to_tile(params->map, tindex);
1708 pfm->tile = tile;
1709 node = pfdm->lattice + tindex;
1710 } else {
1711 /* No dangerous nodes to process, go for a safe one. */
1712 if (!map_index_pq_remove(pfdm->queue, &tindex)) {
1713 /* No more indexes in the priority queue, iteration end. */
1714 return FALSE;
1715 }
1716
1717#ifdef PF_DEBUG
1718 fc_assert(NS_PROCESSED != pfdm->lattice[tindex].status);
1719#endif
1720
1721 /* Change the pf_map iterator and reset data. */
1722 tile = index_to_tile(params->map, tindex);
1723 pfm->tile = tile;
1724 node = pfdm->lattice + tindex;
1725 if (NS_WAITING != node->status) {
1726 /* Node status step C. and D. */
1727#ifdef PF_DEBUG
1728 fc_assert(!node->is_dangerous);
1729#endif
1730 node->status = NS_PROCESSED;
1731 return TRUE;
1732 }
1733 }
1734
1735#ifdef PF_DEBUG
1736 fc_assert(NS_INIT < node-> status);
1737
1738 if (NS_WAITING == node->status) {
1739 /* We've already returned this node once, skip it. */
1740 log_debug("Considering waiting at (%d, %d)", TILE_XY(tile));
1741 } else if (node->is_dangerous) {
1742 /* We don't return dangerous tiles. */
1743 log_debug("Reached dangerous tile (%d, %d)", TILE_XY(tile));
1744 }
1745#endif
1746
1747 scope = node->move_scope;
1748 }
1749
1750 log_error("%s(): internal error.", __FUNCTION__);
1751 return FALSE;
1752}
1753
1754/************************************************************************/
1757 static inline bool pf_danger_map_iterate_until(struct pf_danger_map *pfdm,
1758 struct tile *ptile)
1759{
1760 struct pf_map *pfm = PF_MAP(pfdm);
1761 struct pf_danger_node *node = pfdm->lattice + tile_index(ptile);
1762
1763 /* Start position is handled in every function calling this function. */
1764
1765 if (NS_UNINIT == node->status) {
1766 /* Initialize the node, for doing the following tests. */
1767 if (!pf_danger_node_init(pfdm, node, ptile, PF_MS_NONE)
1768 || node->is_dangerous) {
1769 return FALSE;
1770 }
1771 } else if (TB_IGNORE == node->behavior || node->is_dangerous) {
1772 /* Simpliciation: if we cannot enter this node at all, or we cannot
1773 * stay at this position, don't iterate the whole map. */
1774 return FALSE;
1775 }
1776
1777 while (NS_PROCESSED != node->status && NS_WAITING != node->status) {
1778 if (!pf_map_iterate(pfm)) {
1779 /* All reachable destination have been iterated, 'ptile' is
1780 * unreachable. */
1781 return FALSE;
1782 }
1783 }
1784
1785 return TRUE;
1786}
1787
1788/************************************************************************/
1793 static int pf_danger_map_move_cost(struct pf_map *pfm, struct tile *ptile)
1794{
1795 struct pf_danger_map *pfdm = PF_DANGER_MAP(pfm);
1796
1797 if (ptile == pfm->params.start_tile) {
1798 return 0;
1799 } else if (pf_danger_map_iterate_until(pfdm, ptile)) {
1800 return (pfdm->lattice[tile_index(ptile)].cost
1801 - pf_move_rate(pf_map_parameter(pfm))
1802 + pf_moves_left_initially(pf_map_parameter(pfm)));
1803 } else {
1804 return PF_IMPOSSIBLE_MC;
1805 }
1806}
1807
1808/************************************************************************/
1812 static struct pf_path *pf_danger_map_path(struct pf_map *pfm,
1813 struct tile *ptile)
1814{
1815 struct pf_danger_map *pfdm = PF_DANGER_MAP(pfm);
1816
1817 if (ptile == pfm->params.start_tile) {
1818 return pf_path_new_to_start_tile(pf_map_parameter(pfm));
1819 } else if (pf_danger_map_iterate_until(pfdm, ptile)) {
1820 return pf_danger_map_construct_path(pfdm, ptile);
1821 } else {
1822 return NULL;
1823 }
1824}
1825
1826/************************************************************************/
1831 static bool pf_danger_map_position(struct pf_map *pfm, struct tile *ptile,
1832 struct pf_position *pos)
1833{
1834 struct pf_danger_map *pfdm = PF_DANGER_MAP(pfm);
1835
1836 if (ptile == pfm->params.start_tile) {
1837 pf_position_fill_start_tile(pos, pf_map_parameter(pfm));
1838 return TRUE;
1839 } else if (pf_danger_map_iterate_until(pfdm, ptile)) {
1840 pf_danger_map_fill_position(pfdm, ptile, pos);
1841 return TRUE;
1842 } else {
1843 return FALSE;
1844 }
1845}
1846
1847/************************************************************************/
1850 static void pf_danger_map_destroy(struct pf_map *pfm)
1851{
1852 struct pf_danger_map *pfdm = PF_DANGER_MAP(pfm);
1853 struct pf_danger_node *node;
1854 int i;
1855
1856 /* Need to clean up the dangling danger segments. */
1857 for (i = 0, node = pfdm->lattice; i < MAP_INDEX_SIZE; i++, node++) {
1858 if (node->danger_segment) {
1859 free(node->danger_segment);
1860 }
1861 }
1862 free(pfdm->lattice);
1863 map_index_pq_destroy(pfdm->queue);
1864 map_index_pq_destroy(pfdm->danger_queue);
1865 free(pfdm);
1866}
1867
1868/************************************************************************/
1871 static struct pf_map *pf_danger_map_new(const struct pf_parameter *parameter)
1872{
1873 struct pf_danger_map *pfdm;
1874 struct pf_map *base_map;
1875 struct pf_parameter *params;
1876 struct pf_danger_node *node;
1877
1878 pfdm = fc_malloc(sizeof(*pfdm));
1879 base_map = &pfdm->base_map;
1880 params = &base_map->params;
1881#ifdef PF_DEBUG
1882 /* Set the mode, used for cast check. */
1883 base_map->mode = PF_DANGER;
1884#endif /* PF_DEBUG */
1885
1886 /* Allocate the map. */
1887 pfdm->lattice = fc_calloc(MAP_INDEX_SIZE, sizeof(struct pf_danger_node));
1888 pfdm->queue = map_index_pq_new(INITIAL_QUEUE_SIZE);
1889 pfdm->danger_queue = map_index_pq_new(INITIAL_QUEUE_SIZE);
1890
1891 /* 'get_MC' callback must be set. */
1892 fc_assert_ret_val(parameter->get_MC != NULL, NULL);
1893
1894 /* 'is_pos_dangerous' callback must be set. */
1895 fc_assert_ret_val(parameter->is_pos_dangerous != NULL, NULL);
1896
1897 /* 'get_move_scope' callback must be set. */
1898 fc_assert_ret_val(parameter->get_move_scope != NULL, NULL);
1899
1900 /* Copy parameters */
1901 *params = *parameter;
1902
1903 /* Initialize virtual function table. */
1904 base_map->destroy = pf_danger_map_destroy;
1905 base_map->get_move_cost = pf_danger_map_move_cost;
1906 base_map->get_path = pf_danger_map_path;
1907 base_map->get_position = pf_danger_map_position;
1908 base_map->iterate = pf_danger_map_iterate;
1909
1910 /* Initialise starting node. */
1911 node = pfdm->lattice + tile_index(params->start_tile);
1912 if (!pf_danger_node_init(pfdm, node, params->start_tile, PF_MS_NONE)) {
1913 /* Always fails. */
1914 fc_assert(pf_danger_node_init(pfdm, node, params->start_tile,
1915 PF_MS_NONE));
1916 }
1917
1918 /* NB: do not handle params->transported_by_initially because we want to
1919 * handle only at start, not when crossing over the start tile for a
1920 * second time. See pf_danger_map_iterate(). */
1921
1922 /* Initialise the iterator. */
1923 base_map->tile = params->start_tile;
1924
1925 /* This makes calculations of turn/moves_left more convenient, but we
1926 * need to subtract this value before we return cost to the user. Note
1927 * that cost may be negative if moves_left_initially > move_rate
1928 * (see pf_turns()). */
1929 node->cost = pf_move_rate(params) - pf_moves_left_initially(params);
1930 node->extra_cost = 0;
1931 node->dir_to_here = direction8_invalid();
1932 node->status = (node->is_dangerous ? NS_NEW : NS_PROCESSED);
1933
1934 return PF_MAP(pfdm);
1935}
1936
1937
1938/* ================= Specific pf_fuel_* mode structures ================== */
1939
1940/* Fuel path-finding maps are used for units which need to refuel. Usually
1941 * for air units such as planes or missiles.
1942 *
1943 * A big difference with the danger path-finding maps is that the tiles
1944 * which are not refuel points are not considered as dangerous because the
1945 * server uses to move the units at the end of the turn to refuels points. */
1946
1947struct pf_fuel_pos;
1948
1949/* Node definition. Note we try to have the smallest data as possible. */
1950 struct pf_fuel_node {
1951 /* Note that 'short' here would be followed with padding anyway,
1952 * for alignment reasons, */
1953 signed int cost; /* total_MC. 'cost' may be negative, see comment in
1954 * pf_turns(). */
1955 unsigned extra_cost; /* total_EC. Can be huge, (higher than 'cost'). */
1956 unsigned moves_left : 12; /* Moves left at this position. */
1957 unsigned dir_to_here : 4; /* Direction from which we came. It's
1958 * an 'enum direction8' including
1959 * possibility of direction8_invalid (so we need
1960 * 4 bits) */
1961 unsigned status : 3; /* 'enum pf_node_status' really. */
1962
1963 /* Cached values */
1964 unsigned move_scope : 3; /* 'enum pf_move_scope really. */
1965 unsigned action : 2; /* 'enum pf_action really. */
1966 unsigned node_known_type : 2; /* 'enum known_type' really. */
1967 unsigned behavior : 2; /* 'enum tile_behavior' really. */
1968 unsigned zoc_number : 2; /* 'enum pf_zoc_type' really. */
1969 signed moves_left_req : 13; /* The minimum required moves left to reach
1970 * this tile. It the number of moves we need
1971 * to reach the nearest refuel point. A
1972 * value of 0 means this is a refuel point.
1973 * FIXME: this is right only for units with
1974 * constant move costs! */
1975 unsigned short extra_tile; /* EC */
1976 unsigned short cost_to_here[DIR8_MAGIC_MAX]; /* Step cost[dir to here] */
1977
1978 /* Segment leading across the danger area back to the nearest safe node:
1979 * need to remember costs and stuff. */
1980 struct pf_fuel_pos *pos;
1981 /* Optimal segment to follow to get there (when node is processed). */
1982 struct pf_fuel_pos *segment;
1983};
1984
1985/* We need to remember how we could get to there (until the previous refuel
1986 * point, or start position), because we could re-process the nodes after
1987 * having waiting somewhere. */
1988 struct pf_fuel_pos {
1989 signed int cost;
1990 unsigned extra_cost;
1991 unsigned moves_left : 12;
1992 unsigned dir_to_here : 4;
1993 unsigned ref_count : 4;
1994 struct pf_fuel_pos *prev;
1995};
1996
1997/* Derived structure of struct pf_map. */
1998 struct pf_fuel_map {
1999 struct pf_map base_map; /* Base structure, must be the first! */
2000
2001 struct map_index_pq *queue; /* Queue of nodes we have reached but not
2002 * processed yet (NS_NEW), sorted by their
2003 * total_CC */
2004 struct map_index_pq *waited_queue; /* Queue of nodes to reach farer
2005 * positions after having refueled. */
2006 struct pf_fuel_node *lattice; /* Lattice of nodes */
2007};
2008
2009/* Up-cast macro. */
2010#ifdef PF_DEBUG
2011static inline struct pf_fuel_map *
2012 pf_fuel_map_check(struct pf_map *pfm, const char *file,
2013 const char *function, int line)
2014{
2015 fc_assert_full(file, function, line,
2016 NULL != pfm && PF_FUEL == pfm->mode,
2017 return NULL, "Wrong pf_map to pf_fuel_map conversion.");
2018 return (struct pf_fuel_map *) pfm;
2019}
2020#define PF_FUEL_MAP(pfm) \
2021 pf_fuel_map_check(pfm, __FILE__, __FUNCTION__, __FC_LINE__)
2022#else
2023#define PF_FUEL_MAP(pfm) ((struct pf_fuel_map *) (pfm))
2024#endif /* PF_DEBUG */
2025
2026/* ================= Specific pf_fuel_* mode functions ================== */
2027
2028/************************************************************************/
2031 static inline int pf_fuel_total_CC(const struct pf_parameter *param,
2032 int cost, int extra, int safety)
2033{
2034 return pf_total_CC(param, cost, extra) - safety;
2035}
2036
2037/************************************************************************/
2040 static inline int pf_fuel_waited_total_CC(int cost, int safety)
2041{
2042 return PF_TURN_FACTOR * (cost + 1) - safety - 1;
2043}
2044
2045/************************************************************************/
2050 static inline bool pf_fuel_node_init(struct pf_fuel_map *pffm,
2051 struct pf_fuel_node *node,
2052 struct tile *ptile,
2053 enum pf_move_scope previous_scope)
2054{
2055 const struct pf_parameter *params = pf_map_parameter(PF_MAP(pffm));
2056 enum known_type node_known_type;
2057 enum pf_action action;
2058
2059#ifdef PF_DEBUG
2060 fc_assert(NS_UNINIT == node->status);
2061 /* Else, not a critical problem, but waste of time. */
2062#endif
2063
2064 node->status = NS_INIT;
2065
2066 /* Establish the "known" status of node. */
2067 if (params->omniscience) {
2068 node_known_type = TILE_KNOWN_SEEN;
2069 } else {
2070 node_known_type = tile_get_known(ptile, params->owner);
2071 }
2072 node->node_known_type = node_known_type;
2073
2074 /* Establish the tile behavior. */
2075 if (NULL != params->get_TB) {
2076 node->behavior = params->get_TB(ptile, node_known_type, params);
2077 if (TB_IGNORE == node->behavior && params->start_tile != ptile) {
2078 return FALSE;
2079 }
2080#ifdef ZERO_VARIABLES_FOR_SEARCHING
2081 } else {
2082 /* The default. */
2083 node->behavior = TB_NORMAL;
2084#endif
2085 }
2086
2087 if (TILE_UNKNOWN != node_known_type) {
2088 bool can_disembark;
2089
2090 /* Test if we can invade tile. */
2091 if (!utype_has_flag(params->utype, UTYF_CIVILIAN)
2092 && !player_can_invade_tile(params->owner, ptile)) {
2093 /* Maybe overwrite node behavior. */
2094 if (params->start_tile != ptile) {
2095 node->behavior = TB_IGNORE;
2096 return FALSE;
2097 } else if (TB_NORMAL == node->behavior) {
2098 node->behavior = TB_IGNORE;
2099 }
2100 }
2101
2102 /* Test the possibility to perform an action. */
2103 if (NULL != params->get_action
2104 && PF_ACTION_NONE != (action =
2105 params->get_action(ptile, node_known_type,
2106 params))) {
2107 if (PF_ACTION_IMPOSSIBLE == action) {
2108 /* Maybe overwrite node behavior. */
2109 if (params->start_tile != ptile) {
2110 node->behavior = TB_IGNORE;
2111 return FALSE;
2112 } else if (TB_NORMAL == node->behavior) {
2113 node->behavior = TB_IGNORE;
2114 }
2115 action = PF_ACTION_NONE;
2116 } else if (TB_DONT_LEAVE != node->behavior) {
2117 /* Overwrite node behavior. */
2118 node->behavior = TB_DONT_LEAVE;
2119 }
2120 node->action = action;
2121#ifdef ZERO_VARIABLES_FOR_SEARCHING
2122 node->moves_left_req = 0; /* Attack is always possible theorically. */
2123#endif
2124 } else {
2125#ifdef ZERO_VARIABLES_FOR_SEARCHING
2126 /* Nodes are allocated by fc_calloc(), so should be already set to
2127 * 0. */
2128 node->action = PF_ACTION_NONE;
2129#endif
2130 node->moves_left_req =
2131 params->get_moves_left_req(ptile, node_known_type, params);
2132 if (PF_IMPOSSIBLE_MC == node->moves_left_req) {
2133 /* Overwrite node behavior. */
2134 if (params->start_tile == ptile) {
2135 node->behavior = TB_DONT_LEAVE;
2136 } else {
2137 node->behavior = TB_IGNORE;
2138 return FALSE;
2139 }
2140 }
2141 }
2142
2143 /* Test the possibility to move from/to 'ptile'. */
2144 node->move_scope = params->get_move_scope(ptile, &can_disembark,
2145 previous_scope, params);
2146 if (PF_MS_NONE == node->move_scope
2147 && PF_ACTION_NONE == node->action
2148 && params->ignore_none_scopes) {
2149 /* Maybe overwrite node behavior. */
2150 if (params->start_tile != ptile) {
2151 node->behavior = TB_IGNORE;
2152 return FALSE;
2153 } else if (TB_NORMAL == node->behavior) {
2154 node->behavior = TB_IGNORE;
2155 }
2156 } else if (PF_MS_TRANSPORT == node->move_scope
2157 && !can_disembark
2158 && (params->start_tile != ptile
2159 || NULL == params->transported_by_initially)) {
2160 /* Overwrite node behavior. */
2161 node->behavior = TB_DONT_LEAVE;
2162 }
2163
2164 /* ZOC_MINE means can move unrestricted from/into it, ZOC_ALLIED means
2165 * can move unrestricted into it, but not necessarily from it. */
2166 if (NULL != params->get_zoc
2167 && NULL == tile_city(ptile)
2168 && !terrain_has_flag(tile_terrain(ptile), TER_NO_ZOC)
2169 && !params->get_zoc(params->owner, ptile, params->map)) {
2170 node->zoc_number = (0 < unit_list_size(ptile->units)
2171 ? ZOC_ALLIED : ZOC_NO);
2172#ifdef ZERO_VARIABLES_FOR_SEARCHING
2173 } else {
2174 /* Nodes are allocated by fc_calloc(), so should be already set to
2175 * 0. */
2176 node->zoc_number = ZOC_MINE;
2177#endif
2178 }
2179 } else {
2180 node->moves_left_req =
2181 params->get_moves_left_req(ptile, node_known_type, params);
2182 if (PF_IMPOSSIBLE_MC == node->moves_left_req) {
2183 /* Overwrite node behavior. */
2184 if (params->start_tile == ptile) {
2185 node->behavior = TB_DONT_LEAVE;
2186 } else {
2187 node->behavior = TB_IGNORE;
2188 return FALSE;
2189 }
2190 }
2191
2192 node->move_scope = PF_MS_NATIVE;
2193#ifdef ZERO_VARIABLES_FOR_SEARCHING
2194 /* Nodes are allocated by fc_calloc(), so should be already set to 0. */
2195 node->action = PF_ACTION_NONE;
2196 node->zoc_number = ZOC_MINE;
2197#endif
2198 }
2199
2200 /* Evaluate the extra cost of the destination. */
2201 if (NULL != params->get_EC) {
2202 node->extra_tile = params->get_EC(ptile, node_known_type, params);
2203#ifdef ZERO_VARIABLES_FOR_SEARCHING
2204 } else {
2205 /* Nodes are allocated by fc_calloc(), so should be already set to 0. */
2206 node->extra_tile = 0;
2207#endif
2208 }
2209
2210#ifdef ZERO_VARIABLES_FOR_SEARCHING
2211 /* Nodes are allocated by fc_calloc(), so should be already set to 0. */
2212 node->pos = NULL;
2213 node->segment = NULL;
2214#endif
2215
2216 return TRUE;
2217}
2218
2219/************************************************************************/
2222 static inline bool pf_fuel_node_dangerous(const struct pf_fuel_node *node)
2223{
2224 return (NULL == node->pos
2225 || (node->pos->moves_left < node->moves_left_req
2226 && PF_ACTION_NONE == node->action));
2227}
2228
2229/************************************************************************/
2232 static inline struct pf_fuel_pos *pf_fuel_pos_ref(struct pf_fuel_pos *pos)
2233{
2234#ifdef PF_DEBUG
2235 /* Assert we have enough space to store the new count. Maximum is 10
2236 * (node->pos, node->segment, and 8 for other_pos->prev). */
2237 fc_assert(15 > pos->ref_count);
2238#endif
2239 pos->ref_count++;
2240
2241 return pos;
2242}
2243
2244/************************************************************************/
2248 static inline void pf_fuel_pos_unref(struct pf_fuel_pos *pos)
2249{
2250 while (NULL != pos && 0 == --pos->ref_count) {
2251 struct pf_fuel_pos *prev = pos->prev;
2252
2253 free(pos);
2254 pos = prev;
2255 }
2256}
2257
2258/************************************************************************/
2264static inline struct pf_fuel_pos *
2265pf_fuel_pos_replace(struct pf_fuel_pos *pos, const struct pf_fuel_node *node)
2266{
2267 if (NULL == pos) {
2268 pos = fc_malloc(sizeof(*pos));
2269 pos->ref_count = 1;
2270 } else if (1 < pos->ref_count) {
2271 pos->ref_count--;
2272 pos = fc_malloc(sizeof(*pos));
2273 pos->ref_count = 1;
2274 } else {
2275#ifdef PF_DEBUG
2276 fc_assert(1 == pos->ref_count);
2277#endif
2278 pf_fuel_pos_unref(pos->prev);
2279 }
2280 pos->cost = node->cost;
2281 pos->extra_cost = node->extra_cost;
2282 pos->moves_left = node->moves_left;
2283 pos->dir_to_here = node->dir_to_here;
2284 pos->prev = NULL;
2285
2286 return pos;
2287}
2288
2289/************************************************************************/
2292static inline void
2293pf_fuel_finalize_position_base(const struct pf_parameter *param,
2294 struct pf_position *pos,
2295 int cost, int moves_left)
2296{
2297 int move_rate = param->move_rate;
2298
2299 pos->turn = pf_turns(param, cost);
2300 if (move_rate > 0 && param->start_tile != pos->tile) {
2301 pos->fuel_left = moves_left / move_rate;
2302 pos->moves_left = moves_left % move_rate;
2303 } else if (param->start_tile == pos->tile) {
2304 pos->fuel_left = param->fuel_left_initially;
2305 pos->moves_left = param->moves_left_initially;
2306 } else {
2307 pos->fuel_left = param->fuel_left_initially;
2308 pos->moves_left = moves_left;
2309 }
2310}
2311
2312/************************************************************************/
2315static inline void
2316pf_fuel_finalize_position(struct pf_position *pos,
2317 const struct pf_parameter *params,
2318 const struct pf_fuel_node *node,
2319 const struct pf_fuel_pos *head)
2320{
2321 if (head) {
2322 pf_fuel_finalize_position_base(params, pos,
2323 head->cost, head->moves_left);
2324 } else {
2325 pf_fuel_finalize_position_base(params, pos,
2326 node->cost, node->moves_left);
2327 }
2328}
2329
2330/************************************************************************/
2334 static void pf_fuel_map_fill_position(const struct pf_fuel_map *pffm,
2335 struct tile *ptile,
2336 struct pf_position *pos)
2337{
2338 int tindex = tile_index(ptile);
2339 struct pf_fuel_node *node = pffm->lattice + tindex;
2340 struct pf_fuel_pos *head = node->segment;
2341 const struct pf_parameter *params = pf_map_parameter(PF_MAP(pffm));
2342
2343#ifdef PF_DEBUG
2344 fc_assert_ret_msg(NULL != head,
2345 "Unreached destination (%d, %d).", TILE_XY(ptile));
2346#endif /* PF_DEBUG */
2347
2348 pos->tile = ptile;
2349 pos->total_EC = head->extra_cost;
2350 pos->total_MC = (head->cost - pf_move_rate(params)
2351 + pf_moves_left_initially(params));
2352 pos->dir_to_here = head->dir_to_here;
2353 pos->dir_to_next_pos = direction8_invalid(); /* This field does not apply. */
2354 pf_fuel_finalize_position(pos, params, node, head);
2355}
2356
2357/************************************************************************/
2362static inline int
2363pf_fuel_map_fill_cost_for_full_moves(const struct pf_parameter *param,
2364 int cost, int moves_left)
2365{
2366#ifdef PF_DEBUG
2367 fc_assert(0 < param->move_rate);
2368#endif /* PF_DEBUG */
2369 return cost + moves_left % param->move_rate;
2370}
2371
2372/************************************************************************/
2375static struct pf_path *
2376pf_fuel_map_construct_path(const struct pf_fuel_map *pffm,
2377 struct tile *ptile)
2378{
2379 struct pf_path *path = fc_malloc(sizeof(*path));
2380 enum direction8 dir_next = direction8_invalid();
2381 struct pf_fuel_node *node = pffm->lattice + tile_index(ptile);
2382 struct pf_fuel_pos *segment = node->segment;
2383 unsigned length = 1;
2384 struct tile *iter_tile = ptile;
2385 const struct pf_parameter *params = pf_map_parameter(PF_MAP(pffm));
2386 struct pf_position *pos;
2387 int i;
2388
2389#ifdef PF_DEBUG
2390 fc_assert_ret_val_msg(NULL != segment, NULL,
2391 "Unreached destination (%d, %d).",
2392 TILE_XY(ptile));
2393#endif /* PF_DEBUG */
2394
2395 /* First iterate to find path length. */
2396 /* NB: the start point could be reached in the middle of a segment.
2397 * See comment for pf_fuel_map_create_segment(). */
2398 while (direction8_is_valid(segment->dir_to_here)) {
2399 if (node->moves_left_req == 0) {
2400 /* A refuel point. */
2401 if (segment != node->segment) {
2402 length += 2;
2403 segment = node->segment;
2404 } else {
2405 length++;
2406 }
2407 } else {
2408 length++;
2409 }
2410
2411 /* Step backward. */
2412 iter_tile = mapstep(params->map, iter_tile,
2413 DIR_REVERSE(segment->dir_to_here));
2414 node = pffm->lattice + tile_index(iter_tile);
2415 segment = segment->prev;
2416#ifdef PF_DEBUG
2417 fc_assert(NULL != segment);
2418#endif /* PF_DEBUG */
2419 }
2420 if (node->moves_left_req == 0 && segment != node->segment) {
2421 /* We wait at the start point */
2422 length++;
2423 }
2424
2425 /* Allocate memory for path. */
2426 path->positions = fc_malloc(length * sizeof(struct pf_position));
2427 path->length = length;
2428
2429 /* Reset variables for main iteration. */
2430 iter_tile = ptile;
2431 node = pffm->lattice + tile_index(ptile);
2432 segment = node->segment;
2433
2434 for (i = length - 1; i >= 0; i--) {
2435 /* 1: Deal with waiting. */
2436 if (node->moves_left_req == 0 && segment != node->segment) {
2437 /* Waited at _this_ tile, need to record it twice in the
2438 * path. Here we record our state _after_ waiting (e.g.
2439 * full move points). */
2440 pos = path->positions + i;
2441 pos->tile = iter_tile;
2442 pos->total_EC = segment->extra_cost;
2443 pos->turn = pf_turns(params, segment->cost);
2444 pos->total_MC = ((pos->turn - 1) * params->move_rate
2445 + params->moves_left_initially);
2446 pos->moves_left = params->move_rate;
2447 pos->fuel_left = params->fuel;
2448 pos->dir_to_next_pos = dir_next;
2449 dir_next = direction8_invalid();
2450 segment = node->segment;
2451 i--;
2452 if (NULL == segment) {
2453 /* We waited at start tile, then 'node->segment' is not set. */
2454#ifdef PF_DEBUG
2455 fc_assert(iter_tile == params->start_tile);
2456 fc_assert(0 == i);
2457#endif /* PF_DEBUG */
2458 pf_position_fill_start_tile(path->positions, params);
2459 return path;
2460 }
2461 }
2462
2463 /* 2: Fill the current position. */
2464 pos = path->positions + i;
2465 pos->tile = iter_tile;
2466 pos->total_MC = (pf_moves_left_initially(params)
2467 - pf_move_rate(params) + segment->cost);
2468 pos->total_EC = segment->extra_cost;
2469 pos->dir_to_next_pos = dir_next;
2470 pf_fuel_finalize_position(pos, params, node, segment);
2471
2472 /* 3: Check if we finished. */
2473 if (i == 0) {
2474 /* We should be back at the start now! */
2475 fc_assert_ret_val(iter_tile == params->start_tile, NULL);
2476 return path;
2477 }
2478
2479 /* 4: Calculate the next direction. */
2480 dir_next = segment->dir_to_here;
2481
2482 /* 5: Step further back. */
2483 iter_tile = mapstep(params->map, iter_tile, DIR_REVERSE(dir_next));
2484 node = pffm->lattice + tile_index(iter_tile);
2485 segment = segment->prev;
2486#ifdef PF_DEBUG
2487 fc_assert(NULL != segment);
2488#endif /* PF_DEBUG */
2489 }
2490
2491 fc_assert_msg(FALSE, "Cannot get to the starting point!");
2492 return NULL;
2493}
2494
2495/************************************************************************/
2512 static inline void pf_fuel_map_create_segment(struct pf_fuel_map *pffm,
2513 struct tile *ptile,
2514 struct pf_fuel_node *node)
2515{
2516 struct pf_fuel_pos *pos, *next;
2517 const struct pf_parameter *params = pf_map_parameter(PF_MAP(pffm));
2518
2519 pos = pf_fuel_pos_replace(node->pos, node);
2520 node->pos = pos;
2521
2522 /* Iterate until we reach any built segment. */
2523 do {
2524 next = pos;
2525 ptile = mapstep(params->map, ptile, DIR_REVERSE(node->dir_to_here));
2526 node = pffm->lattice + tile_index(ptile);
2527 pos = node->pos;
2528 if (NULL != pos) {
2529 if (pos->cost == node->cost
2530 && pos->dir_to_here == node->dir_to_here
2531 && pos->extra_cost == node->extra_cost
2532 && pos->moves_left == node->moves_left) {
2533 /* Reached an usable segment. */
2534 next->prev = pf_fuel_pos_ref(pos);
2535 break;
2536 }
2537 }
2538 /* Update position. */
2539 pos = pf_fuel_pos_replace(pos, node);
2540 node->pos = pos;
2541 next->prev = pf_fuel_pos_ref(pos);
2542 } while (0 != node->moves_left_req && direction8_is_valid(node->dir_to_here));
2543}
2544
2545/************************************************************************/
2548 static inline int pf_fuel_map_adjust_cost(int cost, int moves_left,
2549 int move_rate)
2550{
2551 if (move_rate > 0) {
2552 int remaining_moves = moves_left % move_rate;
2553
2554 if (remaining_moves == 0) {
2555 remaining_moves = move_rate;
2556 }
2557
2558 return MIN(cost, remaining_moves);
2559 } else {
2560 return MIN(cost, moves_left);
2561 }
2562}
2563
2564/************************************************************************/
2570static inline bool
2571pf_fuel_map_attack_is_possible(const struct pf_parameter *param,
2572 int moves_left, int moves_left_req)
2573{
2574 if (utype_can_do_action(param->utype, ACTION_SUICIDE_ATTACK)) {
2575 /* Case missile */
2576 return TRUE;
2577 } else if (utype_action_takes_all_mp(param->utype,
2578 action_by_number(ACTION_ATTACK))) {
2579 /* Case Bombers */
2580 if (moves_left <= param-> move_rate) {
2581 /* We are in the last turn of fuel, don't attack */
2582 return FALSE;
2583 } else {
2584 return TRUE;
2585 }
2586 } else {
2587 /* Case fighters */
2588 if (moves_left - SINGLE_MOVE < moves_left_req) {
2589 return FALSE;
2590 } else {
2591 return TRUE;
2592 }
2593 }
2594}
2595
2596/************************************************************************/
2631 static bool pf_fuel_map_iterate(struct pf_map *pfm)
2632{
2633 struct pf_fuel_map *const pffm = PF_FUEL_MAP(pfm);
2634 const struct pf_parameter *const params = pf_map_parameter(pfm);
2635 struct tile *tile = pfm->tile;
2636 int tindex = tile_index(tile);
2637 struct pf_fuel_node *node = pffm->lattice + tindex;
2638 enum pf_move_scope scope = node->move_scope;
2639 int priority, waited_priority;
2640 bool waited = FALSE;
2641
2642 /* The previous position is defined by 'tile' (tile pointer), 'node'
2643 * (the data of the tile for the pf_map), and index (the index of the
2644 * position in the Freeciv map). */
2645
2646 if (!direction8_is_valid(node->dir_to_here)
2647 && NULL != params->transported_by_initially) {
2648#ifdef PF_DEBUG
2649 fc_assert(tile == params->start_tile);
2650#endif
2651 scope |= PF_MS_TRANSPORT;
2652 if (!utype_can_freely_unload(params->utype,
2653 params->transported_by_initially)
2654 && NULL == tile_city(tile)
2655 && !tile_has_native_base(tile, params->transported_by_initially)) {
2656 /* Cannot disembark, don't leave transporter. */
2657 node->behavior = TB_DONT_LEAVE;
2658 }
2659 }
2660
2661 for (;;) {
2662 /* There is no exit from DONT_LEAVE tiles! */
2663 if (node->behavior != TB_DONT_LEAVE
2664 && scope != PF_MS_NONE
2665 && (params->move_rate > 0 || node->cost < 0)) {
2666 int loc_cost = node->cost;
2667 int loc_moves_left = node->moves_left;
2668
2669 if (0 == node->moves_left_req
2670 && 0 < params->move_rate
2671 && 0 == loc_moves_left % params->move_rate
2672 && loc_cost >= params->moves_left_initially) {
2673 /* We have implicitly refueled at the end of the turn. Update also
2674 * 'node->moves_left' to ensure to wait there in paths. */
2675 loc_moves_left = pf_move_rate(params);
2676 node->moves_left = loc_moves_left;
2677 }
2678
2679 adjc_dir_iterate(params->map, tile, tile1, dir) {
2680 /* Calculate the cost of every adjacent position and set them in
2681 * the priority queues for next call to pf_fuel_map_iterate(). */
2682 int tindex1 = tile_index(tile1);
2683 struct pf_fuel_node *node1 = pffm->lattice + tindex1;
2684 int cost, extra = 0;
2685 int moves_left;
2686 int cost_of_path, old_cost_of_path;
2687 struct pf_fuel_pos *pos;
2688
2689 /* As for the previous position, 'tile1', 'node1' and 'tindex1' are
2690 * defining the adjacent position. */
2691
2692 /* Non-full fuel tiles can be updated even after being processed. */
2693 if ((NS_PROCESSED == node1->status || NS_WAITING == node1->status)
2694 && 0 == node1->moves_left_req) {
2695 /* This gives 15% speedup. */
2696 continue;
2697 }
2698
2699 /* Initialise target tile if necessary */
2700 if (node1->status == NS_UNINIT) {
2701 /* Only initialize once. See comment for pf_fuel_node_init().
2702 * Node status step A. to B. */
2703 if (!pf_fuel_node_init(pffm, node1, tile1, scope)) {
2704 continue;
2705 }
2706 } else if (TB_IGNORE == node1->behavior) {
2707 /* We cannot enter this tile at all! */
2708 continue;
2709 }
2710
2711 /* Is the move ZOC-ok? */
2712 if (node->zoc_number != ZOC_MINE && node1->zoc_number == ZOC_NO) {
2713 continue;
2714 }
2715
2716 cost = node1->cost_to_here[dir];
2717 if (0 == cost) {
2718 /* Evaluate the cost of the move. */
2719 if (PF_ACTION_NONE != node1->action) {
2720 if (NULL != params->is_action_possible
2721 && !params->is_action_possible(tile, scope, tile1,
2722 node1->action, params)) {
2723 node1->cost_to_here[dir] = PF_IMPOSSIBLE_MC + 2;
2724 continue;
2725 }
2726 /* action move cost depends on action and unit type. */
2727 if (node1->action == PF_ACTION_ATTACK
2728 && (utype_action_takes_all_mp(params->utype,
2729 action_by_number(
2730 ACTION_ATTACK))
2731 || utype_can_do_action(params->utype,
2732 ACTION_SUICIDE_ATTACK))) {
2733 /* Assume that the attack will be a suicide attack even if a
2734 * regular attack may be legal. */
2735 cost = params->move_rate;
2736 } else {
2737 cost = SINGLE_MOVE;
2738 }
2739 } else if (node1->node_known_type == TILE_UNKNOWN) {
2740 cost = params->utype->unknown_move_cost;
2741 } else {
2742 cost = params->get_MC(tile, scope, tile1, node1->move_scope,
2743 params);
2744 }
2745
2746 if (cost == FC_INFINITY) {
2747 /* tile_move_cost_ptrs() uses FC_INFINITY to flag that all
2748 * movement is spent, e.g., when disembarking from transport. */
2749 cost = params->move_rate;
2750 }
2751
2752#ifdef PF_DEBUG
2753 fc_assert(1 << (8 * sizeof(node1->cost_to_here[dir])) > cost + 2);
2754 fc_assert(0 < cost + 2);
2755#endif /* PF_DEBUG */
2756
2757 node1->cost_to_here[dir] = cost + 2;
2758 if (cost == PF_IMPOSSIBLE_MC) {
2759 continue;
2760 }
2761 } else if (cost == PF_IMPOSSIBLE_MC + 2) {
2762 continue;
2763 } else {
2764 cost -= 2;
2765 }
2766
2767 cost = pf_fuel_map_adjust_cost(cost, loc_moves_left,
2768 params->move_rate);
2769
2770 moves_left = loc_moves_left - cost;
2771 if (moves_left < node1->moves_left_req
2772 && (!utype_can_do_action(params->utype, ACTION_SUICIDE_ATTACK)
2773 || 0 > moves_left)) {
2774 /* We don't have enough moves left, but missiles
2775 * can do suicidal attacks. */
2776 continue;
2777 }
2778
2779 if (PF_ACTION_ATTACK == node1->action
2780 && !pf_fuel_map_attack_is_possible(params, loc_moves_left,
2781 node->moves_left_req)) {
2782 /* We wouldn't have enough moves left after attacking. */
2783 continue;
2784 }
2785
2786 /* Total cost at 'tile1' */
2787 cost += loc_cost;
2788
2789 /* Evaluate the extra cost of the destination, if it's relevant. */
2790 if (NULL != params->get_EC) {
2791 extra = node1->extra_tile + node->extra_cost;
2792 }
2793
2794 /* Update costs and add to queue, if this is a better route
2795 * to tile1. Case safe tiles or reached directly without waiting. */
2796 pos = node1->segment;
2797 cost_of_path = pf_fuel_total_CC(params, cost, extra,
2798 moves_left - node1->moves_left_req);
2799 if (node1->status == NS_INIT) {
2800 /* Not calculated yet. */
2801 old_cost_of_path = 0;
2802 } else if (pos) {
2803 /* We have a path to this tile. The default values could have been
2804 * overwritten if we had more moves left to deal with waiting.
2805 * Then, we have to get back the value of this node to calculate
2806 * the cost. */
2807 old_cost_of_path =
2808 pf_fuel_total_CC(params, pos->cost, pos->extra_cost,
2809 pos->moves_left - node1->moves_left_req);
2810 } else {
2811 /* Default cost */
2812 old_cost_of_path =
2813 pf_fuel_total_CC(params, node1->cost, node1->extra_cost,
2814 node1->moves_left - node1->moves_left_req);
2815 }
2816
2817 /* Step 1: We test if this route is the best to this tile, by a
2818 * direct way, not taking in account waiting. */
2819
2820 if (NS_INIT == node1->status
2821 || (node1->status == NS_NEW && cost_of_path < old_cost_of_path)) {
2822 /* We are reaching this node for the first time, or we found a
2823 * better route to 'tile1', or we would have more moves lefts
2824 * at previous position. Let's register 'tindex1' to the
2825 * priority queue. */
2826 node1->extra_cost = extra;
2827 node1->cost = cost;
2828 node1->moves_left = moves_left;
2829 node1->dir_to_here = dir;
2830 /* Always record the segment, including when it is not dangerous
2831 * to move there. */
2832 pf_fuel_map_create_segment(pffm, tile1, node1);
2833 if (NS_INIT == node1->status) {
2834 /* Node status B. to C. */
2835 node1->status = NS_NEW;
2836 map_index_pq_insert(pffm->queue, tindex1, -cost_of_path);
2837 } else {
2838 /* else staying at D. */
2839#ifdef PF_DEBUG
2840 fc_assert(NS_NEW == node1->status);
2841#endif
2842 if (cost_of_path < old_cost_of_path) {
2843 map_index_pq_replace(pffm->queue, tindex1, -cost_of_path);
2844 }
2845 }
2846 continue; /* adjc_dir_iterate() */
2847 }
2848
2849 /* Step 2: We test if this route could open better routes for other
2850 * tiles, if we waited somewhere. */
2851
2852 if (!waited
2853 || NS_NEW == node1->status
2854 || 0 == node1->moves_left_req) {
2855 /* Stops there if:
2856 * 1. we didn't wait to get there ;
2857 * 2. we didn't process yet the node ;
2858 * 3. this is a refuel point. */
2859 continue; /* adjc_dir_iterate() */
2860 }
2861
2862#ifdef PF_DEBUG
2863 fc_assert(NS_PROCESSED == node1->status);
2864#endif
2865
2866 if (moves_left > node1->moves_left
2867 || (moves_left == node1->moves_left
2868 && extra < node1-> extra_cost)) {
2869 /* We will update costs if:
2870 * 1. we would have more moves left than previously on this node.
2871 * 2. we can have lower extra and will not overwrite anything
2872 * useful. */
2873 node1->extra_cost = extra;
2874 node1->cost = cost;
2875 node1->moves_left = moves_left;
2876 node1->dir_to_here = dir;
2877 map_index_pq_insert(pffm->waited_queue, tindex1,
2878 -pf_fuel_waited_total_CC(cost,
2879 moves_left - node1->moves_left_req));
2880 }
2881 } adjc_dir_iterate_end;
2882 }
2883
2884 if (NS_WAITING == node->status) {
2885 /* Node status final step E. to F. */
2886#ifdef PF_DEBUG
2887 fc_assert(0 == node->moves_left_req);
2888#endif
2889 node->status = NS_PROCESSED;
2890 } else if (0 == node->moves_left_req
2891 && PF_ACTION_NONE == node->action
2892 && node->moves_left < pf_move_rate(params)
2893#ifdef PF_DEBUG
2894 && (fc_assert(0 < params->move_rate), 0 < params->move_rate)
2895#endif
2896 && (0 != node->moves_left % params->move_rate
2897 || node->cost < params->moves_left_initially)) {
2898 /* Consider waiting at this node. To do it, put it back into queue.
2899 * Node status final step D. to E. */
2900 node->status = NS_WAITING;
2901 /* The values we use now to calculate waited total_CC
2902 * will be applied to the node after we get it back from the queue
2903 * to get passing-by segments before it without waiting */
2904 map_index_pq_insert(pffm->queue, tindex,
2905 -pf_fuel_waited_total_CC
2906 (pf_fuel_map_fill_cost_for_full_moves(params,
2907 node->cost,
2908 node->moves_left),
2909 pf_move_rate(params)));
2910 }
2911
2912 /* Get the next node (the index with the highest priority). First try
2913 * to get it from waited_queue. */
2914 if (!map_index_pq_priority(pffm->queue, &priority)
2915 || (map_index_pq_priority(pffm->waited_queue, &waited_priority)
2916 && priority < waited_priority)) {
2917 if (!map_index_pq_remove(pffm->waited_queue, &tindex)) {
2918 /* End of the iteration. */
2919 return FALSE;
2920 }
2921
2922 /* Change the pf_map iterator and reset data. */
2923 tile = index_to_tile(params->map, tindex);
2924 pfm->tile = tile;
2925 node = pffm->lattice + tindex;
2926 waited = TRUE;
2927#ifdef PF_DEBUG
2928 fc_assert(0 < node->moves_left_req);
2929 fc_assert(NS_PROCESSED == node->status);
2930#endif
2931 } else {
2932#ifdef PF_DEBUG
2933#ifndef FREECIV_NDEBUG
2934 bool success =
2935#endif
2936 map_index_pq_remove(pffm->queue, &tindex);
2937
2938 fc_assert(success);
2939#else
2940 map_index_pq_remove(pffm->queue, &tindex);
2941#endif
2942
2943 /* Change the pf_map iterator and reset data. */
2944 tile = index_to_tile(params->map, tindex);
2945 pfm->tile = tile;
2946 node = pffm->lattice + tindex;
2947
2948#ifdef PF_DEBUG
2949 fc_assert(NS_PROCESSED != node->status);
2950#endif /* PF_DEBUG */
2951
2952 waited = (NS_WAITING == node->status);
2953 if (waited) {
2954 /* Arrange waiting at the node */
2955 node->cost = pf_fuel_map_fill_cost_for_full_moves(params, node->cost,
2956 node->moves_left);
2957 node->moves_left = pf_move_rate(params);
2958 } else if (!pf_fuel_node_dangerous(node)) {
2959 /* Node status step C. and D. */
2960 node->status = NS_PROCESSED;
2961 node->segment = pf_fuel_pos_ref(node->pos);
2962 return TRUE;
2963 }
2964 }
2965
2966#ifdef PF_DEBUG
2967 fc_assert(NS_INIT < node->status);
2968
2969 if (NS_WAITING == node->status) {
2970 /* We've already returned this node once, skip it. */
2971 log_debug("Considering waiting at (%d, %d)", TILE_XY(tile));
2972 } else if (NS_PROCESSED == node->status) {
2973 /* We've already returned this node once, skip it. */
2974 log_debug("Reprocessing tile (%d, %d)", TILE_XY(tile));
2975 } else if (pf_fuel_node_dangerous(node)) {
2976 /* We don't return dangerous tiles. */
2977 log_debug("Reached dangerous tile (%d, %d)", TILE_XY(tile));
2978 }
2979#endif /* PF_DEBUG */
2980
2981 scope = node->move_scope;
2982 }
2983
2984 log_error("%s(): internal error.", __FUNCTION__);
2985 return FALSE;
2986}
2987
2988/************************************************************************/
2991 static inline bool pf_fuel_map_iterate_until(struct pf_fuel_map *pffm,
2992 struct tile *ptile)
2993{
2994 struct pf_map *pfm = PF_MAP(pffm);
2995 struct pf_fuel_node *node = pffm->lattice + tile_index(ptile);
2996
2997 /* Start position is handled in every function calling this function. */
2998
2999 if (NS_UNINIT == node->status) {
3000 /* Initialize the node, for doing the following tests. */
3001 if (!pf_fuel_node_init(pffm, node, ptile, PF_MS_NONE)) {
3002 return FALSE;
3003 }
3004 } else if (TB_IGNORE == node->behavior) {
3005 /* Simpliciation: if we cannot enter this node at all, don't iterate the
3006 * whole map. */
3007 return FALSE;
3008 }
3009
3010 while (NULL == node->segment) {
3011 if (!pf_map_iterate(pfm)) {
3012 /* All reachable destination have been iterated, 'ptile' is
3013 * unreachable. */
3014 return FALSE;
3015 }
3016 }
3017
3018 return TRUE;
3019}
3020
3021/************************************************************************/
3026 static int pf_fuel_map_move_cost(struct pf_map *pfm, struct tile *ptile)
3027{
3028 struct pf_fuel_map *pffm = PF_FUEL_MAP(pfm);
3029
3030 if (ptile == pfm->params.start_tile) {
3031 return 0;
3032 } else if (pf_fuel_map_iterate_until(pffm, ptile)) {
3033 const struct pf_fuel_node *node = pffm->lattice + tile_index(ptile);
3034
3035 return (node->segment->cost
3036 - pf_move_rate(pf_map_parameter(pfm))
3037 + pf_moves_left_initially(pf_map_parameter(pfm)));
3038 } else {
3039 return PF_IMPOSSIBLE_MC;
3040 }
3041}
3042
3043/************************************************************************/
3047 static struct pf_path *pf_fuel_map_path(struct pf_map *pfm,
3048 struct tile *ptile)
3049{
3050 struct pf_fuel_map *pffm = PF_FUEL_MAP(pfm);
3051
3052 if (ptile == pfm->params.start_tile) {
3053 return pf_path_new_to_start_tile(pf_map_parameter(pfm));
3054 } else if (pf_fuel_map_iterate_until(pffm, ptile)) {
3055 return pf_fuel_map_construct_path(pffm, ptile);
3056 } else {
3057 return NULL;
3058 }
3059}
3060
3061/************************************************************************/
3066 static bool pf_fuel_map_position(struct pf_map *pfm, struct tile *ptile,
3067 struct pf_position *pos)
3068{
3069 struct pf_fuel_map *pffm = PF_FUEL_MAP(pfm);
3070
3071 if (ptile == pfm->params.start_tile) {
3072 pf_position_fill_start_tile(pos, pf_map_parameter(pfm));
3073 return TRUE;
3074 } else if (pf_fuel_map_iterate_until(pffm, ptile)) {
3075 pf_fuel_map_fill_position(pffm, ptile, pos);
3076 return TRUE;
3077 } else {
3078 return FALSE;
3079 }
3080}
3081
3082/************************************************************************/
3085 static void pf_fuel_map_destroy(struct pf_map *pfm)
3086{
3087 struct pf_fuel_map *pffm = PF_FUEL_MAP(pfm);
3088 struct pf_fuel_node *node;
3089 int i;
3090
3091 /* Need to clean up the dangling fuel segments. */
3092 for (i = 0, node = pffm->lattice; i < MAP_INDEX_SIZE; i++, node++) {
3093 pf_fuel_pos_unref(node->pos);
3094 pf_fuel_pos_unref(node->segment);
3095 }
3096 free(pffm->lattice);
3097 map_index_pq_destroy(pffm->queue);
3098 map_index_pq_destroy(pffm->waited_queue);
3099 free(pffm);
3100}
3101
3102/************************************************************************/
3105 static struct pf_map *pf_fuel_map_new(const struct pf_parameter *parameter)
3106{
3107 struct pf_fuel_map *pffm;
3108 struct pf_map *base_map;
3109 struct pf_parameter *params;
3110 struct pf_fuel_node *node;
3111
3112 pffm = fc_malloc(sizeof(*pffm));
3113 base_map = &pffm->base_map;
3114 params = &base_map->params;
3115#ifdef PF_DEBUG
3116 /* Set the mode, used for cast check. */
3117 base_map->mode = PF_FUEL;
3118#endif /* PF_DEBUG */
3119
3120 /* Allocate the map. */
3121 pffm->lattice = fc_calloc(MAP_INDEX_SIZE, sizeof(struct pf_fuel_node));
3122 pffm->queue = map_index_pq_new(INITIAL_QUEUE_SIZE);
3123 pffm->waited_queue = map_index_pq_new(INITIAL_QUEUE_SIZE);
3124
3125 /* 'get_MC' callback must be set. */
3126 fc_assert_ret_val(parameter->get_MC != NULL, NULL);
3127
3128 /* 'get_moves_left_req' callback must be set. */
3129 fc_assert_ret_val(parameter->get_moves_left_req != NULL, NULL);
3130
3131 /* 'get_move_scope' callback must be set. */
3132 fc_assert_ret_val(parameter->get_move_scope != NULL, NULL);
3133
3134 /* Copy parameters. */
3135 *params = *parameter;
3136
3137 /* Initialize virtual function table. */
3138 base_map->destroy = pf_fuel_map_destroy;
3139 base_map->get_move_cost = pf_fuel_map_move_cost;
3140 base_map->get_path = pf_fuel_map_path;
3141 base_map->get_position = pf_fuel_map_position;
3142 base_map->iterate = pf_fuel_map_iterate;
3143
3144 /* Initialise starting node. */
3145 node = pffm->lattice + tile_index(params->start_tile);
3146 if (!pf_fuel_node_init(pffm, node, params->start_tile, PF_MS_NONE)) {
3147 /* Always fails. */
3148 fc_assert(pf_fuel_node_init(pffm, node, params->start_tile,
3149 PF_MS_NONE));
3150 }
3151
3152 /* NB: do not handle params->transported_by_initially because we want to
3153 * handle only at start, not when crossing over the start tile for a
3154 * second time. See pf_danger_map_iterate(). */
3155
3156 /* Initialise the iterator. */
3157 base_map->tile = params->start_tile;
3158
3159 /* This makes calculations of turn/moves_left more convenient, but we
3160 * need to subtract this value before we return cost to the user. Note
3161 * that cost may be negative if moves_left_initially > move_rate
3162 * (see pf_turns()). */
3163 node->moves_left = pf_moves_left_initially(params);
3164 node->cost = pf_move_rate(params) - node->moves_left;
3165 node->extra_cost = 0;
3166 node->dir_to_here = direction8_invalid();
3167 /* Record a segment. We need it for correct paths. */
3168 node->segment
3169 = pf_fuel_pos_ref(node->pos = pf_fuel_pos_replace(NULL, node));
3170 node->status = NS_PROCESSED;
3171
3172 return PF_MAP(pffm);
3173}
3174
3175
3176/* ====================== pf_map public functions ======================= */
3177
3178/************************************************************************/
3182 struct pf_map *pf_map_new(const struct pf_parameter *parameter)
3183{
3184 if (parameter->is_pos_dangerous) {
3185 if (parameter->get_moves_left_req) {
3186 log_error("path finding code cannot deal with dangers "
3187 "and fuel together.");
3188 }
3189 if (parameter->get_costs) {
3190 log_error("jumbo callbacks for danger maps are not yet implemented.");
3191 }
3192 return pf_danger_map_new(parameter);
3193 } else if (parameter->get_moves_left_req) {
3194 if (parameter->get_costs) {
3195 log_error("jumbo callbacks for fuel maps are not yet implemented.");
3196 }
3197 return pf_fuel_map_new(parameter);
3198 }
3199
3200 return pf_normal_map_new(parameter);
3201}
3202
3203/************************************************************************/
3206 void pf_map_destroy(struct pf_map *pfm)
3207{
3208#ifdef PF_DEBUG
3209 fc_assert_ret(NULL != pfm);
3210#endif
3211 pfm->destroy(pfm);
3212}
3213
3214/************************************************************************/
3219 int pf_map_move_cost(struct pf_map *pfm, struct tile *ptile)
3220{
3221#ifdef PF_DEBUG
3222 fc_assert_ret_val(NULL != pfm, PF_IMPOSSIBLE_MC);
3223 fc_assert_ret_val(NULL != ptile, PF_IMPOSSIBLE_MC);
3224#endif
3225 return pfm->get_move_cost(pfm, ptile);
3226}
3227
3228/************************************************************************/
3235 struct pf_path *pf_map_path(struct pf_map *pfm, struct tile *ptile)
3236{
3237#ifdef PF_DEBUG
3238 struct pf_path *path;
3239
3240 fc_assert_ret_val(NULL != pfm, NULL);
3241 fc_assert_ret_val(NULL != ptile, NULL);
3242 path = pfm->get_path(pfm, ptile);
3243
3244 if (path != NULL) {
3245#ifndef FREECIV_NDEBUG
3246 const struct pf_parameter *param = pf_map_parameter(pfm);
3247 const struct pf_position *pos = &path->positions[0];
3248
3249 fc_assert(path->length >= 1);
3250 fc_assert(pos->tile == param->start_tile);
3251 fc_assert(pos->moves_left == param->moves_left_initially);
3252 fc_assert(pos->fuel_left == param->fuel_left_initially);
3253#endif /* FREECIV_NDEBUG */
3254 }
3255
3256 return path;
3257#else
3258 return pfm->get_path(pfm, ptile);
3259#endif
3260}
3261
3262/************************************************************************/
3267 bool pf_map_position(struct pf_map *pfm, struct tile *ptile,
3268 struct pf_position *pos)
3269{
3270#ifdef PF_DEBUG
3271 fc_assert_ret_val(NULL != pfm, FALSE);
3272 fc_assert_ret_val(NULL != ptile, FALSE);
3273#endif
3274 return pfm->get_position(pfm, ptile, pos);
3275}
3276
3277/************************************************************************/
3288 bool pf_map_iterate(struct pf_map *pfm)
3289{
3290#ifdef PF_DEBUG
3291 fc_assert_ret_val(NULL != pfm, FALSE);
3292#endif
3293
3294 if (NULL == pfm->tile) {
3295 /* The end of the iteration was already reached. Don't try to iterate
3296 * again. */
3297 return FALSE;
3298 }
3299
3300 if (!pfm->iterate(pfm)) {
3301 /* End of iteration. */
3302 pfm->tile = NULL;
3303 return FALSE;
3304 }
3305
3306 return TRUE;
3307}
3308
3309/************************************************************************/
3312 struct tile *pf_map_iter(struct pf_map *pfm)
3313{
3314#ifdef PF_DEBUG
3315 fc_assert_ret_val(NULL != pfm, NULL);
3316#endif
3317 return pfm->tile;
3318}
3319
3320/************************************************************************/
3324 int pf_map_iter_move_cost(struct pf_map *pfm)
3325{
3326#ifdef PF_DEBUG
3327 fc_assert_ret_val(NULL != pfm, PF_IMPOSSIBLE_MC);
3328 fc_assert_ret_val(NULL != pfm->tile, PF_IMPOSSIBLE_MC);
3329#endif
3330 return pfm->get_move_cost(pfm, pfm->tile);
3331}
3332
3333/************************************************************************/
3337 struct pf_path *pf_map_iter_path(struct pf_map *pfm)
3338{
3339#ifdef PF_DEBUG
3340 fc_assert_ret_val(NULL != pfm, NULL);
3341 fc_assert_ret_val(NULL != pfm->tile, NULL);
3342#endif
3343 return pfm->get_path(pfm, pfm->tile);
3344}
3345
3346/************************************************************************/
3350 void pf_map_iter_position(struct pf_map *pfm, struct pf_position *pos)
3351{
3352#ifdef PF_DEBUG
3353 fc_assert_ret(NULL != pfm);
3354 fc_assert_ret(NULL != pfm->tile);
3355#endif
3356 if (!pfm->get_position(pfm, pfm->tile, pos)) {
3357 /* Always fails. */
3358 fc_assert(pfm->get_position(pfm, pfm->tile, pos));
3359 }
3360}
3361
3362/************************************************************************/
3365 const struct pf_parameter *pf_map_parameter(const struct pf_map *pfm)
3366{
3367#ifdef PF_DEBUG
3368 fc_assert_ret_val(NULL != pfm, NULL);
3369#endif
3370 return &pfm->params;
3371}
3372
3373
3374/* ====================== pf_path public functions ======================= */
3375
3376/************************************************************************/
3379 static void pf_position_fill_start_tile(struct pf_position *pos,
3380 const struct pf_parameter *param)
3381{
3382 pos->tile = param->start_tile;
3383 pos->turn = 0;
3384 pos->moves_left = param->moves_left_initially;
3385 pos->fuel_left = param->fuel_left_initially;
3386 pos->total_MC = 0;
3387 pos->total_EC = 0;
3388 pos->dir_to_next_pos = direction8_invalid();
3389 pos->dir_to_here = direction8_invalid();
3390}
3391
3392/************************************************************************/
3395static struct pf_path *
3396pf_path_new_to_start_tile(const struct pf_parameter *param)
3397{
3398 struct pf_path *path = fc_malloc(sizeof(*path));
3399 struct pf_position *pos = fc_malloc(sizeof(*pos));
3400
3401 path->length = 1;
3402 pf_position_fill_start_tile(pos, param);
3403 path->positions = pos;
3404 return path;
3405}
3406
3407/************************************************************************/
3411 void pf_path_destroy(struct pf_path *path)
3412{
3413 if (NULL != path) {
3414 free(path->positions);
3415 free(path);
3416 }
3417}
3418
3419/************************************************************************/
3426 struct pf_path *pf_path_concat(struct pf_path *dest_path,
3427 const struct pf_path *src_path)
3428{
3429 int dest_end;
3430
3431 fc_assert_ret_val(src_path != NULL, NULL);
3432
3433 if (dest_path == NULL) {
3434 /* Just copy path. */
3435 dest_path = fc_malloc(sizeof(*dest_path));
3436 dest_path->length = src_path->length;
3437 dest_path->positions = fc_malloc(sizeof(*dest_path->positions)
3438 * dest_path->length);
3439 memcpy(dest_path->positions, src_path->positions,
3440 sizeof(*dest_path->positions) * dest_path->length);
3441 return dest_path;
3442 }
3443
3444 dest_end = dest_path->length - 1;
3445 fc_assert(dest_path->positions[dest_end].tile
3446 == src_path->positions[0].tile);
3447 fc_assert(dest_path->positions[dest_end].moves_left
3448 == src_path->positions[0].moves_left);
3449 fc_assert(dest_path->positions[dest_end].fuel_left
3450 == src_path->positions[0].fuel_left);
3451
3452 if (src_path->length == 1) {
3453 return dest_path;
3454 }
3455
3456 dest_path->length = dest_end + src_path->length;
3457 dest_path->positions = fc_realloc(dest_path->positions,
3458 sizeof(*dest_path->positions)
3459 * dest_path->length);
3460 /* Be careful to include the first position of src_path, it contains
3461 * the direction (it is undefined in the last position of dest_path) */
3462 memcpy(dest_path->positions + dest_end, src_path->positions,
3463 sizeof(*dest_path->positions) * src_path->length);
3464
3465 return dest_path;
3466}
3467
3468/************************************************************************/
3475 bool pf_path_advance(struct pf_path *path, struct tile *ptile)
3476{
3477 unsigned i;
3478 struct pf_position *new_positions;
3479
3480 for (i = 0; path->positions[i].tile != ptile; i++) {
3481 if (i >= path->length) {
3482 return FALSE;
3483 }
3484 }
3485 fc_assert_ret_val(i < path->length, FALSE);
3486 path->length -= i;
3487 new_positions = fc_malloc(sizeof(*path->positions) * path->length);
3488 memcpy(new_positions, path->positions + i,
3489 path->length * sizeof(*path->positions));
3490 free(path->positions);
3491 path->positions = new_positions;
3492
3493 return TRUE;
3494}
3495
3496/************************************************************************/
3503 bool pf_path_backtrack(struct pf_path *path, struct tile *ptile)
3504{
3505 int i;
3506 struct pf_position *new_positions;
3507
3508 fc_assert_ret_val(path->length > 0, FALSE);
3509
3510 for (i = path->length - 1; path->positions[i].tile != ptile; i--) {
3511 if (i <= 0) {
3512 return FALSE;
3513 }
3514 }
3515
3516 fc_assert_ret_val(i >= 0, FALSE);
3517
3518 path->length = i + 1;
3519 new_positions = fc_malloc(sizeof(*path->positions) * path->length);
3520 memcpy(new_positions, path->positions,
3521 path->length * sizeof(*path->positions));
3522 free(path->positions);
3523 path->positions = new_positions;
3524
3525 return TRUE;
3526}
3527
3528/************************************************************************/
3531 const struct pf_position *pf_path_last_position(const struct pf_path *path)
3532{
3533 return path->positions + (path->length - 1);
3534}
3535
3536/************************************************************************/
3540 void pf_path_print_real(const struct pf_path *path, enum log_level level,
3541 const char *file, const char *function, int line)
3542{
3543 struct pf_position *pos;
3544 int i;
3545
3546 if (path) {
3547 do_log(file, function, line, TRUE, level,
3548 "PF: path (at %p) consists of %d positions:",
3549 (void *) path, path->length);
3550 } else {
3551 do_log(file, function, line, TRUE, level, "PF: path is NULL");
3552 return;
3553 }
3554
3555 for (i = 0, pos = path->positions; i < path->length; i++, pos++) {
3556 do_log(file, function, line, FALSE, level,
3557 "PF: %2d/%2d: (%2d,%2d) dir=%-2s cost=%2d (%2d, %d) EC=%d",
3558 i + 1, path->length, TILE_XY(pos->tile),
3559 dir_get_name(pos->dir_to_next_pos), pos->total_MC,
3560 pos->turn, pos->moves_left, pos->total_EC);
3561 }
3562}
3563
3564
3565/* ===================== pf_reverse_map functions ======================== */
3566
3567/* The path-finding reverse maps are used check the move costs that the
3568 * units needs to reach the start tile. It stores a pf_map for every unit
3569 * type. */
3570
3571static genhash_val_t pf_pos_hash_val(const struct pf_parameter *parameter);
3572static bool pf_pos_hash_cmp(const struct pf_parameter *parameter1,
3573 const struct pf_parameter *parameter2);
3574static void pf_reverse_map_destroy_pos(struct pf_position *pos);
3575static void pf_reverse_map_destroy_param(struct pf_parameter *param);
3576
3577#define SPECHASH_TAG pf_pos
3578#define SPECHASH_IKEY_TYPE struct pf_parameter *
3579#define SPECHASH_IDATA_TYPE struct pf_position *
3580#define SPECHASH_IKEY_VAL pf_pos_hash_val
3581#define SPECHASH_IKEY_COMP pf_pos_hash_cmp
3582#define SPECHASH_IKEY_FREE pf_reverse_map_destroy_param
3583#define SPECHASH_IDATA_FREE pf_reverse_map_destroy_pos
3584#include "spechash.h"
3585
3586/* The reverse map structure. */
3587 struct pf_reverse_map {
3588 struct tile *target_tile; /* Where we want to go. */
3589 int max_turns; /* The maximum of turns. */
3590 struct pf_parameter template; /* Keep a parameter ready for usage. */
3591 struct pf_pos_hash *hash; /* A hash where pf_position are stored. */
3592};
3593
3594/* Here goes all unit type flags which affect the move rules handled by
3595 * the reverse map. */
3596 static const enum unit_type_flag_id signifiant_flags[] = {
3597 UTYF_IGTER, UTYF_CIVILIAN, UTYF_COAST_STRICT
3598};
3599 static const size_t signifiant_flags_num = ARRAY_SIZE(signifiant_flags);
3600
3601/************************************************************************/
3604 static genhash_val_t pf_pos_hash_val(const struct pf_parameter *parameter)
3605{
3606 genhash_val_t result = 0;
3607 size_t b, i;
3608
3609 for (i = 0, b = sizeof(result) * 8 - 1; i < signifiant_flags_num;
3610 i++, b--) {
3611 if (utype_has_flag(parameter->utype, signifiant_flags[i])) {
3612 result |= (1u << b);
3613 }
3614 }
3615
3616 result += (uclass_number(utype_class(parameter->utype))
3617 + (parameter->move_rate << 5)
3618 + (tile_index(parameter->start_tile) << 11));
3619 if (!parameter->omniscience) {
3620 result += parameter->utype->unknown_move_cost << 23;
3621 }
3622
3623 return result;
3624}
3625
3626/************************************************************************/
3629 static bool pf_pos_hash_cmp(const struct pf_parameter *parameter1,
3630 const struct pf_parameter *parameter2)
3631{
3632 size_t i;
3633
3634 if (parameter1->start_tile != parameter2->start_tile
3635 || parameter1->move_rate != parameter2->move_rate) {
3636 return FALSE;
3637 }
3638
3639 if (parameter1->utype == parameter2->utype) {
3640 /* Short test. */
3641 return TRUE;
3642 }
3643
3644 if (utype_class(parameter1->utype) != utype_class(parameter2->utype)) {
3645 return FALSE;
3646 }
3647
3648 if (!parameter1->omniscience) {
3649#ifdef PF_DEBUG
3650 fc_assert(!parameter2->omniscience);
3651#endif
3652 if (parameter1->utype->unknown_move_cost
3653 != parameter2->utype->unknown_move_cost) {
3654 return FALSE;
3655 }
3656 }
3657
3658 for (i = 0; i < signifiant_flags_num; i++) {
3659 if (utype_has_flag(parameter1->utype, signifiant_flags[i])
3660 != utype_has_flag(parameter2->utype, signifiant_flags[i])) {
3661 return FALSE;
3662 }
3663 }
3664
3665 return TRUE;
3666}
3667
3668/************************************************************************/
3671 static void pf_reverse_map_destroy_pos(struct pf_position *pos)
3672{
3673 free(pos);
3674}
3675
3676/************************************************************************/
3679 static void pf_reverse_map_destroy_param(struct pf_parameter *param)
3680{
3681 free(param);
3682}
3683
3684/************************************************************************/
3688 struct pf_reverse_map *pf_reverse_map_new(const struct player *pplayer,
3689 struct tile *target_tile,
3690 int max_turns, bool omniscient,
3691 const struct civ_map *nmap)
3692{
3693 struct pf_reverse_map *pfrm = fc_malloc(sizeof(struct pf_reverse_map));
3694 struct pf_parameter *param = &pfrm->template;
3695
3696 pfrm->target_tile = target_tile;
3697 pfrm->max_turns = max_turns;
3698
3699 /* Initialize the parameter. */
3700 pft_fill_reverse_parameter(nmap, param, target_tile);
3701 param->owner = pplayer;
3702 param->omniscience = omniscient;
3703 param->map = nmap;
3704
3705 /* Initialize the map hash. */
3706 pfrm->hash = pf_pos_hash_new();
3707
3708 return pfrm;
3709}
3710
3711/************************************************************************/
3715 struct pf_reverse_map *pf_reverse_map_new_for_city(const struct city *pcity,
3716 const struct player *attacker,
3717 int max_turns, bool omniscient,
3718 const struct civ_map *nmap)
3719{
3720 return pf_reverse_map_new(attacker, city_tile(pcity), max_turns, omniscient,
3721 nmap);
3722}
3723
3724/************************************************************************/
3727 void pf_reverse_map_destroy(struct pf_reverse_map *pfrm)
3728{
3729 fc_assert_ret(NULL != pfrm);
3730
3731 pf_pos_hash_destroy(pfrm->hash);
3732 free(pfrm);
3733}
3734
3735/************************************************************************/
3739static const struct pf_position *
3740pf_reverse_map_pos(struct pf_reverse_map *pfrm,
3741 const struct pf_parameter *param)
3742{
3743 struct pf_position *pos;
3744 struct pf_map *pfm;
3745 struct pf_parameter *copy;
3746 struct tile *target_tile;
3747 const struct pf_normal_node *lattice;
3748 int max_cost;
3749
3750 /* Check if we already processed something similar. */
3751 if (pf_pos_hash_lookup(pfrm->hash, param, &pos)) {
3752 return pos;
3753 }
3754
3755 /* We didn't. Build map and iterate. */
3756 pfm = pf_normal_map_new(param);
3757 lattice = PF_NORMAL_MAP(pfm)->lattice;
3758 target_tile = pfrm->target_tile;
3759 if (pfrm->max_turns >= 0) {
3760 max_cost = param->move_rate * (pfrm->max_turns + 1);
3761 do {
3762 if (lattice[tile_index(pfm->tile)].cost >= max_cost) {
3763 break;
3764 } else if (pfm->tile == target_tile) {
3765 /* Found our position. Insert in hash, destroy map, and return. */
3766 pos = fc_malloc(sizeof(*pos));
3767 pf_normal_map_fill_position(PF_NORMAL_MAP(pfm), target_tile, pos);
3768 copy = fc_malloc(sizeof(*copy));
3769 *copy = *param;
3770 pf_pos_hash_insert(pfrm->hash, copy, pos);
3771 pf_map_destroy(pfm);
3772 return pos;
3773 }
3774 } while (pfm->iterate(pfm));
3775 } else {
3776 /* No limit for iteration. */
3777 do {
3778 if (pfm->tile == target_tile) {
3779 /* Found our position. Insert in hash, destroy map, and return. */
3780 pos = fc_malloc(sizeof(*pos));
3781 pf_normal_map_fill_position(PF_NORMAL_MAP(pfm), target_tile, pos);
3782 copy = fc_malloc(sizeof(*copy));
3783 *copy = *param;
3784 pf_pos_hash_insert(pfrm->hash, copy, pos);
3785 pf_map_destroy(pfm);
3786 return pos;
3787 }
3788 } while (pfm->iterate(pfm));
3789 }
3790 pf_map_destroy(pfm);
3791
3792 /* Position not found. Let's insert NULL as position to avoid to iterate
3793 * the map again. */
3794 copy = fc_malloc(sizeof(*copy));
3795 *copy = *param;
3796 pf_pos_hash_insert(pfrm->hash, copy, NULL);
3797 return NULL;
3798}
3799
3800/************************************************************************/
3804static inline const struct pf_position *
3805pf_reverse_map_unit_pos(struct pf_reverse_map *pfrm,
3806 const struct unit *punit)
3807{
3808 struct pf_parameter *param = &pfrm->template;
3809
3810 /* Fill parameter. */
3811 param->start_tile = unit_tile(punit);
3812 param->move_rate = unit_move_rate(punit);
3813 /* Do not consider punit->moves_left, because this value is usually
3814 * not restored when calling this function. Let's assume the unit will
3815 * have its whole move rate. */
3816 param->moves_left_initially = param->move_rate;
3817 param->utype = unit_type_get(punit);
3818 return pf_reverse_map_pos(pfrm, param);
3819}
3820
3821/************************************************************************/
3825static inline const struct pf_position *
3826pf_reverse_map_utype_pos(struct pf_reverse_map *pfrm,
3827 const struct unit_type *punittype,
3828 struct tile *ptile)
3829{
3830 struct pf_parameter *param = &pfrm->template;
3831 const struct player *pplayer = param->owner;
3832 int veteran_level = get_unittype_bonus(pplayer, ptile, punittype,
3833 NULL, EFT_VETERAN_BUILD);
3834
3835 if (veteran_level >= utype_veteran_levels(punittype)) {
3836 veteran_level = utype_veteran_levels(punittype) - 1;
3837 }
3838
3839 /* Fill parameter. */
3840 param->start_tile = ptile;
3841 param->move_rate = utype_move_rate(punittype, ptile, pplayer,
3842 veteran_level, punittype->hp);
3843 param->moves_left_initially = param->move_rate;
3844 param->utype = punittype;
3845 return pf_reverse_map_pos(pfrm, param);
3846}
3847
3848/************************************************************************/
3852 int pf_reverse_map_utype_move_cost(struct pf_reverse_map *pfrm,
3853 const struct unit_type *punittype,
3854 struct tile *ptile)
3855{
3856 const struct pf_position *pos = pf_reverse_map_utype_pos(pfrm, punittype,
3857 ptile);
3858
3859 return (pos != NULL ? pos->total_MC : PF_IMPOSSIBLE_MC);
3860}
3861
3862/************************************************************************/
3866 int pf_reverse_map_unit_move_cost(struct pf_reverse_map *pfrm,
3867 const struct unit *punit)
3868{
3869 const struct pf_position *pos = pf_reverse_map_unit_pos(pfrm, punit);
3870
3871 return (pos != NULL ? pos->total_MC : PF_IMPOSSIBLE_MC);
3872}
3873
3874/************************************************************************/
3877 bool pf_reverse_map_utype_position(struct pf_reverse_map *pfrm,
3878 const struct unit_type *punittype,
3879 struct tile *ptile,
3880 struct pf_position *pos)
3881{
3882 const struct pf_position *mypos = pf_reverse_map_utype_pos(pfrm, punittype,
3883 ptile);
3884
3885 if (mypos != NULL) {
3886 *pos = *mypos;
3887 return TRUE;
3888 } else {
3889 return FALSE;
3890 }
3891}
3892
3893/************************************************************************/
3896 bool pf_reverse_map_unit_position(struct pf_reverse_map *pfrm,
3897 const struct unit *punit,
3898 struct pf_position *pos)
3899{
3900 const struct pf_position *mypos = pf_reverse_map_unit_pos(pfrm, punit);
3901
3902 if (mypos != NULL) {
3903 *pos = *mypos;
3904 return TRUE;
3905 } else {
3906 return FALSE;
3907 }
3908}
action_by_number
static struct action * action_by_number(action_id act_id)
Definition actions.h:633
bitvector.h
city_tile
#define city_tile(_pcity_)
Definition city.h:564
incite_cost
char * incite_cost
Definition comments.c:74
target_tile
struct unit struct city struct unit struct tile * target_tile
Definition dialogs_g.h:57
punit
struct unit struct city struct unit struct tile struct extra_type const struct act_prob *act_probs int actor_unit_id struct unit struct unit * punit
Definition dialogs_g.h:74
cost
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
get_unittype_bonus
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:1035
DIR8_MAGIC_MAX
#define DIR8_MAGIC_MAX
Definition fc_types.h:474
game.h
genhash_val_t
unsigned int genhash_val_t
Definition genhash.h:32
pos
static struct tile * pos
Definition finddlg.c:53
do_log
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
log.h
fc_assert_msg
#define fc_assert_msg(condition, message,...)
Definition log.h:181
fc_assert_ret
#define fc_assert_ret(condition)
Definition log.h:191
fc_assert
#define fc_assert(condition)
Definition log.h:176
fc_assert_full
#define fc_assert_full(file, function, line, condition, action, message,...)
Definition log.h:153
fc_assert_ret_msg
#define fc_assert_ret_msg(condition, message,...)
Definition log.h:205
fc_assert_ret_val
#define fc_assert_ret_val(condition, val)
Definition log.h:194
log_debug
#define log_debug(message,...)
Definition log.h:115
log_level
log_level
Definition log.h:28
log_error
#define log_error(message,...)
Definition log.h:103
fc_assert_ret_val_msg
#define fc_assert_ret_val_msg(condition, val, message,...)
Definition log.h:208
dir_get_name
const char * dir_get_name(enum direction8 dir)
Definition map.c:1146
index_to_tile
struct tile * index_to_tile(const struct civ_map *imap, int mindex)
Definition map.c:456
mapstep
struct tile * mapstep(const struct civ_map *nmap, const struct tile *ptile, enum direction8 dir)
Definition map.c:371
map.h
adjc_dir_iterate
#define adjc_dir_iterate(nmap, center_tile, itr_tile, dir_itr)
Definition map.h:438
MAP_INDEX_SIZE
#define MAP_INDEX_SIZE
Definition map.h:137
DIR_REVERSE
#define DIR_REVERSE(dir)
Definition map.h:561
adjc_dir_iterate_end
#define adjc_dir_iterate_end
Definition map.h:442
mem.h
fc_calloc
#define fc_calloc(n, esz)
Definition mem.h:38
fc_realloc
#define fc_realloc(ptr, sz)
Definition mem.h:36
fc_malloc
#define fc_malloc(sz)
Definition mem.h:34
unit_move_rate
int unit_move_rate(const struct unit *punit)
Definition movement.c:90
utype_move_rate
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
movement.h
SINGLE_MOVE
#define SINGLE_MOVE
Definition movement.h:26
pf_fuel_map_path
static struct pf_path * pf_fuel_map_path(struct pf_map *pfm, struct tile *ptile)
Definition path_finding.c:3047
pf_reverse_map_unit_position
bool pf_reverse_map_unit_position(struct pf_reverse_map *pfrm, const struct unit *punit, struct pf_position *pos)
Definition path_finding.c:3896
pf_danger_map_fill_position
static void pf_danger_map_fill_position(const struct pf_danger_map *pfdm, struct tile *ptile, struct pf_position *pos)
Definition path_finding.c:1161
pf_path_concat
struct pf_path * pf_path_concat(struct pf_path *dest_path, const struct pf_path *src_path)
Definition path_finding.c:3426
pf_fuel_map_iterate
static bool pf_fuel_map_iterate(struct pf_map *pfm)
Definition path_finding.c:2631
pf_reverse_map_pos
static const struct pf_position * pf_reverse_map_pos(struct pf_reverse_map *pfrm, const struct pf_parameter *param)
Definition path_finding.c:3740
pf_danger_map_new
static struct pf_map * pf_danger_map_new(const struct pf_parameter *parameter)
Definition path_finding.c:1871
pf_reverse_map_new_for_city
struct pf_reverse_map * pf_reverse_map_new_for_city(const struct city *pcity, const struct player *attacker, int max_turns, bool omniscient, const struct civ_map *nmap)
Definition path_finding.c:3715
pf_map_parameter
const struct pf_parameter * pf_map_parameter(const struct pf_map *pfm)
Definition path_finding.c:3365
pf_path_print_real
void pf_path_print_real(const struct pf_path *path, enum log_level level, const char *file, const char *function, int line)
Definition path_finding.c:3540
pf_path_last_position
const struct pf_position * pf_path_last_position(const struct pf_path *path)
Definition path_finding.c:3531
pf_path_destroy
void pf_path_destroy(struct pf_path *path)
Definition path_finding.c:3411
PF_DANGER_MAP
#define PF_DANGER_MAP(pfm)
Definition path_finding.c:1002
pf_normal_node_init
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)
Definition path_finding.c:261
pf_danger_map_construct_path
static struct pf_path * pf_danger_map_construct_path(const struct pf_danger_map *pfdm, struct tile *ptile)
Definition path_finding.c:1217
pf_danger_node_init
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)
Definition path_finding.c:1012
signifiant_flags_num
static const size_t signifiant_flags_num
Definition path_finding.c:3599
pf_path_backtrack
bool pf_path_backtrack(struct pf_path *path, struct tile *ptile)
Definition path_finding.c:3503
pf_fuel_finalize_position_base
static void pf_fuel_finalize_position_base(const struct pf_parameter *param, struct pf_position *pos, int cost, int moves_left)
Definition path_finding.c:2293
pf_normal_map_move_cost
static int pf_normal_map_move_cost(struct pf_map *pfm, struct tile *ptile)
Definition path_finding.c:788
pf_fuel_map_fill_cost_for_full_moves
static int pf_fuel_map_fill_cost_for_full_moves(const struct pf_parameter *param, int cost, int moves_left)
Definition path_finding.c:2363
pf_map_new
struct pf_map * pf_map_new(const struct pf_parameter *parameter)
Definition path_finding.c:3182
pf_reverse_map_unit_pos
static const struct pf_position * pf_reverse_map_unit_pos(struct pf_reverse_map *pfrm, const struct unit *punit)
Definition path_finding.c:3805
pf_fuel_map_position
static bool pf_fuel_map_position(struct pf_map *pfm, struct tile *ptile, struct pf_position *pos)
Definition path_finding.c:3066
pf_fuel_map_fill_position
static void pf_fuel_map_fill_position(const struct pf_fuel_map *pffm, struct tile *ptile, struct pf_position *pos)
Definition path_finding.c:2334
pf_map_path
struct pf_path * pf_map_path(struct pf_map *pfm, struct tile *ptile)
Definition path_finding.c:3235
pf_map_iterate
bool pf_map_iterate(struct pf_map *pfm)
Definition path_finding.c:3288
pf_fuel_map_create_segment
static void pf_fuel_map_create_segment(struct pf_fuel_map *pffm, struct tile *ptile, struct pf_fuel_node *node)
Definition path_finding.c:2512
pf_reverse_map_new
struct pf_reverse_map * pf_reverse_map_new(const struct player *pplayer, struct tile *target_tile, int max_turns, bool omniscient, const struct civ_map *nmap)
Definition path_finding.c:3688
PF_MAP
#define PF_MAP(pfm)
Definition path_finding.c:97
pf_pos_hash_cmp
static bool pf_pos_hash_cmp(const struct pf_parameter *parameter1, const struct pf_parameter *parameter2)
Definition path_finding.c:3629
pf_map_position
bool pf_map_position(struct pf_map *pfm, struct tile *ptile, struct pf_position *pos)
Definition path_finding.c:3267
pf_move_rate
static int pf_move_rate(const struct pf_parameter *param)
Definition path_finding.c:123
pf_map_iter_position
void pf_map_iter_position(struct pf_map *pfm, struct pf_position *pos)
Definition path_finding.c:3350
pf_map_iter_move_cost
int pf_map_iter_move_cost(struct pf_map *pfm)
Definition path_finding.c:3324
pf_jumbo_map_iterate
static bool pf_jumbo_map_iterate(struct pf_map *pfm)
Definition path_finding.c:519
pf_normal_map_adjust_cost
static int pf_normal_map_adjust_cost(int cost, int moves_left)
Definition path_finding.c:497
pf_normal_map_iterate_until
static bool pf_normal_map_iterate_until(struct pf_normal_map *pfnm, struct tile *ptile)
Definition path_finding.c:752
pf_fuel_node_init
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)
Definition path_finding.c:2050
pf_danger_map_path
static struct pf_path * pf_danger_map_path(struct pf_map *pfm, struct tile *ptile)
Definition path_finding.c:1812
pf_pos_hash_val
static genhash_val_t pf_pos_hash_val(const struct pf_parameter *parameter)
Definition path_finding.c:3604
pf_zoc_type
pf_zoc_type
Definition path_finding.c:71
ZOC_MINE
@ ZOC_MINE
Definition path_finding.c:72
ZOC_ALLIED
@ ZOC_ALLIED
Definition path_finding.c:73
ZOC_NO
@ ZOC_NO
Definition path_finding.c:74
pf_normal_map_new
static struct pf_map * pf_normal_map_new(const struct pf_parameter *parameter)
Definition path_finding.c:857
pf_normal_map_path
static struct pf_path * pf_normal_map_path(struct pf_map *pfm, struct tile *ptile)
Definition path_finding.c:807
pf_fuel_pos_replace
static struct pf_fuel_pos * pf_fuel_pos_replace(struct pf_fuel_pos *pos, const struct pf_fuel_node *node)
Definition path_finding.c:2265
pf_normal_map_construct_path
static struct pf_path * pf_normal_map_construct_path(const struct pf_normal_map *pfnm, struct tile *dest_tile)
Definition path_finding.c:438
pf_danger_map_position
static bool pf_danger_map_position(struct pf_map *pfm, struct tile *ptile, struct pf_position *pos)
Definition path_finding.c:1831
pf_moves_left_initially
static int pf_moves_left_initially(const struct pf_parameter *param)
Definition path_finding.c:109
pf_reverse_map_destroy_pos
static void pf_reverse_map_destroy_pos(struct pf_position *pos)
Definition path_finding.c:3671
pf_fuel_pos_ref
static struct pf_fuel_pos * pf_fuel_pos_ref(struct pf_fuel_pos *pos)
Definition path_finding.c:2232
pf_danger_map_move_cost
static int pf_danger_map_move_cost(struct pf_map *pfm, struct tile *ptile)
Definition path_finding.c:1793
pf_fuel_map_attack_is_possible
static bool pf_fuel_map_attack_is_possible(const struct pf_parameter *param, int moves_left, int moves_left_req)
Definition path_finding.c:2571
signifiant_flags
static enum unit_type_flag_id signifiant_flags[]
Definition path_finding.c:3596
pf_finalize_position
static void pf_finalize_position(const struct pf_parameter *param, struct pf_position *pos)
Definition path_finding.c:184
pf_reverse_map_destroy
void pf_reverse_map_destroy(struct pf_reverse_map *pfrm)
Definition path_finding.c:3727
pf_map_iter_path
struct pf_path * pf_map_iter_path(struct pf_map *pfm)
Definition path_finding.c:3337
pf_fuel_finalize_position
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)
Definition path_finding.c:2316
pf_normal_map_fill_position
static void pf_normal_map_fill_position(const struct pf_normal_map *pfnm, struct tile *ptile, struct pf_position *pos)
Definition path_finding.c:401
PF_FUEL_MAP
#define PF_FUEL_MAP(pfm)
Definition path_finding.c:2023
pf_fuel_map_adjust_cost
static int pf_fuel_map_adjust_cost(int cost, int moves_left, int move_rate)
Definition path_finding.c:2548
pf_danger_map_iterate
static bool pf_danger_map_iterate(struct pf_map *pfm)
Definition path_finding.c:1491
pf_fuel_map_move_cost
static int pf_fuel_map_move_cost(struct pf_map *pfm, struct tile *ptile)
Definition path_finding.c:3026
pf_position_fill_start_tile
static void pf_position_fill_start_tile(struct pf_position *pos, const struct pf_parameter *param)
Definition path_finding.c:3379
pf_fuel_pos_unref
static void pf_fuel_pos_unref(struct pf_fuel_pos *pos)
Definition path_finding.c:2248
pf_reverse_map_unit_move_cost
int pf_reverse_map_unit_move_cost(struct pf_reverse_map *pfrm, const struct unit *punit)
Definition path_finding.c:3866
pf_normal_map_position
static bool pf_normal_map_position(struct pf_map *pfm, struct tile *ptile, struct pf_position *pos)
Definition path_finding.c:826
pf_path_new_to_start_tile
static struct pf_path * pf_path_new_to_start_tile(const struct pf_parameter *param)
Definition path_finding.c:3396
pf_total_CC
static int pf_total_CC(const struct pf_parameter *param, unsigned cost, unsigned extra)
Definition path_finding.c:172
pf_fuel_node_dangerous
static bool pf_fuel_node_dangerous(const struct pf_fuel_node *node)
Definition path_finding.c:2222
pf_danger_map_destroy
static void pf_danger_map_destroy(struct pf_map *pfm)
Definition path_finding.c:1850
pf_node_status
pf_node_status
Definition path_finding.c:58
NS_INIT
@ NS_INIT
Definition path_finding.c:61
NS_UNINIT
@ NS_UNINIT
Definition path_finding.c:59
NS_PROCESSED
@ NS_PROCESSED
Definition path_finding.c:68
NS_WAITING
@ NS_WAITING
Definition path_finding.c:64
NS_NEW
@ NS_NEW
Definition path_finding.c:63
pf_normal_map_iterate
static bool pf_normal_map_iterate(struct pf_map *pfm)
Definition path_finding.c:613
pf_map_destroy
void pf_map_destroy(struct pf_map *pfm)
Definition path_finding.c:3206
pf_moves_left
static int pf_moves_left(const struct pf_parameter *param, int cost)
Definition path_finding.c:155
pf_map_iter
struct tile * pf_map_iter(struct pf_map *pfm)
Definition path_finding.c:3312
pf_danger_map_adjust_cost
static int pf_danger_map_adjust_cost(const struct pf_parameter *params, int cost, bool to_danger, int moves_left)
Definition path_finding.c:1433
pf_reverse_map_utype_pos
static const struct pf_position * pf_reverse_map_utype_pos(struct pf_reverse_map *pfrm, const struct unit_type *punittype, struct tile *ptile)
Definition path_finding.c:3826
pf_fuel_map_iterate_until
static bool pf_fuel_map_iterate_until(struct pf_fuel_map *pffm, struct tile *ptile)
Definition path_finding.c:2991
pf_normal_map_destroy
static void pf_normal_map_destroy(struct pf_map *pfm)
Definition path_finding.c:845
pf_map_move_cost
int pf_map_move_cost(struct pf_map *pfm, struct tile *ptile)
Definition path_finding.c:3219
pf_path_advance
bool pf_path_advance(struct pf_path *path, struct tile *ptile)
Definition path_finding.c:3475
pf_fuel_total_CC
static int pf_fuel_total_CC(const struct pf_parameter *param, int cost, int extra, int safety)
Definition path_finding.c:2031
pf_fuel_map_destroy
static void pf_fuel_map_destroy(struct pf_map *pfm)
Definition path_finding.c:3085
pf_reverse_map_utype_move_cost
int pf_reverse_map_utype_move_cost(struct pf_reverse_map *pfrm, const struct unit_type *punittype, struct tile *ptile)
Definition path_finding.c:3852
pf_fuel_map_new
static struct pf_map * pf_fuel_map_new(const struct pf_parameter *parameter)
Definition path_finding.c:3105
pf_fuel_map_construct_path
static struct pf_path * pf_fuel_map_construct_path(const struct pf_fuel_map *pffm, struct tile *ptile)
Definition path_finding.c:2376
pf_danger_map_iterate_until
static bool pf_danger_map_iterate_until(struct pf_danger_map *pfdm, struct tile *ptile)
Definition path_finding.c:1757
pf_reverse_map_utype_position
bool pf_reverse_map_utype_position(struct pf_reverse_map *pfrm, const struct unit_type *punittype, struct tile *ptile, struct pf_position *pos)
Definition path_finding.c:3877
INITIAL_QUEUE_SIZE
#define INITIAL_QUEUE_SIZE
Definition path_finding.c:40
pf_danger_map_fill_cost_for_full_moves
static int pf_danger_map_fill_cost_for_full_moves(const struct pf_parameter *param, int cost)
Definition path_finding.c:1200
PF_NORMAL_MAP
#define PF_NORMAL_MAP(pfm)
Definition path_finding.c:251
pf_turns
static int pf_turns(const struct pf_parameter *param, int cost)
Definition path_finding.c:133
pf_fuel_waited_total_CC
static int pf_fuel_waited_total_CC(int cost, int safety)
Definition path_finding.c:2040
pf_reverse_map_destroy_param
static void pf_reverse_map_destroy_param(struct pf_parameter *param)
Definition path_finding.c:3679
pf_danger_map_create_segment
static void pf_danger_map_create_segment(struct pf_danger_map *pfdm, struct pf_danger_node *node1)
Definition path_finding.c:1377
path_finding.h
PF_IMPOSSIBLE_MC
#define PF_IMPOSSIBLE_MC
Definition path_finding.h:266
pf_action
pf_action
Definition path_finding.h:287
PF_ACTION_ATTACK
@ PF_ACTION_ATTACK
Definition path_finding.h:289
PF_ACTION_IMPOSSIBLE
@ PF_ACTION_IMPOSSIBLE
Definition path_finding.h:292
PF_ACTION_NONE
@ PF_ACTION_NONE
Definition path_finding.h:288
pf_move_scope
pf_move_scope
Definition path_finding.h:319
PF_MS_TRANSPORT
@ PF_MS_TRANSPORT
Definition path_finding.h:323
PF_MS_NATIVE
@ PF_MS_NATIVE
Definition path_finding.h:321
PF_MS_NONE
@ PF_MS_NONE
Definition path_finding.h:320
PF_TURN_FACTOR
#define PF_TURN_FACTOR
Definition path_finding.h:272
TB_NORMAL
@ TB_NORMAL
Definition path_finding.h:309
TB_DONT_LEAVE
@ TB_DONT_LEAVE
Definition path_finding.h:311
TB_IGNORE
@ TB_IGNORE
Definition path_finding.h:310
pft_fill_reverse_parameter
void pft_fill_reverse_parameter(const struct civ_map *nmap, struct pf_parameter *parameter, struct tile *target_tile)
Definition pf_tools.c:960
pf_tools.h
player_can_invade_tile
bool player_can_invade_tile(const struct player *pplayer, const struct tile *ptile)
Definition player.c:270
level
struct setting_list * level[OLEVELS_NUM]
Definition settings.c:190
ARRAY_SIZE
#define ARRAY_SIZE(x)
Definition shared.h:85
MIN
#define MIN(x, y)
Definition shared.h:55
FC_INFINITY
#define FC_INFINITY
Definition shared.h:36
spechash.h
specpq.h
priority
SPECPQ_PRIORITY_TYPE priority
Definition specpq.h:86
action
Definition actions.h:360
city
Definition city.h:320
civ_map
Definition map_types.h:71
pf_danger_map
Definition path_finding.c:978
pf_danger_map::danger_queue
struct map_index_pq * danger_queue
Definition path_finding.c:984
pf_danger_map::lattice
struct pf_danger_node * lattice
Definition path_finding.c:985
pf_danger_map::queue
struct map_index_pq * queue
Definition path_finding.c:981
pf_danger_map::base_map
struct pf_map base_map
Definition path_finding.c:979
pf_danger_node::pf_danger_pos
Definition path_finding.c:970
pf_danger_node::pf_danger_pos::cost
signed short cost
Definition path_finding.c:971
pf_danger_node::pf_danger_pos::dir_to_here
signed dir_to_here
Definition path_finding.c:973
pf_danger_node::pf_danger_pos::extra_cost
unsigned extra_cost
Definition path_finding.c:972
pf_danger_node
Definition path_finding.c:946
pf_danger_node::danger_segment
struct pf_danger_node::pf_danger_pos * danger_segment
pf_danger_node::node_known_type
unsigned node_known_type
Definition path_finding.c:961
pf_danger_node::move_scope
unsigned move_scope
Definition path_finding.c:959
pf_danger_node::zoc_number
unsigned zoc_number
Definition path_finding.c:963
pf_danger_node::status
unsigned status
Definition path_finding.c:956
pf_danger_node::is_dangerous
bool is_dangerous
Definition path_finding.c:964
pf_danger_node::cost
signed int cost
Definition path_finding.c:949
pf_danger_node::action
unsigned action
Definition path_finding.c:960
pf_danger_node::extra_tile
unsigned short extra_tile
Definition path_finding.c:966
pf_danger_node::extra_cost
unsigned extra_cost
Definition path_finding.c:951
pf_danger_node::behavior
unsigned behavior
Definition path_finding.c:962
pf_danger_node::dir_to_here
unsigned dir_to_here
Definition path_finding.c:952
pf_danger_node::waited
bool waited
Definition path_finding.c:965
pf_fuel_map
Definition path_finding.c:1998
pf_fuel_map::waited_queue
struct map_index_pq * waited_queue
Definition path_finding.c:2004
pf_fuel_map::base_map
struct pf_map base_map
Definition path_finding.c:1999
pf_fuel_map::queue
struct map_index_pq * queue
Definition path_finding.c:2001
pf_fuel_map::lattice
struct pf_fuel_node * lattice
Definition path_finding.c:2006
pf_fuel_node
Definition path_finding.c:1950
pf_fuel_node::segment
struct pf_fuel_pos * segment
Definition path_finding.c:1982
pf_fuel_node::zoc_number
unsigned zoc_number
Definition path_finding.c:1968
pf_fuel_node::extra_cost
unsigned extra_cost
Definition path_finding.c:1955
pf_fuel_node::status
unsigned status
Definition path_finding.c:1961
pf_fuel_node::behavior
unsigned behavior
Definition path_finding.c:1967
pf_fuel_node::node_known_type
unsigned node_known_type
Definition path_finding.c:1966
pf_fuel_node::cost_to_here
unsigned short cost_to_here[DIR8_MAGIC_MAX]
Definition path_finding.c:1976
pf_fuel_node::move_scope
unsigned move_scope
Definition path_finding.c:1964
pf_fuel_node::pos
struct pf_fuel_pos * pos
Definition path_finding.c:1980
pf_fuel_node::moves_left
unsigned moves_left
Definition path_finding.c:1956
pf_fuel_node::cost
signed int cost
Definition path_finding.c:1953
pf_fuel_node::dir_to_here
unsigned dir_to_here
Definition path_finding.c:1957
pf_fuel_node::extra_tile
unsigned short extra_tile
Definition path_finding.c:1975
pf_fuel_node::action
unsigned action
Definition path_finding.c:1965
pf_fuel_node::moves_left_req
signed moves_left_req
Definition path_finding.c:1969
pf_fuel_pos
Definition path_finding.c:1988
pf_fuel_pos::dir_to_here
unsigned dir_to_here
Definition path_finding.c:1992
pf_fuel_pos::extra_cost
unsigned extra_cost
Definition path_finding.c:1990
pf_fuel_pos::cost
signed int cost
Definition path_finding.c:1989
pf_fuel_pos::prev
struct pf_fuel_pos * prev
Definition path_finding.c:1994
pf_fuel_pos::moves_left
unsigned moves_left
Definition path_finding.c:1991
pf_fuel_pos::ref_count
unsigned ref_count
Definition path_finding.c:1993
pf_map
Definition path_finding.c:78
pf_map::get_position
bool(* get_position)(struct pf_map *pfm, struct tile *ptile, struct pf_position *pos)
Definition path_finding.c:87
pf_map::get_move_cost
int(* get_move_cost)(struct pf_map *pfm, struct tile *ptile)
Definition path_finding.c:85
pf_map::tile
struct tile * tile
Definition path_finding.c:92
pf_map::get_path
struct pf_path *(* get_path)(struct pf_map *pfm, struct tile *ptile)
Definition path_finding.c:86
pf_map::iterate
bool(* iterate)(struct pf_map *pfm)
Definition path_finding.c:89
pf_map::destroy
void(* destroy)(struct pf_map *pfm)
Definition path_finding.c:84
pf_map::params
struct pf_parameter params
Definition path_finding.c:93
pf_normal_map
Definition path_finding.c:228
pf_normal_map::base_map
struct pf_map base_map
Definition path_finding.c:229
pf_normal_map::lattice
struct pf_normal_node * lattice
Definition path_finding.c:234
pf_normal_map::queue
struct map_index_pq * queue
Definition path_finding.c:231
pf_normal_node
Definition path_finding.c:206
pf_normal_node::dir_to_here
unsigned dir_to_here
Definition path_finding.c:212
pf_normal_node::status
unsigned status
Definition path_finding.c:216
pf_normal_node::zoc_number
unsigned zoc_number
Definition path_finding.c:223
pf_normal_node::action
unsigned action
Definition path_finding.c:220
pf_normal_node::extra_cost
unsigned extra_cost
Definition path_finding.c:211
pf_normal_node::extra_tile
unsigned short extra_tile
Definition path_finding.c:224
pf_normal_node::node_known_type
unsigned node_known_type
Definition path_finding.c:221
pf_normal_node::move_scope
unsigned move_scope
Definition path_finding.c:219
pf_normal_node::cost
signed int cost
Definition path_finding.c:209
pf_normal_node::behavior
unsigned behavior
Definition path_finding.c:222
pf_parameter
Definition path_finding.h:357
pf_parameter::fuel_left_initially
int fuel_left_initially
Definition path_finding.h:362
pf_parameter::transported_by_initially
const struct unit_type * transported_by_initially
Definition path_finding.h:364
pf_parameter::get_action
enum pf_action(* get_action)(const struct tile *ptile, enum known_type known, const struct pf_parameter *param)
Definition path_finding.h:410
pf_parameter::get_move_scope
enum pf_move_scope(* get_move_scope)(const struct tile *ptile, bool *can_disembark, enum pf_move_scope previous_scope, const struct pf_parameter *param)
Definition path_finding.h:389
pf_parameter::ignore_none_scopes
bool ignore_none_scopes
Definition path_finding.h:393
pf_parameter::map
const struct civ_map * map
Definition path_finding.h:358
pf_parameter::get_TB
enum tile_behavior(* get_TB)(const struct tile *ptile, enum known_type known, const struct pf_parameter *param)
Definition path_finding.h:398
pf_parameter::owner
const struct player * owner
Definition path_finding.h:374
pf_parameter::is_pos_dangerous
bool(* is_pos_dangerous)(const struct tile *ptile, enum known_type, const struct pf_parameter *param)
Definition path_finding.h:436
pf_parameter::get_moves_left_req
int(* get_moves_left_req)(const struct tile *ptile, enum known_type, const struct pf_parameter *param)
Definition path_finding.h:441
pf_parameter::moves_left_initially
int moves_left_initially
Definition path_finding.h:361
pf_parameter::move_rate
int move_rate
Definition path_finding.h:370
pf_parameter::get_zoc
bool(* get_zoc)(const struct player *pplayer, const struct tile *ptile, const struct civ_map *zmap)
Definition path_finding.h:430
pf_parameter::get_MC
unsigned(* get_MC)(const struct tile *from_tile, enum pf_move_scope src_move_scope, const struct tile *to_tile, enum pf_move_scope dst_move_scope, const struct pf_parameter *param)
Definition path_finding.h:382
pf_parameter::get_costs
int(* get_costs)(const struct tile *from_tile, enum direction8 dir, const struct tile *to_tile, int from_cost, int from_extra, unsigned *to_cost, unsigned *to_extra, const struct pf_parameter *param)
Definition path_finding.h:463
pf_parameter::get_EC
unsigned(* get_EC)(const struct tile *ptile, enum known_type known, const struct pf_parameter *param)
Definition path_finding.h:405
pf_parameter::fuel
int fuel
Definition path_finding.h:371
pf_parameter::utype
const struct unit_type * utype
Definition path_finding.h:373
pf_parameter::is_action_possible
bool(* is_action_possible)(const struct tile *from_tile, enum pf_move_scope src_move_scope, const struct tile *to_tile, enum pf_action action, const struct pf_parameter *param)
Definition path_finding.h:417
pf_parameter::omniscience
bool omniscience
Definition path_finding.h:376
pf_parameter::start_tile
struct tile * start_tile
Definition path_finding.h:359
pf_path
Definition path_finding.h:344
pf_path::length
unsigned length
Definition path_finding.h:345
pf_path::positions
struct pf_position * positions
Definition path_finding.h:346
pf_position
Definition path_finding.h:327
pf_position::dir_to_next_pos
enum direction8 dir_to_next_pos
Definition path_finding.h:339
pf_position::tile
struct tile * tile
Definition path_finding.h:328
pf_reverse_map
Definition path_finding.c:3587
pf_reverse_map::template
struct pf_parameter template
Definition path_finding.c:3590
pf_reverse_map::hash
struct pf_pos_hash * hash
Definition path_finding.c:3591
pf_reverse_map::target_tile
struct tile * target_tile
Definition path_finding.c:3588
pf_reverse_map::max_turns
int max_turns
Definition path_finding.c:3589
player
Definition player.h:247
tile
Definition tile.h:50
tile::units
struct unit_list * units
Definition tile.h:58
unit_type
Definition unittype.h:500
unit_type::unknown_move_cost
int unknown_move_cost
Definition unittype.h:518
unit
Definition unit.h:138
unit::moves_left
int moves_left
Definition unit.h:150
veteran_level
Definition unittype.h:486
support.h
TRUE
#define TRUE
Definition support.h:46
FALSE
#define FALSE
Definition support.h:47
bool
#define bool
Definition support.h:71
terrain_has_flag
#define terrain_has_flag(terr, flag)
Definition terrain.h:283
tile_has_native_base
bool tile_has_native_base(const struct tile *ptile, const struct unit_type *punittype)
Definition tile.c:324
tile_get_known
enum known_type tile_get_known(const struct tile *ptile, const struct player *pplayer)
Definition tile.c:392
tile_city
struct city * tile_city(const struct tile *ptile)
Definition tile.c:83
tile_index
#define tile_index(_pt_)
Definition tile.h:88
known_type
known_type
Definition tile.h:35
TILE_UNKNOWN
@ TILE_UNKNOWN
Definition tile.h:36
TILE_KNOWN_SEEN
@ TILE_KNOWN_SEEN
Definition tile.h:38
tile_terrain
#define tile_terrain(_tile)
Definition tile.h:110
TILE_XY
#define TILE_XY(ptile)
Definition tile.h:43
unit_tile
#define unit_tile(_pu)
Definition unit.h:390
utype_action_takes_all_mp
bool utype_action_takes_all_mp(const struct unit_type *putype, struct action *paction)
Definition unittype.c:1191
unit_type_get
const struct unit_type * unit_type_get(const struct unit *punit)
Definition unittype.c:123
utype_can_freely_unload
bool utype_can_freely_unload(const struct unit_type *pcargotype, const struct unit_type *ptranstype)
Definition unittype.c:300
utype_veteran_levels
int utype_veteran_levels(const struct unit_type *punittype)
Definition unittype.c:2613
uclass_number
Unit_Class_id uclass_number(const struct unit_class *pclass)
Definition unittype.c:2467
utype_can_do_action
bool utype_can_do_action(const struct unit_type *putype, const action_id act_id)
Definition unittype.c:371
utype_class
#define utype_class(_t_)
Definition unittype.h:749
utype_has_flag
static bool utype_has_flag(const struct unit_type *punittype, int flag)
Definition unittype.h:617