path_finding.cpp

Go to the documentation of this file.

/*
 Copyright (c) 1996-2020 Freeciv21 and Freeciv contributors. This file is
 __    __          part of Freeciv21. Freeciv21 is free software: you can
/ \\..// \    redistribute it and/or modify it under the terms of the GNU
  ( oo )        General Public License  as published by the Free Software
   \__/         Foundation, either version 3 of the License,  or (at your
                      option) any later version. You should have received
    a copy of the GNU General Public License along with Freeciv21. If not,
                  see https://www.gnu.org/licenses/.
 */
// utility
#include "bitvector.h"
#include "genhash.h"
#include "log.h"
 
// common
#include "game.h"
#include "map.h"
#include "movement.h"
 
/* common/aicore */
#include "pf_tools.h"
 
// Qt
#include <QDebug>
#include <QString>
 
#include "path_finding.h"
 
// For explanations on how to use this module, see "path_finding.h".
 
#define SPECPQ_TAG map_index
#define SPECPQ_DATA_TYPE int
#define SPECPQ_PRIORITY_TYPE int
#include "specpq.h"
#define INITIAL_QUEUE_SIZE 100
 
#ifdef FREECIV_DEBUG
// Extra checks for debugging.
#define PF_DEBUG
#endif
 
// ======================== Internal structures ==========================
 
#ifdef PF_DEBUG
// The mode we use the pf_map. Used for cast converion checks.
enum pf_mode {
  PF_NORMAL = 1, // Usual goto
  PF_DANGER,     // Goto with dangerous positions
  PF_FUEL        // Goto for fueled units
};
#endif // PF_DEBUG
 
enum pf_node_status {
  NS_UNINIT = 0, /* memory is calloced, hence zero means
                  * uninitialised. */
  NS_INIT,       /* node initialized, but we didn't search a route
                  * yet. */
  NS_NEW,        // the optimal route isn't found yet.
  NS_WAITING,    /* the optimal route is found, considering waiting.
                  * Only used for pf_danger_map and pf_fuel_map, it
                  * means we are waiting on a safe place for full
                  * moves before crossing a dangerous area. */
  NS_PROCESSED   // the optimal route is found.
};
 
enum pf_zoc_type {
  ZOC_MINE = 0, // My ZoC.
  ZOC_ALLIED,   // Allied ZoC.
  ZOC_NO        // No ZoC.
};
 
// Abstract base class for pf_normal_map, pf_danger_map, and pf_fuel_map.
struct pf_map {
#ifdef PF_DEBUG
  enum pf_mode mode; // The mode of the map, for conversion checking.
#endif               // PF_DEBUG
 
  // "Virtual" function table.
  void (*destroy)(struct pf_map *pfm); // Destructor.
  int (*get_move_cost)(struct pf_map *pfm, struct tile *ptile);
  PFPath (*get_path)(struct pf_map *pfm, struct tile *ptile);
  bool (*get_position)(struct pf_map *pfm, struct tile *ptile,
                       struct pf_position *pos);
  bool (*iterate)(struct pf_map *pfm);
 
  // Private data.
  struct tile *tile;          // The current position (aka iterator).
  struct pf_parameter params; // Initial parameters.
};
 
pf_map *PF_MAP(void *x) { return reinterpret_cast<pf_map *>(x); }
 
const pf_map *PF_MAP(const void *x)
{
  return reinterpret_cast<const pf_map *>(x);
}
 
// ========================== Common functions ===========================
 
static inline int pf_moves_left_initially(const struct pf_parameter *param)
{
  return (param->moves_left_initially
          + (param->fuel_left_initially - 1) * param->move_rate);
}
 
static inline int pf_move_rate(const struct pf_parameter *param)
{
  return param->move_rate * param->fuel;
}
 
static inline int pf_turns(const struct pf_parameter *param, int cost)
{
  /* Negative cost can happen when a unit initially has more MP than its
   * move-rate (due to wonders transfer etc). Although this may be a bug,
   * we'd better be ready.
   *
   * Note that cost == 0 corresponds to the current turn with full MP. */
  if (param->fuel_left_initially < param->fuel) {
    cost -= (param->fuel - param->fuel_left_initially) * param->move_rate;
  }
  if (cost <= 0) {
    return 0;
  } else if (param->move_rate <= 0) {
    return FC_INFINITY; // This unit cannot move by itself.
  } else {
    return cost / param->move_rate;
  }
}
 
static inline int pf_moves_left(const struct pf_parameter *param, int cost)
{
  int move_rate = pf_move_rate(param);
 
  // Cost may be negative; see pf_turns().
  if (cost <= 0) {
    return move_rate - cost;
  } else if (move_rate <= 0) {
    return 0; // This unit never have moves left.
  } else {
    return move_rate - (cost % move_rate);
  }
}
 
static inline int pf_total_CC(const struct pf_parameter *param, int cost,
                              int extra)
{
  return PF_TURN_FACTOR * cost + extra * pf_move_rate(param);
}
 
static inline void pf_finalize_position(const struct pf_parameter *param,
                                        struct pf_position *pos)
{
  int move_rate = param->move_rate;
 
  if (0 < move_rate) {
    pos->moves_left %= move_rate;
  }
}
 
static void pf_position_fill_start_tile(struct pf_position *pos,
                                        const struct pf_parameter *param);
 
// ================ Specific pf_normal_* mode structures =================
 
/* Normal path-finding maps are used for most of units with standard rules.
 * See what units make pf_map_new() to pick danger or fuel maps instead. */
// Node definition. Note we try to have the smallest data as possible.
struct pf_normal_node {
  signed short cost;   /* total_MC. 'cost' may be negative, see comment in
                        * pf_turns(). */
  unsigned extra_cost; // total_EC. Can be huge, (higher than 'cost').
  unsigned dir_to_here : 4; /* Direction from which we came. It's
                             * an 'enum direction8' including
                             * possibility of direction8_invalid (so we need
                             * 4 bits) */
  unsigned status : 3;      // 'enum pf_node_status' really.
 
  // Cached values
  unsigned move_scope : 3;      // 'enum pf_move_scope really.
  unsigned action : 2;          // 'enum pf_action really.
  unsigned node_known_type : 2; // 'enum known_type' really.
  unsigned behavior : 2;        // 'enum tile_behavior' really.
  unsigned zoc_number : 2;      // 'enum pf_zoc_type' really.
  unsigned short extra_tile;    // EC
};
 
// Derived structure of struct pf_map.
struct pf_normal_map {
  struct pf_map base_map; // Base structure, must be the first!
 
  struct map_index_pq *queue;     /* Queue of nodes we have reached but not
                                   * processed yet (NS_NEW), sorted by their
                                   * total_CC. */
  struct pf_normal_node *lattice; // Lattice of nodes.
};
 
// Up-cast macro.
#ifdef PF_DEBUG
static inline pf_normal_map *pf_normal_map_check(pf_map *pfm)
{
  fc_assert_ret_val_msg(nullptr != pfm && PF_NORMAL == pfm->mode, nullptr,
                        "Wrong pf_map to pf_normal_map conversion.");
  return reinterpret_cast<struct pf_normal_map *>(pfm);
}
#define PF_NORMAL_MAP(pfm) pf_normal_map_check(pfm)
#else
#define PF_NORMAL_MAP(pfm) ((struct pf_normal_map *) (pfm))
#endif // PF_DEBUG
 
// ================  Specific pf_normal_* mode functions =================
 
static inline bool pf_normal_node_init(struct pf_normal_map *pfnm,
                                       struct pf_normal_node *node,
                                       struct tile *ptile,
                                       enum pf_move_scope previous_scope)
{
  const struct pf_parameter *params = pf_map_parameter(PF_MAP(pfnm));
  enum known_type node_known_type;
  enum pf_action action;
 
#ifdef PF_DEBUG
  fc_assert(NS_UNINIT == node->status);
  // Else, not a critical problem, but waste of time.
#endif
 
  node->status = NS_INIT;
 
  // Establish the "known" status of node.
  if (params->omniscience) {
    node_known_type = TILE_KNOWN_SEEN;
  } else {
    node_known_type = tile_get_known(ptile, params->owner);
  }
  node->node_known_type = node_known_type;
 
  // Establish the tile behavior.
  if (nullptr != params->get_TB) {
    node->behavior = params->get_TB(ptile, node_known_type, params);
    if (TB_IGNORE == node->behavior && params->start_tile != ptile) {
      return false;
    }
  }
 
  if (TILE_UNKNOWN != node_known_type) {
    bool can_disembark;
 
    // Test if we can invade tile.
    if (!utype_has_flag(params->utype, UTYF_CIVILIAN)
        && !player_can_invade_tile(params->owner, ptile)) {
      // Maybe overwrite node behavior.
      if (params->start_tile != ptile) {
        node->behavior = TB_IGNORE;
        return false;
      } else if (TB_NORMAL == node->behavior) {
        node->behavior = TB_IGNORE;
      }
    }
 
    // Test the possibility to perform an action.
    if (nullptr != params->get_action) {
      action = params->get_action(ptile, node_known_type, params);
      if (PF_ACTION_IMPOSSIBLE == action) {
        // Maybe overwrite node behavior.
        if (params->start_tile != ptile) {
          node->behavior = TB_IGNORE;
          return false;
        } else if (TB_NORMAL == node->behavior) {
          node->behavior = TB_IGNORE;
        }
        action = PF_ACTION_NONE;
      } else if (PF_ACTION_NONE != action
                 && TB_DONT_LEAVE != node->behavior) {
        // Overwrite node behavior.
        node->behavior = TB_DONT_LEAVE;
      }
      node->action = action;
    }
 
    /* Test the possibility to move from/to 'ptile'. */
    node->move_scope = params->get_move_scope(ptile, &can_disembark,
                                              previous_scope, params);
    if (PF_MS_NONE == node->move_scope && PF_ACTION_NONE == node->action
        && params->ignore_none_scopes) {
      // Maybe overwrite node behavior.
      if (params->start_tile != ptile) {
        node->behavior = TB_IGNORE;
        return false;
      } else if (TB_NORMAL == node->behavior) {
        node->behavior = TB_IGNORE;
      }
    } else if (PF_MS_TRANSPORT == node->move_scope && !can_disembark
               && (params->start_tile != ptile
                   || nullptr == params->transported_by_initially)) {
      // Overwrite node behavior.
      node->behavior = TB_DONT_LEAVE;
    }
 
    /* ZOC_MINE means can move unrestricted from/into it, ZOC_ALLIED means
     * can move unrestricted into it, but not necessarily from it. */
    if (nullptr != params->get_zoc && nullptr == tile_city(ptile)
        && !terrain_has_flag(tile_terrain(ptile), TER_NO_ZOC)
        && !params->get_zoc(params->owner, ptile, params->map)) {
      node->zoc_number =
          (0 < unit_list_size(ptile->units) ? ZOC_ALLIED : ZOC_NO);
    }
  } else {
    node->move_scope = PF_MS_NATIVE;
  }
 
  // Evaluate the extra cost of the destination
  if (nullptr != params->get_EC) {
    node->extra_tile = params->get_EC(ptile, node_known_type, params);
  }
 
  return true;
}
 
static void pf_normal_map_fill_position(const struct pf_normal_map *pfnm,
                                        struct tile *ptile,
                                        struct pf_position *pos)
{
  int tindex = tile_index(ptile);
  struct pf_normal_node *node = pfnm->lattice + tindex;
  const struct pf_parameter *params = pf_map_parameter(PF_MAP(pfnm));
 
#ifdef PF_DEBUG
  fc_assert_ret_msg(NS_PROCESSED == node->status,
                    "Unreached destination (%d, %d).", TILE_XY(ptile));
#endif // PF_DEBUG
 
  pos->tile = ptile;
  pos->total_EC = node->extra_cost;
  pos->total_MC =
      (node->cost - pf_move_rate(params) + pf_moves_left_initially(params));
  pos->turn = pf_turns(params, node->cost);
  pos->moves_left = pf_moves_left(params, node->cost);
#ifdef PF_DEBUG
  fc_assert(params->fuel == 1);
  fc_assert(params->fuel_left_initially == 1);
#endif // PF_DEBUG
  pos->fuel_left = 1;
  pos->dir_to_here = direction8(node->dir_to_here);
  pos->dir_to_next_pos = direction8_invalid(); // This field does not apply.
 
  if (node->cost > 0) {
    pf_finalize_position(params, pos);
  }
}
 
static PFPath pf_normal_map_construct_path(const struct pf_normal_map *pfnm,
                                           struct tile *dest_tile)
{
  struct pf_normal_node *node = pfnm->lattice + tile_index(dest_tile);
  const struct pf_parameter *params = pf_map_parameter(PF_MAP(pfnm));
  enum direction8 dir_next = direction8_invalid();
  struct tile *ptile;
  int i;
 
#ifdef PF_DEBUG
  fc_assert_ret_val_msg(NS_PROCESSED == node->status, PFPath(),
                        "Unreached destination (%d, %d).",
                        TILE_XY(dest_tile));
#endif // PF_DEBUG
 
  ptile = dest_tile;
  /* 1: Count the number of steps to get here.
   * To do it, backtrack until we hit the starting point */
  for (i = 0;; i++) {
    if (ptile == params->start_tile) {
      // Ah-ha, reached the starting point!
      break;
    }
 
    ptile = mapstep(params->map, ptile, DIR_REVERSE(node->dir_to_here));
    node = pfnm->lattice + tile_index(ptile);
  }
 
  // 2: Allocate the memory
  PFPath path(i + 1);
 
  // 3: Backtrack again and fill the positions this time
  ptile = dest_tile;
  node = pfnm->lattice + tile_index(ptile);
 
