The Battle for Wesnoth  1.19.0-dev
location.cpp
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  * Routines related to game-maps, terrain, locations, directions. etc.
19  */
20 
21 #include <cassert>
22 
23 #include "map/location.hpp"
24 
25 #include "config.hpp"
26 #include "formula/string_utils.hpp"
27 #include "gettext.hpp"
28 #include "log.hpp"
30 #include "utils/math.hpp"
31 
32 
33 static lg::log_domain log_config("config");
34 #define ERR_CF LOG_STREAM(err, log_config)
35 
36 std::ostream &operator<<(std::ostream &s, const map_location& l) {
37  s << (l.wml_x()) << ',' << (l.wml_y());
38  return s;
39 }
40 std::ostream &operator<<(std::ostream &s, const std::vector<map_location>& v) {
41  std::vector<map_location>::const_iterator i = v.begin();
42  for(; i!= v.end(); ++i) {
43  s << "(" << *i << ") ";
44  }
45  return s;
46 }
47 
48 /**
49  * Default list of directions
50  *
51  **/
52 const std::vector<map_location::DIRECTION> & map_location::default_dirs() {
53  static const std::vector<map_location::DIRECTION> dirs {map_location::NORTH,
56  return dirs;
57 }
58 
59 std::size_t hash_value(const map_location& a){
60  std::hash<std::size_t> h;
61  return h( (static_cast<uint32_t>(a.x) << 16) ^ static_cast<uint32_t>(a.y) );
62 }
63 
64 
66 {
67  if(str.empty()) {
68  return NDIRECTIONS;
69  }
70 
71  // Syntax: [-] (n|ne|se|s|sw|nw) [:cw|:ccw]
72  // - means "take opposite direction" and has higher precedence
73  // :cw and :ccw mean "one step (counter-)clockwise"
74  // Parentheses can be used for grouping or to apply an operator more than once
75 
76  const std::size_t open = str.find_first_of('('), close = str.find_last_of(')');
77  if (open != std::string::npos && close != std::string::npos) {
78  std::string sub = str.substr(open + 1, close - open - 1);
80  sub = str;
81  sub.replace(open, close - open + 1, write_direction(dir));
82  return parse_direction(sub);
83  }
84 
85  const std::size_t start = str[0] == '-' ? 1 : 0;
86  const std::size_t end = str.find_first_of(':');
87  const std::string& main_dir = str.substr(start, end - start);
89 
90  if (main_dir == "n") {
91  dir = NORTH;
92  } else if (main_dir == "ne") {
93  dir = NORTH_EAST;
94  } else if (main_dir == "se") {
95  dir = SOUTH_EAST;
96  } else if (main_dir == "s") {
97  dir = SOUTH;
98  } else if (main_dir == "sw") {
99  dir = SOUTH_WEST;
100  } else if (main_dir == "nw") {
101  dir = NORTH_WEST;
102  } else {
103  return NDIRECTIONS;
104  }
105 
106  if (start == 1) {
107  dir = get_opposite_dir(dir);
108  }
109 
110  if (end != std::string::npos) {
111  const std::string rel_dir = str.substr(end + 1);
112  if (rel_dir == "cw") {
113  dir = rotate_right(dir, 1);
114  } else if (rel_dir == "ccw") {
115  dir = rotate_right(dir, -1);
116  } else {
117  return NDIRECTIONS;
118  }
119  }
120 
121  return dir;
122 }
123 
124 std::vector<map_location::DIRECTION> map_location::parse_directions(const std::string& str)
125 {
127  std::vector<map_location::DIRECTION> to_return;
128  std::vector<std::string> dir_strs = utils::split(str);
129  std::vector<std::string>::const_iterator i, i_end=dir_strs.end();
130  for(i = dir_strs.begin(); i != i_end; ++i) {
132  // Filter out any invalid directions
133  if(temp != NDIRECTIONS) {
134  to_return.push_back(temp);
135  }
136  }
137  return to_return;
138 }
139 
141 {
142  switch(dir) {
143  case NORTH:
144  return std::string("n");
145  case NORTH_EAST:
146  return std::string("ne");
147  case NORTH_WEST:
148  return std::string("nw");
149  case SOUTH:
150  return std::string("s");
151  case SOUTH_EAST:
152  return std::string("se");
153  case SOUTH_WEST:
154  return std::string("sw");
155  default:
156  return std::string();
157 
158  }
159 }
160 
162 {
163  switch(dir) {
164  case NORTH:
165  return _("North");
166  case NORTH_EAST:
167  return _("North East");
168  case NORTH_WEST:
169  return _("North West");
170  case SOUTH:
171  return _("South");
172  case SOUTH_EAST:
173  return _("South East");
174  case SOUTH_WEST:
175  return _("South West");
176  default:
177  return std::string();
178 
179  }
180 }
181 
182 map_location::map_location(const config& cfg, const variable_set *variables) :
183  x(-1000),
184  y(-1000)
185 {
186  std::string xs = cfg["x"], ys = cfg["y"];
187  if (variables)
188  {
189  xs = utils::interpolate_variables_into_string( xs, *variables);
190  ys = utils::interpolate_variables_into_string( ys, *variables);
191  }
192  // The co-ordinates in config files will be 1-based,
193  // while we want them as 0-based.
194  if(xs.empty() == false && xs != "recall") {
195  try {
196  x = std::stoi(xs) - 1;
197  } catch(const std::invalid_argument&) {
198  ERR_CF << "Invalid map coordinate: " << xs;
199  }
200  }
201 
202  if(ys.empty() == false && ys != "recall") {\
203  try {
204  y = std::stoi(ys) - 1;
205  } catch(const std::invalid_argument&) {
206  ERR_CF << "Invalid map coordinate: " << ys;
207  }
208  }
209 }
210 
211 void map_location::write(config& cfg) const
212 {
213  cfg["x"] = x + 1;
214  cfg["y"] = y + 1;
215 }
216 
217 static bool is_vertically_higher_than ( const map_location & m1, const map_location & m2 ) {
218  return (is_odd(m1.wml_x()) && is_even(m2.wml_x())) ? (m1.wml_y() <= m2.wml_y()) : (m1.wml_y() < m2.wml_y());
219 }
220 
222 {
224 }
225 
227 {
228  if (opt == map_location::DEFAULT) {
230 
231  int dx = loc.x - x;
232  int dy = loc.y - y;
233  if (loc.x%2==0 && x%2==1) dy--;
234 
235  if (dx==0 && dy==0) return NDIRECTIONS;
236 
237  int dist = std::abs(dx); // Distance from north-south line
238  int dist_diag_SW_NE = std::abs(dy + (dx + (dy>0?0:1) )/2); // Distance from diagonal line SW-NE
239  int dist_diag_SE_NW = std::abs(dy - (dx - (dy>0?0:1) )/2); // Distance from diagonal line SE-NW
240 
241  if (dy > 0) dir = SOUTH;
242  else dir = NORTH;
243 
244  if (dist_diag_SE_NW < dist) {
245  if (dx>0) dir = SOUTH_EAST;
246  else dir = NORTH_WEST;
247  dist = dist_diag_SE_NW;
248  }
249  if (dist_diag_SW_NE < dist) {
250  if (dx>0) dir = NORTH_EAST;
251  else dir = SOUTH_WEST;
252  }
253  return dir;
254  } else {
255  map_location temp(loc);
256 
257  if (is_vertically_higher_than(temp,*this)) {
258  temp = temp.rotate_right_around_center(*this,1u);
259  if (!is_vertically_higher_than(temp,*this)) {
261  }
262  temp = temp.rotate_right_around_center(*this,1u);
263  if (!is_vertically_higher_than(temp,*this)) {
264  return map_location::NORTH;
265  }
267  } else if (is_vertically_higher_than(*this,temp)) {
268  temp = temp.rotate_right_around_center(*this,1u);
269  if (!is_vertically_higher_than(*this,temp)) {
271  }
272  temp = temp.rotate_right_around_center(*this,1u);
273  if (!is_vertically_higher_than(*this,temp)) {
274  return map_location::SOUTH;
275  }
277  } else if (temp.x > x) {
279  } else if (temp.x < x) {
281  } else {
283  }
284  }
285 }
286 
287 std::pair<int,int> map_location::get_in_basis_N_NE() const {
288  map_location temp(*this);
289  std::pair<int, int> ret;
290 
291  ret.second = temp.x;
292  temp = temp.get_direction(SOUTH_WEST,temp.x);
293  assert(temp.x == 0);
294 
295  ret.first = -temp.y;
296  temp = temp.get_direction(NORTH,temp.y);
297  assert(temp.y == 0);
298 
299  temp = temp.get_direction(NORTH, ret.first);
300  temp = temp.get_direction(NORTH_EAST, ret.second);
301  assert(temp == *this);
302 
303  return ret;
304 }
305 
307  map_location temp(*this);
308  temp.vector_difference_assign(center);
309 
310  std::pair<int,int> coords = temp.get_in_basis_N_NE();
313 
314  return center.get_direction(d1, coords.first).get_direction(d2, coords.second);
315 }
316 
317 bool map_location::matches_range(const std::string& xloc, const std::string &yloc) const
318 {
319  const auto xlocs = utils::split(xloc);
320  const auto ylocs = utils::split(yloc);
321 
322  if(xlocs.size() == 0 && ylocs.size() == 0) {
323  return true;
324  }
325 
326  // Warn if both x and y were given, but they have different numbers of commas;
327  // the missing entries will be assumed to be 1-infinity.
328  //
329  // No warning if only x or only y was given, as matching only that coordinate seems sane.
330  if(xlocs.size() != ylocs.size() && xlocs.size() && ylocs.size()) {
331  ERR_CF << "Different size lists when pairing coordinate ranges: " << xloc << " vs " << yloc;
332  }
333 
334  std::size_t i = 0;
335  for(; i < xlocs.size() && i < ylocs.size(); ++i) {
336  const auto xr = utils::parse_range(xlocs[i]);
337  const auto yr = utils::parse_range(ylocs[i]);
338  // The ranges are 1-based, but the coordinates are 0-based. Thus the +1 s.
339  if(xr.first <= x+1 && x+1 <= xr.second
340  && yr.first <= y+1 && y+1 <= yr.second) {
341  return true;
342  }
343  }
344  for(; i < xlocs.size(); ++i) {
345  const auto xr = utils::parse_range(xlocs[i]);
346  if(xr.first <= x+1 && x+1 <= xr.second) {
347  return true;
348  }
349  }
350  for(; i < ylocs.size(); ++i) {
351  const auto yr = utils::parse_range(ylocs[i]);
352  if(yr.first <= y+1 && y+1 <= yr.second) {
353  return true;
354  }
355  }
356  return false;
357 }
358 
360 {
361  if (dir == map_location::NDIRECTIONS) {
363  }
364 
365  if (dir == NORTH) {
366  return map_location(x,y-n);
367  }
368 
369  if (dir == SOUTH) {
370  return map_location(x,y+n);
371  }
372 
373  int x_factor = (static_cast<unsigned int> (dir) <= 2u) ? 1 : -1; //whether we go east + or west -
374 
375  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
376  int y_factor = (tmp_y <= 2u) ? 1 : -1; //whether we go south + or north -
377 
378  if (tmp_y <= 2u) {
379  return map_location(x + x_factor * n, y + y_factor * ((n + ((x & 1) == 1)) / 2));
380  } else {
381  return map_location(x + x_factor * n, y + y_factor * ((n + ((x & 1) == 0)) / 2));
382  }
383 
384 /*
385  switch(dir) {
386  case NORTH: return map_location(x, y - n);
387  case SOUTH: return map_location(x, y + n);
388  case SOUTH_EAST: return map_location(x + n, y + (n+is_odd(x))/2 );
389  case SOUTH_WEST: return map_location(x - n, y + (n+is_odd(x))/2 );
390  case NORTH_EAST: return map_location(x + n, y - (n+is_even(x))/2 );
391  case NORTH_WEST: return map_location(x - n, y - (n+is_even(x))/2 );
392  default:
393  assert(false);
394  return map_location::null_location();
395  }*/
396 }
397 
398 void write_location_range(const std::set<map_location>& locs, config& cfg)
399 {
400  if(locs.empty()){
401  cfg["x"] = "";
402  cfg["y"] = "";
403  return;
404  }
405 
406  // need that operator< uses x first
407  assert(map_location(0,1) < map_location(1,0));
408 
409  std::stringstream x, y;
410  std::set<map_location>::const_iterator
411  i = locs.begin(),
412  first = i,
413  last = i;
414 
415  x << (i->wml_x());
416  y << (i->wml_y());
417 
418  for(++i; i != locs.end(); ++i) {
419  if(i->wml_x() != first->wml_x() || i->wml_y() - 1 != last->wml_y()) {
420  if (last->wml_y() != first->wml_y()) {
421  y << "-" << (last->wml_y());
422  }
423  x << "," << (i->wml_x());
424  y << "," << (i->wml_y());
425  first = i;
426  }
427  last = i;
428  }
429  // finish last range
430  if(last->wml_y() != first->wml_y())
431  y << "-" << (last->wml_y());
432 
433  cfg["x"] = x.str();
434  cfg["y"] = y.str();
435 }
436 
437 static map_location read_locations_helper(const std::string & xi, const std::string & yi)
438 {
439  return map_location(std::stoi(xi)-1, std::stoi(yi)-1);
440 }
441 
442 void read_locations(const config& cfg, std::vector<map_location>& locs)
443 {
444  const std::vector<std::string> xvals = utils::split(cfg["x"]);
445  const std::vector<std::string> yvals = utils::split(cfg["y"]);
446 
447  if (xvals.size() != yvals.size()) {
448  throw std::invalid_argument("Number of x and y coordinates do not match.");
449  }
450 
451  std::transform(xvals.begin(), xvals.end(), yvals.begin(), std::back_inserter(locs), &read_locations_helper);
452 }
453 
454 void write_locations(const std::vector<map_location>& locs, config& cfg)
455 {
456  std::stringstream x, y;
457 
458  std::vector<map_location>::const_iterator i = locs.begin(),
459  end = locs.end();
460 
461  for(; i != end; ++i) {
462  x << (i->wml_x());
463  y << (i->wml_y());
464  if(i+1 != end){
465  x << ",";
466  y << ",";
467  }
468  }
469 
470  cfg["x"] = x.str();
471  cfg["y"] = y.str();
472 }
473 
475 {
476  res->x = a.x;
477  res->y = a.y - 1;
478  ++res;
479  res->x = a.x + 1;
480  res->y = a.y - (((a.x & 1) == 0) ? 1 : 0);
481  ++res;
482  res->x = a.x + 1;
483  res->y = a.y + (((a.x & 1) == 1) ? 1 : 0);
484  ++res;
485  res->x = a.x;
486  res->y = a.y + 1;
487  ++res;
488  res->x = a.x - 1;
489  res->y = a.y + (((a.x & 1) == 1) ? 1 : 0);
490  ++res;
491  res->x = a.x - 1;
492  res->y = a.y - (((a.x & 1) == 0) ? 1 : 0);
493 }
494 
495 std::array<map_location, 6> get_adjacent_tiles(const map_location& center)
496 {
497  std::array<map_location, 6> res;
498  get_adjacent_tiles(center, res.data());
499  return res;
500 }
501 
503 {
504  // Two tiles are adjacent:
505  // if y is different by 1, and x by 0,
506  // or if x is different by 1 and y by 0,
507  // or if x and y are each different by 1,
508  // and the x value of the hex with the greater y value is even.
509 
510  switch (a.y - b.y) {
511  case 1 :
512  switch (a.x - b.x) {
513  case 1:
514  case -1:
515  return (a.x & 1) == 0;
516  case 0:
517  return true;
518  default:
519  return false;
520  }
521  case -1 :
522  switch (a.x - b.x) {
523  case 1:
524  case -1:
525  return (b.x & 1) == 0;
526  case 0:
527  return true;
528  default:
529  return false;
530  }
531  case 0 :
532  return ((a.x - b.x) == 1) || ((a.x - b.x) == - 1);
533  default:
534  return false;
535  }
536 
537  /*
538  const int xdiff = std::abs(a.x - b.x);
539  const int ydiff = std::abs(a.y - b.y);
540  return (ydiff == 1 && a.x == b.x) || (xdiff == 1 && a.y == b.y) ||
541  (xdiff == 1 && ydiff == 1 && (a.y > b.y ? is_even(a.x) : is_even(b.x)));
542  */
543 }
544 
545 std::size_t distance_between(const map_location& a, const map_location& b)
546 {
547  const std::size_t hdistance = std::abs(a.x - b.x);
548 
549  const std::size_t vpenalty = ( (((a.x & 1)==0) && ((b.x & 1)==1) && (a.y < b.y))
550  || (((b.x & 1)==0) && ((a.x & 1)==1) && (b.y < a.y)) ) ? 1 : 0;
551 
552 /* Don't want to include util.hpp in this header
553  const std::size_t vpenalty = ( (is_even(a.x) && is_odd(b.x) && (a.y < b.y))
554  || (is_even(b.x) && is_odd(a.x) && (b.y < a.y)) ) ? 1 : 0;
555 */
556  // For any non-negative integer i, i - i/2 - i%2 == i/2
557  // previously returned (hdistance + vdistance - vsavings)
558  // = hdistance + vdistance - minimum(vdistance,hdistance/2+hdistance%2)
559  // = maximum(hdistance, vdistance+hdistance-hdistance/2-hdistance%2)
560  // = maximum(hdistance,std::abs(a.y-b.y)+vpenalty+hdistance/2)
561 
562  return std::max<int>(hdistance, std::abs(a.y - b.y) + vpenalty + hdistance/2);
563 }
A config object defines a single node in a WML file, with access to child nodes.
Definition: config.hpp:159
std::size_t i
Definition: function.cpp:968
static std::string _(const char *str)
Definition: gettext.hpp:93
std::size_t hash_value(const map_location &a)
Definition: location.cpp:59
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.cpp:474
static bool is_vertically_higher_than(const map_location &m1, const map_location &m2)
Definition: location.cpp:217
static map_location read_locations_helper(const std::string &xi, const std::string &yi)
Definition: location.cpp:437
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:545
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:454
std::ostream & operator<<(std::ostream &s, const map_location &l)
Dumps a position on a stream, for debug purposes.
Definition: location.cpp:36
#define ERR_CF
Definition: location.cpp:34
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:442
bool tiles_adjacent(const map_location &a, const map_location &b)
Function which tells if two locations are adjacent.
Definition: location.cpp:502
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:398
static lg::log_domain log_config("config")
Standard logging facilities (interface).
General math utility functions.
constexpr bool is_even(T num)
Definition: math.hpp:33
constexpr bool is_odd(T num)
Definition: math.hpp:36
EXIT_STATUS start(bool clear_id, const std::string &filename, bool take_screenshot, const std::string &screenshot_filename)
Main interface for launching the editor from the title screen.
std::string interpolate_variables_into_string(const std::string &str, const string_map *const symbols)
Function which will interpolate variables, starting with '$' in the string 'str' with the equivalent ...
std::pair< int, int > parse_range(const std::string &str)
Recognises the following patterns, and returns a {min, max} pair.
std::vector< std::string > split(const config_attribute_value &val)
Encapsulates the map of the game.
Definition: location.hpp:38
map_location & vector_difference_assign(const map_location &a)
Definition: location.hpp:129
static DIRECTION parse_direction(const std::string &str)
Definition: location.cpp:65
static const std::vector< DIRECTION > & default_dirs()
Default list of directions.
Definition: location.cpp:52
std::pair< int, int > get_in_basis_N_NE() const
Definition: location.cpp:287
DIRECTION
Valid directions which can be moved in our hexagonal world.
Definition: location.hpp:40
map_location get_direction(DIRECTION dir, unsigned int n=1u) const
Definition: location.cpp:359
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:124
DIRECTION get_relative_dir(const map_location &loc, map_location::RELATIVE_DIR_MODE mode) const
Definition: location.cpp:226
map_location rotate_right_around_center(const map_location &center, int k) const
Definition: location.cpp:306
int wml_y() const
Definition: location.hpp:154
static DIRECTION rotate_right(DIRECTION d, unsigned int k=1u)
Definition: location.hpp:45
static const map_location & null_location()
Definition: location.hpp:81
int wml_x() const
Definition: location.hpp:153
static std::string write_translated_direction(DIRECTION dir)
Definition: location.cpp:161
void write(config &cfg) const
Definition: location.cpp:211
bool matches_range(const std::string &xloc, const std::string &yloc) const
Definition: location.cpp:317
static DIRECTION get_opposite_dir(DIRECTION d)
Definition: location.hpp:55
static std::string write_direction(DIRECTION dir)
Definition: location.cpp:140
static map_location::DIRECTION n
static map_location::DIRECTION s
#define h
#define a
#define b