The Battle for Wesnoth  1.19.0-dev
pathfind.hpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2003 - 2024
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  */
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 {
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)
147  , marks()
148  {
149  }
150 
152  : route(rhs.route)
153  , steps(route.steps)
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 
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 }
double t
Definition: astarsearch.cpp:63
Game board class.
Definition: game_board.hpp:46
Encapsulates the map of the game.
Definition: map.hpp:172
A const-only interface for how many (movement, vision, or "jamming") points a unit needs for each hex...
Definition: movetype.hpp:54
The basic "size" of the unit - flying, small land, large land, etc.
Definition: movetype.hpp:45
This class stores all the data for a single 'side' (in game nomenclature).
Definition: team.hpp:74
A single unit type that the player may recruit.
Definition: types.hpp:43
This class represents a single unit of a specific type.
Definition: unit.hpp:133
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:117
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)
VACANT_TILE_TYPE
Definition: pathfind.hpp:39
@ VACANT_CASTLE
Definition: pathfind.hpp:39
@ VACANT_ANY
Definition: pathfind.hpp:39
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:134
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:658
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,...
Definition: pathfind.cpp:54
Encapsulates the map of the game.
Definition: location.hpp:38
static double getNoPathValue()
Definition: pathfind.hpp:65
virtual double cost(const map_location &loc, const double so_far) const =0
Function which doesn't take anything into account.
Definition: pathfind.hpp:256
virtual double cost(const map_location &loc, const double so_far) const
Definition: pathfind.cpp:871
dummy_path_calculator(const unit &u, const gamemap &map)
Definition: pathfind.cpp:868
Function which only uses terrain, ignoring shroud, enemies, etc.
Definition: pathfind.hpp:242
emergency_path_calculator(const unit &u, const gamemap &map)
Definition: pathfind.cpp:857
virtual double cost(const map_location &loc, const double so_far) const
Definition: pathfind.cpp:861
Structure which uses find_routes() to build a cost map This maps each hex to a the movements a unit w...
Definition: pathfind.hpp:268
const bool force_ignore_zoc_
Definition: pathfind.hpp:299
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:889
double get_average_cost_at(map_location loc) const
Accessor for the costs.
Definition: pathfind.cpp:999
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:919
const team & viewing_team_
Definition: pathfind.hpp:301
int get_cost_at(map_location loc) const
Accessor for the costs.
Definition: pathfind.cpp:988
std::pair< int, int > get_pair_at(map_location loc) const
Accessor for the cost/reach-amount pairs.
Definition: pathfind.cpp:970
const bool ignore_units_
Definition: pathfind.hpp:303
std::vector< std::pair< int, int > > cost_map
Definition: pathfind.hpp:296
const bool allow_teleport_
Definition: pathfind.hpp:300
A refinement of paths for use when calculating jamming.
Definition: pathfind.hpp:124
jamming_path(const unit &jammer, const map_location &loc)
Construct a list of jammed hexes for a unit.
Definition: pathfind.cpp:641
virtual ~jamming_path()
Default destructor.
Definition: pathfind.cpp:654
mark(int turns_number=0, bool in_zoc=false, bool do_capture=false, bool is_invisible=false)
Definition: pathfind.hpp:170
bool operator==(const mark &m) const
Definition: pathfind.hpp:179
Structure which holds a single route and marks for special events.
Definition: pathfind.hpp:142
marked_route(const marked_route &rhs)
Definition: pathfind.hpp:151
marked_route & operator=(const marked_route &rhs)
Definition: pathfind.hpp:159
std::map< map_location, mark > mark_map
Definition: pathfind.hpp:183
std::vector< map_location > & steps
Definition: pathfind.hpp:187
virtual double cost(const map_location &loc, const double so_far) const
Definition: pathfind.cpp:829
move_type_path_calculator(const movetype &mt, int movement_left, int total_movement, const team &t, const gamemap &map)
Definition: pathfind.cpp:823
Ordered vector of possible destinations.
Definition: pathfind.hpp:95
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:497
void insert(const map_location &)
Definition: pathfind.cpp:485
bool contains(const map_location &) const
Definition: pathfind.cpp:514
const_iterator find(const map_location &) const
Definition: pathfind.cpp:478
map_location curr
Definition: pathfind.hpp:89
map_location prev
Definition: pathfind.hpp:89
Object which contains all the possible locations a unit can move to, with associated best routes to t...
Definition: pathfind.hpp:73
virtual ~paths()
Virtual destructor (default processing).
Definition: pathfind.cpp:560
dest_vect destinations
Definition: pathfind.hpp:101
Structure which holds a single route between one location and another.
Definition: pathfind.hpp:133
std::vector< map_location > steps
Definition: pathfind.hpp:135
int move_cost
Movement cost for reaching the end of the route.
Definition: pathfind.hpp:137
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:732
const std::vector< team > & teams_
Definition: pathfind.hpp:215
virtual double cost(const map_location &loc, const double so_far) const
Definition: pathfind.cpp:742
A refinement of paths for use when calculating vision.
Definition: pathfind.hpp:108
std::set< map_location > edges
The edges are the non-destination hexes bordering the destinations.
Definition: pathfind.hpp:117
virtual ~vision_path()
Default destructor.
Definition: pathfind.cpp:627
vision_path(const unit &viewer, const map_location &loc, const std::map< map_location, int > &jamming_map)
Constructs a list of vision paths for a unit.
Definition: pathfind.cpp:576