  for (; i >= 0; i--) {
    pf_normal_map_fill_position(pfnm, ptile, &path[i]);
    // fill_position doesn't set direction
    path[i].dir_to_next_pos = dir_next;
 
    dir_next = direction8(node->dir_to_here);
 
    if (i > 0) {
      // Step further back, if we haven't finished yet
      ptile = mapstep(params->map, ptile, DIR_REVERSE(dir_next));
      node = pfnm->lattice + tile_index(ptile);
    }
  }
 
  return path;
}
 
static int pf_normal_map_adjust_cost(int cost, int moves_left)
{
  fc_assert_ret_val(cost >= 0, PF_IMPOSSIBLE_MC);
 
  return MIN(cost, moves_left);
}
 
static bool pf_jumbo_map_iterate(struct pf_map *pfm)
{
  struct pf_normal_map *pfnm = PF_NORMAL_MAP(pfm);
  struct tile *tile = pfm->tile;
  int tindex = tile_index(tile);
  struct pf_normal_node *node = pfnm->lattice + tindex;
  const struct pf_parameter *params = pf_map_parameter(pfm);
 
  // Processing Stage
 
  /* The previous position is defined by 'tile' (tile pointer), 'node'
   * (the data of the tile for the pf_map), and index (the index of the
   * position in the Freeciv map). */
 
  adjc_dir_iterate(params->map, tile, tile1, dir)
  {
    /* Calculate the cost of every adjacent position and set them in the
     * priority queue for next call to pf_jumbo_map_iterate(). */
    int tindex1 = tile_index(tile1);
    struct pf_normal_node *node1 = pfnm->lattice + tindex1;
    int priority, cost1, extra_cost1;
 
    /* As for the previous position, 'tile1', 'node1' and 'tindex1' are
     * defining the adjacent position. */
 
    if (node1->status == NS_PROCESSED) {
      // This gives 15% speedup
      continue;
    }
 
    if (NS_UNINIT == node1->status) {
      /* Set cost as impossible for initializing, params->get_costs(), will
       * overwrite with the right value. */
      cost1 = PF_IMPOSSIBLE_MC;
      extra_cost1 = 0;
    } else {
      cost1 = node1->cost;
      extra_cost1 = node1->extra_cost;
    }
 
    /* User-supplied callback 'get_costs' takes care of everything (ZOC,
     * known, costs etc). See explanations in "path_finding.h". */
    priority =
        params->get_costs(tile, dir, tile1, node->cost, node->extra_cost,
                          &cost1, &extra_cost1, params);
    if (priority >= 0) {
      /* We found a better route to 'tile1', record it (the costs are
       * recorded already). Node status step A. to B. */
      if (NS_NEW == node1->status) {
        map_index_pq_replace(pfnm->queue, tindex1, -priority);
      } else {
        map_index_pq_insert(pfnm->queue, tindex1, -priority);
      }
      node1->cost = cost1;
      node1->extra_cost = extra_cost1;
      node1->status = NS_NEW;
      node1->dir_to_here = dir;
    }
  }
  adjc_dir_iterate_end;
 
  // Get the next node (the index with the highest priority).
  if (!map_index_pq_remove(pfnm->queue, &tindex)) {
    // No more indexes in the priority queue, iteration end.
    return false;
  }
 
#ifdef PF_DEBUG
  fc_assert(NS_NEW == pfnm->lattice[tindex].status);
#endif
 
  // Change the pf_map iterator. Node status step B. to C.
  pfm->tile = index_to_tile(params->map, tindex);
  pfnm->lattice[tindex].status = NS_PROCESSED;
 
  return true;
}
 
static bool pf_normal_map_iterate(struct pf_map *pfm)
{
  struct pf_normal_map *pfnm = PF_NORMAL_MAP(pfm);
  struct tile *tile = pfm->tile;
  int tindex = tile_index(tile);
  struct pf_normal_node *node = pfnm->lattice + tindex;
  const struct pf_parameter *params = pf_map_parameter(pfm);
  int cost_of_path;
  pf_move_scope scope = pf_move_scope(node->move_scope);
 
  // There is no exit from DONT_LEAVE tiles!
  if (node->behavior != TB_DONT_LEAVE && scope != PF_MS_NONE
      && (params->move_rate > 0 || node->cost < 0)) {
    // Processing Stage
 
    /* The previous position is defined by 'tile' (tile pointer), 'node'
     * (the data of the tile for the pf_map), and index (the index of the
     * position in the Freeciv map). */
 
    adjc_dir_iterate(params->map, tile, tile1, dir)
    {
      /* Calculate the cost of every adjacent position and set them in the
       * priority queue for next call to pf_normal_map_iterate(). */
      int tindex1 = tile_index(tile1);
      struct pf_normal_node *node1 = pfnm->lattice + tindex1;
      int cost;
      int extra = 0;
 
      /* As for the previous position, 'tile1', 'node1' and 'tindex1' are
       * defining the adjacent position. */
 
      if (node1->status == NS_PROCESSED) {
        // This gives 15% speedup. Node status already at step D.
        continue;
      }
 
      // Initialise target tile if necessary.
      if (node1->status == NS_UNINIT) {
        /* Only initialize once. See comment for pf_normal_node_init().
         * Node status step A. to B. */
        if (!pf_normal_node_init(pfnm, node1, tile1, scope)) {
          continue;
        }
      } else if (TB_IGNORE == node1->behavior) {
        // We cannot enter this tile at all!
        continue;
      }
 
      // Is the move ZOC-ok?
      if (node->zoc_number != ZOC_MINE && node1->zoc_number == ZOC_NO) {
        continue;
      }
 
      // Evaluate the cost of the move.
      if (PF_ACTION_NONE != node1->action) {
        if (nullptr != params->is_action_possible
            && !params->is_action_possible(
                tile, scope, tile1, pf_action(node1->action), params)) {
          continue;
        }
        // action move cost depends on action and unit type.
        if (node1->action == PF_ACTION_ATTACK
            && (utype_has_flag(params->utype, UTYF_ONEATTACK)
                || utype_can_do_action(params->utype,
                                       ACTION_SUICIDE_ATTACK))) {
          /* Assume that the attack will be a suicide attack even if a
           * regular attack may be legal. */
          cost = params->move_rate;
        } else {
          cost = SINGLE_MOVE;
        }
      } else if (node1->node_known_type == TILE_UNKNOWN) {
        cost = params->utype->unknown_move_cost;
      } else {
        cost = params->get_MC(tile, scope, tile1,
                              pf_move_scope(node1->move_scope), params);
      }
      if (cost == PF_IMPOSSIBLE_MC) {
        continue;
      }
      cost =
          pf_normal_map_adjust_cost(cost, pf_moves_left(params, node->cost));
      if (cost == PF_IMPOSSIBLE_MC) {
        continue;
      }
 
      // Total cost at tile1. Cost may be negative; see pf_turns().
      cost += node->cost;
 
      // Evaluate the extra cost if it's relevant
      if (nullptr != params->get_EC) {
        extra = node->extra_cost;
        // Add the cached value
        extra += node1->extra_tile;
      }
 
      // Update costs.
      cost_of_path = pf_total_CC(params, cost, extra);
 
      if (NS_INIT == node1->status) {
        // We are reaching this node for the first time.
        node1->status = NS_NEW;
        node1->extra_cost = extra;
        node1->cost = cost;
        node1->dir_to_here = dir;
        // As we prefer lower costs, let's reverse the cost of the path.
        map_index_pq_insert(pfnm->queue, tindex1, -cost_of_path);
      } else if (cost_of_path
                 < pf_total_CC(params, node1->cost, node1->extra_cost)) {
        /* We found a better route to 'tile1'. Let's register 'tindex1' to
         * the priority queue. Node status step B. to C. */
        node1->status = NS_NEW;
        node1->extra_cost = extra;
        node1->cost = cost;
        node1->dir_to_here = dir;
        // As we prefer lower costs, let's reverse the cost of the path.
        map_index_pq_replace(pfnm->queue, tindex1, -cost_of_path);
      }
    }
    adjc_dir_iterate_end;
  }
 
  // Get the next node (the index with the highest priority).
  if (!map_index_pq_remove(pfnm->queue, &tindex)) {
    // No more indexes in the priority queue, iteration end.
    return false;
  }
 
#ifdef PF_DEBUG
  fc_assert(NS_NEW == pfnm->lattice[tindex].status);
#endif
 
  // Change the pf_map iterator. Node status step C. to D.
  pfm->tile = index_to_tile(params->map, tindex);
  pfnm->lattice[tindex].status = NS_PROCESSED;
 
  return true;
}
 
static inline bool pf_normal_map_iterate_until(struct pf_normal_map *pfnm,
                                               struct tile *ptile)
{
  struct pf_map *pfm = PF_MAP(pfnm);
  struct pf_normal_node *node = pfnm->lattice + tile_index(ptile);
 
  if (nullptr == pf_map_parameter(pfm)->get_costs) {
    // Start position is handled in every function calling this function.
    if (NS_UNINIT == node->status) {
      // Initialize the node, for doing the following tests.
      if (!pf_normal_node_init(pfnm, node, ptile, PF_MS_NONE)) {
        return false;
      }
    } else if (TB_IGNORE == node->behavior) {
      /* Simpliciation: if we cannot enter this node at all, don't iterate
       * the whole map. */
      return false;
    }
  } // Else, this is a jumbo map, not dealing with normal nodes.
 
  while (NS_PROCESSED != node->status) {
    if (!pf_map_iterate(pfm)) {
      /* All reachable destination have been iterated, 'ptile' is
       * unreachable. */
      return false;
    }
  }
 
  return true;
}
 
static int pf_normal_map_move_cost(struct pf_map *pfm, struct tile *ptile)
{
  struct pf_normal_map *pfnm = PF_NORMAL_MAP(pfm);
 
  if (ptile == pfm->params.start_tile) {
    return 0;
  } else if (pf_normal_map_iterate_until(pfnm, ptile)) {
    return (pfnm->lattice[tile_index(ptile)].cost
            - pf_move_rate(pf_map_parameter(pfm))
            + pf_moves_left_initially(pf_map_parameter(pfm)));
  } else {
    return PF_IMPOSSIBLE_MC;
  }
}
 
static PFPath pf_normal_map_path(struct pf_map *pfm, struct tile *ptile)
{
  struct pf_normal_map *pfnm = PF_NORMAL_MAP(pfm);
 
  if (ptile == pfm->params.start_tile) {
    return PFPath(pf_map_parameter(pfm));
  } else if (pf_normal_map_iterate_until(pfnm, ptile)) {
    return pf_normal_map_construct_path(pfnm, ptile);
  } else {
    return PFPath();
  }
}
 
static bool pf_normal_map_position(struct pf_map *pfm, struct tile *ptile,
                                   struct pf_position *pos)
{
  struct pf_normal_map *pfnm = PF_NORMAL_MAP(pfm);
 
  if (ptile == pfm->params.start_tile) {
    pf_position_fill_start_tile(pos, pf_map_parameter(pfm));
    return true;
  } else if (pf_normal_map_iterate_until(pfnm, ptile)) {
    pf_normal_map_fill_position(pfnm, ptile, pos);
    return true;
  } else {
    return false;
  }
}
 
static void pf_normal_map_destroy(struct pf_map *pfm)
{
  struct pf_normal_map *pfnm = PF_NORMAL_MAP(pfm);
 
  delete[] pfnm->lattice;
  map_index_pq_destroy(pfnm->queue);
  delete pfnm;
}
 
static struct pf_map *pf_normal_map_new(const struct pf_parameter *parameter)
{
  struct pf_normal_map *pfnm;
  struct pf_map *base_map;
  struct pf_parameter *params;
  struct pf_normal_node *node;
 
  if (nullptr == parameter->get_costs) {
    // 'get_MC' callback must be set.
    fc_assert_ret_val(nullptr != parameter->get_MC, nullptr);
 
    // 'get_move_scope' callback must be set.
    fc_assert_ret_val(parameter->get_move_scope != nullptr, nullptr);
  }
 
  pfnm = new pf_normal_map;
  base_map = &pfnm->base_map;
  params = &base_map->params;
#ifdef PF_DEBUG
  // Set the mode, used for cast check.
  base_map->mode = PF_NORMAL;
#endif // PF_DEBUG
 
  // Allocate the map.
  pfnm->lattice = new pf_normal_node[MAP_INDEX_SIZE]();
  pfnm->queue = map_index_pq_new(INITIAL_QUEUE_SIZE);
 
  // Copy parameters.
  *params = *parameter;
 
  // Initialize virtual function table.
  base_map->destroy = pf_normal_map_destroy;
  base_map->get_move_cost = pf_normal_map_move_cost;
  base_map->get_path = pf_normal_map_path;
  base_map->get_position = pf_normal_map_position;
  if (nullptr != params->get_costs) {
    base_map->iterate = pf_jumbo_map_iterate;
  } else {
    base_map->iterate = pf_normal_map_iterate;
  }
 
  // Initialise starting node.
  node = pfnm->lattice + tile_index(params->start_tile);
  if (nullptr == params->get_costs) {
    if (!pf_normal_node_init(pfnm, node, params->start_tile, PF_MS_NONE)) {
      // Always fails.
      fc_assert(true
                == pf_normal_node_init(pfnm, node, params->start_tile,
                                       PF_MS_NONE));
    }
 
    if (nullptr != params->transported_by_initially) {
      /* Overwrite. It is safe because we cannot return to start tile with
       * pf_normal_map. */
      node->move_scope |= PF_MS_TRANSPORT;
      if (!utype_can_freely_unload(params->utype,
                                   params->transported_by_initially)
          && nullptr == tile_city(params->start_tile)
          && !tile_has_native_base(params->start_tile,
                                   params->transported_by_initially)) {
        // Cannot disembark, don't leave transporter.
        node->behavior = TB_DONT_LEAVE;
      }
    }
  }
 
