The Battle for Wesnoth  1.17.0-dev
pathutils.cpp
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  * Various pathfinding functions and utilities.
19  */
20 
21 #include "pathutils.hpp"
22 #include "pathutils_impl.hpp"
23 
24 #include "map/map.hpp"
25 
26 
27 /**
28  * Function that will add to @a result all locations exactly @a radius tiles
29  * from @a center (or nothing if @a radius is not positive). @a result must be
30  * a std::vector of locations.
31  */
32 void get_tile_ring(const map_location& center, const int radius,
33  std::vector<map_location>& result)
34 {
35  if ( radius <= 0 ) {
36  return;
37  }
38 
40 
41  for(int n = 0; n != 6; ++n) {
42  const map_location::DIRECTION dir = static_cast<map_location::DIRECTION>(n);
43  for(int i = 0; i != radius; ++i) {
44  result.push_back(loc);
45  loc = loc.get_direction(dir, 1);
46  }
47  }
48 }
49 
50 
51 /**
52  * Function that will add to @a result all locations within @a radius tiles
53  * of @a center (excluding @a center itself). @a result must be a std::vector
54  * of locations.
55  */
56 void get_tiles_in_radius(const map_location& center, const int radius,
57  std::vector<map_location>& result)
58 {
59  for(int n = 1; n <= radius; ++n) {
60  get_tile_ring(center, n, result);
61  }
62 }
63 
64 
65 /**
66  * Function that will add to @a result all locations within @a radius tiles
67  * of @a center (including @a center itself). @a result must be a std::set
68  * of locations.
69  */
70 void get_tiles_radius(const map_location& center, std::size_t radius,
71  std::set<map_location>& result)
72 {
73  // Re-use some logic.
74  std::vector<map_location> internal_result(1, center);
75  get_tiles_in_radius(center, static_cast<int>(radius), internal_result);
76 
77  // Convert to a set.
78  result.insert(internal_result.begin(), internal_result.end());
79 }
80 
81 
82 namespace { // Helpers for get_tiles_radius() without a radius filter.
83 
84  // Ranges of rows are stored as pairs of a row number and a number of rows.
85  typedef std::pair<int, std::size_t> row_range;
86  // This is a map from column numbers to sets of ranges of rows.
87  typedef std::map<int, std::set<row_range>> column_ranges;
88 
89 
90  /**
91  * Function that will collect all locations within @a radius tiles of an
92  * element of @a locs, subject to the restriction col_begin <= x < col_end.
93  */
94  // Complexity: O(nr lg(nr)), where n = locs.size() and r = radius.
95  // In this formula, r is bound by col_end-col_begin (but that is
96  // probably a rare event).
97  void get_column_ranges(column_ranges & collected_tiles,
98  const std::vector<map_location>& locs,
99  const std::size_t radius,
100  const int col_begin, const int col_end)
101  {
102  // Shorter names for the directions we'll use.
106 
107  // Perform this conversion once.
108  const int radius_i = static_cast<int>(radius);
109 
110  for (const map_location &loc : locs)
111  if ( loc != map_location::null_location() )
112  {
113  // Calculate the circle of hexes around this one.
114  std::size_t height = radius;
115  map_location top = loc.get_direction(NORTH_WEST, radius_i);
116  // Don't start off the map edge.
117  if ( top.x < col_begin ) {
118  const int col_shift = std::min(col_begin, loc.x) - top.x;
119  top = top.get_direction(NORTH_EAST, col_shift);
120  height += col_shift;
121  }
122  // The left side.
123  const int end_l = std::min(loc.x, col_end);
124  for ( ; top.x < end_l; top = top.get_direction(NORTH_EAST, 1) )
125  collected_tiles[top.x].insert(row_range(top.y, ++height));
126  // Extra increment so the middle column is tall enough.
127  height += 2;
128  // Don't start off the map edge (we allow loc to be off-board).
129  if ( top.x < col_begin ) {
130  const int col_shift = col_begin - top.x;
131  top = top.get_direction(SOUTH_EAST, col_shift);
132  height -= col_shift;
133  }
134  // The middle column and right side.
135  const int end_r = std::min(loc.x + radius_i + 1, col_end);
136  for ( ; top.x < end_r; top = top.get_direction(SOUTH_EAST, 1) )
137  collected_tiles[top.x].insert(row_range(top.y, --height));
138  }
139  }
140 
141  /**
142  * Function that interprets @a collected_tiles and adds to @a result those
143  * whose y-coordinate satisfies row_begin <= y < row_end.
144  * When passed to this function, @a result must not be empty. (This allows
145  * a code simplification and is currently always the case anyway.)
146  */
147  // Complexity: O(number of distinct hexes collected), assuming that the
148  // insertion hint makes insertions O(1). Furthermore, hexes outside the
149  // interval [row_begin, row_end) are skipped and do not count towards the
150  // complexity.
151  void ranges_to_tiles(std::set<map_location> & result,
152  const column_ranges & collected_tiles,
153  int row_begin, int row_end)
154  {
155  // This should help optimize the insertions (since we will be
156  // processing hexes in their lexicographical order).
157  // Note: This hint will get incremented later, which is the only
158  // reason we require result to be initially non-empty.
159  auto insert_hint = result.begin();
160 
161  for(const auto& [column, range] : collected_tiles) {
162  // For this loop, the order within the set is crucial; we need
163  // rows.first to be non-decreasing with each iteration.
164  // Loop invariant: within this column, all rows before next_row
165  // have been processed and either added to result or skipped.
166  // There is no going back (nor a need to).
167  int next_row = row_begin;
168 
169  for(const auto& [row_index, num_rows] : range) {
170  // Skipping some rows?
171  if(next_row < row_index) {
172  next_row = row_index;
173  }
174 
175  // Add this range of hexes.
176  const int end = std::min(row_index + static_cast<int>(num_rows), row_end);
177  for(; next_row < end; ++next_row) {
178  insert_hint = result.insert(++insert_hint, map_location(column, next_row));
179  }
180 
181  // Have we reached the end of the board?
182  if(next_row >= row_end) {
183  break;
184  }
185  }
186  }
187  }
188 
189 } // namespage for get_tiles_radius() helpers.
190 
191 
192 /**
193  * Function that will add to @a result all elements of @a locs, plus all
194  * on-board locations that are within @a radius tiles of an element of locs.
195  * @a result must be a std::set of locations.
196  */
197 // Complexity: O(nr lg(nr) + nr^2), where n = locs.size(), r = radius.
198 // The nr^2 term is bounded by the size of the board.
199 void get_tiles_radius(const gamemap& map, const std::vector<map_location>& locs,
200  std::size_t radius, std::set<map_location>& result,
201  bool with_border)
202 {
203  // Make sure the provided locations are included.
204  // This would be needed in case some of the provided locations are off-map.
205  // It also allows simpler processing if the radius is zero.
206  // For efficiency, do this first since locs is potentially unsorted.
207  result.insert(locs.begin(), locs.end());
208 
209  if ( radius != 0 && !locs.empty() )
210  {
211  const int border = with_border ? map.border_size() : 0;
212  column_ranges collected_tiles;
213 
214  // Collect the hexes within the desired disks into collected_tiles.
215  // This maps each x-value to a set of ranges of y-values that
216  // are covered by the disks around each element of locs.
217  // (So the data size at this point is proportional to the number
218  // of x-values involved, which is O(nr). The lg(nr) factor comes
219  // from the data being sorted.)
220  get_column_ranges(collected_tiles, locs, radius, -border, map.w() + border);
221 
222  // Now that all the tiles have been collected, add them to result.
223  // (There are O(nr^2) hexes to add.) By collecting before adding, each
224  // hex will be processed only once, even when disks overlap. This is
225  // how we can get good performance if there is significant overlap, and
226  // how the work required can be bound by the size of the board.
227  ranges_to_tiles(result, collected_tiles, -border, map.h() + border);
228  }
229 }
230 
231 
232 /**
233  * Function that will add to @a result all elements of @a locs, plus all
234  * on-board locations matching @a pred that are connected to elements of
235  * locs by a chain of at most @a radius tiles, each of which matches @a pred.
236  * @a result must be a std::set of locations.
237  */
238 void get_tiles_radius(const gamemap& map, const std::vector<map_location>& locs,
239  std::size_t radius, std::set<map_location> &result,
240  bool with_border, const xy_pred& pred)
241 {
242  typedef std::set<map_location> location_set;
243  location_set not_visited(locs.begin(), locs.end());
244 
245  get_tiles_radius(std::move(not_visited), radius, result,
246  [&](const map_location& l) {
247  return with_border ? map.on_board_with_border(l) : map.on_board(l);
248  },
249  [&](const map_location& l) {
250  return pred(l);
251  }
252  );
253 }
void get_tiles_in_radius(const map_location &center, const int radius, std::vector< map_location > &result)
Function that will add to result all locations within radius tiles of center (excluding center itself...
Definition: pathutils.cpp:56
map_location get_direction(DIRECTION dir, unsigned int n=1u) const
Definition: location.cpp:360
void get_tile_ring(const map_location &center, const int radius, std::vector< map_location > &result)
Function that will add to result all locations exactly radius tiles from center (or nothing if radius...
Definition: pathutils.cpp:32
int w() const
Effective map width.
Definition: map.hpp:50
bool on_board_with_border(const map_location &loc) const
Definition: map.cpp:390
Encapsulates the map of the game.
Definition: map.hpp:171
Encapsulates the map of the game.
Definition: location.hpp:38
std::size_t i
Definition: function.cpp:967
void get_tiles_radius(const map_location &center, std::size_t radius, std::set< map_location > &result)
Function that will add to result all locations within radius tiles of center (including center itself...
Definition: pathutils.cpp:70
bool on_board(const map_location &loc) const
Tell if a location is on the map.
Definition: map.cpp:385
DIRECTION
Valid directions which can be moved in our hexagonal world.
Definition: location.hpp:40
std::set< map_location > location_set
int border_size() const
Size of the map border.
Definition: map.hpp:56
static const map_location & null_location()
Definition: location.hpp:81
static map_location::DIRECTION n
int h() const
Effective map height.
Definition: map.hpp:53