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