  // Initialise the iterator.
  base_map->tile = params->start_tile;
 
  /* This makes calculations of turn/moves_left more convenient, but we
   * need to subtract this value before we return cost to the user. Note
   * that cost may be negative if moves_left_initially > move_rate
   * (see pf_turns()). */
  node->cost = pf_move_rate(params) - pf_moves_left_initially(params);
  node->extra_cost = 0;
  node->dir_to_here = direction8_invalid();
  node->status = NS_PROCESSED;
 
  return PF_MAP(pfnm);
}
 
// ================ Specific pf_danger_* mode structures =================
 
/* Danger path-finding maps are used for units which can cross some areas
 * but not ending their turn there. It used to be used for triremes notably.
 * But since Freeciv 2.2, units with the "Trireme" flag just have
 * restricted moves, then it is not use anymore. */
 
// Node definition. Note we try to have the smallest data as possible.
struct pf_danger_node {
  signed short cost;   /* total_MC. 'cost' may be negative, see comment in
                        * pf_turns(). */
  unsigned extra_cost; // total_EC. Can be huge, (higher than 'cost').
  unsigned dir_to_here : 4; /* Direction from which we came. It's
                             * an 'enum direction8' including
                             * possibility of direction8_invalid (so we need
                             * 4 bits) */
  unsigned status : 3;      // 'enum pf_node_status' really.
 
  // Cached values
  unsigned move_scope : 3;      // 'enum pf_move_scope really.
  unsigned action : 2;          // 'enum pf_action really.
  unsigned node_known_type : 2; // 'enum known_type' really.
  unsigned behavior : 2;        // 'enum tile_behavior' really.
  unsigned zoc_number : 2;      // 'enum pf_zoc_type' really.
  bool is_dangerous : 1;        // Whether we cannot end the turn there.
  bool waited : 1;              // TRUE if waited to get there.
  unsigned short extra_tile;    // EC
 
  /* Segment leading across the danger area back to the nearest safe node:
   * need to remeber costs and stuff. */
  struct pf_danger_pos {
    signed short cost;      // See comment above.
    unsigned extra_cost;    // See comment above.
    signed dir_to_here : 4; // See comment above.
  } * danger_segment;
};
 
// Derived structure of struct pf_map.
struct pf_danger_map {
  struct pf_map base_map; // Base structure, must be the first!
 
  struct map_index_pq *queue; /* Queue of nodes we have reached but not
                               * processed yet (NS_NEW and NS_WAITING),
                               * sorted by their total_CC. */
  struct map_index_pq *danger_queue; // Dangerous positions.
  struct pf_danger_node *lattice;    // Lattice of nodes.
};
 
// Up-cast macro.
#ifdef PF_DEBUG
static inline pf_danger_map *pf_danger_map_check(pf_map *pfm)
{
  fc_assert_ret_val_msg(nullptr != pfm && PF_DANGER == pfm->mode, nullptr,
                        "Wrong pf_map to pf_danger_map conversion.");
  return reinterpret_cast<struct pf_danger_map *>(pfm);
}
#define PF_DANGER_MAP(pfm) pf_danger_map_check(pfm)
#else
#define PF_DANGER_MAP(pfm) ((struct pf_danger_map *) (pfm))
#endif // PF_DEBUG
 
// ===============  Specific pf_danger_* mode functions ==================
 
static inline bool pf_danger_node_init(struct pf_danger_map *pfdm,
                                       struct pf_danger_node *node,
                                       struct tile *ptile,
                                       enum pf_move_scope previous_scope)
{
  const struct pf_parameter *params = pf_map_parameter(PF_MAP(pfdm));
  enum known_type node_known_type;
  enum pf_action action;
 
#ifdef PF_DEBUG
  fc_assert(NS_UNINIT == node->status);
  // Else, not a critical problem, but waste of time.
#endif
 
  node->status = NS_INIT;
 
  // Establish the "known" status of node.
  if (params->omniscience) {
    node_known_type = TILE_KNOWN_SEEN;
  } else {
    node_known_type = tile_get_known(ptile, params->owner);
  }
  node->node_known_type = node_known_type;
 
  // Establish the tile behavior.
  if (nullptr != params->get_TB) {
    node->behavior = params->get_TB(ptile, node_known_type, params);
    if (TB_IGNORE == node->behavior && params->start_tile != ptile) {
      return false;
    }
  }
 
  if (TILE_UNKNOWN != node_known_type) {
    bool can_disembark;
 
    // Test if we can invade tile.
    if (!utype_has_flag(params->utype, UTYF_CIVILIAN)
        && !player_can_invade_tile(params->owner, ptile)) {
      // Maybe overwrite node behavior.
      if (params->start_tile != ptile) {
        node->behavior = TB_IGNORE;
        return false;
      } else if (TB_NORMAL == node->behavior) {
        node->behavior = TB_IGNORE;
      }
    }
 
    // Test the possibility to perform an action.
    if (nullptr != params->get_action) {
      action = params->get_action(ptile, node_known_type, params);
      if (PF_ACTION_IMPOSSIBLE == action) {
        // Maybe overwrite node behavior.
        if (params->start_tile != ptile) {
          node->behavior = TB_IGNORE;
          return false;
        } else if (TB_NORMAL == node->behavior) {
          node->behavior = TB_IGNORE;
        }
        action = PF_ACTION_NONE;
      } else if (PF_ACTION_NONE != action
                 && TB_DONT_LEAVE != node->behavior) {
        // Overwrite node behavior.
        node->behavior = TB_DONT_LEAVE;
      }
      node->action = action;
    }
 
    /* Test the possibility to move from/to 'ptile'. */
    node->move_scope = params->get_move_scope(ptile, &can_disembark,
                                              previous_scope, params);
    if (PF_MS_NONE == node->move_scope && PF_ACTION_NONE == node->action
        && params->ignore_none_scopes) {
      // Maybe overwrite node behavior.
      if (params->start_tile != ptile) {
        node->behavior = TB_IGNORE;
        return false;
      } else if (TB_NORMAL == node->behavior) {
        node->behavior = TB_IGNORE;
      }
    } else if (PF_MS_TRANSPORT == node->move_scope && !can_disembark
               && (params->start_tile != ptile
                   || nullptr == params->transported_by_initially)) {
      // Overwrite node behavior.
      node->behavior = TB_DONT_LEAVE;
    }
 
    /* ZOC_MINE means can move unrestricted from/into it, ZOC_ALLIED means
     * can move unrestricted into it, but not necessarily from it. */
    if (nullptr != params->get_zoc && nullptr == tile_city(ptile)
        && !terrain_has_flag(tile_terrain(ptile), TER_NO_ZOC)
        && !params->get_zoc(params->owner, ptile, params->map)) {
      node->zoc_number =
          (0 < unit_list_size(ptile->units) ? ZOC_ALLIED : ZOC_NO);
    }
  } else {
    node->move_scope = PF_MS_NATIVE;
  }
 
  // Evaluate the extra cost of the destination.
  if (nullptr != params->get_EC) {
    node->extra_tile = params->get_EC(ptile, node_known_type, params);
  }
 
  node->is_dangerous =
      params->is_pos_dangerous(ptile, node_known_type, params);
 
  return true;
}
 
static void pf_danger_map_fill_position(const struct pf_danger_map *pfdm,
                                        struct tile *ptile,
                                        struct pf_position *pos)
{
  int tindex = tile_index(ptile);
  struct pf_danger_node *node = pfdm->lattice + tindex;
  const struct pf_parameter *params = pf_map_parameter(PF_MAP(pfdm));
 
#ifdef PF_DEBUG
  fc_assert_ret_msg(NS_PROCESSED == node->status
                        || NS_WAITING == node->status,
                    "Unreached destination (%d, %d).", TILE_XY(ptile));
#endif // PF_DEBUG
 
  pos->tile = ptile;
  pos->total_EC = node->extra_cost;
  pos->total_MC =
      (node->cost - pf_move_rate(params) + pf_moves_left_initially(params));
  pos->turn = pf_turns(params, node->cost);
  pos->moves_left = pf_moves_left(params, node->cost);
#ifdef PF_DEBUG
  fc_assert(params->fuel == 1);
  fc_assert(params->fuel_left_initially == 1);
#endif // PF_DEBUG
  pos->fuel_left = 1;
  pos->dir_to_here = direction8(node->dir_to_here);
  pos->dir_to_next_pos = direction8_invalid(); // This field does not apply.
 
  if (node->cost > 0) {
    pf_finalize_position(params, pos);
  }
}
 
static inline int
pf_danger_map_fill_cost_for_full_moves(const struct pf_parameter *param,
                                       int cost)
{
  int moves_left = pf_moves_left(param, cost);
 
  if (moves_left < pf_move_rate(param)) {
    return cost + moves_left;
  } else {
    return cost;
  }
}
 
static PFPath pf_danger_map_construct_path(const struct pf_danger_map *pfdm,
                                           struct tile *ptile)
{
  enum direction8 dir_next = direction8_invalid();
  struct pf_danger_node::pf_danger_pos *danger_seg = nullptr;
  bool waited = false;
  struct pf_danger_node *node = pfdm->lattice + tile_index(ptile);
  int length = 1;
  struct tile *iter_tile = ptile;
  const struct pf_parameter *params = pf_map_parameter(PF_MAP(pfdm));
  int i;
 
#ifdef PF_DEBUG
  fc_assert_ret_val_msg(NS_PROCESSED == node->status
                            || NS_WAITING == node->status,
                        PFPath(), // Return empty path
                        "Unreached destination (%d, %d).", TILE_XY(ptile));
#endif // PF_DEBUG
 
  // First iterate to find path length.
  while (iter_tile != params->start_tile) {
    if (!node->is_dangerous && node->waited) {
      length += 2;
    } else {
      length++;
    }
 
    if (!node->is_dangerous || !danger_seg) {
      // We are in the normal node and dir_to_here field is valid
      dir_next = direction8(node->dir_to_here);
      /* d_node->danger_segment is the indicator of what lies ahead
       * if it's non-nullptr, we are entering a danger segment,
       * if it's nullptr, we are not on one so danger_seg should be nullptr.
       */
      danger_seg = node->danger_segment;
    } else {
      // We are in a danger segment.
      dir_next = direction8(danger_seg->dir_to_here);
      danger_seg++;
    }
 
    // Step backward.
    iter_tile = mapstep(params->map, iter_tile, DIR_REVERSE(dir_next));
    node = pfdm->lattice + tile_index(iter_tile);
  }
 
  // Allocate memory for path.
  auto path = PFPath(length);
 
  // Reset variables for main iteration.
  iter_tile = ptile;
  node = pfdm->lattice + tile_index(ptile);
  danger_seg = nullptr;
  waited = false;
 
  for (i = length - 1; i >= 0; i--) {
    bool old_waited = false;
 
    // 1: Deal with waiting.
    if (!node->is_dangerous) {
      if (waited) {
        /* Waited at _this_ tile, need to record it twice in the
         * path. Here we record our state _after_ waiting (e.g.
         * full move points). */
        path[i].tile = iter_tile;
        path[i].total_EC = node->extra_cost;
        path[i].turn = pf_turns(
            params,
            pf_danger_map_fill_cost_for_full_moves(params, node->cost));
        path[i].moves_left = params->move_rate;
        path[i].fuel_left = params->fuel;
        path[i].total_MC = ((path[i].turn - 1) * params->move_rate
                            + params->moves_left_initially);
        path[i].dir_to_next_pos = dir_next;
        pf_finalize_position(params, &path[i]);
        /* Set old_waited so that we record direction8_invalid() as a
         * direction at the step we were going to wait. */
        old_waited = true;
        i--;
      }
      // Update "waited" (node->waited means "waited to get here").
      waited = node->waited;
    }
 
    // 2: Fill the current position.
    path[i].tile = iter_tile;
    if (!node->is_dangerous || !danger_seg) {
      path[i].total_MC = node->cost;
      path[i].total_EC = node->extra_cost;
    } else {
      // When on dangerous tiles, must have a valid danger segment.
      fc_assert_ret_val(danger_seg != nullptr, PFPath());
      path[i].total_MC = danger_seg->cost;
      path[i].total_EC = danger_seg->extra_cost;
    }
    path[i].turn = pf_turns(params, path[i].total_MC);
    path[i].moves_left = pf_moves_left(params, path[i].total_MC);
#ifdef PF_DEBUG
    fc_assert(params->fuel == 1);
    fc_assert(params->fuel_left_initially == 1);
#endif // PF_DEBUG
    path[i].fuel_left = 1;
    path[i].total_MC -=
        (pf_move_rate(params) - pf_moves_left_initially(params));
    path[i].dir_to_next_pos = (old_waited ? direction8_invalid() : dir_next);
    if (node->cost > 0) {
      pf_finalize_position(params, &path[i]);
    }
 
    // 3: Check if we finished.
    if (i == 0) {
      // We should be back at the start now!
      fc_assert_ret_val(iter_tile == params->start_tile, PFPath());
      return path;
    }
 
    // 4: Calculate the next direction.
    if (!node->is_dangerous || !danger_seg) {
      // We are in the normal node and dir_to_here field is valid.
      dir_next = direction8(node->dir_to_here);
      /* d_node->danger_segment is the indicator of what lies ahead.
       * If it's non-nullptr, we are entering a danger segment,
       * If it's nullptr, we are not on one so danger_seg should be nullptr.
       */
      danger_seg = node->danger_segment;
    } else {
      // We are in a danger segment.
      dir_next = direction8(danger_seg->dir_to_here);
      danger_seg++;
    }
 
    // 5: Step further back.
    iter_tile = mapstep(params->map, iter_tile, DIR_REVERSE(dir_next));
    node = pfdm->lattice + tile_index(iter_tile);
  }
 
