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