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