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