The Battle for Wesnoth  1.15.0-dev
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 https://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) ) {
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 
651 marked_route mark_route(const plain_route &rt, bool update_move_cost)
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 total_costs = 0;
664  int movement = u.movement_left();
665  const team& unit_team = resources::gameboard->get_team(u.side());
666  bool zoc = false;
667 
668  std::vector<map_location>::const_iterator i = rt.steps.begin();
669 
670  for (; i !=rt.steps.end(); ++i) {
671  bool last_step = (i+1 == rt.steps.end());
672 
673  // move_cost of the next step is irrelevant for the last step
674  assert(last_step || resources::gameboard->map().on_board(*(i+1)));
675  const int move_cost = last_step ? 0 : u.movement_cost((resources::gameboard->map())[*(i+1)]);
676 
677  const team& viewing_team = resources::gameboard->teams()[display::get_singleton()->viewing_team()];
678 
679  if (last_step || zoc || move_cost > movement) {
680  // check if we stop an a village and so maybe capture it
681  // if it's an enemy unit and a fogged village, we assume a capture
682  // (if he already owns it, we can't know that)
683  // if it's not an enemy, we can always know if he owns the village
684  bool capture = resources::gameboard->map().is_village(*i) && ( !unit_team.owns_village(*i)
685  || (viewing_team.is_enemy(u.side()) && viewing_team.fogged(*i)) );
686 
687  ++turns;
688 
689  bool invisible = u.invisible(*i, false);
690 
691  res.marks[*i] = marked_route::mark(turns, zoc, capture, invisible);
692 
693  if(last_step) {
694  if(capture) {
695  total_costs += movement;
696  }
697  break; // finished and we used dummy move_cost
698  }
699 
700  total_costs += movement;
701  movement = u.total_movement();
702  if(move_cost > movement) {
703  return res; //we can't reach destination
704  }
705  }
706 
707  zoc = enemy_zoc(unit_team, *(i + 1), viewing_team)
708  && !u.get_ability_bool("skirmisher", *(i+1));
709 
710  if (zoc) {
711  total_costs += movement;
712  movement = 0;
713  } else {
714  movement -= move_cost;
715  total_costs += move_cost;
716  }
717  }
718 
719  if(update_move_cost) {
720  res.move_cost = total_costs;
721  }
722  return res;
723 }
724 
726  const std::vector<team>& teams, const gamemap& map,
727  bool ignore_unit, bool ignore_defense, bool see_all)
728  : unit_(u), viewing_team_(t), teams_(teams), map_(map),
729  movement_left_(unit_.movement_left()),
730  total_movement_(unit_.total_movement()),
731  ignore_unit_(ignore_unit), ignore_defense_(ignore_defense),
732  see_all_(see_all)
733 {}
734 
735 double shortest_path_calculator::cost(const map_location& loc, const double so_far) const
736 {
737  assert(map_.on_board(loc));
738 
739  // loc is shrouded, consider it impassable
740  // NOTE: This is why AI must avoid to use shroud
741  if (!see_all_ && viewing_team_.shrouded(loc))
742  return getNoPathValue();
743 
745  const int terrain_cost = unit_.movement_cost(terrain);
746  // Pathfinding heuristic: the cost must be at least 1
747  VALIDATE(terrain_cost >= 1, _("Terrain with a movement cost less than 1 encountered."));
748 
749  // Compute how many movement points are left in the game turn
750  // needed to reach the previous hex.
751  // total_movement_ is not zero, thanks to the pathfinding heuristic
752  int remaining_movement = movement_left_ - static_cast<int>(so_far);
753  if (remaining_movement < 0) {
754  remaining_movement = total_movement_ - (-remaining_movement) % total_movement_;
755  }
756 
757  if (terrain_cost >= movetype::UNREACHABLE || (total_movement_ < terrain_cost && remaining_movement < terrain_cost)) {
758  return getNoPathValue();
759  }
760 
761  int other_unit_subcost = 0;
762  if (!ignore_unit_) {
763  const unit *other_unit =
765 
766  // We can't traverse visible enemy and we also prefer empty hexes
767  // (less blocking in multi-turn moves and better when exploring fog,
768  // because we can't stop on a friend)
769 
770  if (other_unit)
771  {
772  if (teams_[unit_.side() - 1].is_enemy(other_unit->side()))
773  return getNoPathValue();
774  else
775  // This value will be used with the defense_subcost (see below)
776  // The 1 here means: consider occupied hex as a -1% defense
777  // (less important than 10% defense because friends may move)
778  other_unit_subcost = 1;
779  }
780  }
781 
782  // this will sum all different costs of this move
783  int move_cost = 0;
784 
785  // Suppose that we have only 2 remaining MP and want to move onto a hex
786  // costing 3 MP. We don't have enough MP now, so we must end our turn here,
787  // thus spend our remaining MP by waiting (next turn, with full MP, we will
788  // be able to move on that hex)
789  if (remaining_movement < terrain_cost) {
790  move_cost += remaining_movement;
791  remaining_movement = total_movement_; // we consider having full MP now
792  }
793 
794  // check ZoC
795  if (!ignore_unit_ && remaining_movement != terrain_cost
797  && !unit_.get_ability_bool("skirmisher", loc)) {
798  // entering ZoC cost all remaining MP
799  move_cost += remaining_movement;
800  } else {
801  // empty hex, pay only the terrain cost
802  move_cost += terrain_cost;
803  }
804 
805  // We will add a tiny cost based on terrain defense, so the pathfinding
806  // will prefer good terrains between 2 with the same MP cost
807  // Keep in mind that defense_modifier is inverted (= 100 - defense%)
808  const int defense_subcost = ignore_defense_ ? 0 : unit_.defense_modifier(terrain);
809 
810  // We divide subcosts by 100 * 100, because defense is 100-based and
811  // we don't want any impact on move cost for less then 100-steps path
812  // (even ~200 since mean defense is around ~50%)
813  return move_cost + (defense_subcost + other_unit_subcost) / 10000.0;
814 }
815 
816 move_type_path_calculator::move_type_path_calculator(const movetype& mt, int movement_left, int total_movement, const team& t, const gamemap& map)
817  : movement_type_(mt), movement_left_(movement_left),
818  total_movement_(total_movement), viewing_team_(t), map_(map)
819 {}
820 
821 // This is an simplified version of shortest_path_calculator (see above for explanation)
822 double move_type_path_calculator::cost(const map_location& loc, const double so_far) const
823 {
824  assert(map_.on_board(loc));
825  if (viewing_team_.shrouded(loc))
826  return getNoPathValue();
827 
829  const int terrain_cost = movement_type_.movement_cost(terrain);
830 
831  if (total_movement_ < terrain_cost)
832  return getNoPathValue();
833 
834  int remaining_movement = movement_left_ - static_cast<int>(so_far);
835  if (remaining_movement < 0)
836  remaining_movement = total_movement_ - (-remaining_movement) % total_movement_;
837 
838  int move_cost = 0;
839 
840  if (remaining_movement < terrain_cost) {
841  move_cost += remaining_movement;
842  }
843 
844  move_cost += terrain_cost;
845 
846  return move_cost;
847 }
848 
849 
851  : unit_(u), map_(map)
852 {}
853 
854 double emergency_path_calculator::cost(const map_location& loc, const double) const
855 {
856  assert(map_.on_board(loc));
857 
858  return unit_.movement_cost(map_[loc]);
859 }
860 
862 {}
863 
864 double dummy_path_calculator::cost(const map_location&, const double) const
865 {
866  return 1.0;
867 }
868 
869 /**
870  * Constructs a cost-map. For a unit each hex is mapped to the cost the
871  * unit will need to reach this hex. Considers movement-loss caused by
872  * turn changes.
873  * Can also used with multiple units to accumulate their costs efficiently.
874  * Will also count how many units could reach a hex for easy normalization.
875  * @param u the unit
876  * @param force_ignore_zoc Set to true to completely ignore zones of control.
877  * @param allow_teleport Set to true to consider teleportation abilities.
878  * @param viewing_team Usually the current team, except for "show enemy moves", etc.
879  * @param see_all Set to true to remove unit visibility from consideration.
880  * @param ignore_units Set to true if units should never obstruct paths (implies ignoring ZoC as well).
881  */
882 full_cost_map::full_cost_map(const unit& u, bool force_ignore_zoc,
883  bool allow_teleport, const team &viewing_team,
884  bool see_all, bool ignore_units)
885  :force_ignore_zoc_(force_ignore_zoc), allow_teleport_(allow_teleport),
886  viewing_team_(viewing_team), see_all_(see_all), ignore_units_(ignore_units)
887 {
888  const gamemap& map = resources::gameboard->map();
889  cost_map = std::vector<std::pair<int, int>>(map.w() * map.h(), std::make_pair(-1, 0));
890  add_unit(u);
891 }
892 
893 /**
894  * Same as other constructor but without unit. Use this when working
895  * with add_unit().
896  */
897 full_cost_map::full_cost_map(bool force_ignore_zoc,
898  bool allow_teleport, const team &viewing_team,
899  bool see_all, bool ignore_units)
900  :force_ignore_zoc_(force_ignore_zoc), allow_teleport_(allow_teleport),
901  viewing_team_(viewing_team), see_all_(see_all), ignore_units_(ignore_units)
902 {
903  const gamemap& map = resources::gameboard->map();
904  cost_map = std::vector<std::pair<int, int>>(map.w() * map.h(), std::make_pair(-1, 0));
905 }
906 
907 /**
908  * Adds a units cost map to cost_map (increments the elements in cost_map)
909  * @param u a real existing unit on the map
910  */
911 void full_cost_map::add_unit(const unit& u, bool use_max_moves)
912 {
913  try {
914  // We don't need the destinations, but find_routes() wants to have this parameter
916 
917  find_routes(
918  u.get_location(),
921  (use_max_moves) ? u.total_movement() : u.movement_left(),
922  u.total_movement(),
923  99,
924  dummy,
925  nullptr,
926  allow_teleport_ ? &u : nullptr,
927  ignore_units_ ? nullptr : &resources::gameboard->get_team(u.side()),
928  force_ignore_zoc_ ? nullptr : &u,
929  see_all_ ? nullptr : &viewing_team_,
930  nullptr,
931  &cost_map
932  );
933  } catch(const std::out_of_range&) {
934  // Invalid unit side.
935  }
936 }
937 
938 /**
939  * Adds a units cost map to cost_map (increments the elements in cost_map)
940  * This function can be used to generate a cost_map with a non existing unit.
941  * @param origin the location on the map from where the calculations shall start
942  * @param ut the unit type we are interested in
943  * @param side the side of the unit. Important for zocs.
944  */
945 void full_cost_map::add_unit(const map_location& origin, const unit_type* const ut, int side)
946 {
947  if (!ut) {
948  return;
949  }
950  unit_ptr u = unit::create(*ut, side, false);
951  u->set_location(origin);
952  add_unit(*u);
953 }
954 
955 /**
956  * Accessor for the cost/reach-amount pairs.
957  * Read comment in pathfind.hpp to cost_map.
958  *
959  * @return the entry of the cost_map at (x, y)
960  * or (-1, 0) if value is not set or (x, y) is invalid.
961  */
962 std::pair<int, int> full_cost_map::get_pair_at(int x, int y) const
963 {
964  const gamemap& map = resources::gameboard->map();
965  assert(cost_map.size() == static_cast<unsigned>(map.w() * map.h()));
966 
967  if (x < 0 || x >= map.w() || y < 0 || y >= map.h()) {
968  return std::make_pair(-1, 0); // invalid
969  }
970 
971  return cost_map[x + (y * map.w())];
972 }
973 
974 /**
975  * Accessor for the costs.
976  *
977  * @return the value of the cost_map at (x, y)
978  * or -1 if value is not set or (x, y) is invalid.
979  */
980 int full_cost_map::get_cost_at(int x, int y) const
981 {
982  return get_pair_at(x, y).first;
983 }
984 
985 /**
986  * Accessor for the costs.
987  *
988  * @return The average cost of all added units for this hex
989  * or -1 if no unit can reach the hex.
990  */
991 double full_cost_map::get_average_cost_at(int x, int y) const
992 {
993  if (get_pair_at(x, y).second == 0) {
994  return -1;
995  } else {
996  return static_cast<double>(get_pair_at(x, y).first) / get_pair_at(x, y).second;
997  }
998 }
999 }//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
Game board class.
Definition: game_board.hpp:50
Stores a set of terrain costs (for movement, vision, or "jamming").
Definition: movetype.hpp:86
virtual double cost(const map_location &loc, const double so_far) const
Definition: pathfind.cpp:822
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:651
int h() const
Effective map height.
Definition: map.hpp:128
unit_iterator end()
Definition: map.hpp:415
static display * get_singleton()
Returns the display object if a display object exists.
Definition: display.hpp:88
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
virtual double cost(const map_location &loc, const double so_far) const
Definition: pathfind.cpp:854
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:517
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:850
int jamming() const
Gets the unit&#39;s jamming points.
Definition: unit.hpp:1305
int vision() const
Gets the unit&#39;s vision points.
Definition: unit.hpp:1299
This class represents a single unit of a specific type.
Definition: unit.hpp:99
int dummy
Definition: lstrlib.cpp:1125
bool is_castle(const map_location &loc) const
Definition: map.cpp:69
int movement_cost(const t_translation::terrain_code &terrain) const
Get the unit&#39;s movement cost on a particular terrain.
Definition: unit.hpp:1339
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 get_state(const std::string &state) const
Check if the unit is affected by a status effect.
Definition: unit.cpp:1310
Add a special kind of assert to validate whether the input from WML doesn&#39;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
#define a
static const int UNREACHABLE
Magic value that signifies a hex is unreachable.
Definition: movetype.hpp:83
const movetype & movement_type() const
Get the unit&#39;s movement type.
Definition: unit.hpp:1329
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
std::pair< int, int > get_pair_at(int x, int y) const
Accessor for the cost/reach-amount pairs.
Definition: pathfind.cpp:962
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:50
static bool step_compare(const paths::step &a, const map_location &b)
Definition: pathfind.cpp:480
bool on_board(const map_location &loc) const
Tell if a location is on the map.
Definition: map.cpp:377
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:911
const unit * unit_
-file sdl_utils.hpp
double get_average_cost_at(int x, int y) const
Accessor for the costs.
Definition: pathfind.cpp:991
virtual double cost(const map_location &loc, const double so_far) const
Definition: pathfind.cpp:864
virtual ~jamming_path()
Default destructor.
Definition: pathfind.cpp:647
static unit_ptr create(const config &cfg, bool use_traits=false, const vconfig *vcfg=nullptr)
Initializes a unit from a config.
Definition: unit.hpp:154
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
#define b
int defense_modifier(const t_translation::terrain_code &terrain) const
The unit&#39;s defense on a given terrain.
Definition: unit.cpp:1596
This class stores all the data for a single &#39;side&#39; (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
map_location prev
Definition: pathfind.cpp:162
std::vector< map_location > steps
Definition: pathfind.hpp:134
#define VALIDATE(cond, message)
The macro to use for the validation of WML.
int get_cost_at(int x, int y) const
Accessor for the costs.
Definition: pathfind.cpp:980
bool uses_shroud() const
Definition: team.hpp:316
move_type_path_calculator(const movetype &mt, int movement_left, int total_movement, const team &t, const gamemap &map)
Definition: pathfind.cpp:816
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:809
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")
terrain_costs & get_vision()
Definition: movetype.hpp:180
game_board * gameboard
Definition: resources.cpp:20
virtual double cost(const map_location &loc, const double so_far) const
Definition: pathfind.cpp:735
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:861
Encapsulates the map of the game.
Definition: map.hpp:36
bool is_enemy(int n) const
Definition: team.hpp:243
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: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:882
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:170
static const ::config * terrain
The terrain used to create the cache.
Definition: minimap.cpp:130
terrain_costs & get_movement()
Definition: movetype.hpp:179
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
Encapsulates the map of the game.
Definition: location.hpp:42
unit_iterator find(std::size_t id)
Definition: map.cpp:311
bool invisible(const map_location &loc, bool see_all=true) const
Definition: unit.cpp:2381
virtual ~paths()
Virtual destructor (default processing).
Definition: pathfind.cpp:566
bool shrouded(const map_location &loc) const
Definition: team.cpp:644
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:141
static std::string mark
Definition: tstring.cpp:73
int w() const
Effective map width.
Definition: map.hpp:125
std::size_t i
Definition: function.cpp:933
Ordered vector of possible destinations.
Definition: pathfind.hpp:92
const std::vector< team > & teams_
Definition: pathfind.hpp:214
void get_adjacents(std::set< map_location > &adjacents, map_location loc) const
Definition: teleport.cpp:228
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:275
static bool operator<(const placing_info &a, const placing_info &b)
Definition: game_state.cpp:138
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
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:725
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:99
const bool force_ignore_zoc_
Definition: pathfind.hpp:298
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:71
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
#define next(ls)
Definition: llex.cpp:32
int w
Definition: pathfind.cpp:193
bool is_village(const map_location &loc) const
Definition: map.cpp:65
int turns()
Definition: game.cpp:558
boost::intrusive_ptr< unit > unit_ptr
Definition: ptr.hpp:29
double t
Definition: astarsearch.cpp:64
bool find(E event, F functor)
Tests whether an event handler is available.
const map_location & get_location() const
The current map location this unit is at.
Definition: unit.hpp:1256
std::size_t viewing_team() const
The viewing team is the team currently viewing the game.
Definition: display.hpp:102
std::set< map_location > edges
The edges are the non-destination hexes bordering the destinations.
Definition: pathfind.hpp:116
bool contains(const map_location &) const
Definition: pathfind.cpp:520
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
static const map_location & null_location()
Definition: location.hpp:85
Container associating units to locations.
Definition: map.hpp:99
int total_movement() const
The maximum moves this unit has.
Definition: unit.hpp:1165
bool fogged(const map_location &loc) const
Definition: team.cpp:653
unsigned search_num
Definition: pathfind.cpp:166
bool emits_zoc() const
Tests whether the unit has a zone-of-control, considering incapacitated.
Definition: unit.hpp:1237
int side() const
The side this unit belongs to.
Definition: unit.hpp:303
static void reverse(lua_State *L, StkId from, StkId to)
Definition: lapi.cpp:193
const_iterator find(const map_location &) const
Definition: pathfind.cpp:484
const std::vector< findroute_node > & nodes
Definition: pathfind.cpp:225
bool owns_village(const map_location &loc) const
Definition: team.hpp:185
bool valid() const
Definition: map.hpp:276
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
std::string::const_iterator iterator
Definition: tokenizer.hpp:24
int movement_left() const
Gets how far a unit can move, considering the incapacitated flag.
Definition: unit.hpp:1181
void insert(const map_location &)
Definition: pathfind.cpp:491