The Battle for Wesnoth  1.15.2+dev
pathfind.hpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2003 - 2018 by David White <dave@whitevine.net>
3  Part of the Battle for Wesnoth Project https://www.wesnoth.org/
4 
5  This program is free software; you can redistribute it and/or modify
6  it under the terms of the GNU General Public License as published by
7  the Free Software Foundation; either version 2 of the License, or
8  (at your option) any later version.
9  This program is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY.
11 
12  See the COPYING file for more details.
13 */
14 
15 /**
16  * @file
17  * This module contains various pathfinding functions and utilities.
18  */
19 
20 #pragma once
21 
22 class gamemap;
23 class team;
24 class unit;
25 class unit_type;
26 class game_board;
27 #include "map/location.hpp"
28 #include "movetype.hpp"
29 
30 #include <vector>
31 #include <map>
32 #include <set>
33 
34 namespace pathfind {
35 
36 class teleport_map;
37 
39 
40 /// Function that will find a location on the board that is as near
41 /// to @a loc as possible, but which is unoccupied by any units.
43  VACANT_TILE_TYPE vacancy=VACANT_ANY,
44  const unit* pass_check=nullptr,
45  const team* shroud_check=nullptr,
46  const game_board* board=nullptr);
47 /// Wrapper for find_vacant_tile() when looking for a vacant castle tile
48 /// near a leader.
49 map_location find_vacant_castle(const unit & leader);
50 
51 /** Determines if a given location is in an enemy zone of control. */
52 bool enemy_zoc(const team& current_team, const map_location& loc,
53  const team& viewing_team, bool see_all=false);
54 
55 
57 {
59 
60  virtual double cost(const map_location& loc, const double so_far) const = 0;
61  virtual ~cost_calculator() {}
62 
63  static double getNoPathValue() { return (42424242.0); }
64 };
65 
66 /**
67  * Object which contains all the possible locations a unit can move to,
68  * with associated best routes to those locations.
69  */
70 struct paths
71 {
73  : destinations()
74  {
75  }
76 
77  /// Construct a list of paths for the specified unit.
78  paths(const unit& u,
79  bool force_ignore_zocs, bool allow_teleport,
80  const team &viewing_team, int additional_turns = 0,
81  bool see_all = false, bool ignore_units = false);
82  /// Virtual destructor (default processing).
83  virtual ~paths();
84 
85  struct step
86  {
88  int move_left;
89  };
90 
91  /** Ordered vector of possible destinations. */
92  struct dest_vect : std::vector<step>
93  {
94  const_iterator find(const map_location &) const;
95  bool contains(const map_location &) const;
96  void insert(const map_location &);
97  std::vector<map_location> get_path(const const_iterator &) const;
98  };
100 };
101 
102 /**
103  * A refinement of paths for use when calculating vision.
104  */
105 struct vision_path : public paths
106 {
107  /// Construct a list of seen hexes for a unit.
108  vision_path(const unit& viewer, const map_location& loc,
109  const std::map<map_location, int>& jamming_map);
110  vision_path(const movetype::terrain_costs & view_costs, bool slowed,
111  int sight_range, const map_location & loc,
112  const std::map<map_location, int>& jamming_map);
113  virtual ~vision_path();
114 
115  /// The edges are the non-destination hexes bordering the destinations.
116  std::set<map_location> edges;
117 };
118 
119 /**
120  * A refinement of paths for use when calculating jamming.
121  */
122 struct jamming_path : public paths
123 {
124  /// Construct a list of jammed hexes for a unit.
125  jamming_path(const unit& jammer, const map_location& loc);
126  virtual ~jamming_path();
127 };
128 
129 
130 /** Structure which holds a single route between one location and another. */
132 {
133  plain_route() : steps(), move_cost(0) {}
134  std::vector<map_location> steps;
135  /** Movement cost for reaching the end of the route. */
137 };
138 
139 /** Structure which holds a single route and marks for special events. */
141 {
143  : route()
144  , steps(route.steps)
145  , move_cost(route.move_cost)
146  , marks()
147  {
148  }
149 
151  : route(rhs.route)
152  , steps(route.steps)
153  , move_cost(route.move_cost)
154  , marks(rhs.marks)
155  {
156  }
157 
159  {
160  this->route = rhs.route;
161  this->steps = this->route.steps;
162  this->move_cost = this->route.move_cost;
163  this->marks = rhs.marks;
164  return *this;
165  }
166 
167  struct mark
168  {
169  mark(int turns_number = 0, bool in_zoc = false,
170  bool do_capture = false, bool is_invisible = false)
171  : turns(turns_number), zoc(in_zoc),
172  capture(do_capture), invisible(is_invisible) {}
173  int turns;
174  bool zoc;
175  bool capture;
176  bool invisible;
177 
178  bool operator==(const mark& m) const {
179  return turns == m.turns && zoc == m.zoc && capture == m.capture && invisible == m.invisible;
180  }
181  };
182  typedef std::map<map_location, mark> mark_map;
184 
185  //make steps and move_cost of the underlying plain_route directly accessible
186  std::vector<map_location>& steps;
187  int& move_cost;
188 
189  mark_map marks;
190 };
191 
192 plain_route a_star_search(const map_location& src, const map_location& dst,
193  double stop_at, const cost_calculator& costCalculator,
194  const std::size_t parWidth, const std::size_t parHeight,
195  const teleport_map* teleports = nullptr, bool border = false);
196 
197 /**
198  * Add marks on a route @a rt assuming that the unit located at the first hex of
199  * rt travels along it.
200  */
201 marked_route mark_route(const plain_route &rt, bool update_move_cost = false);
202 
204 {
205  shortest_path_calculator(const unit& u, const team& t,
206  const std::vector<team> &teams, const gamemap &map,
207  bool ignore_unit = false, bool ignore_defense_ = false,
208  bool see_all = false);
209  virtual double cost(const map_location& loc, const double so_far) const;
210 
211 private:
212  const unit& unit_;
214  const std::vector<team>& teams_;
215  const gamemap& map_;
216  const int movement_left_;
217  const int total_movement_;
218  bool const ignore_unit_;
219  bool const ignore_defense_;
220  bool see_all_;
221 };
222 
224 {
225  move_type_path_calculator(const movetype& mt, int movement_left, int total_movement, const team& t, const gamemap& map);
226  virtual double cost(const map_location& loc, const double so_far) const;
227 
228 private:
230  const int movement_left_;
231  const int total_movement_;
233  const gamemap& map_;
234 };
235 
236 /**
237  * Function which only uses terrain, ignoring shroud, enemies, etc.
238  * Required by move_unit_fake if the normal path fails.
239  */
241 {
242  emergency_path_calculator(const unit& u, const gamemap& map);
243  virtual double cost(const map_location& loc, const double so_far) const;
244 
245 private:
246  const unit& unit_;
247  const gamemap& map_;
248 };
249 
250 /**
251  * Function which doesn't take anything into account. Used by
252  * move_unit_fake for the last-chance case.
253  */
255 {
256  dummy_path_calculator(const unit& u, const gamemap& map);
257  virtual double cost(const map_location& loc, const double so_far) const;
258 };
259 
260 /**
261  * Structure which uses find_routes() to build a cost map
262  * This maps each hex to a the movements a unit will need to reach
263  * this hex.
264  * Can be used commutative by calling add_unit() multiple times.
265  */
267 {
268  // "normal" constructor
269  full_cost_map(const unit& u, bool force_ignore_zoc,
270  bool allow_teleport, const team &viewing_team,
271  bool see_all=true, bool ignore_units=true);
272 
273  // constructor for work with add_unit()
274  // same as "normal" constructor. Just without unit
275  full_cost_map(bool force_ignore_zoc,
276  bool allow_teleport, const team &viewing_team,
277  bool see_all=true, bool ignore_units=true);
278 
279  void add_unit(const unit& u, bool use_max_moves=true);
280  void add_unit(const map_location& origin, const unit_type* const unit_type, int side);
281  int get_cost_at(int x, int y) const;
282  std::pair<int, int> get_pair_at(int x, int y) const;
283  double get_average_cost_at(int x, int y) const;
284  virtual ~full_cost_map()
285  {
286  }
287 
288  // This is a vector of pairs
289  // Every hex has an entry.
290  // The first int is the accumulated cost for one or multiple units
291  // It is -1 when no unit can reach this hex.
292  // The second int is how many units can reach this hex.
293  // (For some units some hexes or even a whole regions are unreachable)
294  // To calculate a *average cost map* it is recommended to divide first/second.
295  std::vector<std::pair<int, int>> cost_map;
296 
297 private:
298  const bool force_ignore_zoc_;
299  const bool allow_teleport_;
301  const bool see_all_;
302  const bool ignore_units_;
303 };
304 }
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
A const-only interface for how many (movement, vision, or "jamming") points a unit needs for each hex...
Definition: movetype.hpp:48
marked_route & operator=(const marked_route &rhs)
Definition: pathfind.hpp:158
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
Function which doesn&#39;t take anything into account.
Definition: pathfind.hpp:254
std::vector< std::pair< int, int > > cost_map
Definition: pathfind.hpp:295
This class represents a single unit of a specific type.
Definition: unit.hpp:99
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 contains(const pane::item &item, const std::string &tag, const text_box &text_box)
A filter testing whether a search string is used in a text.
Definition: filter.hpp:63
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
A refinement of paths for use when calculating jamming.
Definition: pathfind.hpp:122
dest_vect destinations
Definition: pathfind.hpp:99
marked_route(const marked_route &rhs)
Definition: pathfind.hpp:150
The basic "size" of the unit - flying, small land, large land, etc.
Definition: movetype.hpp:41
bool operator==(const mark &m) const
Definition: pathfind.hpp:178
A single unit type that the player may recruit.
Definition: types.hpp:42
static double getNoPathValue()
Definition: pathfind.hpp:63
This class stores all the data for a single &#39;side&#39; (in game nomenclature).
Definition: team.hpp:44
std::vector< map_location > steps
Definition: pathfind.hpp:134
Structure which holds a single route between one location and another.
Definition: pathfind.hpp:131
const bool allow_teleport_
Definition: pathfind.hpp:299
map_location prev
Definition: pathfind.hpp:87
VACANT_TILE_TYPE
Definition: pathfind.hpp:38
Encapsulates the map of the game.
Definition: map.hpp:36
Function which only uses terrain, ignoring shroud, enemies, etc.
Definition: pathfind.hpp:240
Structure which holds a single route and marks for special events.
Definition: pathfind.hpp:140
int move_cost
Movement cost for reaching the end of the route.
Definition: pathfind.hpp:136
Encapsulates the map of the game.
Definition: location.hpp:42
mark(int turns_number=0, bool in_zoc=false, bool do_capture=false, bool is_invisible=false)
Definition: pathfind.hpp:169
Ordered vector of possible destinations.
Definition: pathfind.hpp:92
const std::vector< team > & teams_
Definition: pathfind.hpp:214
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
map_location curr
Definition: astarsearch.cpp:65
const team & viewing_team_
Definition: pathfind.hpp:300
const bool ignore_units_
Definition: pathfind.hpp:302
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
A refinement of paths for use when calculating vision.
Definition: pathfind.hpp:105
const bool force_ignore_zoc_
Definition: pathfind.hpp:298
std::map< map_location, mark > mark_map
Definition: pathfind.hpp:182
int turns()
Definition: game.cpp:583
double t
Definition: astarsearch.cpp:64
virtual double cost(const map_location &loc, const double so_far) const =0
bool find(E event, F functor)
Tests whether an event handler is available.
std::set< map_location > edges
The edges are the non-destination hexes bordering the destinations.
Definition: pathfind.hpp:116
Object which contains all the possible locations a unit can move to, with associated best routes to t...
Definition: pathfind.hpp:70
plain_route a_star_search(const map_location &src, const map_location &dst, double stop_at, const cost_calculator &calc, const std::size_t width, const std::size_t height, const teleport_map *teleports, bool border)
std::vector< map_location > & steps
Definition: pathfind.hpp:186