  fc_assert_msg(false, "Cannot get to the starting point!");
  return PFPath();
}
 
static void pf_danger_map_create_segment(struct pf_danger_map *pfdm,
                                         struct pf_danger_node *node1)
{
  struct tile *ptile = PF_MAP(pfdm)->tile;
  struct pf_danger_node *node = pfdm->lattice + tile_index(ptile);
  struct pf_danger_node::pf_danger_pos *pos;
  int length = 0, i;
  const struct pf_parameter *params = pf_map_parameter(PF_MAP(pfdm));
 
#ifdef PF_DEBUG
  if (nullptr != node1->danger_segment) {
    qCritical("Possible memory leak in pf_danger_map_create_segment().");
  }
#endif // PF_DEBUG
 
  // First iteration for determining segment length
  while (node->is_dangerous
         && direction8_is_valid(direction8(node->dir_to_here))) {
    length++;
    ptile = mapstep(params->map, ptile, DIR_REVERSE(node->dir_to_here));
    node = pfdm->lattice + tile_index(ptile);
  }
 
  // Allocate memory for segment
  node1->danger_segment = new pf_danger_node::pf_danger_pos[length];
 
  // Reset tile and node pointers for main iteration
  ptile = PF_MAP(pfdm)->tile;
  node = pfdm->lattice + tile_index(ptile);
 
  // Now fill the positions
  for (i = 0, pos = node1->danger_segment; i < length; i++, pos++) {
    // Record the direction
    pos->dir_to_here = direction8(node->dir_to_here);
    pos->cost = node->cost;
    pos->extra_cost = node->extra_cost;
    if (i == length - 1) {
      // The last dangerous node contains "waiting" info
      node1->waited = node->waited;
    }
 
    // Step further down the tree
    ptile = mapstep(params->map, ptile, DIR_REVERSE(node->dir_to_here));
    node = pfdm->lattice + tile_index(ptile);
  }
 
#ifdef PF_DEBUG
  // Make sure we reached a safe node or the start point
  fc_assert_ret(!node->is_dangerous
                || !direction8_is_valid(direction8(node->dir_to_here)));
#endif
}
 
static inline int
pf_danger_map_adjust_cost(const struct pf_parameter *params, int cost,
                          bool to_danger, int moves_left)
{
  if (cost == PF_IMPOSSIBLE_MC) {
    return PF_IMPOSSIBLE_MC;
  }
 
  cost = MIN(cost, pf_move_rate(params));
 
  if (to_danger && cost >= moves_left) {
    // We would have to end the turn on a dangerous tile!
    return PF_IMPOSSIBLE_MC;
  } else {
    return MIN(cost, moves_left);
  }
}
 
static bool pf_danger_map_iterate(struct pf_map *pfm)
{
  struct pf_danger_map *const pfdm = PF_DANGER_MAP(pfm);
  const struct pf_parameter *const params = pf_map_parameter(pfm);
  struct tile *tile = pfm->tile;
  int tindex = tile_index(tile);
  struct pf_danger_node *node = pfdm->lattice + tindex;
  pf_move_scope scope = pf_move_scope(node->move_scope);
 
  /* The previous position is defined by 'tile' (tile pointer), 'node'
   * (the data of the tile for the pf_map), and index (the index of the
   * position in the Freeciv map). */
 
  if (!direction8_is_valid(direction8(node->dir_to_here))
      && nullptr != params->transported_by_initially) {
#ifdef PF_DEBUG
    fc_assert(tile == params->start_tile);
#endif
    scope = pf_move_scope(scope | PF_MS_TRANSPORT);
    if (!utype_can_freely_unload(params->utype,
                                 params->transported_by_initially)
        && nullptr == tile_city(tile)
        && !tile_has_native_base(tile, params->transported_by_initially)) {
      // Cannot disembark, don't leave transporter.
      node->behavior = TB_DONT_LEAVE;
    }
  }
 
  for (;;) {
    // There is no exit from DONT_LEAVE tiles!
    if (node->behavior != TB_DONT_LEAVE && scope != PF_MS_NONE
        && (params->move_rate > 0 || node->cost < 0)) {
      // Cost at tile but taking into account waiting.
      int loc_cost;
      if (node->status != NS_WAITING) {
        loc_cost = node->cost;
      } else {
        // We have waited, so we have full moves.
        loc_cost =
            pf_danger_map_fill_cost_for_full_moves(params, node->cost);
      }
 
      adjc_dir_iterate(params->map, tile, tile1, dir)
      {
        /* Calculate the cost of every adjacent position and set them in
         * the priority queues for next call to pf_danger_map_iterate(). */
        int tindex1 = tile_index(tile1);
        struct pf_danger_node *node1 = pfdm->lattice + tindex1;
        int cost;
        int extra = 0;
 
        /* As for the previous position, 'tile1', 'node1' and 'tindex1' are
         * defining the adjacent position. */
 
        if (node1->status == NS_PROCESSED || node1->status == NS_WAITING) {
          /* This gives 15% speedup. Node status already at step D., E.
           * or F. */
          continue;
        }
 
        // Initialise target tile if necessary.
        if (node1->status == NS_UNINIT) {
          /* Only initialize once. See comment for pf_danger_node_init().
           * Node status step A. to B. */
          if (!pf_danger_node_init(pfdm, node1, tile1, scope)) {
            continue;
          }
        } else if (TB_IGNORE == node1->behavior) {
          // We cannot enter this tile at all!
          continue;
        }
 
        // Is the move ZOC-ok?
        if (node->zoc_number != ZOC_MINE && node1->zoc_number == ZOC_NO) {
          continue;
        }
 
        // Evaluate the cost of the move.
        if (PF_ACTION_NONE != node1->action) {
          if (nullptr != params->is_action_possible
              && !params->is_action_possible(
                  tile, scope, tile1, pf_action(node1->action), params)) {
            continue;
          }
          // action move cost depends on action and unit type.
          if (node1->action == PF_ACTION_ATTACK
              && (utype_has_flag(params->utype, UTYF_ONEATTACK)
                  || utype_can_do_action(params->utype,
                                         ACTION_SUICIDE_ATTACK))) {
            /* Assume that the attack will be a suicide attack even if a
             * regular attack may be legal. */
            cost = params->move_rate;
          } else {
            cost = SINGLE_MOVE;
          }
        } else if (node1->node_known_type == TILE_UNKNOWN) {
          cost = params->utype->unknown_move_cost;
        } else {
          cost = params->get_MC(tile, scope, tile1,
                                pf_move_scope(node1->move_scope), params);
        }
        if (cost == PF_IMPOSSIBLE_MC) {
          continue;
        }
        cost = pf_danger_map_adjust_cost(params, cost, node1->is_dangerous,
                                         pf_moves_left(params, loc_cost));
 
        if (cost == PF_IMPOSSIBLE_MC) {
          // This move is deemed impossible.
          continue;
        }
 
        // Total cost at 'tile1'.
        cost += loc_cost;
 
        // Evaluate the extra cost of the destination, if it's relevant.
        if (nullptr != params->get_EC) {
          extra = node1->extra_tile + node->extra_cost;
        }
 
        /* Update costs and add to queue, if this is a better route
         * to 'tile1'. */
        if (!node1->is_dangerous) {
          int cost_of_path = pf_total_CC(params, cost, extra);
 
          if (NS_INIT == node1->status
              || (cost_of_path
                  < pf_total_CC(params, node1->cost, node1->extra_cost))) {
            /* We are reaching this node for the first time, or we found a
             * better route to 'tile1'. Let's register 'tindex1' to the
             * priority queue. Node status step B. to C. */
            node1->extra_cost = extra;
            node1->cost = cost;
            node1->dir_to_here = dir;
            delete[] node1->danger_segment;
            node1->danger_segment = nullptr;
            if (node->is_dangerous) {
              /* We came from a dangerous tile. So we need to record the
               * path we came from until the previous safe position is
               * found. See comment for pf_danger_map_create_segment(). */
              pf_danger_map_create_segment(pfdm, node1);
            } else {
              // Maybe clear previously "waited" status of the node.
              node1->waited = false;
            }
            if (NS_INIT == node1->status) {
              node1->status = NS_NEW;
              map_index_pq_insert(pfdm->queue, tindex1, -cost_of_path);
            } else {
#ifdef PF_DEBUG
              fc_assert(NS_NEW == node1->status);
#endif
              map_index_pq_replace(pfdm->queue, tindex1, -cost_of_path);
            }
          }
        } else {
          /* The procedure is slightly different for dangerous nodes.
           * We will update costs if:
           * 1. we are here for the first time;
           * 2. we can possibly go further across dangerous area; or
           * 3. we can have lower extra and will not overwrite anything
           * useful. Node status step B. to C. */
          if (node1->status == NS_INIT) {
            // case 1.
            node1->extra_cost = extra;
            node1->cost = cost;
            node1->dir_to_here = dir;
            node1->status = NS_NEW;
            node1->waited = (node->status == NS_WAITING);
            // Extra costs of all nodes in danger_queue are equal!
            map_index_pq_insert(pfdm->danger_queue, tindex1, -cost);
          } else if ((pf_moves_left(params, cost)
                      > pf_moves_left(params, node1->cost))
                     || (node1->status == NS_PROCESSED
                         && (pf_total_CC(params, cost, extra) < pf_total_CC(
                                 params, node1->cost, node1->extra_cost)))) {
            // case 2 or 3.
            node1->extra_cost = extra;
            node1->cost = cost;
            node1->dir_to_here = dir;
            node1->status = NS_NEW;
            node1->waited = (node->status == NS_WAITING);
            // Extra costs of all nodes in danger_queue are equal!
            map_index_pq_replace(pfdm->danger_queue, tindex1, -cost);
          }
        }
      }
      adjc_dir_iterate_end;
    }
 
    if (NS_WAITING == node->status) {
      // Node status final step E. to F.
#ifdef PF_DEBUG
      fc_assert(!node->is_dangerous);
#endif
      node->status = NS_PROCESSED;
    } else if (!node->is_dangerous
               && (pf_moves_left(params, node->cost)
                   < pf_move_rate(params))) {
      int fc, cc;
      /* Consider waiting at this node. To do it, put it back into queue.
       * Node status final step D. to E. */
      fc = pf_danger_map_fill_cost_for_full_moves(params, node->cost);
      cc = pf_total_CC(params, fc, node->extra_cost);
      node->status = NS_WAITING;
      map_index_pq_insert(pfdm->queue, tindex, -cc);
    }
 
    /* Get the next node (the index with the highest priority). First try
     * to get it from danger_queue. */
    if (map_index_pq_remove(pfdm->danger_queue, &tindex)) {
      // Change the pf_map iterator and reset data.
      tile = index_to_tile(params->map, tindex);
      pfm->tile = tile;
      node = pfdm->lattice + tindex;
    } else {
      // No dangerous nodes to process, go for a safe one.
      if (!map_index_pq_remove(pfdm->queue, &tindex)) {
        // No more indexes in the priority queue, iteration end.
        return false;
      }
 
#ifdef PF_DEBUG
      fc_assert(NS_PROCESSED != pfdm->lattice[tindex].status);
#endif
 
      // Change the pf_map iterator and reset data.
      tile = index_to_tile(params->map, tindex);
      pfm->tile = tile;
      node = pfdm->lattice + tindex;
      if (NS_WAITING != node->status) {
        // Node status step C. and D.
#ifdef PF_DEBUG
        fc_assert(!node->is_dangerous);
#endif
        node->status = NS_PROCESSED;
        return true;
      }
    }
 
#ifdef PF_DEBUG
    fc_assert(NS_INIT < node->status);
 
    if (NS_WAITING == node->status) {
      // We've already returned this node once, skip it.
      log_debug("Considering waiting at (%d, %d)", TILE_XY(tile));
    } else if (node->is_dangerous) {
      // We don't return dangerous tiles.
      log_debug("Reached dangerous tile (%d, %d)", TILE_XY(tile));
    }
#endif
 
    scope = pf_move_scope(node->move_scope);
  }
 
  qCritical("%s(): internal error.", __FUNCTION__);
  return false;
}
 
static inline bool pf_danger_map_iterate_until(struct pf_danger_map *pfdm,
                                               struct tile *ptile)
{
  struct pf_map *pfm = PF_MAP(pfdm);
  struct pf_danger_node *node = pfdm->lattice + tile_index(ptile);
 
  // Start position is handled in every function calling this function.
 
  if (NS_UNINIT == node->status) {
    // Initialize the node, for doing the following tests.
    if (!pf_danger_node_init(pfdm, node, ptile, PF_MS_NONE)
        || node->is_dangerous) {
      return false;
    }
  } else if (TB_IGNORE == node->behavior || node->is_dangerous) {
    /* Simpliciation: if we cannot enter this node at all, or we cannot
     * stay at this position, don't iterate the whole map. */
    return false;
  }
 
  while (NS_PROCESSED != node->status && NS_WAITING != node->status) {
    if (!pf_map_iterate(pfm)) {
      /* All reachable destination have been iterated, 'ptile' is
       * unreachable. */
      return false;
    }
  }
 
  return true;
}
 
static int pf_danger_map_move_cost(struct pf_map *pfm, struct tile *ptile)
{
  struct pf_danger_map *pfdm = PF_DANGER_MAP(pfm);
 
  if (ptile == pfm->params.start_tile) {
    return 0;
  } else if (pf_danger_map_iterate_until(pfdm, ptile)) {
    return (pfdm->lattice[tile_index(ptile)].cost
            - pf_move_rate(pf_map_parameter(pfm))
            + pf_moves_left_initially(pf_map_parameter(pfm)));
  } else {
    return PF_IMPOSSIBLE_MC;
  }
}
 
