The Battle for Wesnoth  1.13.11+dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
location.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 http://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 /** @file */
16 
17 #pragma once
18 
19 class config;
20 class variable_set;
21 
22 #include <array>
23 #include <cmath>
24 #include <cstdlib>
25 #include <set>
26 #include <string>
27 #include <tuple>
28 #include <vector>
29 #include <algorithm>
30 #include <utility>
31 
32 struct wml_loc {};
33 
34 /**
35  * Encapsulates the map of the game.
36  *
37  * Although the game is hexagonal, the map is stored as a grid.
38  * Each type of terrain is represented by a multiletter terrain code.
39  * @todo Update for new map-format.
40  */
41 /** Represents a location on the map. */
42 struct map_location {
43  /** Valid directions which can be moved in our hexagonal world. */
46 
47  static const std::vector<DIRECTION> & default_dirs();
48 
49  static DIRECTION rotate_right(DIRECTION d, unsigned int k = 1u);
50  static DIRECTION rotate_right(DIRECTION d, signed int k);
51 
53 
54  static DIRECTION parse_direction(const std::string& str);
55 
56  /**
57  * Parse_directions takes a comma-separated list, and filters out any
58  * invalid directions
59  */
60  static std::vector<DIRECTION> parse_directions(const std::string& str);
63 
64  map_location() : x(-1000), y(-1000) {}
65  map_location(int x, int y) : x(x), y(y) {}
66  map_location(int x, int y, wml_loc) : x(x - 1), y(y - 1) {}
67  map_location(const config& cfg, const variable_set *variables = nullptr);
68 
69  static const map_location & ZERO();
70  static const map_location & null_location();
71 
72  void write(config& cfg) const;
73 
74  inline bool valid() const { return x >= 0 && y >= 0; }
75 
76  inline bool valid(const int parWidth, const int parHeight) const
77  { return ((x >= 0) && (y >= 0) && (x < parWidth) && (y < parHeight)); }
78 
79  inline bool valid(const int parWidth, const int parHeight, const int border) const
80  { return ((x + border >= 0) && (y + border >= 0) && (x < parWidth + border) && (y < parHeight + border)); }
81 
82  bool matches_range(const std::string& xloc, const std::string& yloc) const;
83 
84  // Inlining those for performance reasons
85  bool operator<(const map_location& a) const { return std::tie(x, y) < std::tie(a.x, a.y); }
86  bool operator==(const map_location& a) const { return x == a.x && y == a.y; }
87  bool operator!=(const map_location& a) const { return !operator==(a); }
88 
89  /** three-way comparator */
90  int do_compare(const map_location& a) const {return x == a.x ? y - a.y : x - a.x; }
91 
92  // Location arithmetic operations treating the locations as vectors in
93  // a hex-based space. These operations form an abelian group, i.e.
94  // everything works as you would expect addition and subtraction to
95  // work, with associativity and commutativity.
97  map_location vector_sum(const map_location &a) const;
100 
101  // Do n step in the direction d
102  map_location get_direction(DIRECTION d, unsigned int n = 1u) const;
103  map_location get_direction(DIRECTION d, signed int n) const;
104 
106  DIRECTION get_relative_dir(const map_location & loc, map_location::RELATIVE_DIR_MODE mode /*= map_location::RADIAL_SYMMETRY*/ ) const;
107  DIRECTION get_relative_dir(const map_location & loc) const; //moved the default setting to .cpp file for ease of testing
108 
109  // Express as a vector in the basis N, NE. N, and NE may be obtained by zero.get_direction(NORTH), ...(NORTH_EAST), respectively.
110  std::pair<int,int> get_in_basis_N_NE() const;
111 
112  // Rotates the map_location clockwise in 60 degree increments around a center point. Negative numbers of steps are permitted.
113  map_location rotate_right_around_center(const map_location & center, int k) const;
114 
115  friend std::size_t hash_value(const map_location& a);
116 
117  int wml_x() const { return x + 1; }
118  int wml_y() const { return y + 1; }
119 
120  void set_wml_x(int v) { x = v - 1; }
121  void set_wml_y(int v) { y = v - 1; }
122  //on purpose these functions don't take map_location objects, if you use map_location objects to store 'differences' between 2 locations use vector_sum().
123  void add(int x_diff, int y_diff) { x += x_diff; y += y_diff; }
124  map_location plus(int x_diff, int y_diff) const { return map_location(x + x_diff, y + y_diff); }
125 
126 
127  int x, y;
128 };
129 
130 using adjacent_loc_array_t = std::array<map_location, 6>;
131 
132 /** Function which tells if two locations are adjacent. */
133 bool tiles_adjacent(const map_location& a, const map_location& b);
134 
135 /**
136  * Function which, given a location, will place all adjacent locations in res.
137  * res must point to an array of 6 location objects.
138  */
139 void get_adjacent_tiles(const map_location& a, map_location* res);
140 
141 /**
142  * Function which gives the number of hexes between two tiles
143  * (i.e. the minimum number of hexes that have to be traversed
144  * to get from one hex to the other).
145  */
146 size_t distance_between(const map_location& a, const map_location& b);
147 
148 /**
149  * Write a set of locations into a config using ranges,
150  * adding keys x=x1,..,xn and y=y1a-y1b,..,yna-ynb
151  */
152 void write_location_range(const std::set<map_location>& locs, config& cfg);
153 
154 /**
155  * Parse x,y keys of a config into a vector of locations
156  *
157  * Throws bad_lexical_cast if it fails to parse.
158  */
159 void read_locations(const config& cfg, std::vector<map_location>& locs);
160 
161 /** Write a vector of locations into a config
162  * adding keys x=x1,x2,..,xn and y=y1,y2,..,yn */
163 void write_locations(const std::vector<map_location>& locs, config& cfg);
164 
165 /** Dumps a position on a stream, for debug purposes. */
166 std::ostream &operator<<(std::ostream &s, const map_location& l);
167 /** Dumps a vector of positions on a stream, for debug purposes. */
168 std::ostream &operator<<(std::ostream &s, const std::vector<map_location>& v);
169 
170 namespace std {
171 template<>
172 struct hash<map_location> {
173  size_t operator()(const map_location& l) const {
174  // The 2000 bias supposedly ensures that the correct x is recovered for negative y
175  // This implementation copied from the Lua location_set
176  return (l.wml_x()) * 16384 + (l.wml_y()) + 2000;
177  }
178 };
179 }
180 
181 /** Inlined bodies **/
182 
183 /** Inline direction manipulators **/
185  return (d == map_location::NDIRECTIONS) ? map_location::NDIRECTIONS : static_cast<map_location::DIRECTION>((d + (k%6u)) % 6u);
186 }
187 
189  return (k>=0) ? rotate_right(d, static_cast<unsigned int> (k)) : rotate_right(d, (static_cast<unsigned int>(-k) % 6u) * 5u);
190 }
191 
193  return rotate_right(d,3u);
194 }
195 
196 /** Old implementation: **/
197 /*map_location::DIRECTION map_location::get_opposite_dir(map_location::DIRECTION d) {
198  switch (d) {
199  case NORTH:
200  return SOUTH;
201  case NORTH_EAST:
202  return SOUTH_WEST;
203  case SOUTH_EAST:
204  return NORTH_WEST;
205  case SOUTH:
206  return NORTH;
207  case SOUTH_WEST:
208  return NORTH_EAST;
209  case NORTH_WEST:
210  return SOUTH_EAST;
211  case NDIRECTIONS:
212  default:
213  return NDIRECTIONS;
214  }
215 }*/
216 
217 
218 /** Inline constant map_location defns **/
220  static const map_location z(0,0);
221  return z;
222 }
223 
225  static const map_location l;
226  return l;
227 }
228 
229 /** Inline vector ops **/
231 {
232  return map_location(-x, -y - (x & 1)); //subtract one if we're on an odd x coordinate
233 }
234 
236 {
237  return map_location(*this).vector_sum_assign(a);
238 }
239 
241 {
242  y += ((x & 1) && (a.x & 1)); //add one if both x coords are odd
243  x += a.x;
244  y += a.y;
245  return *this;
246 }
247 
249 {
251 }
252 
253 /** Get Direction function **/
254 
256  map_location::DIRECTION dir, signed int n) const
257 {
258  return (n >= 0) ? get_direction(dir, static_cast<unsigned int> (n)) : get_direction(get_opposite_dir(dir), static_cast<unsigned int> (-n));
259 }
260 
262  map_location::DIRECTION dir, unsigned int n) const
263 {
264  if (dir == map_location::NDIRECTIONS) {
266  }
267 
268  if (dir == NORTH) {
269  return map_location(x,y-n);
270  }
271 
272  if (dir == SOUTH) {
273  return map_location(x,y+n);
274  }
275 
276  int x_factor = (static_cast<unsigned int> (dir) <= 2u) ? 1 : -1; //whether we go east + or west -
277 
278  unsigned int tmp_y = dir - 2; //South East => 0, South => 1, South West => 2, North West => 3, North => INT_MAX, North East => INT_MAX - 1
279  int y_factor = (tmp_y <= 2u) ? 1 : -1; //whether we go south + or north -
280 
281  if (tmp_y <= 2u) {
282  return map_location(x + x_factor * n, y + y_factor * ((n + ((x & 1) == 1)) / 2));
283  } else {
284  return map_location(x + x_factor * n, y + y_factor * ((n + ((x & 1) == 0)) / 2));
285  }
286 
287 /*
288  switch(dir) {
289  case NORTH: return map_location(x, y - n);
290  case SOUTH: return map_location(x, y + n);
291  case SOUTH_EAST: return map_location(x + n, y + (n+is_odd(x))/2 );
292  case SOUTH_WEST: return map_location(x - n, y + (n+is_odd(x))/2 );
293  case NORTH_EAST: return map_location(x + n, y - (n+is_even(x))/2 );
294  case NORTH_WEST: return map_location(x - n, y - (n+is_even(x))/2 );
295  default:
296  assert(false);
297  return map_location::null_location();
298  }*/
299 }
300 
301 /** inline get_adjacent, and get_distance functions **/
302 
304 {
305  res->x = a.x;
306  res->y = a.y-1;
307  ++res;
308  res->x = a.x+1;
309  res->y = a.y - (((a.x & 1)==0) ? 1:0);
310  ++res;
311  res->x = a.x+1;
312  res->y = a.y + (((a.x & 1)==1) ? 1:0);
313  ++res;
314  res->x = a.x;
315  res->y = a.y+1;
316  ++res;
317  res->x = a.x-1;
318  res->y = a.y + (((a.x & 1)==1) ? 1:0);
319  ++res;
320  res->x = a.x-1;
321  res->y = a.y - (((a.x & 1)==0) ? 1:0);
322 /* Changed this when I inlined it to eliminate util.hpp dependency.
323  res->x = a.x;
324  res->y = a.y-1;
325  ++res;
326  res->x = a.x+1;
327  res->y = a.y - (is_even(a.x) ? 1:0);
328  ++res;
329  res->x = a.x+1;
330  res->y = a.y + (is_odd(a.x) ? 1:0);
331  ++res;
332  res->x = a.x;
333  res->y = a.y+1;
334  ++res;
335  res->x = a.x-1;
336  res->y = a.y + (is_odd(a.x) ? 1:0);
337  ++res;
338  res->x = a.x-1;
339  res->y = a.y - (is_even(a.x) ? 1:0);
340 */
341 }
342 
343 inline bool tiles_adjacent(const map_location& a, const map_location& b)
344 {
345  // Two tiles are adjacent:
346  // if y is different by 1, and x by 0,
347  // or if x is different by 1 and y by 0,
348  // or if x and y are each different by 1,
349  // and the x value of the hex with the greater y value is even.
350 
351  switch (a.y - b.y) {
352  case 1 :
353  switch (a.x - b.x) {
354  case 1:
355  case -1:
356  return (a.x & 1) == 0;
357  case 0:
358  return true;
359  default:
360  return false;
361  }
362  case -1 :
363  switch (a.x - b.x) {
364  case 1:
365  case -1:
366  return (b.x & 1) == 0;
367  case 0:
368  return true;
369  default:
370  return false;
371  }
372  case 0 :
373  return ((a.x - b.x) == 1) || ((a.x - b.x) == - 1);
374  default:
375  return false;
376  }
377 
378  /*
379  const int xdiff = std::abs(a.x - b.x);
380  const int ydiff = std::abs(a.y - b.y);
381  return (ydiff == 1 && a.x == b.x) || (xdiff == 1 && a.y == b.y) ||
382  (xdiff == 1 && ydiff == 1 && (a.y > b.y ? is_even(a.x) : is_even(b.x)));
383  */
384 }
385 
386 inline size_t distance_between(const map_location& a, const map_location& b)
387 {
388  const size_t hdistance = std::abs(a.x - b.x);
389 
390  const size_t vpenalty = ( (((a.x & 1)==0) && ((b.x & 1)==1) && (a.y < b.y))
391  || (((b.x & 1)==0) && ((a.x & 1)==1) && (b.y < a.y)) ) ? 1 : 0;
392 
393 /* Don't want to include util.hpp in this header
394  const size_t vpenalty = ( (is_even(a.x) && is_odd(b.x) && (a.y < b.y))
395  || (is_even(b.x) && is_odd(a.x) && (b.y < a.y)) ) ? 1 : 0;
396 */
397  // For any non-negative integer i, i - i/2 - i%2 == i/2
398  // previously returned (hdistance + vdistance - vsavings)
399  // = hdistance + vdistance - minimum(vdistance,hdistance/2+hdistance%2)
400  // = maximum(hdistance, vdistance+hdistance-hdistance/2-hdistance%2)
401  // = maximum(hdistance,std::abs(a.y-b.y)+vpenalty+hdistance/2)
402 
403  return std::max<int>(hdistance, std::abs(a.y - b.y) + vpenalty + hdistance/2);
404 }
void set_wml_y(int v)
Definition: location.hpp:121
void write_location_range(const std::set< map_location > &locs, config &cfg)
Write a set of locations into a config using ranges, adding keys x=x1,..,xn and y=y1a-y1b,..,yna-ynb.
Definition: location.cpp:402
map_location(int x, int y)
Definition: location.hpp:65
std::ostream & operator<<(std::ostream &s, const map_location &l)
Dumps a position on a stream, for debug purposes.
Definition: location.cpp:35
static DIRECTION parse_direction(const std::string &str)
Definition: location.cpp:64
static std::string write_translated_direction(DIRECTION dir)
Definition: location.cpp:160
std::vector< char_t > string
bool matches_range(const std::string &xloc, const std::string &yloc) const
Definition: location.cpp:316
map_location(int x, int y, wml_loc)
Definition: location.hpp:66
map_location rotate_right_around_center(const map_location &center, int k) const
Definition: location.cpp:305
#define a
void get_adjacent_tiles(const map_location &a, map_location *res)
Function which, given a location, will place all adjacent locations in res.
Definition: location.hpp:303
bool operator!=(const map_location &a) const
Definition: location.hpp:87
static const map_location & ZERO()
Old implementation:
Definition: location.hpp:219
map_location & vector_difference_assign(const map_location &a)
Definition: location.hpp:248
void set_wml_x(int v)
Definition: location.hpp:120
STL namespace.
map_location plus(int x_diff, int y_diff) const
Definition: location.hpp:124
int wml_y() const
Definition: location.hpp:118
DIRECTION get_relative_dir(const map_location &loc, map_location::RELATIVE_DIR_MODE mode) const
Definition: location.cpp:225
#define d
static std::vector< DIRECTION > parse_directions(const std::string &str)
Parse_directions takes a comma-separated list, and filters out any invalid directions.
Definition: location.cpp:123
bool valid(const int parWidth, const int parHeight) const
Definition: location.hpp:76
bool valid(const int parWidth, const int parHeight, const int border) const
Definition: location.hpp:79
#define b
int wml_x() const
Definition: location.hpp:117
void add(int x_diff, int y_diff)
Definition: location.hpp:123
bool tiles_adjacent(const map_location &a, const map_location &b)
Function which tells if two locations are adjacent.
Definition: location.hpp:343
bool valid() const
Definition: location.hpp:74
size_t distance_between(const map_location &a, const map_location &b)
Function which gives the number of hexes between two tiles (i.e.
Definition: location.hpp:386
map_location vector_sum(const map_location &a) const
Definition: location.hpp:235
static DIRECTION get_opposite_dir(DIRECTION d)
Definition: location.hpp:192
static const std::vector< DIRECTION > & default_dirs()
Default list of directions.
Definition: location.cpp:51
std::array< map_location, 6 > adjacent_loc_array_t
Definition: location.hpp:130
static const map_location & null_location()
Definition: location.hpp:224
void write(config &cfg) const
Definition: location.cpp:210
Encapsulates the map of the game.
Definition: location.hpp:42
void write_locations(const std::vector< map_location > &locs, config &cfg)
Write a vector of locations into a config adding keys x=x1,x2,..,xn and y=y1,y2,..,yn.
Definition: location.cpp:458
static DIRECTION rotate_right(DIRECTION d, unsigned int k=1u)
Inlined bodies.
Definition: location.hpp:184
static map_location::DIRECTION s
DIRECTION
Valid directions which can be moved in our hexagonal world.
Definition: location.hpp:44
bool operator<(const map_location &a) const
Definition: location.hpp:85
map_location & vector_sum_assign(const map_location &a)
Definition: location.hpp:240
size_t operator()(const map_location &l) const
Definition: location.hpp:173
std::pair< int, int > get_in_basis_N_NE() const
Definition: location.cpp:286
int do_compare(const map_location &a) const
three-way comparator
Definition: location.hpp:90
map_location get_direction(DIRECTION d, unsigned int n=1u) const
Definition: location.hpp:261
map_location vector_negation() const
Inline vector ops.
Definition: location.hpp:230
A config object defines a single node in a WML file, with access to child nodes.
Definition: config.hpp:93
static map_location::DIRECTION n
static std::string write_direction(DIRECTION dir)
Definition: location.cpp:139
void read_locations(const config &cfg, std::vector< map_location > &locs)
Parse x,y keys of a config into a vector of locations.
Definition: location.cpp:446
bool operator==(const map_location &a) const
Definition: location.hpp:86
friend std::size_t hash_value(const map_location &a)
Definition: location.cpp:58