The Battle for Wesnoth  1.17.0-dev
pathfind.cpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2005 - 2021
3  by Guillaume Melquiond <guillaume.melquiond@gmail.com>
4  Copyright (C) 2003 by David White <dave@whitevine.net>
5  Part of the Battle for Wesnoth Project https://www.wesnoth.org/
6 
7  This program is free software; you can redistribute it and/or modify
8  it under the terms of the GNU General Public License as published by
9  the Free Software Foundation; either version 2 of the License, or
10  (at your option) any later version.
11  This program is distributed in the hope that it will be useful,
12  but WITHOUT ANY WARRANTY.
13 
14  See the COPYING file for more details.
15 */
16 
17 /**
18  * @file
19  * Various pathfinding functions and utilities.
20  */
21 
22 #include "pathfind/pathfind.hpp"
23 #include "pathfind/teleport.hpp"
24 
25 #include "display.hpp"
26 #include "game_board.hpp"
27 #include "gettext.hpp"
28 #include "log.hpp"
29 #include "map/map.hpp"
30 #include "resources.hpp"
31 #include "team.hpp"
32 #include "units/unit.hpp"
33 #include "units/map.hpp"
34 #include "wml_exception.hpp"
35 
36 #include <iostream>
37 #include <vector>
38 #include <algorithm>
39 
40 static lg::log_domain log_engine("engine");
41 #define ERR_PF LOG_STREAM(err, log_engine)
42 
43 namespace pathfind {
44 
45 
46 /**
47  * Function that will find a location on the board that is as near
48  * to @a loc as possible, but which is unoccupied by any units.
49  * If no valid location can be found, it will return a null location.
50  * If @a pass_check is provided, the found location must have a terrain
51  * that this unit can enter.
52  * If @a shroud_check is provided, only locations not covered by this
53  * team's shroud will be considered.
54  */
56  const unit* pass_check, const team* shroud_check, const game_board* board)
57 {
58  if (!board) {
59  board = resources::gameboard;
60  assert(board);
61  }
62  const gamemap & map = board->map();
63  const unit_map & units = board->units();
64 
65  if (!map.on_board(loc)) return map_location();
66 
67  const bool do_shroud = shroud_check && shroud_check->uses_shroud();
68  std::set<map_location> pending_tiles_to_check, tiles_checked;
69  pending_tiles_to_check.insert(loc);
70  // Iterate out 50 hexes from loc
71  for (int distance = 0; distance < 50; ++distance) {
72  if (pending_tiles_to_check.empty())
73  return map_location();
74  //Copy over the hexes to check and clear the old set
75  std::set<map_location> tiles_checking;
76  tiles_checking.swap(pending_tiles_to_check);
77  //Iterate over all the hexes we need to check
78  for (const map_location &l : tiles_checking)
79  {
80  // Skip shrouded locations.
81  if ( do_shroud && shroud_check->shrouded(l) )
82  continue;
83  //If this area is not a castle but should, skip it.
84  if ( vacancy == VACANT_CASTLE && !map.is_castle(l) ) continue;
85  const bool pass_check_and_unreachable = pass_check
86  && pass_check->movement_cost(map[l]) == movetype::UNREACHABLE;
87  //If the unit can't reach the tile and we have searched
88  //an area of at least radius 10 (arbitrary), skip the tile.
89  //Necessary for cases such as an unreachable
90  //starting hex surrounded by 6 other unreachable hexes, in which case
91  //the algorithm would not even search distance==1
92  //even if there's a reachable hex for distance==2.
93  if (pass_check_and_unreachable && distance > 10) continue;
94  //If the hex is empty and we do either no pass check or the hex is reachable, return it.
95  if (units.find(l) == units.end() && !pass_check_and_unreachable) return l;
96 
97  for(const map_location& l2 : get_adjacent_tiles(l)) {
98  if (!map.on_board(l2)) continue;
99  // Add the tile to be checked if it hasn't already been and
100  // isn't being checked.
101  if (tiles_checked.find(l2) == tiles_checked.end() &&
102  tiles_checking.find(l2) == tiles_checking.end())
103  {
104  pending_tiles_to_check.insert(l2);
105  }
106  }
107  }
108  tiles_checked.swap(tiles_checking);
109  }
110  return map_location();
111 }
112 
113 /**
114  * Wrapper for find_vacant_tile() when looking for a vacant castle tile
115  * near a leader.
116  * If no valid location can be found, it will return a null location.
117  */
119 {
121  nullptr, &resources::gameboard->get_team(leader.side()));
122 }
123 
124 
125 /**
126  * Determines if a given location is in an enemy zone of control.
127  *
128  * @param current_team The moving team (only ZoC of enemies of this team are considered).
129  * @param loc The location to check.
130  * @param viewing_team Only units visible to this team are considered.
131  * @param see_all If true, all units are considered (and viewing_team is ignored).
132  *
133  * @return true iff a visible enemy exerts zone of control over loc.
134  */
135 bool enemy_zoc(const team& current_team, const map_location& loc,
136  const team& viewing_team, bool see_all)
137 {
138  // Check the adjacent tiles.
139  for(const map_location& adj : get_adjacent_tiles(loc)) {
140  const unit *u = resources::gameboard->get_visible_unit(adj, viewing_team, see_all);
141  if ( u && current_team.is_enemy(u->side()) && u->emits_zoc() )
142  return true;
143  }
144 
145  // No adjacent tiles had an enemy exerting ZoC over loc.
146  return false;
147 }
148 
149 
150 namespace {
151  /**
152  * Nodes used by find_routes().
153  * These store the information necessary for extending the path
154  * and for tracing the route back to the source.
155  */
156  struct findroute_node {
159  // search_num is used to detect which nodes have been collected
160  // in the current search. (More than just a boolean value so
161  // that nodes can be stored between searches.)
162  unsigned search_num;
163 
164  // Constructors.
165  findroute_node(int moves, int turns, const map_location &prev_loc, unsigned search_count)
166  : moves_left(moves)
167  , turns_left(turns)
168  , prev(prev_loc)
169  , search_num(search_count)
170  { }
171  findroute_node()
172  : moves_left(0)
173  , turns_left(0)
174  , prev()
175  , search_num(0)
176  { }
177 
178  // Compare these nodes based on movement consumed.
179  bool operator<(const findroute_node& o) const
180  {
181  return std::tie(turns_left, moves_left) > std::tie(o.turns_left, o.moves_left);
182  }
183  };
184 
185  /**
186  * Converts map locations to and from integer indices.
187  */
188  struct findroute_indexer {
189  int w, h; // Width and height of the map.
190 
191  // Constructor:
192  findroute_indexer(int a, int b) : w(a), h(b) { }
193  // Convert to an index: (throws on out of bounds)
194  unsigned operator()(int x, int y) const {
195  VALIDATE(this->on_board(x,y),
196  "Pathfind: Location not on board");
197  return x + static_cast<unsigned>(y)*w;
198  }
199  unsigned operator()(const map_location& loc) const {
200  return (*this)(loc.x, loc.y);
201  }
202  // Convert from an index:
203  map_location operator()(unsigned index) const {
204  return map_location(
205  static_cast<int>(index%w),
206  static_cast<int>(index/w));
207  }
208  // Check if location is on board
209  inline bool on_board(const map_location& loc) const {
210  return this->on_board(loc.x, loc.y);
211  }
212  inline bool on_board(int x, int y) const {
213  return (x >= 0) && (x < w) && (y >= 0) && (y < h);
214  }
215  };
216 
217  /**
218  * A function object for comparing indices.
219  */
220  struct findroute_comp {
221  const std::vector<findroute_node>& nodes;
222 
223  // Constructor:
224  findroute_comp(const std::vector<findroute_node>& n) : nodes(n) { }
225  // Binary predicate evaluating the order of its arguments:
226  bool operator()(int l, int r) const {
227  return nodes[r] < nodes[l];
228  }
229  };
230 }
231 
232 /**
233  * Creates a list of routes that a unit can traverse from the provided location.
234  * (This is called when creating pathfind::paths and descendant classes.)
235  *
236  * @param[in] origin The location at which to begin the routes.
237  * @param[in] costs The costs to use for route finding.
238  * @param[in] slowed Whether or not to use the slowed costs.
239  * @param[in] moves_left The number of movement points left for the current turn.
240  * @param[in] max_moves The number of movement points in each future turn.
241  * @param[in] turns_left The number of future turns of movement to calculate.
242  * @param[out] destinations The traversable routes.
243  * @param[out] edges The hexes (possibly off-map) adjacent to those in
244  * destinations. (It is permissible for this to contain
245  * some hexes that are also in destinations.)
246  *
247  * @param[in] teleporter If not nullptr, teleportation will be considered, using
248  * this unit's abilities.
249  * @param[in] current_team If not nullptr, enemies of this team can obstruct routes
250  * both by occupying hexes and by exerting zones of control.
251  * In addition, the presence of units can affect
252  * teleportation options.
253  * @param[in] skirmisher If not nullptr, use this to determine where ZoC can and
254  * cannot be ignored (due to this unit having or not
255  * having the skirmisher ability).
256  * If nullptr, then ignore all zones of control.
257  * (No effect if current_team is nullptr).
258  * @param[in] viewing_team If not nullptr, use this team's vision when detecting
259  * enemy units and teleport destinations.
260  * If nullptr, then "see all".
261  * (No effect if teleporter and current_team are both nullptr.)
262  * @param[in] jamming_map The relevant "jamming" of the costs being used
263  * (currently only used with vision costs).
264  * @param[out] full_cost_map If not nullptr, build a cost_map instead of destinations.
265  * Destinations is ignored.
266  * full_cost_map is a vector of pairs. The first entry is the
267  * cost itself, the second how many units already visited this hex
268  * @param[in] check_vision If true, use vision check for teleports, that is, ignore
269  * units potentially blocking the teleport exit
270  */
271 static void find_routes(
272  const map_location & origin, const movetype::terrain_costs & costs,
273  bool slowed, int moves_left, int max_moves, int turns_left,
274  paths::dest_vect & destinations, std::set<map_location> * edges,
275  const unit * teleporter, const team * current_team,
276  const unit * skirmisher, const team * viewing_team,
277  const std::map<map_location, int> * jamming_map=nullptr,
278  std::vector<std::pair<int, int>> * full_cost_map=nullptr, bool check_vision=false)
279 {
280  const gamemap& map = resources::gameboard->map();
281 
282  const bool see_all = viewing_team == nullptr;
283  // When see_all is true, the viewing team never matters, but we still
284  // need to supply one to some functions.
285  if ( viewing_team == nullptr )
286  viewing_team = &resources::gameboard->teams().front();
287 
288  // Build a teleport map, if needed.
289  const teleport_map teleports = teleporter ?
290  get_teleport_locations(*teleporter, *viewing_team, see_all, current_team == nullptr, check_vision) :
291  teleport_map();
292 
293  // Since this is called so often, keep memory reserved for the node list.
294  static std::vector<findroute_node> nodes;
295  static unsigned search_counter = 0;
296  // Incrementing search_counter means we ignore results from earlier searches.
297  ++search_counter;
298  // Whenever the counter cycles, trash the contents of nodes and restart at 1.
299  if ( search_counter == 0 ) {
300  nodes.resize(0);
301  search_counter = 1;
302  }
303  // Initialize the nodes for this search.
304  nodes.resize(map.w() * map.h());
305  findroute_comp node_comp(nodes);
306  findroute_indexer index(map.w(), map.h());
307 
308  assert(index.on_board(origin));
309 
310  // Check if full_cost_map has the correct size.
311  // If not, ignore it. If yes, initialize the start position.
312  if ( full_cost_map ) {
313  if ( full_cost_map->size() != static_cast<unsigned>(map.w() * map.h()) )
314  full_cost_map = nullptr;
315  else {
316  if ( (*full_cost_map)[index(origin)].second == 0 )
317  (*full_cost_map)[index(origin)].first = 0;
318  (*full_cost_map)[index(origin)].second += 1;
319  }
320  }
321 
322  // Used to optimize the final collection of routes.
323  int xmin = origin.x, xmax = origin.x, ymin = origin.y, ymax = origin.y;
324  int nb_dest = 1;
325 
326  // Record the starting location.
327  nodes[index(origin)] = findroute_node(moves_left, turns_left,
329  search_counter);
330  // Begin the search at the starting location.
331  std::vector<unsigned> hexes_to_process(1, index(origin)); // Will be maintained as a heap.
332 
333  while ( !hexes_to_process.empty() ) {
334  // Process the hex closest to the origin.
335  const unsigned cur_index = hexes_to_process.front();
336  const map_location cur_hex = index(cur_index);
337  const findroute_node& current = nodes[cur_index];
338  // Remove from the heap.
339  std::pop_heap(hexes_to_process.begin(), hexes_to_process.end(), node_comp);
340  hexes_to_process.pop_back();
341 
342  // Get the locations adjacent to current.
343  std::vector<map_location> adj_locs(6);
344  get_adjacent_tiles(cur_hex, adj_locs.data());
345 
346  // Sort adjacents by on-boardness
347  auto off_board_it = std::partition(adj_locs.begin(), adj_locs.end(), [&index](map_location loc){
348  return index.on_board(loc);
349  });
350  // Store off-board edges if needed
351  if(edges != nullptr){
352  edges->insert(off_board_it, adj_locs.end());
353  }
354  // Remove off-board map locations
355  adj_locs.erase(off_board_it, adj_locs.end());
356 
357  if ( teleporter ) {
358  auto allowed_teleports = teleports.get_adjacents(cur_hex);
359  adj_locs.insert(adj_locs.end(), allowed_teleports.begin(), allowed_teleports.end());
360  }
361  for ( int i = adj_locs.size()-1; i >= 0; --i ) {
362  // Get the node associated with this location.
363  const map_location & next_hex = adj_locs[i];
364  const unsigned next_index = index(next_hex);
365  findroute_node & next = nodes[next_index];
366 
367  // Skip nodes we have already collected.
368  // (Since no previously checked routes were longer than
369  // the current one, the current route cannot be shorter.)
370  // (Significant difference from classic Dijkstra: we have
371  // vertex weights, not edge weights.)
372  if ( next.search_num == search_counter )
373  continue;
374 
375  // If we go to next, it will be from current.
376  next.prev = cur_hex;
377 
378  // Calculate the cost of entering next_hex.
379  int cost = costs.cost(map[next_hex], slowed);
380  if ( jamming_map ) {
381  const std::map<map_location, int>::const_iterator jam_it =
382  jamming_map->find(next_hex);
383  if ( jam_it != jamming_map->end() )
384  cost += jam_it->second;
385  }
386 
387  // Calculate movement remaining after entering next_hex.
388  next.moves_left = current.moves_left - cost;
389  next.turns_left = current.turns_left;
390  if ( next.moves_left < 0 ) {
391  // Have to delay until the next turn.
392  next.turns_left--;
393  next.moves_left = max_moves - cost;
394  }
395  if ( next.moves_left < 0 || next.turns_left < 0 ) {
396  // Either can never enter this hex or out of turns.
397  if ( edges != nullptr )
398  edges->insert(next_hex);
399  continue;
400  }
401 
402  if ( current_team ) {
403  // Account for enemy units.
404  const unit *v = resources::gameboard->get_visible_unit(next_hex, *viewing_team, see_all);
405  if ( v && current_team->is_enemy(v->side()) ) {
406  // Cannot enter enemy hexes.
407  if ( edges != nullptr )
408  edges->insert(next_hex);
409  continue;
410  }
411 
412  if ( skirmisher && next.moves_left > 0 &&
413  enemy_zoc(*current_team, next_hex, *viewing_team, see_all) &&
414  !skirmisher->get_ability_bool("skirmisher", next_hex) ) {
415  next.moves_left = 0;
416  }
417  }
418 
419  if ( viewing_team && current_team && viewing_team != current_team && viewing_team->shrouded(next_hex) ) {
420  // bug #2199: in "Show Enemy Moves", don't pathfind enemy units through the player's shroud
421  continue;
422  }
423 
424  // Update full_cost_map
425  if ( full_cost_map ) {
426  if ( (*full_cost_map)[next_index].second == 0 )
427  (*full_cost_map)[next_index].first = 0;
428  int summed_cost = (turns_left - next.turns_left + 1) * max_moves - next.moves_left;
429  (*full_cost_map)[next_index].first += summed_cost;
430  (*full_cost_map)[next_index].second += 1;
431  }
432 
433  // Mark next as being collected.
434  next.search_num = search_counter;
435 
436  // Add this node to the heap.
437  hexes_to_process.push_back(next_index);
438  std::push_heap(hexes_to_process.begin(), hexes_to_process.end(), node_comp);
439 
440  // Bookkeeping (for later).
441  ++nb_dest;
442  if ( next_hex.x < xmin )
443  xmin = next_hex.x;
444  else if ( xmax < next_hex.x )
445  xmax = next_hex.x;
446  if ( next_hex.y < ymin )
447  ymin = next_hex.y;
448  else if ( ymax < next_hex.y )
449  ymax = next_hex.y;
450  }//for (i)
451  }//while (hexes_to_process)
452 
453  // Currently the only caller who uses full_cost_map doesn't need the
454  // destinations. We can skip this part.
455  if ( full_cost_map ) {
456  return;
457  }
458 
459  // Build the routes for every map_location that we reached.
460  // The ordering must be compatible with map_location::operator<.
461  destinations.reserve(nb_dest);
462  for (int x = xmin; x <= xmax; ++x) {
463  for (int y = ymin; y <= ymax; ++y)
464  {
465  const findroute_node &n = nodes[index(x,y)];
466  if ( n.search_num == search_counter ) {
467  paths::step s =
468  { map_location(x,y), n.prev, n.moves_left + n.turns_left*max_moves };
469  destinations.push_back(s);
470  }
471  }
472  }
473 }
474 
475 static bool step_compare(const paths::step& a, const map_location& b) {
476  return a.curr < b;
477 }
478 
479 paths::dest_vect::const_iterator paths::dest_vect::find(const map_location &loc) const
480 {
481  const_iterator i = std::lower_bound(begin(), end(), loc, step_compare);
482  if (i != end() && i->curr != loc) return end();
483  return i;
484 }
485 
487 {
488  iterator i = std::lower_bound(begin(), end(), loc, step_compare);
489  if (i != end() && i->curr == loc) return;
490  paths::step s { loc, map_location(), 0 };
492 }
493 
494 /**
495  * Returns the path going from the source point (included) to the
496  * destination point @a j (excluded).
497  */
498 std::vector<map_location> paths::dest_vect::get_path(const const_iterator &j) const
499 {
500  std::vector<map_location> path;
501  if (!j->prev.valid()) {
502  path.push_back(j->curr);
503  } else {
504  const_iterator i = j;
505  do {
506  i = find(i->prev);
507  assert(i != end());
508  path.push_back(i->curr);
509  } while (i->prev.valid());
510  }
511  std::reverse(path.begin(), path.end());
512  return path;
513 }
514 
516 {
517  return find(loc) != end();
518 }
519 
520 /**
521  * Construct a list of paths for the specified unit.
522  *
523  * This function is used for several purposes, including showing a unit's
524  * potential moves and generating currently possible paths.
525  * @param u The unit whose moves and movement type will be used.
526  * @param force_ignore_zoc Set to true to completely ignore zones of control.
527  * @param allow_teleport Set to true to consider teleportation abilities.
528  * @param viewing_team Usually the current team, except for "show enemy moves", etc.
529  * @param additional_turns The number of turns to account for, in addition to the current.
530  * @param see_all Set to true to remove unit visibility from consideration.
531  * @param ignore_units Set to true if units should never obstruct paths (implies ignoring ZoC as well).
532  */
533 paths::paths(const unit& u, bool force_ignore_zoc,
534  bool allow_teleport, const team &viewing_team,
535  int additional_turns, bool see_all, bool ignore_units)
536  : destinations()
537 {
538  try {
539  find_routes(
540  u.get_location(),
543  u.movement_left(),
544  u.total_movement(),
545  additional_turns,
546  destinations,
547  nullptr,
548  allow_teleport ? &u : nullptr,
549  ignore_units ? nullptr : &resources::gameboard->get_team(u.side()),
550  force_ignore_zoc ? nullptr : &u,
551  see_all ? nullptr : &viewing_team
552  );
553  } catch(const std::out_of_range&) {
554  // Invalid unit side.
555  }
556 }
557 
558 /**
559  * Virtual destructor to support child classes.
560  */
562 {
563 }
564 
565 /**
566  * Constructs a list of vision paths for a unit.
567  *
568  * This is used to construct a list of hexes that the indicated unit can see.
569  * It differs from pathfinding in that it will only ever go out one turn,
570  * and that it will also collect a set of border hexes (the "one hex beyond"
571  * movement to which vision extends).
572  * @param viewer The unit doing the viewing.
573  * @param loc The location from which the viewing occurs
574  * (does not have to be the unit's location).
575  * @param jamming_map The relevant "jamming" of the costs being used.
576  */
577 vision_path::vision_path(const unit& viewer, const map_location& loc,
578  const std::map<map_location, int>& jamming_map)
579  : paths(), edges()
580 {
581  const int sight_range = viewer.vision();
582 
583  // The three nullptr parameters indicate (in order):
584  // ignore units, ignore ZoC (no effect), and don't build a cost_map.
585  const team& viewing_team = resources::gameboard->teams()[display::get_singleton()->viewing_team()];
586  find_routes(loc, viewer.movement_type().get_vision(),
587  viewer.get_state(unit::STATE_SLOWED), sight_range, sight_range,
588  0, destinations, &edges, &viewer, nullptr, nullptr, &viewing_team, &jamming_map, nullptr, true);
589 }
590 
591 /**
592  * Constructs a list of vision paths for a unit.
593  *
594  * This constructor is provided so that only the relevant portion of a unit's
595  * data is required to construct the vision paths.
596  * @param view_costs The vision costs of the unit doing the viewing.
597  * @param slowed Whether or not the unit is slowed.
598  * @param sight_range The vision() of the unit.
599  * @param loc The location from which the viewing occurs
600  * (does not have to be the unit's location).
601  * @param jamming_map The relevant "jamming" of the costs being used.
602  */
604  int sight_range, const map_location & loc,
605  const std::map<map_location, int>& jamming_map)
606  : paths(), edges()
607 {
608  // The three nullptr parameters indicate (in order):
609  // ignore units, ignore ZoC (no effect), and don't build a cost_map.
610  const team& viewing_team = resources::gameboard->teams()[display::get_singleton()->viewing_team()];
612  find_routes(loc, view_costs, slowed, sight_range, sight_range, 0,
613  destinations, &edges, u.valid() ? &*u : nullptr, nullptr, nullptr, &viewing_team, &jamming_map, nullptr, true);
614 }
615 
616 /** Default destructor */
618 {
619 }
620 
621 
622 /**
623  * Constructs a list of jamming paths for a unit.
624  *
625  * This is used to construct a list of hexes that the indicated unit can jam.
626  * It differs from pathfinding in that it will only ever go out one turn.
627  * @param jammer The unit doing the jamming.
628  * @param loc The location from which the jamming occurs
629  * (does not have to be the unit's location).
630  */
631 jamming_path::jamming_path(const unit& jammer, const map_location& loc)
632  : paths()
633 {
634  const int jamming_range = jammer.jamming();
635 
636  // The five nullptr parameters indicate (in order): no edges, no teleports,
637  // ignore units, ignore ZoC (no effect), and see all (no effect).
638  find_routes(loc, jammer.movement_type().get_jamming(),
639  jammer.get_state(unit::STATE_SLOWED), jamming_range, jamming_range,
640  0, destinations, nullptr, nullptr, nullptr, nullptr, nullptr);
641 }
642 
643 /** Default destructor */
645 {
646 }
647 
648 marked_route mark_route(const plain_route &rt, bool update_move_cost)
649 {
650  marked_route res;
651 
652  if (rt.steps.empty()) return marked_route();
653  res.route = rt;
654 
656  if (it == resources::gameboard->units().end()) return marked_route();
657  const unit& u = *it;
658 
659  int turns = 0;
660  int total_costs = 0;
661  int movement = u.movement_left();
662  const team& unit_team = resources::gameboard->get_team(u.side());
663  bool zoc = false;
664 
665  std::vector<map_location>::const_iterator i = rt.steps.begin();
666 
667  for (; i !=rt.steps.end(); ++i) {
668  bool last_step = (i+1 == rt.steps.end());
669 
670  // move_cost of the next step is irrelevant for the last step
671  assert(last_step || resources::gameboard->map().on_board(*(i+1)));
672  const int move_cost = last_step ? 0 : u.movement_cost(static_cast<const game_board*>(resources::gameboard)->map()[*(i+1)]);
673 
674  const team& viewing_team = resources::gameboard->teams()[display::get_singleton()->viewing_team()];
675 
676  if (last_step || zoc || move_cost > movement) {
677  // check if we stop an a village and so maybe capture it
678  // if it's an enemy unit and a fogged village, we assume a capture
679  // (if he already owns it, we can't know that)
680  // if it's not an enemy, we can always know if he owns the village
681  bool capture = resources::gameboard->map().is_village(*i) && ( !unit_team.owns_village(*i)
682  || (viewing_team.is_enemy(u.side()) && viewing_team.fogged(*i)) );
683 
684  ++turns;
685 
686  bool invisible = u.invisible(*i, false);
687 
688  res.marks[*i] = marked_route::mark(turns, zoc, capture, invisible);
689 
690  if(last_step) {
691  if(capture) {
692  total_costs += movement;
693  }
694  break; // finished and we used dummy move_cost
695  }
696 
697  total_costs += movement;
698  movement = u.total_movement();
699  if(move_cost > movement) {
700  return res; //we can't reach destination
701  }
702  }
703 
704  zoc = enemy_zoc(unit_team, *(i + 1), viewing_team)
705  && !u.get_ability_bool("skirmisher", *(i+1));
706 
707  if (zoc) {
708  total_costs += movement;
709  movement = 0;
710  } else {
711  movement -= move_cost;
712  total_costs += move_cost;
713  }
714  }
715 
716  if(update_move_cost) {
717  res.move_cost = total_costs;
718  }
719  return res;
720 }
721 
723  const std::vector<team>& teams, const gamemap& map,
724  bool ignore_unit, bool ignore_defense, bool see_all)
725  : unit_(u), viewing_team_(t), teams_(teams), map_(map),
726  movement_left_(unit_.movement_left()),
727  total_movement_(unit_.total_movement()),
728  ignore_unit_(ignore_unit), ignore_defense_(ignore_defense),
729  see_all_(see_all)
730 {}
731 
732 double shortest_path_calculator::cost(const map_location& loc, const double so_far) const
733 {
734  assert(map_.on_board(loc));
735 
736  // loc is shrouded, consider it impassable
737  // NOTE: This is why AI must avoid to use shroud
738  if (!see_all_ && viewing_team_.shrouded(loc))
739  return getNoPathValue();
740 
741  const t_translation::terrain_code terrain = map_[loc];
742  const int terrain_cost = unit_.movement_cost(terrain);
743  // Pathfinding heuristic: the cost must be at least 1
744  VALIDATE(terrain_cost >= 1, _("Terrain with a movement cost less than 1 encountered."));
745 
746  // Compute how many movement points are left in the game turn
747  // needed to reach the previous hex.
748  // total_movement_ is not zero, thanks to the pathfinding heuristic
749  int remaining_movement = movement_left_ - static_cast<int>(so_far);
750  if (remaining_movement < 0) {
751  remaining_movement = total_movement_ - (-remaining_movement) % total_movement_;
752  }
753 
754  if (terrain_cost >= movetype::UNREACHABLE || (total_movement_ < terrain_cost && remaining_movement < terrain_cost)) {
755  return getNoPathValue();
756  }
757 
758  int other_unit_subcost = 0;
759  if (!ignore_unit_) {
760  const unit *other_unit =
762 
763  // We can't traverse visible enemy and we also prefer empty hexes
764  // (less blocking in multi-turn moves and better when exploring fog,
765  // because we can't stop on a friend)
766 
767  if (other_unit)
768  {
769  if (teams_[unit_.side() - 1].is_enemy(other_unit->side()))
770  return getNoPathValue();
771  else
772  // This value will be used with the defense_subcost (see below)
773  // The 1 here means: consider occupied hex as a -1% defense
774  // (less important than 10% defense because friends may move)
775  other_unit_subcost = 1;
776  }
777  }
778 
779  // this will sum all different costs of this move
780  int move_cost = 0;
781 
782  // Suppose that we have only 2 remaining MP and want to move onto a hex
783  // costing 3 MP. We don't have enough MP now, so we must end our turn here,
784  // thus spend our remaining MP by waiting (next turn, with full MP, we will
785  // be able to move on that hex)
786  if (remaining_movement < terrain_cost) {
787  move_cost += remaining_movement;
788  remaining_movement = total_movement_; // we consider having full MP now
789  }
790 
791  // check ZoC
792  if (!ignore_unit_ && remaining_movement != terrain_cost
794  && !unit_.get_ability_bool("skirmisher", loc)) {
795  // entering ZoC cost all remaining MP
796  move_cost += remaining_movement;
797  } else {
798  // empty hex, pay only the terrain cost
799  move_cost += terrain_cost;
800  }
801 
802  // We will add a tiny cost based on terrain defense, so the pathfinding
803  // will prefer good terrains between 2 with the same MP cost
804  // Keep in mind that defense_modifier is inverted (= 100 - defense%)
805  const int defense_subcost = ignore_defense_ ? 0 : unit_.defense_modifier(terrain);
806 
807  // We divide subcosts by 100 * 100, because defense is 100-based and
808  // we don't want any impact on move cost for less then 100-steps path
809  // (even ~200 since mean defense is around ~50%)
810  return move_cost + (defense_subcost + other_unit_subcost) / 10000.0;
811 }
812 
813 move_type_path_calculator::move_type_path_calculator(const movetype& mt, int movement_left, int total_movement, const team& t, const gamemap& map)
814  : movement_type_(mt), movement_left_(movement_left),
815  total_movement_(total_movement), viewing_team_(t), map_(map)
816 {}
817 
818 // This is an simplified version of shortest_path_calculator (see above for explanation)
819 double move_type_path_calculator::cost(const map_location& loc, const double so_far) const
820 {
821  assert(map_.on_board(loc));
822  if (viewing_team_.shrouded(loc))
823  return getNoPathValue();
824 
825  const t_translation::terrain_code terrain = map_[loc];
826  const int terrain_cost = movement_type_.movement_cost(terrain);
827 
828  if (total_movement_ < terrain_cost)
829  return getNoPathValue();
830 
831  int remaining_movement = movement_left_ - static_cast<int>(so_far);
832  if (remaining_movement < 0)
833  remaining_movement = total_movement_ - (-remaining_movement) % total_movement_;
834 
835  int move_cost = 0;
836 
837  if (remaining_movement < terrain_cost) {
838  move_cost += remaining_movement;
839  }
840 
841  move_cost += terrain_cost;
842 
843  return move_cost;
844 }
845 
846 
848  : unit_(u), map_(map)
849 {}
850 
851 double emergency_path_calculator::cost(const map_location& loc, const double) const
852 {
853  assert(map_.on_board(loc));
854 
855  return unit_.movement_cost(map_[loc]);
856 }
857 
859 {}
860 
861 double dummy_path_calculator::cost(const map_location&, const double) const
862 {
863  return 1.0;
864 }
865 
866 /**
867  * Constructs a cost-map. For a unit each hex is mapped to the cost the
868  * unit will need to reach this hex. Considers movement-loss caused by
869  * turn changes.
870  * Can also used with multiple units to accumulate their costs efficiently.
871  * Will also count how many units could reach a hex for easy normalization.
872  * @param u the unit
873  * @param force_ignore_zoc Set to true to completely ignore zones of control.
874  * @param allow_teleport Set to true to consider teleportation abilities.
875  * @param viewing_team Usually the current team, except for "show enemy moves", etc.
876  * @param see_all Set to true to remove unit visibility from consideration.
877  * @param ignore_units Set to true if units should never obstruct paths (implies ignoring ZoC as well).
878  */
879 full_cost_map::full_cost_map(const unit& u, bool force_ignore_zoc,
880  bool allow_teleport, const team &viewing_team,
881  bool see_all, bool ignore_units)
882  :force_ignore_zoc_(force_ignore_zoc), allow_teleport_(allow_teleport),
883  viewing_team_(viewing_team), see_all_(see_all), ignore_units_(ignore_units)
884 {
885  const gamemap& map = resources::gameboard->map();
886  cost_map = std::vector<std::pair<int, int>>(map.w() * map.h(), std::pair(-1, 0));
887  add_unit(u);
888 }
889 
890 /**
891  * Same as other constructor but without unit. Use this when working
892  * with add_unit().
893  */
894 full_cost_map::full_cost_map(bool force_ignore_zoc,
895  bool allow_teleport, const team &viewing_team,
896  bool see_all, bool ignore_units)
897  :force_ignore_zoc_(force_ignore_zoc), allow_teleport_(allow_teleport),
898  viewing_team_(viewing_team), see_all_(see_all), ignore_units_(ignore_units)
899 {
900  const gamemap& map = resources::gameboard->map();
901  cost_map = std::vector<std::pair<int, int>>(map.w() * map.h(), std::pair(-1, 0));
902 }
903 
904 /**
905  * Adds a units cost map to cost_map (increments the elements in cost_map)
906  * @param u a real existing unit on the map
907  * @param use_max_moves whether to use the unit's max movement or the unit's remaining movement
908  */
909 void full_cost_map::add_unit(const unit& u, bool use_max_moves)
910 {
911  try {
912  // We don't need the destinations, but find_routes() wants to have this parameter
914 
915  find_routes(
916  u.get_location(),
919  (use_max_moves) ? u.total_movement() : u.movement_left(),
920  u.total_movement(),
921  99,
922  dummy,
923  nullptr,
924  allow_teleport_ ? &u : nullptr,
925  ignore_units_ ? nullptr : &resources::gameboard->get_team(u.side()),
926  force_ignore_zoc_ ? nullptr : &u,
927  see_all_ ? nullptr : &viewing_team_,
928  nullptr,
929  &cost_map
930  );
931  } catch(const std::out_of_range&) {
932  // Invalid unit side.
933  }
934 }
935 
936 /**
937  * Adds a units cost map to cost_map (increments the elements in cost_map)
938  * This function can be used to generate a cost_map with a non existing unit.
939  * @param origin the location on the map from where the calculations shall start
940  * @param ut the unit type we are interested in
941  * @param side the side of the unit. Important for zocs.
942  */
943 void full_cost_map::add_unit(const map_location& origin, const unit_type* const ut, int side)
944 {
945  if (!ut) {
946  return;
947  }
948  unit_ptr u = unit::create(*ut, side, false);
949  u->set_location(origin);
950  add_unit(*u);
951 }
952 
953 /**
954  * Accessor for the cost/reach-amount pairs.
955  * Read comment in pathfind.hpp to cost_map.
956  *
957  * @return the entry of the cost_map at (x, y)
958  * or (-1, 0) if value is not set or (x, y) is invalid.
959  */
960 std::pair<int, int> full_cost_map::get_pair_at(map_location loc) const
961 {
962  const gamemap& map = resources::gameboard->map();
963  assert(cost_map.size() == static_cast<unsigned>(map.w() * map.h()));
964 
965  if (!map.on_board(loc)) {
966  return std::pair(-1, 0); // invalid
967  }
968 
969  return cost_map[loc.x + (loc.y * map.w())];
970 }
971 
972 /**
973  * Accessor for the costs.
974  *
975  * @return the value of the cost_map at (x, y)
976  * or -1 if value is not set or (x, y) is invalid.
977  */
979 {
980  return get_pair_at(loc).first;
981 }
982 
983 /**
984  * Accessor for the costs.
985  *
986  * @return The average cost of all added units for this hex
987  * or -1 if no unit can reach the hex.
988  */
990 {
991  auto p = get_pair_at(loc);
992  if (p.second == 0) {
993  return -1;
994  } else {
995  return static_cast<double>(p.first) /p.second;
996  }
997 }
998 }//namespace pathfind
bool enemy_zoc(const team &current_team, const map_location &loc, const team &viewing_team, bool see_all)
Determines if a given location is in an enemy zone of control.
Definition: pathfind.cpp:135
Game board class.
Definition: game_board.hpp:51
A const-only interface for how many (movement, vision, or "jamming") points a unit needs for each hex...
Definition: movetype.hpp:53
virtual double cost(const map_location &loc, const double so_far) const
Definition: pathfind.cpp:819
marked_route mark_route(const plain_route &rt, bool update_move_cost)
Add marks on a route rt assuming that the unit located at the first hex of rt travels along it...
Definition: pathfind.cpp:648
unit_iterator end()
Definition: map.hpp:429
static display * get_singleton()
Returns the display object if a display object exists.
Definition: display.hpp:92
virtual const std::vector< team > & teams() const override
Definition: game_board.hpp:85
std::vector< std::pair< int, int > > cost_map
Definition: pathfind.hpp:296
virtual double cost(const map_location &loc, const double so_far) const
Definition: pathfind.cpp:851
void get_adjacent_tiles(const map_location &a, map_location *res)
Function which, given a location, will place all adjacent locations in res.
Definition: location.cpp:475
virtual const unit_map & units() const override
Definition: game_board.hpp:112
jamming_path(const unit &jammer, const map_location &loc)
Construct a list of jammed hexes for a unit.
Definition: pathfind.cpp:631
emergency_path_calculator(const unit &u, const gamemap &map)
Definition: pathfind.cpp:847
int jamming() const
Gets the unit&#39;s jamming points.
Definition: unit.hpp:1395
int vision() const
Gets the unit&#39;s vision points.
Definition: unit.hpp:1389
This class represents a single unit of a specific type.
Definition: unit.hpp:121
int dummy
Definition: lstrlib.cpp:1347
bool is_castle(const map_location &loc) const
Definition: map.cpp:70
int movement_cost(const t_translation::terrain_code &terrain) const
Get the unit&#39;s movement cost on a particular terrain.
Definition: unit.hpp:1429
map_location find_vacant_castle(const unit &leader)
Wrapper for find_vacant_tile() when looking for a vacant castle tile near a leader.
Definition: pathfind.cpp:118
bool get_state(const std::string &state) const
Check if the unit is affected by a status effect.
Definition: unit.cpp:1311
Add a special kind of assert to validate whether the input from WML doesn&#39;t contain any problems that...
const terrain_costs & get_jamming() const
Definition: movetype.hpp:272
int cost(const t_translation::terrain_code &terrain, bool slowed=false) const
Returns the cost associated with the given terrain.
Definition: movetype.hpp:69
#define a
static const int UNREACHABLE
Magic value that signifies a hex is unreachable.
Definition: movetype.hpp:176
const movetype & movement_type() const
Get the unit&#39;s movement type.
Definition: unit.hpp:1419
map_location find_vacant_tile(const map_location &loc, VACANT_TILE_TYPE vacancy, const unit *pass_check, const team *shroud_check, const game_board *board)
Function that will find a location on the board that is as near to loc as possible, but which is unoccupied by any units.
Definition: pathfind.cpp:55
virtual const gamemap & map() const override
Definition: game_board.hpp:102
dest_vect destinations
Definition: pathfind.hpp:101
A terrain string which is converted to a terrain is a string with 1 or 2 layers the layers are separa...
Definition: translation.hpp:50
static bool step_compare(const paths::step &a, const map_location &b)
Definition: pathfind.cpp:475
The basic "size" of the unit - flying, small land, large land, etc.
Definition: movetype.hpp:44
void add_unit(const unit &u, bool use_max_moves=true)
Adds a units cost map to cost_map (increments the elements in cost_map)
Definition: pathfind.cpp:909
const unit * unit_
static std::string _(const char *str)
Definition: gettext.hpp:93
virtual double cost(const map_location &loc, const double so_far) const
Definition: pathfind.cpp:861
virtual ~jamming_path()
Default destructor.
Definition: pathfind.cpp:644
std::shared_ptr< unit > unit_ptr
Definition: ptr.hpp:26
static unit_ptr create(const config &cfg, bool use_traits=false, const vconfig *vcfg=nullptr)
Initializes a unit from a config.
Definition: unit.hpp:190
A single unit type that the player may recruit.
Definition: types.hpp:45
double get_average_cost_at(map_location loc) const
Accessor for the costs.
Definition: pathfind.cpp:989
std::set< map_location > get_adjacents(map_location loc) const
Definition: teleport.cpp:234
static double getNoPathValue()
Definition: pathfind.hpp:65
#define b
int defense_modifier(const t_translation::terrain_code &terrain) const
The unit&#39;s defense on a given terrain.
Definition: unit.cpp:1605
This class stores all the data for a single &#39;side&#39; (in game nomenclature).
Definition: team.hpp:72
team & get_team(int i)
Definition: game_board.hpp:97
map_location prev
Definition: pathfind.cpp:158
std::vector< map_location > steps
Definition: pathfind.hpp:135
#define VALIDATE(cond, message)
The macro to use for the validation of WML.
int w() const
Effective map width.
Definition: map.hpp:50
bool uses_shroud() const
Definition: team.hpp:330
move_type_path_calculator(const movetype &mt, int movement_left, int total_movement, const team &t, const gamemap &map)
Definition: pathfind.cpp:813
Structure which holds a single route between one location and another.
Definition: pathfind.hpp:132
unit * get_visible_unit(const map_location &loc, const team &current_team, bool see_all=false)
Definition: game_board.cpp:211
const bool allow_teleport_
Definition: pathfind.hpp:300
map_location curr
Definition: pathfind.hpp:89
const terrain_costs & get_movement() const
Definition: movetype.hpp:270
int h
Definition: pathfind.cpp:189
static lg::log_domain log_engine("engine")
game_board * gameboard
Definition: resources.cpp:21
const terrain_costs & get_vision() const
Definition: movetype.hpp:271
virtual double cost(const map_location &loc, const double so_far) const
Definition: pathfind.cpp:732
VACANT_TILE_TYPE
Definition: pathfind.hpp:39
static IdxT partition(lua_State *L, IdxT lo, IdxT up)
Definition: ltablib.cpp:296
dummy_path_calculator(const unit &u, const gamemap &map)
Definition: pathfind.cpp:858
Encapsulates the map of the game.
Definition: map.hpp:171
bool is_enemy(int n) const
Definition: team.hpp:255
std::string path
Definition: game_config.cpp:39
map_display and display: classes which take care of displaying the map and game-data on the screen...
int moves_left
Definition: pathfind.cpp:157
virtual ~vision_path()
Default destructor.
Definition: pathfind.cpp:617
full_cost_map(const unit &u, bool force_ignore_zoc, bool allow_teleport, const team &viewing_team, bool see_all=true, bool ignore_units=true)
Constructs a cost-map.
Definition: pathfind.cpp:879
Structure which holds a single route and marks for special events.
Definition: pathfind.hpp:141
std::vector< map_location > get_path(const const_iterator &) const
Returns the path going from the source point (included) to the destination point j (excluded)...
Definition: pathfind.cpp:498
Encapsulates the map of the game.
Definition: location.hpp:38
unit_iterator find(std::size_t id)
Definition: map.cpp:310
bool invisible(const map_location &loc, bool see_all=true) const
Definition: unit.cpp:2436
virtual ~paths()
Virtual destructor (default processing).
Definition: pathfind.cpp:561
bool shrouded(const map_location &loc) const
Definition: team.cpp:652
bool get_ability_bool(const std::string &tag_name, const map_location &loc) const
Checks whether this unit currently possesses or is affected by a given ability.
Definition: abilities.cpp:149
static std::string mark
Definition: tstring.cpp:71
std::size_t i
Definition: function.cpp:967
Ordered vector of possible destinations.
Definition: pathfind.hpp:94
const std::vector< team > & teams_
Definition: pathfind.hpp:215
mock_party p
static map_location::DIRECTION s
static void find_routes(const map_location &origin, const movetype::terrain_costs &costs, bool slowed, int moves_left, int max_moves, int turns_left, paths::dest_vect &destinations, std::set< map_location > *edges, const unit *teleporter, const team *current_team, const unit *skirmisher, const team *viewing_team, const std::map< map_location, int > *jamming_map=nullptr, std::vector< std::pair< int, int >> *full_cost_map=nullptr, bool check_vision=false)
Creates a list of routes that a unit can traverse from the provided location.
Definition: pathfind.cpp:271
static bool operator<(const placing_info &a, const placing_info &b)
Definition: game_state.cpp:140
Structure which uses find_routes() to build a cost map This maps each hex to a the movements a unit w...
Definition: pathfind.hpp:267
const team & viewing_team_
Definition: pathfind.hpp:301
const bool ignore_units_
Definition: pathfind.hpp:303
shortest_path_calculator(const unit &u, const team &t, const std::vector< team > &teams, const gamemap &map, bool ignore_unit=false, bool ignore_defense_=false, bool see_all=false)
Definition: pathfind.cpp:722
bool on_board(const map_location &loc) const
Tell if a location is on the map.
Definition: map.cpp:385
std::pair< int, int > get_pair_at(map_location loc) const
Accessor for the cost/reach-amount pairs.
Definition: pathfind.cpp:960
std::string & insert(std::string &str, const std::size_t pos, const std::string &insert)
Insert a UTF-8 string at the specified position.
Definition: unicode.cpp:100
const bool force_ignore_zoc_
Definition: pathfind.hpp:299
std::size_t index(const std::string &str, const std::size_t index)
Codepoint index corresponding to the nth character in a UTF-8 string.
Definition: unicode.cpp:72
int movement_cost(const t_translation::terrain_code &terrain, bool slowed=false) const
Returns the cost to move through the indicated terrain.
Definition: movetype.hpp:282
#define next(ls)
Definition: llex.cpp:32
int w
Definition: pathfind.cpp:189
bool is_village(const map_location &loc) const
Definition: map.cpp:66
int turns()
Definition: game.cpp:559
double t
Definition: astarsearch.cpp:65
const map_location & get_location() const
The current map location this unit is at.
Definition: unit.hpp:1346
std::size_t viewing_team() const
The viewing team is the team currently viewing the game.
Definition: display.hpp:106
std::set< map_location > edges
The edges are the non-destination hexes bordering the destinations.
Definition: pathfind.hpp:117
bool contains(const map_location &) const
Definition: pathfind.cpp:515
Standard logging facilities (interface).
const teleport_map get_teleport_locations(const unit &u, const team &viewing_team, bool see_all, bool ignore_units, bool check_vision)
Definition: teleport.cpp:270
Object which contains all the possible locations a unit can move to, with associated best routes to t...
Definition: pathfind.hpp:72
static const map_location & null_location()
Definition: location.hpp:81
Container associating units to locations.
Definition: map.hpp:98
int total_movement() const
The maximum moves this unit has.
Definition: unit.hpp:1255
bool fogged(const map_location &loc) const
Definition: team.cpp:661
unsigned search_num
Definition: pathfind.cpp:162
bool emits_zoc() const
Tests whether the unit has a zone-of-control, considering incapacitated.
Definition: unit.hpp:1327
int side() const
The side this unit belongs to.
Definition: unit.hpp:334
static void reverse(lua_State *L, StkId from, StkId to)
Definition: lapi.cpp:203
const_iterator find(const map_location &) const
Definition: pathfind.cpp:479
const std::vector< findroute_node > & nodes
Definition: pathfind.cpp:221
bool owns_village(const map_location &loc) const
Definition: team.hpp:197
bool valid() const
Definition: map.hpp:274
static map_location::DIRECTION n
int h() const
Effective map height.
Definition: map.hpp:53
vision_path(const unit &viewer, const map_location &loc, const std::map< map_location, int > &jamming_map)
Constructs a list of vision paths for a unit.
Definition: pathfind.cpp:577
This module contains various pathfinding functions and utilities.
int turns_left
Definition: pathfind.cpp:157
std::string::const_iterator iterator
Definition: tokenizer.hpp:25
int movement_left() const
Gets how far a unit can move, considering the incapacitated flag.
Definition: unit.hpp:1271
void insert(const map_location &)
Definition: pathfind.cpp:486
int get_cost_at(map_location loc) const
Accessor for the costs.
Definition: pathfind.cpp:978