static PFPath pf_danger_map_path(struct pf_map *pfm, struct tile *ptile)
{
  struct pf_danger_map *pfdm = PF_DANGER_MAP(pfm);
 
  if (ptile == pfm->params.start_tile) {
    return PFPath(pf_map_parameter(pfm));
  } else if (pf_danger_map_iterate_until(pfdm, ptile)) {
    return pf_danger_map_construct_path(pfdm, ptile);
  } else {
    return PFPath();
  }
}
 
static bool pf_danger_map_position(struct pf_map *pfm, struct tile *ptile,
                                   struct pf_position *pos)
{
  struct pf_danger_map *pfdm = PF_DANGER_MAP(pfm);
 
  if (ptile == pfm->params.start_tile) {
    pf_position_fill_start_tile(pos, pf_map_parameter(pfm));
    return true;
  } else if (pf_danger_map_iterate_until(pfdm, ptile)) {
    pf_danger_map_fill_position(pfdm, ptile, pos);
    return true;
  } else {
    return false;
  }
}
 
static void pf_danger_map_destroy(struct pf_map *pfm)
{
  struct pf_danger_map *pfdm = PF_DANGER_MAP(pfm);
  struct pf_danger_node *node;
  int i;
 
  // Need to clean up the dangling danger segments.
  for (i = 0, node = pfdm->lattice; i < MAP_INDEX_SIZE; i++, node++) {
    delete[] node->danger_segment;
    node->danger_segment = nullptr;
  }
  delete[] pfdm->lattice;
  map_index_pq_destroy(pfdm->queue);
  map_index_pq_destroy(pfdm->danger_queue);
  delete pfdm;
}
 
static struct pf_map *pf_danger_map_new(const struct pf_parameter *parameter)
{
  struct pf_danger_map *pfdm;
  struct pf_map *base_map;
  struct pf_parameter *params;
  struct pf_danger_node *node;
 
  pfdm = new pf_danger_map;
  base_map = &pfdm->base_map;
  params = &base_map->params;
#ifdef PF_DEBUG
  // Set the mode, used for cast check.
  base_map->mode = PF_DANGER;
#endif // PF_DEBUG
 
  // Allocate the map.
  pfdm->lattice = new pf_danger_node[MAP_INDEX_SIZE]();
  pfdm->queue = map_index_pq_new(INITIAL_QUEUE_SIZE);
  pfdm->danger_queue = map_index_pq_new(INITIAL_QUEUE_SIZE);
 
  // 'get_MC' callback must be set.
  fc_assert_ret_val(parameter->get_MC != nullptr, nullptr);
 
  // 'is_pos_dangerous' callback must be set.
  fc_assert_ret_val(parameter->is_pos_dangerous != nullptr, nullptr);
 
  // 'get_move_scope' callback must be set.
  fc_assert_ret_val(parameter->get_move_scope != nullptr, nullptr);
 
  // Copy parameters
  *params = *parameter;
 
  // Initialize virtual function table.
  base_map->destroy = pf_danger_map_destroy;
  base_map->get_move_cost = pf_danger_map_move_cost;
  base_map->get_path = pf_danger_map_path;
  base_map->get_position = pf_danger_map_position;
  base_map->iterate = pf_danger_map_iterate;
 
  // Initialise starting node.
  node = pfdm->lattice + tile_index(params->start_tile);
  if (!pf_danger_node_init(pfdm, node, params->start_tile, PF_MS_NONE)) {
    // Always fails.
    fc_assert(
        true
        == pf_danger_node_init(pfdm, node, params->start_tile, PF_MS_NONE));
  }
 
  /* NB: do not handle params->transported_by_initially because we want to
   * handle only at start, not when crossing over the start tile for a
   * second time. See pf_danger_map_iterate(). */
 
  // Initialise the iterator.
  base_map->tile = params->start_tile;
 
  /* This makes calculations of turn/moves_left more convenient, but we
   * need to subtract this value before we return cost to the user. Note
   * that cost may be negative if moves_left_initially > move_rate
   * (see pf_turns()). */
  node->cost = pf_move_rate(params) - pf_moves_left_initially(params);
  node->extra_cost = 0;
  node->dir_to_here = direction8_invalid();
  node->status = (node->is_dangerous ? NS_NEW : NS_PROCESSED);
 
  return PF_MAP(pfdm);
}
 
// ================= Specific pf_fuel_* mode structures ==================
 
/* Fuel path-finding maps are used for units which need to refuel. Usually
 * for air units such as planes or missiles.
 *
 * A big difference with the danger path-finding maps is that the tiles
 * which are not refuel points are not considered as dangerous because the
 * server uses to move the units at the end of the turn to refuels points. */
 
struct pf_fuel_pos;
 
// Node definition. Note we try to have the smallest data as possible.
struct pf_fuel_node {
  signed short cost;   /* total_MC. 'cost' may be negative, see comment in
                        * pf_turns(). */
  unsigned extra_cost; // total_EC. Can be huge, (higher than 'cost').
  unsigned moves_left : 12; // Moves left at this position.
  unsigned dir_to_here : 4; /* Direction from which we came. It's
                             * an 'enum direction8' including
                             * possibility of direction8_invalid (so we need
                             * 4 bits) */
  unsigned status : 3;      // 'enum pf_node_status' really.
 
  // Cached values
  unsigned move_scope : 3;      // 'enum pf_move_scope really.
  unsigned action : 2;          // 'enum pf_action really.
  unsigned node_known_type : 2; // 'enum known_type' really.
  unsigned behavior : 2;        // 'enum tile_behavior' really.
  unsigned zoc_number : 2;      // 'enum pf_zoc_type' really.
  signed moves_left_req : 13;   /* The minimum required moves left to reach
                                 * this tile. It the number of moves we need
                                 * to reach the nearest refuel point. A
                                 * value of 0 means this is a refuel point.
                                 * FIXME: this is right only for units with
                                 * constant move costs! */
  unsigned short extra_tile;    // EC
  unsigned short cost_to_here[DIR8_MAGIC_MAX]; // Step cost[dir to here]
 
  /* Segment leading across the danger area back to the nearest safe node:
   * need to remember costs and stuff. */
  struct pf_fuel_pos *pos;
  // Optimal segment to follow to get there (when node is processed).
  struct pf_fuel_pos *segment;
};
 
/* We need to remember how we could get to there (until the previous refuel
 * point, or start position), because we could re-process the nodes after
 * having waiting somewhere. */
struct pf_fuel_pos {
  signed short cost;
  unsigned extra_cost;
  unsigned moves_left : 12;
  unsigned dir_to_here : 4;
  unsigned ref_count : 4;
  struct pf_fuel_pos *prev;
};
 
// Derived structure of struct pf_map.
struct pf_fuel_map {
  struct pf_map base_map; // Base structure, must be the first!
 
  struct map_index_pq *queue; /* Queue of nodes we have reached but not
                               * processed yet (NS_NEW), sorted by their
                               * total_CC */
  struct map_index_pq *waited_queue; /* Queue of nodes to reach farer
                                      * positions after having refueled. */
  struct pf_fuel_node *lattice;      // Lattice of nodes
};
 
// Up-cast macro.
#ifdef PF_DEBUG
static inline pf_fuel_map *pf_fuel_map_check(pf_map *pfm)
{
  fc_assert_ret_val_msg(nullptr != pfm && PF_FUEL == pfm->mode, nullptr,
                        "Wrong pf_map to pf_fuel_map conversion.");
  return reinterpret_cast<struct pf_fuel_map *>(pfm);
}
#define PF_FUEL_MAP(pfm) pf_fuel_map_check(pfm)
#else
#define PF_FUEL_MAP(pfm) ((struct pf_fuel_map *) (pfm))
#endif // PF_DEBUG
 
// =================  Specific pf_fuel_* mode functions ==================
 
static inline int pf_fuel_total_CC(const struct pf_parameter *param,
                                   int cost, int extra, int safety)
{
  return pf_total_CC(param, cost, extra) - safety;
}
 
static inline int pf_fuel_waited_total_CC(int cost, int safety)
{
  return PF_TURN_FACTOR * (cost + 1) - safety - 1;
}
 
static inline bool pf_fuel_node_init(struct pf_fuel_map *pffm,
                                     struct pf_fuel_node *node,
                                     struct tile *ptile,
                                     enum pf_move_scope previous_scope)
{
  const struct pf_parameter *params = pf_map_parameter(PF_MAP(pffm));
  enum known_type node_known_type;
  enum pf_action action;
 
#ifdef PF_DEBUG
  fc_assert(NS_UNINIT == node->status);
  // Else, not a critical problem, but waste of time.
#endif
 
  node->status = NS_INIT;
 
  // Establish the "known" status of node.
  if (params->omniscience) {
    node_known_type = TILE_KNOWN_SEEN;
  } else {
    node_known_type = tile_get_known(ptile, params->owner);
  }
  node->node_known_type = node_known_type;
 
  // Establish the tile behavior.
  if (nullptr != params->get_TB) {
    node->behavior = params->get_TB(ptile, node_known_type, params);
    if (TB_IGNORE == node->behavior && params->start_tile != ptile) {
      return false;
    }
  }
 
  if (TILE_UNKNOWN != node_known_type) {
    bool can_disembark;
 
    // Test if we can invade tile.
    if (!utype_has_flag(params->utype, UTYF_CIVILIAN)
        && !player_can_invade_tile(params->owner, ptile)) {
      // Maybe overwrite node behavior.
      if (params->start_tile != ptile) {
        node->behavior = TB_IGNORE;
        return false;
      } else if (TB_NORMAL == node->behavior) {
        node->behavior = TB_IGNORE;
      }
    }
 
    // Test the possibility to perform an action.
    if (nullptr != params->get_action
        && PF_ACTION_NONE
               != (action =
                       params->get_action(ptile, node_known_type, params))) {
      if (PF_ACTION_IMPOSSIBLE == action) {
        // Maybe overwrite node behavior.
        if (params->start_tile != ptile) {
          node->behavior = TB_IGNORE;
          return false;
        } else if (TB_NORMAL == node->behavior) {
          node->behavior = TB_IGNORE;
        }
        action = PF_ACTION_NONE;
      } else if (TB_DONT_LEAVE != node->behavior) {
        // Overwrite node behavior.
        node->behavior = TB_DONT_LEAVE;
      }
      node->action = action;
    } else {
      node->moves_left_req =
          params->get_moves_left_req(ptile, node_known_type, params);
      if (PF_IMPOSSIBLE_MC == node->moves_left_req) {
        // Overwrite node behavior.
        if (params->start_tile == ptile) {
          node->behavior = TB_DONT_LEAVE;
        } else {
          node->behavior = TB_IGNORE;
          return false;
        }
      }
    }
 
    /* Test the possibility to move from/to 'ptile'. */
    node->move_scope = params->get_move_scope(ptile, &can_disembark,
                                              previous_scope, params);
    if (PF_MS_NONE == node->move_scope && PF_ACTION_NONE == node->action
        && params->ignore_none_scopes) {
      // Maybe overwrite node behavior.
      if (params->start_tile != ptile) {
        node->behavior = TB_IGNORE;
        return false;
      } else if (TB_NORMAL == node->behavior) {
        node->behavior = TB_IGNORE;
      }
    } else if (PF_MS_TRANSPORT == node->move_scope && !can_disembark
               && (params->start_tile != ptile
                   || nullptr == params->transported_by_initially)) {
      // Overwrite node behavior.
      node->behavior = TB_DONT_LEAVE;
    }
 
    /* ZOC_MINE means can move unrestricted from/into it, ZOC_ALLIED means
     * can move unrestricted into it, but not necessarily from it. */
    if (nullptr != params->get_zoc && nullptr == tile_city(ptile)
        && !terrain_has_flag(tile_terrain(ptile), TER_NO_ZOC)
        && !params->get_zoc(params->owner, ptile, params->map)) {
      node->zoc_number =
          (0 < unit_list_size(ptile->units) ? ZOC_ALLIED : ZOC_NO);
    }
  } else {
    node->moves_left_req =
        params->get_moves_left_req(ptile, node_known_type, params);
    if (PF_IMPOSSIBLE_MC == node->moves_left_req) {
      // Overwrite node behavior.
      if (params->start_tile == ptile) {
        node->behavior = TB_DONT_LEAVE;
      } else {
        node->behavior = TB_IGNORE;
        return false;
      }
    }
 
    node->move_scope = PF_MS_NATIVE;
  }
 
  // Evaluate the extra cost of the destination.
  if (nullptr != params->get_EC) {
    node->extra_tile = params->get_EC(ptile, node_known_type, params);
  }
 
  return true;
}
 
static inline bool pf_fuel_node_dangerous(const struct pf_fuel_node *node)
{
  return (nullptr == node->pos
          || (node->pos->moves_left < node->moves_left_req
              && PF_ACTION_NONE == node->action));
}
 
static inline struct pf_fuel_pos *pf_fuel_pos_ref(struct pf_fuel_pos *pos)
{
#ifdef PF_DEBUG
  /* Unsure we have enough space to store the new count. Maximum is 10
   * (node->pos, node->segment, and 8 for other_pos->prev). */
  fc_assert(15 > pos->ref_count);
#endif
  pos->ref_count++;
  return pos;
}
 
static inline void pf_fuel_pos_unref(struct pf_fuel_pos *pos)
{
  while (nullptr != pos && 0 == --pos->ref_count) {
    struct pf_fuel_pos *prev = pos->prev;
 
    delete pos;
    pos = prev;
  }
}
 
