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 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) ) {
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) break; // finished and we used dummy move_cost
694 
695  total_costs += movement;
696  movement = u.total_movement();
697  if(move_cost > movement) {
698  return res; //we can't reach destination
699  }
700  }
701 
702  zoc = enemy_zoc(unit_team, *(i + 1), viewing_team)
703  && !u.get_ability_bool("skirmisher", *(i+1));
704 
705  if (zoc) {
706  total_costs += movement;
707  movement = 0;
708  } else {
709  movement -= move_cost;
710  total_costs += move_cost;
711  }
712  }
713 
714  if(update_move_cost) {
715  res.move_cost = total_costs;
716  }
717  return res;
718 }
719 
721  const std::vector<team>& teams, const gamemap& map,
722  bool ignore_unit, bool ignore_defense, bool see_all)
723  : unit_(u), viewing_team_(t), teams_(teams), map_(map),
724  movement_left_(unit_.movement_left()),
725  total_movement_(unit_.total_movement()),
726  ignore_unit_(ignore_unit), ignore_defense_(ignore_defense),
727  see_all_(see_all)
728 {}
729 
730 double shortest_path_calculator::cost(const map_location& loc, const double so_far) const
731 {
732  assert(map_.on_board(loc));
733 
734  // loc is shrouded, consider it impassable
735  // NOTE: This is why AI must avoid to use shroud
736  if (!see_all_ && viewing_team_.shrouded(loc))
737  return getNoPathValue();
738 
739  const t_translation::terrain_code terrain = map_[loc];
740  const int terrain_cost = unit_.movement_cost(terrain);
741  // Pathfinding heuristic: the cost must be at least 1
742  VALIDATE(terrain_cost >= 1, _("Terrain with a movement cost less than 1 encountered."));
743 
744  // Compute how many movement points are left in the game turn
745  // needed to reach the previous hex.
746  // total_movement_ is not zero, thanks to the pathfinding heuristic
747  int remaining_movement = movement_left_ - static_cast<int>(so_far);
748  if (remaining_movement < 0) {
749  remaining_movement = total_movement_ - (-remaining_movement) % total_movement_;
750  }
751 
752  if (terrain_cost >= movetype::UNREACHABLE || (total_movement_ < terrain_cost && remaining_movement < terrain_cost)) {
753  return getNoPathValue();
754  }
755 
756  int other_unit_subcost = 0;
757  if (!ignore_unit_) {
758  const unit *other_unit =
760 
761  // We can't traverse visible enemy and we also prefer empty hexes
762  // (less blocking in multi-turn moves and better when exploring fog,
763  // because we can't stop on a friend)
764 
765  if (other_unit)
766  {
767  if (teams_[unit_.side() - 1].is_enemy(other_unit->side()))
768  return getNoPathValue();
769  else
770  // This value will be used with the defense_subcost (see below)
771  // The 1 here means: consider occupied hex as a -1% defense
772  // (less important than 10% defense because friends may move)
773  other_unit_subcost = 1;
774  }
775  }
776 
777  // this will sum all different costs of this move
778  int move_cost = 0;
779 
780  // Suppose that we have only 2 remaining MP and want to move onto a hex
781  // costing 3 MP. We don't have enough MP now, so we must end our turn here,
782  // thus spend our remaining MP by waiting (next turn, with full MP, we will
783  // be able to move on that hex)
784  if (remaining_movement < terrain_cost) {
785  move_cost += remaining_movement;
786  remaining_movement = total_movement_; // we consider having full MP now
787  }
788 
789  // check ZoC
790  if (!ignore_unit_ && remaining_movement != terrain_cost
792  && !unit_.get_ability_bool("skirmisher", loc)) {
793  // entering ZoC cost all remaining MP
794  move_cost += remaining_movement;
795  } else {
796  // empty hex, pay only the terrain cost
797  move_cost += terrain_cost;
798  }
799 
800  // We will add a tiny cost based on terrain defense, so the pathfinding
801  // will prefer good terrains between 2 with the same MP cost
802  // Keep in mind that defense_modifier is inverted (= 100 - defense%)
803  const int defense_subcost = ignore_defense_ ? 0 : unit_.defense_modifier(terrain);
804 
805  // We divide subcosts by 100 * 100, because defense is 100-based and
806  // we don't want any impact on move cost for less then 100-steps path
807  // (even ~200 since mean defense is around ~50%)
808  return move_cost + (defense_subcost + other_unit_subcost) / 10000.0;
809 }
810 
811 move_type_path_calculator::move_type_path_calculator(const movetype& mt, int movement_left, int total_movement, const team& t, const gamemap& map)
812  : movement_type_(mt), movement_left_(movement_left),
813  total_movement_(total_movement), viewing_team_(t), map_(map)
814 {}
815 
816 // This is an simplified version of shortest_path_calculator (see above for explanation)
817 double move_type_path_calculator::cost(const map_location& loc, const double so_far) const
818 {
819  assert(map_.on_board(loc));
820  if (viewing_team_.shrouded(loc))
821  return getNoPathValue();
822 
823  const t_translation::terrain_code terrain = map_[loc];
824  const int terrain_cost = movement_type_.movement_cost(terrain);
825 
826  if (total_movement_ < terrain_cost)
827  return getNoPathValue();
828 
829  int remaining_movement = movement_left_ - static_cast<int>(so_far);
830  if (remaining_movement < 0)
831  remaining_movement = total_movement_ - (-remaining_movement) % total_movement_;
832 
833  int move_cost = 0;
834 
835  if (remaining_movement < terrain_cost) {
836  move_cost += remaining_movement;
837  }
838 
839  move_cost += terrain_cost;
840 
841  return move_cost;
842 }
843 
844 
846  : unit_(u), map_(map)
847 {}
848 
849 double emergency_path_calculator::cost(const map_location& loc, const double) const
850 {
851  assert(map_.on_board(loc));
852 
853  return unit_.movement_cost(map_[loc]);
854 }
855 
857 {}
858 
859 double dummy_path_calculator::cost(const map_location&, const double) const
860 {
861  return 1.0;
862 }
863 
864 /**
865  * Constructs a cost-map. For a unit each hex is mapped to the cost the
866  * unit will need to reach this hex. Considers movement-loss caused by
867  * turn changes.
868  * Can also used with multiple units to accumulate their costs efficiently.
869  * Will also count how many units could reach a hex for easy normalization.
870  * @param u the unit
871  * @param force_ignore_zoc Set to true to completely ignore zones of control.
872  * @param allow_teleport Set to true to consider teleportation abilities.
873  * @param viewing_team Usually the current team, except for "show enemy moves", etc.
874  * @param see_all Set to true to remove unit visibility from consideration.
875  * @param ignore_units Set to true if units should never obstruct paths (implies ignoring ZoC as well).
876  */
877 full_cost_map::full_cost_map(const unit& u, bool force_ignore_zoc,
878  bool allow_teleport, const team &viewing_team,
879  bool see_all, bool ignore_units)
880  :force_ignore_zoc_(force_ignore_zoc), allow_teleport_(allow_teleport),
881  viewing_team_(viewing_team), see_all_(see_all), ignore_units_(ignore_units)
882 {
883  const gamemap& map = resources::gameboard->map();
884  cost_map = std::vector<std::pair<int, int>>(map.w() * map.h(), std::make_pair(-1, 0));
885  add_unit(u);
886 }
887 
888 /**
889  * Same as other constructor but without unit. Use this when working
890  * with add_unit().
891  */
892 full_cost_map::full_cost_map(bool force_ignore_zoc,
893  bool allow_teleport, const team &viewing_team,
894  bool see_all, bool ignore_units)
895  :force_ignore_zoc_(force_ignore_zoc), allow_teleport_(allow_teleport),
896  viewing_team_(viewing_team), see_all_(see_all), ignore_units_(ignore_units)
897 {
898  const gamemap& map = resources::gameboard->map();
899  cost_map = std::vector<std::pair<int, int>>(map.w() * map.h(), std::make_pair(-1, 0));
900 }
901 
902 /**
903  * Adds a units cost map to cost_map (increments the elements in cost_map)
904  * @param u a real existing unit on the map
905  */
906 void full_cost_map::add_unit(const unit& u, bool use_max_moves)
907 {
908  try {
909  // We don't need the destinations, but find_routes() wants to have this parameter
911 
912  find_routes(
913  u.get_location(),
916  (use_max_moves) ? u.total_movement() : u.movement_left(),
917  u.total_movement(),
918  99,
919  dummy,
920  nullptr,
921  allow_teleport_ ? &u : nullptr,
922  ignore_units_ ? nullptr : &resources::gameboard->get_team(u.side()),
923  force_ignore_zoc_ ? nullptr : &u,
924  see_all_ ? nullptr : &viewing_team_,
925  nullptr,
926  &cost_map
927  );
928  } catch(const std::out_of_range&) {
929  // Invalid unit side.
930  }
931 }
932 
933 /**
934  * Adds a units cost map to cost_map (increments the elements in cost_map)
935  * This function can be used to generate a cost_map with a non existing unit.
936  * @param origin the location on the map from where the calculations shall start
937  * @param ut the unit type we are interested in
938  * @param side the side of the unit. Important for zocs.
939  */
940 void full_cost_map::add_unit(const map_location& origin, const unit_type* const ut, int side)
941 {
942  if (!ut) {
943  return;
944  }
945  unit_ptr u = unit::create(*ut, side, false);
946  u->set_location(origin);
947  add_unit(*u);
948 }
949 
950 /**
951  * Accessor for the cost/reach-amount pairs.
952  * Read comment in pathfind.hpp to cost_map.
953  *
954  * @return the entry of the cost_map at (x, y)
955  * or (-1, 0) if value is not set or (x, y) is invalid.
956  */
957 std::pair<int, int> full_cost_map::get_pair_at(int x, int y) const
958 {
959  const gamemap& map = resources::gameboard->map();
960  assert(cost_map.size() == static_cast<unsigned>(map.w() * map.h()));
961 
962  if (x < 0 || x >= map.w() || y < 0 || y >= map.h()) {
963  return std::make_pair(-1, 0); // invalid
964  }
965 
966  return cost_map[x + (y * map.w())];
967 }
968 
969 /**
970  * Accessor for the costs.
971  *
972  * @return the value of the cost_map at (x, y)
973  * or -1 if value is not set or (x, y) is invalid.
974  */
975 int full_cost_map::get_cost_at(int x, int y) const
976 {
977  return get_pair_at(x, y).first;
978 }
979 
980 /**
981  * Accessor for the costs.
982  *
983  * @return The average cost of all added units for this hex
984  * or -1 if no unit can reach the hex.
985  */
986 double full_cost_map::get_average_cost_at(int x, int y) const
987 {
988  if (get_pair_at(x, y).second == 0) {
989  return -1;
990  } else {
991  return static_cast<double>(get_pair_at(x, y).first) / get_pair_at(x, y).second;
992  }
993 }
994 }//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:817
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:93
unit_iterator end()
Definition: map.hpp:415
static display * get_singleton()
Returns the display object if a display object exists.
Definition: display.hpp:99
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:849
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:845
int jamming() const
Gets the unit&#39;s jamming points.
Definition: unit.hpp:1223
int vision() const
Gets the unit&#39;s vision points.
Definition: unit.hpp:1217
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:68
int movement_cost(const t_translation::terrain_code &terrain) const
Get the unit&#39;s movement cost on a particular terrain.
Definition: unit.hpp:1257
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:1247
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:957
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:49
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:367
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:906
const unit * unit_
-file sdl_utils.hpp
double get_average_cost_at(int x, int y) const
Accessor for the costs.
Definition: pathfind.cpp:986
virtual double cost(const map_location &loc, const double so_far) const
Definition: pathfind.cpp:859
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:122
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:1561
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:975
bool uses_shroud() const
Definition: team.hpp:314
move_type_path_calculator(const movetype &mt, int movement_left, int total_movement, const team &t, const gamemap &map)
Definition: pathfind.cpp:811
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:741
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:730
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:856
Encapsulates the map of the game.
Definition: map.hpp:34
bool is_enemy(int n) const
Definition: team.hpp:241
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:877
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
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:2337
virtual ~paths()
Virtual destructor (default processing).
Definition: pathfind.cpp:566
bool shrouded(const map_location &loc) const
Definition: team.cpp:632
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:140
static std::string mark
Definition: tstring.cpp:73
int w() const
Effective map width.
Definition: map.hpp:90
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:136
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:720
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:64
int turns()
Definition: game.cpp:559
boost::intrusive_ptr< unit > unit_ptr
Definition: ptr.hpp:29
double t
Definition: astarsearch.cpp:63
const map_location & get_location() const
The current map location this unit is at.
Definition: unit.hpp:1174
std::size_t viewing_team() const
The viewing team is the team currently viewing the game.
Definition: display.hpp:128
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:1090
bool fogged(const map_location &loc) const
Definition: team.cpp:641
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:1156
int side() const
The side this unit belongs to.
Definition: unit.hpp:265
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:184
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 path
File path.
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:1100
void insert(const map_location &)
Definition: pathfind.cpp:491