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