static inline struct pf_fuel_pos *
pf_fuel_pos_replace(struct pf_fuel_pos *pos, const struct pf_fuel_node *node)
{
  if (nullptr == pos) {
    pos = new pf_fuel_pos;
    pos->ref_count = 1;
  } else if (1 < pos->ref_count) {
    pos->ref_count--;
    pos = new pf_fuel_pos;
    pos->ref_count = 1;
  } else {
#ifdef PF_DEBUG
    fc_assert(1 == pos->ref_count);
#endif
    pf_fuel_pos_unref(pos->prev);
  }
  pos->cost = node->cost;
  pos->extra_cost = node->extra_cost;
  pos->moves_left = node->moves_left;
  pos->dir_to_here = node->dir_to_here;
  pos->prev = nullptr;
 
  return pos;
}
 
static inline void
pf_fuel_finalize_position_base(const struct pf_parameter *param,
                               struct pf_position *pos, int cost,
                               int moves_left)
{
  int move_rate = param->move_rate;
 
  pos->turn = pf_turns(param, cost);
  if (move_rate > 0 && param->start_tile != pos->tile) {
    pos->fuel_left = moves_left / move_rate;
    pos->moves_left = moves_left % move_rate;
  } else if (param->start_tile == pos->tile) {
    pos->fuel_left = param->fuel_left_initially;
    pos->moves_left = param->moves_left_initially;
  } else {
    pos->fuel_left = param->fuel_left_initially;
    pos->moves_left = moves_left;
  }
}
 
static inline 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)
{
  if (head) {
    pf_fuel_finalize_position_base(params, pos, head->cost,
                                   head->moves_left);
  } else {
    pf_fuel_finalize_position_base(params, pos, node->cost,
                                   node->moves_left);
  }
}
 
static void pf_fuel_map_fill_position(const struct pf_fuel_map *pffm,
                                      struct tile *ptile,
                                      struct pf_position *pos)
{
  int tindex = tile_index(ptile);
  struct pf_fuel_node *node = pffm->lattice + tindex;
  struct pf_fuel_pos *head = node->segment;
  const struct pf_parameter *params = pf_map_parameter(PF_MAP(pffm));
 
#ifdef PF_DEBUG
  fc_assert_ret_msg(nullptr != head, "Unreached destination (%d, %d).",
                    TILE_XY(ptile));
#endif // PF_DEBUG
 
  pos->tile = ptile;
  pos->total_EC = head->extra_cost;
  pos->total_MC =
      (head->cost - pf_move_rate(params) + pf_moves_left_initially(params));
  pos->dir_to_here = direction8(head->dir_to_here);
  pos->dir_to_next_pos = direction8_invalid(); // This field does not apply.
  pf_fuel_finalize_position(pos, params, node, head);
}
 
static inline int
pf_fuel_map_fill_cost_for_full_moves(const struct pf_parameter *param,
                                     int cost, int moves_left)
{
#ifdef PF_DEBUG
  fc_assert(0 < param->move_rate);
#endif // PF_DEBUG
  return cost + moves_left % param->move_rate;
}
 
static PFPath pf_fuel_map_construct_path(const struct pf_fuel_map *pffm,
                                         struct tile *ptile)
{
  enum direction8 dir_next = direction8_invalid();
  struct pf_fuel_node *node = pffm->lattice + tile_index(ptile);
  struct pf_fuel_pos *segment = node->segment;
  int length = 1;
  struct tile *iter_tile = ptile;
  const struct pf_parameter *params = pf_map_parameter(PF_MAP(pffm));
  int i;
 
#ifdef PF_DEBUG
  fc_assert_ret_val_msg(nullptr != segment, PFPath(),
                        "Unreached destination (%d, %d).", TILE_XY(ptile));
#endif // PF_DEBUG
 
  // First iterate to find path length.
  /* NB: the start point could be reached in the middle of a segment.
   * See comment for pf_fuel_map_create_segment(). */
  while (direction8_is_valid(direction8(segment->dir_to_here))) {
    if (node->moves_left_req == 0) {
      // A refuel point.
      if (segment != node->segment) {
        length += 2;
        segment = node->segment;
      } else {
        length++;
      }
    } else {
      length++;
    }
 
    // Step backward.
    iter_tile =
        mapstep(params->map, iter_tile, DIR_REVERSE(segment->dir_to_here));
    node = pffm->lattice + tile_index(iter_tile);
    segment = segment->prev;
#ifdef PF_DEBUG
    fc_assert(nullptr != segment);
#endif // PF_DEBUG
  }
  if (node->moves_left_req == 0 && segment != node->segment) {
    // We wait at the start point
    length++;
  }
 
  // Allocate memory for path.
  auto path = PFPath(length);
 
  // Reset variables for main iteration.
  iter_tile = ptile;
  node = pffm->lattice + tile_index(ptile);
  segment = node->segment;
 
  for (i = length - 1; i >= 0; i--) {
    // 1: Deal with waiting.
    if (node->moves_left_req == 0 && segment != node->segment) {
      /* Waited at _this_ tile, need to record it twice in the
       * path. Here we record our state _after_ waiting (e.g.
       * full move points). */
      // MAKE DOUBLY SURE THIS SECTION IS OK
      path[i].tile = iter_tile;
      path[i].total_EC = segment->extra_cost;
      path[i].turn = pf_turns(params, segment->cost);
      path[i].total_MC = ((path[i].turn - 1) * params->move_rate
                          + params->moves_left_initially);
      path[i].moves_left = params->move_rate;
      path[i].fuel_left = params->fuel;
      path[i].dir_to_next_pos = dir_next;
 
      dir_next = direction8_invalid();
      segment = node->segment;
      i--;
      if (nullptr == segment) {
        // We waited at start tile, then 'node->segment' is not set.
#ifdef PF_DEBUG
        fc_assert(iter_tile == params->start_tile);
        fc_assert(0 == i);
#endif // PF_DEBUG
        pf_position_fill_start_tile(&path[i], params);
        return path;
      }
    }
 
    // 2: Fill the current position.
    path[i].tile = iter_tile;
    path[i].total_MC = (pf_moves_left_initially(params)
                        - pf_move_rate(params) + segment->cost);
    path[i].total_EC = segment->extra_cost;
    path[i].dir_to_next_pos = dir_next;
    pf_fuel_finalize_position(&path[i], params, node, segment);
 
    // 3: Check if we finished.
    if (i == 0) {
      // We should be back at the start now!
      fc_assert_ret_val(iter_tile == params->start_tile, PFPath());
      return path;
    }
 
    // 4: Calculate the next direction.
    dir_next = direction8(segment->dir_to_here);
 
    // 5: Step further back.
    iter_tile = mapstep(params->map, iter_tile, DIR_REVERSE(dir_next));
    node = pffm->lattice + tile_index(iter_tile);
    segment = segment->prev;
#ifdef PF_DEBUG
    fc_assert(nullptr != segment);
#endif // PF_DEBUG
  }
 
  fc_assert_msg(false, "Cannot get to the starting point!");
  return PFPath();
}
 
static inline void pf_fuel_map_create_segment(struct pf_fuel_map *pffm,
                                              struct tile *ptile,
                                              struct pf_fuel_node *node)
{
  struct pf_fuel_pos *pos, *next;
  const struct pf_parameter *params = pf_map_parameter(PF_MAP(pffm));
 
  pos = pf_fuel_pos_replace(node->pos, node);
  node->pos = pos;
 
  // Iterate until we reach any built segment.
  do {
    next = pos;
    ptile = mapstep(params->map, ptile, DIR_REVERSE(node->dir_to_here));
    node = pffm->lattice + tile_index(ptile);
    pos = node->pos;
    if (nullptr != pos) {
      if (pos->cost == node->cost && pos->dir_to_here == node->dir_to_here
          && pos->extra_cost == node->extra_cost
          && pos->moves_left == node->moves_left) {
        // Reached an usable segment.
        next->prev = pf_fuel_pos_ref(pos);
        break;
      }
    }
    // Update position.
    pos = pf_fuel_pos_replace(pos, node);
    node->pos = pos;
    next->prev = pf_fuel_pos_ref(pos);
  } while (0 != node->moves_left_req
           && direction8_is_valid(direction8(node->dir_to_here)));
}
 
static inline int pf_fuel_map_adjust_cost(int cost, int moves_left,
                                          int move_rate)
{
  if (move_rate > 0) {
    int remaining_moves = moves_left % move_rate;
 
    if (remaining_moves == 0) {
      remaining_moves = move_rate;
    }
 
    return MIN(cost, remaining_moves);
  } else {
    return MIN(cost, moves_left);
  }
}
 
static inline bool
pf_fuel_map_attack_is_possible(const struct pf_parameter *param,
                               int moves_left, int moves_left_req)
{
  if (utype_can_do_action(param->utype, ACTION_SUICIDE_ATTACK)) {
    // Case missile
    return true;
  } else if (utype_has_flag(param->utype, UTYF_ONEATTACK)) {
    // Case Bombers
    if (moves_left <= param->move_rate) {
      // We are in the last turn of fuel, don't attack
      return false;
    } else {
      return true;
    }
  } else {
    // Case fighters
    return moves_left - SINGLE_MOVE >= moves_left_req;
  }
}
 
