The Battle for Wesnoth  1.19.14+dev
location.hpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2003 - 2025
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 #pragma once
17 
18 class config;
20 class variable_set;
21 
22 #include <array>
23 #include <set>
24 #include "utils/span.hpp"
25 #include <string>
26 #include <tuple>
27 #include <vector>
28 #include <utility>
29 
30 struct wml_loc {};
31 
32 /// Represents a map location in cubic hexagonal coordinates.
33 /// See <https://www.redblobgames.com/grids/hexagons/#coordinates-cube> for a more detailed explanation.
35  int q, r, s;
36 };
37 
38 /**
39  * Encapsulates the map of the game.
40  *
41  * Although the game is hexagonal, the map is stored as a grid.
42  * Each type of terrain is represented by a multiletter terrain code.
43  * @todo Update for new map-format.
44  */
45 /** Represents a location on the map. */
46 struct map_location {
47  /** Valid directions which can be moved in our hexagonal world. */
48  enum class direction {
49  north,
50  north_east,
51  south_east,
52  south,
53  south_west,
54  north_west,
56  };
57 
58  static std::vector<direction> all_directions();
59 
60  /** Returns the direction one would face having taken @a steps clockwise around an undefined center. */
61  static constexpr direction rotate_direction(direction d, int steps = 1)
62  {
65  }
66 
67  // Compensate for weirdness with the C++ % operator.
68  // The plain formula (d + (steps % 6)) % 6 works for almost every case, but it returns incorrect
69  // results for a counterclockwise rotation on direction::north. Instead, for any negative steps,
70  // cancel out the sign and scale by the highest possible direction value (viz., 5). This has the
71  // effect of a clockwise rotation ending at the same value as the specified counter-clockwise op.
72  int adjusted_steps = steps >= 0 ? steps : steps * -5;
73  return direction{(static_cast<int>(d) + (adjusted_steps % 6)) % 6};
74  }
75 
77  {
78  return rotate_direction(d, 3);
79  }
80 
81  static direction parse_direction(const std::string& str);
82 
83  /**
84  * Parse_directions takes a comma-separated list, and filters out any
85  * invalid directions
86  */
87  static std::vector<direction> parse_directions(const std::string& str);
88  static std::string write_direction(direction dir);
89  static std::string write_translated_direction(direction dir);
90 
91  map_location() : x(-1000), y(-1000) {}
92  map_location(int x, int y) : x(x), y(y) {}
93  map_location(int x, int y, wml_loc) : x(x - 1), y(y - 1) {}
95  map_location(const config& cfg, const variable_set *variables = nullptr);
96 
97  static const map_location& ZERO()
98  {
99  static const map_location z(0,0);
100  return z;
101  }
102 
103  static const map_location& null_location()
104  {
105  static const map_location l;
106  return l;
107  }
108 
109  void write(config& cfg) const;
110 
111  bool valid() const { return x >= 0 && y >= 0; }
112 
113  bool valid(const int parWidth, const int parHeight) const
114  { return ((x >= 0) && (y >= 0) && (x < parWidth) && (y < parHeight)); }
115 
116  bool valid(const int parWidth, const int parHeight, const int border) const
117  { return ((x + border >= 0) && (y + border >= 0) && (x < parWidth + border) && (y < parHeight + border)); }
118 
119  bool matches_range(const std::string& xloc, const std::string& yloc) const;
120 
121  // Inlining those for performance reasons
122  bool operator<(const map_location& a) const { return std::tie(x, y) < std::tie(a.x, a.y); }
123  bool operator==(const map_location& a) const { return x == a.x && y == a.y; }
124  bool operator!=(const map_location& a) const { return !operator==(a); }
125 
126  /** three-way comparator */
127  int do_compare(const map_location& a) const {return x == a.x ? y - a.y : x - a.x; }
128 
129  // Location arithmetic operations treating the locations as vectors in
130  // a hex-based space. These operations form an abelian group, i.e.
131  // everything works as you would expect addition and subtraction to
132  // work, with associativity and commutativity.
134  {
135  return map_location(-x, -y - (x & 1)); //subtract one if we're on an odd x coordinate
136  }
137 
139  {
140  return map_location(*this).vector_sum_assign(a);
141  }
142 
144  {
145  y += ((x & 1) && (a.x & 1)); //add one if both x coords are odd
146  x += a.x;
147  y += a.y;
148  return *this;
149  }
150 
152  {
154  }
155 
156  // Do n step in the direction d
157  map_location get_direction(direction dir, unsigned int n = 1u) const;
158  map_location get_direction(direction dir, signed int n) const
159  {
160  return (n >= 0) ? get_direction(dir, static_cast<unsigned int> (n)) : get_direction(get_opposite_direction(dir), static_cast<unsigned int> (-n));
161  }
162 
164  direction get_relative_dir(const map_location& loc, map_location::RELATIVE_DIR_MODE mode /*= map_location::RADIAL_SYMMETRY*/ ) const;
165  direction get_relative_dir(const map_location& loc) const; //moved the default setting to .cpp file for ease of testing
166 
168  int q = x;
169  int r = y - int((x - abs(x) % 2) / 2);
170  int s = -q - r;
171  return cubic_location{q, r, s};
172  }
174  int x = h.q;
175  int y = h.r + int((h.q - abs(h.q) % 2) / 2);
176  return map_location(x, y);
177  }
178 
179  std::vector<map_location> get_ring(int min, int max) const;
180 
181  // Rotates the map_location clockwise in 60 degree increments around a center point. Negative numbers of steps are permitted.
182  map_location rotate_right_around_center(const map_location& center, int k) const;
183 
184  friend std::size_t hash_value(const map_location& a);
185 
186  int wml_x() const { return x + 1; }
187  int wml_y() const { return y + 1; }
188 
189  void set_wml_x(int v) { x = v - 1; }
190  void set_wml_y(int v) { y = v - 1; }
191  //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().
192  void add(int x_diff, int y_diff) { x += x_diff; y += y_diff; }
193  map_location plus(int x_diff, int y_diff) const { return map_location(x + x_diff, y + y_diff); }
194 
195 
196  int x, y;
197 };
198 
199 /** Function which tells if two locations are adjacent. */
200 bool tiles_adjacent(const map_location& a, const map_location& b);
201 
202 /**
203  * Function which, given a location, will place all adjacent locations in res.
204  * res must point to an array of 6 location objects.
205  */
207 
208 /** Returns an array of the six hexes adjacent to @p center. */
209 std::array<map_location, 6> get_adjacent_tiles(const map_location& center);
210 
211 /**
212  * Function which gives the number of hexes between two tiles
213  * (i.e. the minimum number of hexes that have to be traversed
214  * to get from one hex to the other).
215  */
216 std::size_t distance_between(const map_location& a, const map_location& b);
217 
218 /**
219  * Write a set of locations into a config using ranges,
220  * adding keys x=x1,..,xn and y=y1a-y1b,..,yna-ynb
221  */
222 void write_location_range(const std::set<map_location>& locs, config& cfg);
223 
224 /**
225  * Parse x,y keys of a config into a vector of locations
226  *
227  * Throws bad_lexical_cast if it fails to parse.
228  */
229 void read_locations(const config& cfg, std::vector<map_location>& locs);
230 
231 /** Write a vector of locations into a config
232  * adding keys x=x1,x2,..,xn and y=y1,y2,..,yn */
233 void write_locations(const std::vector<map_location>& locs, config& cfg);
234 
235 /** Dumps a position on a stream, for debug purposes. */
236 std::ostream& operator<<(std::ostream& s, const map_location& l);
237 /** Dumps a vector of positions on a stream, for debug purposes. */
238 std::ostream& operator<<(std::ostream& s, const std::vector<map_location>& v);
239 
240 /** Print a direction's string representation to stream. */
241 std::ostream& operator<<(std::ostream& s, map_location::direction dir);
242 
243 namespace std {
244 template<>
245 struct hash<map_location> {
246  std::size_t operator()(const map_location& l) const noexcept {
247  // The 2000 bias supposedly ensures that the correct x is recovered for negative y
248  // This implementation copied from the Lua location_set
249  return (l.wml_x()) * 16384 + (l.wml_y()) + 2000;
250  }
251 };
252 }
map_location loc
Definition: move.cpp:172
Variant for storing WML attributes.
A config object defines a single node in a WML file, with access to child nodes.
Definition: config.hpp:158
@ border
The border of the map.
const config * cfg
std::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.cpp:583
void get_adjacent_tiles(const map_location &a, utils::span< map_location, 6 > res)
Function which, given a location, will place all adjacent locations in res.
Definition: location.cpp:512
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,.....
Definition: location.cpp:492
std::ostream & operator<<(std::ostream &s, const map_location &l)
Dumps a position on a stream, for debug purposes.
Definition: location.cpp:36
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:480
bool tiles_adjacent(const map_location &a, const map_location &b)
Function which tells if two locations are adjacent.
Definition: location.cpp:540
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,...
Definition: location.cpp:436
Represents a map location in cubic hexagonal coordinates.
Definition: location.hpp:34
Encapsulates the map of the game.
Definition: location.hpp:46
map_location & vector_sum_assign(const map_location &a)
Definition: location.hpp:143
map_location & vector_difference_assign(const map_location &a)
Definition: location.hpp:151
static map_location from_cubic(cubic_location h)
Definition: location.hpp:173
bool valid(const int parWidth, const int parHeight) const
Definition: location.hpp:113
static std::string write_direction(direction dir)
Definition: location.cpp:154
map_location vector_negation() const
Definition: location.hpp:133
map_location(int x, int y)
Definition: location.hpp:92
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:138
void add(int x_diff, int y_diff)
Definition: location.hpp:192
friend std::size_t hash_value(const map_location &a)
Definition: location.cpp:73
static std::vector< direction > all_directions()
Definition: location.cpp:61
void set_wml_y(int v)
Definition: location.hpp:190
bool operator==(const map_location &a) const
Definition: location.hpp:123
map_location vector_sum(const map_location &a) const
Definition: location.hpp:138
map_location get_direction(direction dir, unsigned int n=1u) const
Definition: location.cpp:362
map_location rotate_right_around_center(const map_location &center, int k) const
Definition: location.cpp:299
bool valid() const
Definition: location.hpp:111
int wml_y() const
Definition: location.hpp:187
std::vector< map_location > get_ring(int min, int max) const
Definition: location.cpp:401
bool operator!=(const map_location &a) const
Definition: location.hpp:124
static constexpr direction get_opposite_direction(direction d)
Definition: location.hpp:76
void set_wml_x(int v)
Definition: location.hpp:189
bool operator<(const map_location &a) const
Definition: location.hpp:122
cubic_location to_cubic() const
Definition: location.hpp:167
direction
Valid directions which can be moved in our hexagonal world.
Definition: location.hpp:48
bool valid(const int parWidth, const int parHeight, const int border) const
Definition: location.hpp:116
direction get_relative_dir(const map_location &loc, map_location::RELATIVE_DIR_MODE mode) const
Definition: location.cpp:238
static const map_location & null_location()
Definition: location.hpp:103
int wml_x() const
Definition: location.hpp:186
map_location(int x, int y, wml_loc)
Definition: location.hpp:93
static direction parse_direction(const std::string &str)
Definition: location.cpp:79
map_location get_direction(direction dir, signed int n) const
Definition: location.hpp:158
static std::string write_translated_direction(direction dir)
Definition: location.cpp:174
void write(config &cfg) const
Definition: location.cpp:223
bool matches_range(const std::string &xloc, const std::string &yloc) const
Definition: location.cpp:320
map_location plus(int x_diff, int y_diff) const
Definition: location.hpp:193
int do_compare(const map_location &a) const
three-way comparator
Definition: location.hpp:127
static constexpr direction rotate_direction(direction d, int steps=1)
Returns the direction one would face having taken steps clockwise around an undefined center.
Definition: location.hpp:61
static const map_location & ZERO()
Definition: location.hpp:97
std::size_t operator()(const map_location &l) const noexcept
Definition: location.hpp:246
static map_location::direction n
static map_location::direction s
#define d
#define h
#define b