The Battle for Wesnoth  1.15.2+dev
location.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  * Routines related to game-maps, terrain, locations, directions. etc.
18  */
19 
20 #include <cassert>
21 
22 #include "map/location.hpp"
23 
24 #include "config.hpp"
25 #include "formula/string_utils.hpp"
26 #include "gettext.hpp"
27 #include "log.hpp"
29 #include "utils/math.hpp"
30 
31 #include <boost/functional/hash_fwd.hpp>
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 << "\n";
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 << "\n";
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 << "\n";
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 /* Changed this when I inlined it to eliminate util.hpp dependency.
494  res->x = a.x;
495  res->y = a.y-1;
496  ++res;
497  res->x = a.x+1;
498  res->y = a.y - (is_even(a.x) ? 1:0);
499  ++res;
500  res->x = a.x+1;
501  res->y = a.y + (is_odd(a.x) ? 1:0);
502  ++res;
503  res->x = a.x;
504  res->y = a.y+1;
505  ++res;
506  res->x = a.x-1;
507  res->y = a.y + (is_odd(a.x) ? 1:0);
508  ++res;
509  res->x = a.x-1;
510  res->y = a.y - (is_even(a.x) ? 1:0);
511 */
512 }
513 
515 {
516  // Two tiles are adjacent:
517  // if y is different by 1, and x by 0,
518  // or if x is different by 1 and y by 0,
519  // or if x and y are each different by 1,
520  // and the x value of the hex with the greater y value is even.
521 
522  switch (a.y - b.y) {
523  case 1 :
524  switch (a.x - b.x) {
525  case 1:
526  case -1:
527  return (a.x & 1) == 0;
528  case 0:
529  return true;
530  default:
531  return false;
532  }
533  case -1 :
534  switch (a.x - b.x) {
535  case 1:
536  case -1:
537  return (b.x & 1) == 0;
538  case 0:
539  return true;
540  default:
541  return false;
542  }
543  case 0 :
544  return ((a.x - b.x) == 1) || ((a.x - b.x) == - 1);
545  default:
546  return false;
547  }
548 
549  /*
550  const int xdiff = std::abs(a.x - b.x);
551  const int ydiff = std::abs(a.y - b.y);
552  return (ydiff == 1 && a.x == b.x) || (xdiff == 1 && a.y == b.y) ||
553  (xdiff == 1 && ydiff == 1 && (a.y > b.y ? is_even(a.x) : is_even(b.x)));
554  */
555 }
556 
557 std::size_t distance_between(const map_location& a, const map_location& b)
558 {
559  const std::size_t hdistance = std::abs(a.x - b.x);
560 
561  const std::size_t vpenalty = ( (((a.x & 1)==0) && ((b.x & 1)==1) && (a.y < b.y))
562  || (((b.x & 1)==0) && ((a.x & 1)==1) && (b.y < a.y)) ) ? 1 : 0;
563 
564 /* Don't want to include util.hpp in this header
565  const std::size_t vpenalty = ( (is_even(a.x) && is_odd(b.x) && (a.y < b.y))
566  || (is_even(b.x) && is_odd(a.x) && (b.y < a.y)) ) ? 1 : 0;
567 */
568  // For any non-negative integer i, i - i/2 - i%2 == i/2
569  // previously returned (hdistance + vdistance - vsavings)
570  // = hdistance + vdistance - minimum(vdistance,hdistance/2+hdistance%2)
571  // = maximum(hdistance, vdistance+hdistance-hdistance/2-hdistance%2)
572  // = maximum(hdistance,std::abs(a.y-b.y)+vpenalty+hdistance/2)
573 
574  return std::max<int>(hdistance, std::abs(a.y - b.y) + vpenalty + hdistance/2);
575 }
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
static DIRECTION parse_direction(const std::string &str)
Definition: location.cpp:65
map_location & vector_difference_assign(const map_location &a)
Definition: location.hpp:133
bool is_odd(T num)
Definition: math.hpp:34
static std::string write_translated_direction(DIRECTION dir)
Definition: location.cpp:161
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:474
DIRECTION get_relative_dir(const map_location &loc, map_location::RELATIVE_DIR_MODE mode) const
Definition: location.cpp:226
std::pair< int, int > get_in_basis_N_NE() const
Definition: location.cpp:287
static bool is_vertically_higher_than(const map_location &m1, const map_location &m2)
Definition: location.cpp:217
#define a
int wml_x() const
Definition: location.hpp:157
static lg::log_domain log_config("config")
#define h
static DIRECTION rotate_right(DIRECTION d, unsigned int k=1u)
Definition: location.hpp:49
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
Definitions for the interface to Wesnoth Markup Language (WML).
std::vector< std::string > split(const std::string &val, const char c, const int flags)
Splits a (comma-)separated string into a vector of pieces.
map_location get_direction(DIRECTION dir, unsigned int n=1u) const
Definition: location.cpp:359
#define b
std::ostream & operator<<(std::ostream &s, const map_location &l)
Dumps a position on a stream, for debug purposes.
Definition: location.cpp:36
static UNUSEDNOWARN std::string _(const char *str)
Definition: gettext.hpp:91
int wml_y() const
Definition: location.hpp:158
bool is_even(T num)
Definition: math.hpp:31
map_location rotate_right_around_center(const map_location &center, int k) const
Definition: location.cpp:306
General math utility functions.
static const std::vector< DIRECTION > & default_dirs()
Default list of directions.
Definition: location.cpp:52
Encapsulates the map of the game.
Definition: location.hpp:42
bool tiles_adjacent(const map_location &a, const map_location &b)
Function which tells if two locations are adjacent.
Definition: location.cpp:514
std::size_t i
Definition: function.cpp:933
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:398
static map_location::DIRECTION s
DIRECTION
Valid directions which can be moved in our hexagonal world.
Definition: location.hpp:44
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:59
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:557
Standard logging facilities (interface).
static const map_location & null_location()
Definition: location.hpp:85
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:28
A config object defines a single node in a WML file, with access to child nodes.
Definition: config.hpp:68
static map_location::DIRECTION n
static std::string write_direction(DIRECTION dir)
Definition: location.cpp:140
static map_location read_locations_helper(const std::string &xi, const std::string &yi)
Definition: location.cpp:437
void write(config &cfg) const
Definition: location.cpp:211
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:454
friend std::size_t hash_value(const map_location &a)
Definition: location.cpp:59
#define ERR_CF
Definition: location.cpp:34