static bool pf_fuel_map_iterate(struct pf_map *pfm)
{
  struct pf_fuel_map *const pffm = PF_FUEL_MAP(pfm);
  const struct pf_parameter *const params = pf_map_parameter(pfm);
  struct tile *tile = pfm->tile;
  int tindex = tile_index(tile);
  struct pf_fuel_node *node = pffm->lattice + tindex;
  enum pf_move_scope scope = pf_move_scope(node->move_scope);
  int priority, waited_priority;
  bool waited = false;
 
  /* The previous position is defined by 'tile' (tile pointer), 'node'
   * (the data of the tile for the pf_map), and index (the index of the
   * position in the Freeciv map). */
 
  if (!direction8_is_valid(direction8(node->dir_to_here))
      && nullptr != params->transported_by_initially) {
#ifdef PF_DEBUG
    fc_assert(tile == params->start_tile);
#endif
    scope = pf_move_scope(scope | PF_MS_TRANSPORT);
    if (!utype_can_freely_unload(params->utype,
                                 params->transported_by_initially)
        && nullptr == tile_city(tile)
        && !tile_has_native_base(tile, params->transported_by_initially)) {
      // Cannot disembark, don't leave transporter.
      node->behavior = TB_DONT_LEAVE;
    }
  }
 
  for (;;) {
    // There is no exit from DONT_LEAVE tiles!
    if (node->behavior != TB_DONT_LEAVE && scope != PF_MS_NONE
        && (params->move_rate > 0 || node->cost < 0)) {
      int loc_cost = node->cost;
      int loc_moves_left = node->moves_left;
 
      if (0 == node->moves_left_req && 0 < params->move_rate
          && 0 == loc_moves_left % params->move_rate
          && loc_cost >= params->moves_left_initially) {
        /* We have implicitly refueled at the end of the turn. Update also
         * 'node->moves_left' to ensure to wait there in paths. */
        loc_moves_left = pf_move_rate(params);
        node->moves_left = loc_moves_left;
      }
 
      adjc_dir_iterate(params->map, tile, tile1, dir)
      {
        /* Calculate the cost of every adjacent position and set them in
         * the priority queues for next call to pf_fuel_map_iterate(). */
        int tindex1 = tile_index(tile1);
        struct pf_fuel_node *node1 = pffm->lattice + tindex1;
        int cost, extra = 0;
        int moves_left;
        int cost_of_path, old_cost_of_path;
        struct pf_fuel_pos *pos;
 
        /* As for the previous position, 'tile1', 'node1' and 'tindex1' are
         * defining the adjacent position. */
 
        // Non-full fuel tiles can be updated even after being processed.
        if ((NS_PROCESSED == node1->status || NS_WAITING == node1->status)
            && 0 == node1->moves_left_req) {
          // This gives 15% speedup.
          continue;
        }
 
        // Initialise target tile if necessary
        if (node1->status == NS_UNINIT) {
          /* Only initialize once. See comment for pf_fuel_node_init().
           * Node status step A. to B. */
          if (!pf_fuel_node_init(pffm, node1, tile1, scope)) {
            continue;
          }
        } else if (TB_IGNORE == node1->behavior) {
          // We cannot enter this tile at all!
          continue;
        }
 
        // Is the move ZOC-ok?
        if (node->zoc_number != ZOC_MINE && node1->zoc_number == ZOC_NO) {
          continue;
        }
 
        cost = node1->cost_to_here[dir];
        if (0 == cost) {
          // Evaluate the cost of the move.
          if (PF_ACTION_NONE != node1->action) {
            if (nullptr != params->is_action_possible
                && !params->is_action_possible(
                    tile, scope, tile1, pf_action(node1->action), params)) {
              node1->cost_to_here[dir] = PF_IMPOSSIBLE_MC + 2;
              continue;
            }
            // action move cost depends on action and unit type.
            if (node1->action == PF_ACTION_ATTACK
                && (utype_has_flag(params->utype, UTYF_ONEATTACK)
                    || utype_can_do_action(params->utype,
                                           ACTION_SUICIDE_ATTACK))) {
              /* Assume that the attack will be a suicide attack even if a
               * regular attack may be legal. */
              cost = params->move_rate;
            } else {
              cost = SINGLE_MOVE;
            }
          } else if (node1->node_known_type == TILE_UNKNOWN) {
            cost = params->utype->unknown_move_cost;
          } else {
            cost = params->get_MC(tile, scope, tile1,
                                  pf_move_scope(node1->move_scope), params);
          }
 
          if (cost == FC_INFINITY) {
            /* tile_move_cost_ptrs() uses FC_INFINITY to flag that all
             * movement is spent, e.g., when disembarking from transport. */
            cost = params->move_rate;
          }
 
#ifdef PF_DEBUG
          fc_assert(1 << (8 * sizeof(node1->cost_to_here[dir])) > cost + 2);
          fc_assert(0 < cost + 2);
#endif // PF_DEBUG
 
          node1->cost_to_here[dir] = cost + 2;
          if (cost == PF_IMPOSSIBLE_MC) {
            continue;
          }
        } else if (cost == PF_IMPOSSIBLE_MC + 2) {
          continue;
        } else {
          cost -= 2;
        }
 
        cost =
            pf_fuel_map_adjust_cost(cost, loc_moves_left, params->move_rate);
 
        moves_left = loc_moves_left - cost;
        if (moves_left < node1->moves_left_req
            && (!utype_can_do_action(params->utype, ACTION_SUICIDE_ATTACK)
                || 0 > moves_left)) {
          /* We don't have enough moves left, but missiles
           * can do suicidal attacks. */
          continue;
        }
 
        if (PF_ACTION_ATTACK == node1->action
            && !pf_fuel_map_attack_is_possible(params, loc_moves_left,
                                               node->moves_left_req)) {
          // We wouldn't have enough moves left after attacking.
          continue;
        }
 
        // Total cost at 'tile1'
        cost += loc_cost;
 
        // Evaluate the extra cost of the destination, if it's relevant.
        if (nullptr != params->get_EC) {
          extra = node1->extra_tile + node->extra_cost;
        }
 
        /* Update costs and add to queue, if this is a better route
         * to tile1. Case safe tiles or reached directly without waiting. */
        pos = node1->segment;
        cost_of_path = pf_fuel_total_CC(params, cost, extra,
                                        moves_left - node1->moves_left_req);
        if (node1->status == NS_INIT) {
          // Not calculated yet.
          old_cost_of_path = 0;
        } else if (pos) {
          /* We have a path to this tile. The default values could have been
           * overwritten if we had more moves left to deal with waiting.
           * Then, we have to get back the value of this node to calculate
           * the cost. */
          old_cost_of_path =
              pf_fuel_total_CC(params, pos->cost, pos->extra_cost,
                               pos->moves_left - node1->moves_left_req);
        } else {
          // Default cost
          old_cost_of_path =
              pf_fuel_total_CC(params, node1->cost, node1->extra_cost,
                               node1->moves_left - node1->moves_left_req);
        }
 
        /* Step 1: We test if this route is the best to this tile, by a
         * direct way, not taking in account waiting. */
 
        if (NS_INIT == node1->status
            || (node1->status == NS_NEW
                && cost_of_path < old_cost_of_path)) {
          /* We are reaching this node for the first time, or we found a
           * better route to 'tile1', or we would have more moves lefts
           * at previous position. Let's register 'tindex1' to the
           * priority queue. */
          node1->extra_cost = extra;
          node1->cost = cost;
          node1->moves_left = moves_left;
          node1->dir_to_here = dir;
          /* Always record the segment, including when it is not dangerous
           * to move there. */
          pf_fuel_map_create_segment(pffm, tile1, node1);
          if (NS_INIT == node1->status) {
            // Node status B. to C.
            node1->status = NS_NEW;
            map_index_pq_insert(pffm->queue, tindex1, -cost_of_path);
          } else {
            // else staying at D.
#ifdef PF_DEBUG
            fc_assert(NS_NEW == node1->status);
#endif
            if (cost_of_path < old_cost_of_path) {
              map_index_pq_replace(pffm->queue, tindex1, -cost_of_path);
            }
          }
          continue; // adjc_dir_iterate()
        }
 
        /* Step 2: We test if this route could open better routes for other
         * tiles, if we waited somewhere. */
 
        if (!waited || NS_NEW == node1->status
            || 0 == node1->moves_left_req) {
          /* Stops there if:
           * 1. we didn't wait to get there ;
           * 2. we didn't process yet the node ;
           * 3. this is a refuel point. */
          continue; // adjc_dir_iterate()
        }
 
#ifdef PF_DEBUG
        fc_assert(NS_PROCESSED == node1->status);
#endif
 
        if (moves_left > node1->moves_left
            || (moves_left == node1->moves_left
                && extra < node1->extra_cost)) {
          /* We will update costs if:
           * 1. we would have more moves left than previously on this node.
           * 2. we can have lower extra and will not overwrite anything
           *    useful. */
          node1->extra_cost = extra;
          node1->cost = cost;
          node1->moves_left = moves_left;
          node1->dir_to_here = dir;
          map_index_pq_insert(pffm->waited_queue, tindex1,
                              -pf_fuel_waited_total_CC(
                                  cost, moves_left - node1->moves_left_req));
        }
      }
      adjc_dir_iterate_end;
    }
 
    if (NS_WAITING == node->status) {
      // Node status final step E. to F.
#ifdef PF_DEBUG
      fc_assert(0 == node->moves_left_req);
#endif
      node->status = NS_PROCESSED;
    } else if (0 == node->moves_left_req && PF_ACTION_NONE == node->action
               && node->moves_left < pf_move_rate(params)
#ifdef PF_DEBUG
               && (fc_assert(0 < params->move_rate), 0 < params->move_rate)
#endif
               && (0 != node->moves_left % params->move_rate
                   || node->cost < params->moves_left_initially)) {
      /* Consider waiting at this node. To do it, put it back into queue.
       * Node status final step D. to E. */
      node->status = NS_WAITING;
      /* The values we use now to calculate waited total_CC
       * will be applied to the node after we get it back from the queue
       * to get passing-by segments before it without waiting */
      map_index_pq_insert(
          pffm->queue, tindex,
          -pf_fuel_waited_total_CC(pf_fuel_map_fill_cost_for_full_moves(
                                       params, node->cost, node->moves_left),
                                   pf_move_rate(params)));
    }
 
    /* Get the next node (the index with the highest priority). First try
     * to get it from waited_queue. */
    if (!map_index_pq_priority(pffm->queue, &priority)
        || (map_index_pq_priority(pffm->waited_queue, &waited_priority)
            && priority < waited_priority)) {
      if (!map_index_pq_remove(pffm->waited_queue, &tindex)) {
        // End of the iteration.
        return false;
      }
 
      // Change the pf_map iterator and reset data.
      tile = index_to_tile(params->map, tindex);
      pfm->tile = tile;
      node = pffm->lattice + tindex;
      waited = true;
#ifdef PF_DEBUG
      fc_assert(0 < node->moves_left_req);
      fc_assert(NS_PROCESSED == node->status);
#endif
    } else {
#ifdef PF_DEBUG
      bool success = map_index_pq_remove(pffm->queue, &tindex);
 
      fc_assert(true == success);
#else
      map_index_pq_remove(pffm->queue, &tindex);
#endif
 
      // Change the pf_map iterator and reset data.
      tile = index_to_tile(params->map, tindex);
      pfm->tile = tile;
      node = pffm->lattice + tindex;
 
#ifdef PF_DEBUG
      fc_assert(NS_PROCESSED != node->status);
#endif // PF_DEBUG
 
      waited = (NS_WAITING == node->status);
      if (waited) {
        // Arrange waiting at the node
        node->cost = pf_fuel_map_fill_cost_for_full_moves(params, node->cost,
                                                          node->moves_left);
        node->moves_left = pf_move_rate(params);
      } else if (!pf_fuel_node_dangerous(node)) {
        // Node status step C. and D.
        node->status = NS_PROCESSED;
        node->segment = pf_fuel_pos_ref(node->pos);
        return true;
      }
    }
 
#ifdef PF_DEBUG
    fc_assert(NS_INIT < node->status);
 
    if (NS_WAITING == node->status) {
      // We've already returned this node once, skip it.
      log_debug("Considering waiting at (%d, %d)", TILE_XY(tile));
    } else if (NS_PROCESSED == node->status) {
      // We've already returned this node once, skip it.
      log_debug("Reprocessing tile (%d, %d)", TILE_XY(tile));
    } else if (pf_fuel_node_dangerous(node)) {
      // We don't return dangerous tiles.
      log_debug("Reached dangerous tile (%d, %d)", TILE_XY(tile));
    }
#endif // PF_DEBUG
 
    scope = pf_move_scope(node->move_scope);
  }
 
  qCritical("%s(): internal error.", __FUNCTION__);
  return false;
}
 
static inline bool pf_fuel_map_iterate_until(struct pf_fuel_map *pffm,
                                             struct tile *ptile)
{
  struct pf_map *pfm = PF_MAP(pffm);
  struct pf_fuel_node *node = pffm->lattice + tile_index(ptile);
 
  // Start position is handled in every function calling this function.
 
  if (NS_UNINIT == node->status) {
    // Initialize the node, for doing the following tests.
    if (!pf_fuel_node_init(pffm, node, ptile, PF_MS_NONE)) {
      return false;
    }
  } else if (TB_IGNORE == node->behavior) {
    /* Simpliciation: if we cannot enter this node at all, don't iterate the
     * whole map. */
    return false;
  }
 
  while (nullptr == node->segment) {
    if (!pf_map_iterate(pfm)) {
      /* All reachable destination have been iterated, 'ptile' is
       * unreachable. */
      return false;
    }
  }
 
  return true;
}
 
static int pf_fuel_map_move_cost(struct pf_map *pfm, struct tile *ptile)
{
  struct pf_fuel_map *pffm = PF_FUEL_MAP(pfm);
 
  if (ptile == pfm->params.start_tile) {
    return 0;
  } else if (pf_fuel_map_iterate_until(pffm, ptile)) {
    const struct pf_fuel_node *node = pffm->lattice + tile_index(ptile);
 
    return (node->segment->cost - pf_move_rate(pf_map_parameter(pfm))
            + pf_moves_left_initially(pf_map_parameter(pfm)));
  } else {
    return PF_IMPOSSIBLE_MC;
  }
}
 
static PFPath pf_fuel_map_path(struct pf_map *pfm, struct tile *ptile)
{
  struct pf_fuel_map *pffm = PF_FUEL_MAP(pfm);
 
  if (ptile == pfm->params.start_tile) {
    return PFPath(pf_map_parameter(pfm));
  } else if (pf_fuel_map_iterate_until(pffm, ptile)) {
    return pf_fuel_map_construct_path(pffm, ptile);
  } else {
    return PFPath();
  }
}
 
static bool pf_fuel_map_position(struct pf_map *pfm, struct tile *ptile,
                                 struct pf_position *pos)
{
  struct pf_fuel_map *pffm = PF_FUEL_MAP(pfm);
 
  if (ptile == pfm->params.start_tile) {
    pf_position_fill_start_tile(pos, pf_map_parameter(pfm));
    return true;
  } else if (pf_fuel_map_iterate_until(pffm, ptile)) {
    pf_fuel_map_fill_position(pffm, ptile, pos);
    return true;
  } else {
    return false;
  }
}
 
static void pf_fuel_map_destroy(struct pf_map *pfm)
{
  struct pf_fuel_map *pffm = PF_FUEL_MAP(pfm);
  struct pf_fuel_node *node;
  int i;
 
  // Need to clean up the dangling fuel segments.
  for (i = 0, node = pffm->lattice; i < MAP_INDEX_SIZE; i++, node++) {
    pf_fuel_pos_unref(node->pos);
    pf_fuel_pos_unref(node->segment);
  }
  delete pffm->lattice;
  map_index_pq_destroy(pffm->queue);
  map_index_pq_destroy(pffm->waited_queue);
  delete pffm;
}
 
static struct pf_map *pf_fuel_map_new(const struct pf_parameter *parameter)
{
  struct pf_fuel_map *pffm;
  struct pf_map *base_map;
  struct pf_parameter *params;
  struct pf_fuel_node *node;
 
  // 'get_MC' callback must be set.
  fc_assert_ret_val(parameter->get_MC != nullptr, nullptr);
 
  // 'get_moves_left_req' callback must be set.
  fc_assert_ret_val(parameter->get_moves_left_req != nullptr, nullptr);
 
  // 'get_move_scope' callback must be set.
  fc_assert_ret_val(parameter->get_move_scope != nullptr, nullptr);
 
  pffm = new pf_fuel_map;
  base_map = &pffm->base_map;
  params = &base_map->params;
#ifdef PF_DEBUG
  // Set the mode, used for cast check.
  base_map->mode = PF_FUEL;
#endif // PF_DEBUG
 
  // Allocate the map.
  pffm->lattice = new pf_fuel_node[MAP_INDEX_SIZE]();
  pffm->queue = map_index_pq_new(INITIAL_QUEUE_SIZE);
  pffm->waited_queue = map_index_pq_new(INITIAL_QUEUE_SIZE);
 
  // Copy parameters.
  *params = *parameter;
 
  // Initialize virtual function table.
  base_map->destroy = pf_fuel_map_destroy;
  base_map->get_move_cost = pf_fuel_map_move_cost;
  base_map->get_path = pf_fuel_map_path;
  base_map->get_position = pf_fuel_map_position;
  base_map->iterate = pf_fuel_map_iterate;
 
  // Initialise starting node.
  node = pffm->lattice + tile_index(params->start_tile);
  if (!pf_fuel_node_init(pffm, node, params->start_tile, PF_MS_NONE)) {
    // Always fails.
    fc_assert(
        true
        == pf_fuel_node_init(pffm, node, params->start_tile, PF_MS_NONE));
  }
 
  /* NB: do not handle params->transported_by_initially because we want to
   * handle only at start, not when crossing over the start tile for a
   * second time. See pf_danger_map_iterate(). */
 
  // Initialise the iterator.
  base_map->tile = params->start_tile;
 
  /* This makes calculations of turn/moves_left more convenient, but we
   * need to subtract this value before we return cost to the user. Note
   * that cost may be negative if moves_left_initially > move_rate
   * (see pf_turns()). */
  node->moves_left = pf_moves_left_initially(params);
  node->cost = pf_move_rate(params) - node->moves_left;
  node->extra_cost = 0;
  node->dir_to_here = direction8_invalid();
  // Record a segment. We need it for correct paths.
  node->segment =
      pf_fuel_pos_ref(node->pos = pf_fuel_pos_replace(nullptr, node));
  node->status = NS_PROCESSED;
 
  return PF_MAP(pffm);
}
 
// ====================== pf_map public functions =======================
 
struct pf_map *pf_map_new(const struct pf_parameter *parameter)
{
  if (parameter->is_pos_dangerous) {
    if (parameter->get_moves_left_req) {
      qCritical("path finding code cannot deal with dangers "
                "and fuel together.");
    }
    if (parameter->get_costs) {
      qCritical("jumbo callbacks for danger maps are not yet implemented.");
    }
    return pf_danger_map_new(parameter);
  } else if (parameter->get_moves_left_req) {
    if (parameter->get_costs) {
      qCritical("jumbo callbacks for fuel maps are not yet implemented.");
    }
    return pf_fuel_map_new(parameter);
  }
 
  return pf_normal_map_new(parameter);
}
 
void pf_map_destroy(struct pf_map *pfm)
{
#ifdef PF_DEBUG
  fc_assert_ret(nullptr != pfm);
#endif
  pfm->destroy(pfm);
}
 
int pf_map_move_cost(struct pf_map *pfm, struct tile *ptile)
{
#ifdef PF_DEBUG
  fc_assert_ret_val(nullptr != pfm, PF_IMPOSSIBLE_MC);
  fc_assert_ret_val(nullptr != ptile, PF_IMPOSSIBLE_MC);
#endif
  return pfm->get_move_cost(pfm, ptile);
}
 
PFPath pf_map_path(struct pf_map *pfm, struct tile *ptile)
{
#ifdef PF_DEBUG
  PFPath path;
 
  fc_assert_ret_val(nullptr != pfm, path);
  fc_assert_ret_val(nullptr != ptile, path);
  path = pfm->get_path(pfm, ptile);
 
  if (!path.empty()) {
    const struct pf_parameter *param = pf_map_parameter(pfm);
    const struct pf_position pos = path[0];
 
    fc_assert(path.length() >= 1);
    fc_assert(pos.tile == param->start_tile);
    fc_assert(pos.moves_left == param->moves_left_initially);
    fc_assert(pos.fuel_left == param->fuel_left_initially);
  }
 
  return path;
#else
  return pfm->get_path(pfm, ptile);
#endif
}
 
bool pf_map_position(struct pf_map *pfm, struct tile *ptile,
                     struct pf_position *pos)
{
#ifdef PF_DEBUG
  fc_assert_ret_val(nullptr != pfm, false);
  fc_assert_ret_val(nullptr != ptile, false);
#endif
  return pfm->get_position(pfm, ptile, pos);
}
 
bool pf_map_iterate(struct pf_map *pfm)
{
#ifdef PF_DEBUG
  fc_assert_ret_val(nullptr != pfm, false);
#endif
 
  if (nullptr == pfm->tile) {
    /* The end of the iteration was already reached. Don't try to iterate
     * again. */
    return false;
  }
 
  if (!pfm->iterate(pfm)) {
    // End of iteration.
    pfm->tile = nullptr;
    return false;
  }
 
  return true;
}
 
struct tile *pf_map_iter(struct pf_map *pfm)
{
#ifdef PF_DEBUG
  fc_assert_ret_val(nullptr != pfm, nullptr);
#endif
  return pfm->tile;
}
 
int pf_map_iter_move_cost(struct pf_map *pfm)
{
#ifdef PF_DEBUG
  fc_assert_ret_val(nullptr != pfm, PF_IMPOSSIBLE_MC);
  fc_assert_ret_val(nullptr != pfm->tile, PF_IMPOSSIBLE_MC);
#endif
  return pfm->get_move_cost(pfm, pfm->tile);
}
 
PFPath pf_map_iter_path(struct pf_map *pfm)
{
#ifdef PF_DEBUG
  fc_assert_ret_val(nullptr != pfm, PFPath());
  fc_assert_ret_val(nullptr != pfm->tile, PFPath());
#endif
  return pfm->get_path(pfm, pfm->tile);
}
 
void pf_map_iter_position(struct pf_map *pfm, struct pf_position *pos)
{
#ifdef PF_DEBUG
  fc_assert_ret(nullptr != pfm);
  fc_assert_ret(nullptr != pfm->tile);
#endif
  if (!pfm->get_position(pfm, pfm->tile, pos)) {
    // Always fails.
    fc_assert(pfm->get_position(pfm, pfm->tile, pos));
  }
}
 
const struct pf_parameter *pf_map_parameter(const struct pf_map *pfm)
{
#ifdef PF_DEBUG
  fc_assert_ret_val(nullptr != pfm, nullptr);
#endif
  return &pfm->params;
}
 
// ====================== PFPath public functions =======================
 
static void pf_position_fill_start_tile(struct pf_position *pos,
                                        const struct pf_parameter *param)
{
  pos->tile = param->start_tile;
  pos->turn = 0;
  pos->moves_left = param->moves_left_initially;
  pos->fuel_left = param->fuel_left_initially;
  pos->total_MC = 0;
  pos->total_EC = 0;
  pos->dir_to_next_pos = direction8_invalid();
  pos->dir_to_here = direction8_invalid();
}
 
// Constructor to just initialize with size
PFPath::PFPath(int size) : positions(std::vector<pf_position>(size)) {}
PFPath::PFPath(const struct pf_parameter *param)
    : positions(std::vector<pf_position>(1))
{
  pf_position_fill_start_tile(&positions[0], param);
}
 
// Destructor
PFPath::~PFPath() { positions.clear(); }
// Check if path is empty
bool PFPath::empty() const { return positions.empty(); }
// Return Length of path
int PFPath::length() const { return positions.size(); }
bool PFPath::advance(struct tile *ptile)
{
  int i;
  int length = positions.size();
  for (i = 0; positions[i].tile != ptile; i++) {
    if (i >= length) {
      return false;
    }
  }
  fc_assert_ret_val(i < length, false);
  length -= i;
  std::vector<pf_position> new_positions(length);
  for (int j = 0; j < length; j++) {
    new_positions[j] = positions[i + j];
  }
  positions = new_positions;
  return true;
}
 
pf_position &PFPath::operator[](int i)
{
  if (i < 0) {
    fc_assert_msg((-i <= positions.size()), "id %d/%zu", i,
                  positions.size());
    return positions[positions.size() + i];
  }
  fc_assert_msg((i < positions.size()), "id %d/%zu", i, positions.size());
  return positions[i];
}
 
const pf_position &PFPath::operator[](int i) const
{
  if (i < 0) {
    fc_assert_msg((-i <= positions.size()), "id %d/%zu", i,
                  positions.size());
    return positions[positions.size() + i];
  }
  fc_assert_msg((i < positions.size()), "id %d/%zu", i, positions.size());
  return positions[i];
}
 
QDebug &operator<<(QDebug &logger, const PFPath &path)
{
  struct pf_position pos;
  int i;
 
  if (!path.empty()) {
    logger << QString::asprintf(
        "PF: path (at %p) consists of %d positions:\n", (void *) &path,
        path.length());
  } else {
    logger << "PF: path is empty";
    return logger;
  }
 
  for (i = 0; i < path.length(); i++) {
    pos = path[i];
    logger << QString::asprintf(
        "PF:   %2d/%2d: (%2d,%2d) dir=%-2s cost=%2d (%2d, %d) EC=%d\n",
        i + 1, path.length(), TILE_XY(pos.tile),
        dir_get_name(pos.dir_to_next_pos), pos.total_MC, pos.turn,
        pos.moves_left, pos.total_EC);
  }
  return logger;
}
 
// ===================== pf_reverse_map functions ========================
 
/* The path-finding reverse maps are used check the move costs that the
 * units needs to reach the start tile. It stores a pf_map for every unit
 * type. */
 
static const enum unit_type_flag_id signifiant_flags[3] = {
    UTYF_IGTER, UTYF_CIVILIAN, UTYF_COAST_STRICT};
 
inline bool operator==(const pf_parameter &e1, const pf_parameter &e2)
{
  size_t i;
  static const size_t signifiant_flags_num = ARRAY_SIZE(signifiant_flags);
 
  if (e1.start_tile != e2.start_tile || e1.move_rate != e2.move_rate) {
    return false;
  }
 
  if (e1.utype == e2.utype) {
    // Short test.
    return true;
  }
 
  if (utype_class(e1.utype) != utype_class(e2.utype)) {
    return false;
  }
 
  if (!e1.omniscience) {
#ifdef PF_DEBUG
    fc_assert(e2.omniscience == false);
#endif
    if (e1.utype->unknown_move_cost != e2.utype->unknown_move_cost) {
      return false;
    }
  }
 
  for (i = 0; i < signifiant_flags_num; i++) {
    if (utype_has_flag(e1.utype, signifiant_flags[i])
        != utype_has_flag(e2.utype, signifiant_flags[i])) {
      return false;
    }
  }
 
  return true;
}
 
// The reverse map structure.
struct pf_reverse_map {
  struct tile *target_tile;            // Where we want to go.
  int max_turns;                       // The maximum of turns.
  struct pf_parameter template_params; // Keep a parameter ready for usage.
  QHash<const pf_parameter *, struct pf_position *>
      *hash; // A hash where pf_position are stored.
};
 
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 *map)
{
  auto *pfrm = new pf_reverse_map;
  struct pf_parameter *param = &pfrm->template_params;
 
  pfrm->target_tile = target_tile;
  pfrm->max_turns = max_turns;
 
  // Initialize the parameter.
  pft_fill_reverse_parameter(param, target_tile);
  param->owner = pplayer;
  param->omniscience = omniscient;
  param->map = map;
 
  // Initialize the map hash.
  pfrm->hash = new QHash<const pf_parameter *, struct pf_position *>;
 
  return pfrm;
}
 
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 *map)
{
  return pf_reverse_map_new(attacker, city_tile(pcity), max_turns,
                            omniscient, map);
}
 
void pf_reverse_map_destroy(struct pf_reverse_map *pfrm)
{
  fc_assert_ret(nullptr != pfrm);
  QHash<const pf_parameter *, pf_position *>::const_iterator it =
      pfrm->hash->constBegin();
  while (it != pfrm->hash->constEnd()) {
    delete it.key();
    delete it.value();
    ++it;
  }
  delete pfrm->hash;
  delete pfrm;
}
 
static const struct pf_position *
pf_reverse_map_pos(struct pf_reverse_map *pfrm,
                   const struct pf_parameter *param)
{
  struct pf_position *pos;
  struct pf_map *pfm;
  struct pf_parameter *copy;
  struct tile *target_tile;
  const struct pf_normal_node *lattice;
  int max_cost;
 
  // Check if we already processed something similar.
  if (pfrm->hash->contains(param)) {
    pos = pfrm->hash->value(param);
    return pos;
  }
 
  // We didn't. Build map and iterate.
  pfm = pf_normal_map_new(param);
  lattice = PF_NORMAL_MAP(pfm)->lattice;
  target_tile = pfrm->target_tile;
  if (pfrm->max_turns >= 0) {
    max_cost = param->move_rate * (pfrm->max_turns + 1);
    do {
      if (lattice[tile_index(pfm->tile)].cost >= max_cost) {
        break;
      } else if (pfm->tile == target_tile) {
        // Found our position. Insert in hash, destroy map, and return.
        pos = new pf_position;
        pf_normal_map_fill_position(PF_NORMAL_MAP(pfm), target_tile, pos);
        copy = new pf_parameter;
        *copy = *param;
        pfrm->hash->insert(copy, pos);
        pf_map_destroy(pfm);
        return pos;
      }
    } while (pfm->iterate(pfm));
  } else {
    // No limit for iteration.
    do {
      if (pfm->tile == target_tile) {
        // Found our position. Insert in hash, destroy map, and return.
        pos = new pf_position;
        pf_normal_map_fill_position(PF_NORMAL_MAP(pfm), target_tile, pos);
        copy = new pf_parameter;
        *copy = *param;
        pfrm->hash->insert(copy, pos);
        pf_map_destroy(pfm);
        return pos;
      }
    } while (pfm->iterate(pfm));
  }
  pf_map_destroy(pfm);
 
  /* Position not found. Let's insert nullptr as position to avoid to iterate
   * the map again. */
  copy = new pf_parameter;
  *copy = *param;
  pfrm->hash->insert(copy, nullptr);
  return nullptr;
}
 
static inline const struct pf_position *
pf_reverse_map_unit_pos(struct pf_reverse_map *pfrm,
                        const struct unit *punit)
{
  struct pf_parameter *param = &pfrm->template_params;
 
  // Fill parameter.
  param->start_tile = unit_tile(punit);
  param->move_rate = unit_move_rate(punit);
  /* Do not consider punit->moves_left, because this value is usually
   * not restored when calling this function. Let's assume the unit will
   * have its whole move rate. */
  param->moves_left_initially = param->move_rate;
  param->utype = unit_type_get(punit);
  return pf_reverse_map_pos(pfrm, param);
}
 
int pf_reverse_map_unit_move_cost(struct pf_reverse_map *pfrm,
                                  const struct unit *punit)
{
  const struct pf_position *pos = pf_reverse_map_unit_pos(pfrm, punit);
 
  return (pos != nullptr ? pos->total_MC : PF_IMPOSSIBLE_MC);
}
 
bool pf_reverse_map_unit_position(struct pf_reverse_map *pfrm,
                                  const struct unit *punit,
                                  struct pf_position *pos)
{
  const struct pf_position *mypos = pf_reverse_map_unit_pos(pfrm, punit);
 
  if (mypos != nullptr) {
    *pos = *mypos;
    return true;
  } else {
    return false;
  }
}