FIFE  be64c707dea6b3250bd4355bf5c825d25920087d
hexgrid.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005-2019 by the FIFE team *
3  * http://www.fifengine.net *
4  * This file is part of FIFE. *
5  * *
6  * FIFE is free software; you can redistribute it and/or *
7  * modify it under the terms of the GNU Lesser General Public *
8  * License as published by the Free Software Foundation; either *
9  * version 2.1 of the License, or (at your option) any later version. *
10  * *
11  * This library is distributed in the hope that it will be useful, *
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
14  * Lesser General Public License for more details. *
15  * *
16  * You should have received a copy of the GNU Lesser General Public *
17  * License along with this library; if not, write to the *
18  * Free Software Foundation, Inc., *
19  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA *
20  ***************************************************************************/
21 
22 // Standard C++ library includes
23 #include <cassert>
24 
25 // 3rd party library includes
26 
27 // FIFE includes
28 // These includes are split up in two parts, separated by one empty line
29 // First block: files included from the FIFE root src directory
30 // Second block: files included from the same folder
31 #include "util/math/fife_math.h"
32 #include "util/log/logger.h"
33 
34 #include "hexgrid.h"
35 
36 namespace FIFE {
37  static Logger _log(LM_HEXGRID);
38 
39  static const double HEX_WIDTH = 1;
40  static const double HEX_TO_EDGE = HEX_WIDTH / 2;
41  static const double HEX_TO_CORNER = 0.5 / Mathd::Cos(Mathd::pi() / 6);
42  static const double HEX_EDGE_HALF = HEX_TO_CORNER * Mathd::Sin(Mathd::pi() / 6);
43  static const double VERTICAL_MULTIP = Mathd::Sqrt(HEX_WIDTH*HEX_WIDTH - HEX_TO_EDGE*HEX_TO_EDGE);
44  static const double VERTICAL_MULTIP_INV = 1 / VERTICAL_MULTIP;
45  static const double HEX_EDGE_GRADIENT = 1 / Mathd::Sqrt(3);
46 
47  HexGrid::HexGrid(bool axial):
48  CellGrid(),
49  m_axial(axial) {
50  FL_DBG(_log, "Constructing new HexGrid");
51  FL_DBG(_log, LMsg("HEX_WIDTH ") << HEX_WIDTH);
52  FL_DBG(_log, LMsg("HEX_TO_EDGE ") << HEX_TO_EDGE);
53  FL_DBG(_log, LMsg("HEX_TO_CORNER ") << HEX_TO_CORNER);
54  FL_DBG(_log, LMsg("HEX_EDGE_HALF ") << HEX_EDGE_HALF);
55  FL_DBG(_log, LMsg("VERTICAL_MULTIP ") << VERTICAL_MULTIP);
56  }
57 
59  HexGrid* nGrid = new HexGrid(m_axial);
60  nGrid->setRotation(m_rotation);
61  nGrid->setXScale(m_xscale);
62  nGrid->setYScale(m_yscale);
63  nGrid->setXShift(m_xshift);
64  nGrid->setYShift(m_yshift);
65  nGrid->setZShift(m_zshift);
67 
68  return nGrid;
69  }
70 
72  }
73 
74  bool HexGrid::isAccessible(const ModelCoordinate& curpos, const ModelCoordinate& target) {
75  int32_t x = target.x-curpos.x;
76  int32_t y = target.y-curpos.y;
77 
78  if (ABS(x) <= 1 && ABS(y) <= 1) {
79  if (m_axial) {
80  if (y == 0 || x == 0 || x == -y)
81  return true;
82  } else {
83  if (y == 0) {
84  return true;
85  } else if (curpos.y & 1) {
86  if (x >= 0) return true;
87  } else if (x <= 0) return true;
88  }
89  }
90  return false;
91  }
92 
93  double HexGrid::getAdjacentCost(const ModelCoordinate& curpos, const ModelCoordinate& target) {
94  if (curpos == target) {
95  return 0.0;
96  }
97  return 1.0;
98  }
99 
100  double HexGrid::getHeuristicCost(const ModelCoordinate& curpos, const ModelCoordinate& target) {
101  return static_cast<double>(ABS(target.x - curpos.x) + ABS(target.y - curpos.y));
102  }
103 
104  const std::string& HexGrid::getType() const {
105  if (m_axial) {
106  static std::string type("hexagonal_axial");
107  return type;
108  } else {
109  static std::string type("hexagonal");
110  return type;
111  }
112  }
113 
114  const std::string& HexGrid::getName() const {
115  if (m_axial) {
116  static std::string hexGrid("Hex Grid (Axial)");
117  return hexGrid;
118  } else {
119  static std::string hexGrid("Hex Grid");
120  return hexGrid;
121  }
122  }
123 
124  double HexGrid::getXZigzagOffset(double y) {
125  if (m_axial) {
126  return HEX_TO_EDGE * y;
127  } else {
128  // each uneven row has shifted coordinate of 0.5 horizontally
129  // shift has to be gradual on vertical axis
130  double ay = ABS(y);
131  int32_t i_layer_y = static_cast<int32_t>(ay);
132  double offset = ay - static_cast<double>(i_layer_y);
133  if ((i_layer_y % 2) == 1) {
134  offset = 1 - offset;
135  }
136  return HEX_TO_EDGE * offset;
137  }
138  }
139 
141  ExactModelCoordinate tranformed_coords(layer_coords);
142  tranformed_coords.x += getXZigzagOffset(layer_coords.y);
143  tranformed_coords.y *= VERTICAL_MULTIP;
144  ExactModelCoordinate result = m_matrix * tranformed_coords;
145  FL_DBG(_log, LMsg("layercoords ") << layer_coords << " converted to map: " << result);
146  return result;
147  }
148 
150  ExactModelCoordinate layer_coords = m_inverse_matrix * map_coord;
151  layer_coords.y /= VERTICAL_MULTIP;
152  layer_coords.x -= getXZigzagOffset(layer_coords.y);
153  FL_DBG(_log, LMsg("mapcoords ") << map_coord << " converted to layer: " << layer_coords);
154  return layer_coords;
155  }
156 
158  FL_DBG(_log, LMsg("==============\nConverting map coords ") << map_coord << " to int32_t layer coords...");
159  ExactModelCoordinate elc = m_inverse_matrix * map_coord;
160  elc.y *= VERTICAL_MULTIP_INV;
161  return toLayerCoordinatesHelper(elc);
162  }
163 
165  ExactModelCoordinate elc = exact_layer_coords;
166  elc.x += getXZigzagOffset(elc.y);
167  return toLayerCoordinatesHelper(elc);
168  }
169 
171  // this helper method takes exact layer coordinates with zigzag removed
172  // and converts them to layer coordinates
173  ExactModelCoordinate elc = coords;
174 
175  // approximate conversion using squares instead of hexes
176  if( static_cast<int32_t>(round(elc.y)) & 1 )
177  elc.x -= 0.5;
178  ExactModelCoordinate lc = ExactModelCoordinate(round(elc.x), round(elc.y), round(elc.z));
179 
180  int32_t x = static_cast<int32_t>(lc.x);
181  int32_t y = static_cast<int32_t>(lc.y);
182  int32_t z = static_cast<int32_t>(lc.z);
183 
184  // distance of given point from our approximation
185  // If y uneven dx=-dx and dy=-dy
186  double dx,dy;
187  if (y & 1) {
188  dx = elc.x - lc.x;
189  dy = elc.y - lc.y;
190  } else {
191  dx = lc.x - elc.x;
192  dy = lc.y - elc.y;
193  }
194 
195  // adjustment for cases where our approximation lies beyond the hex edge
196  if (ABS(dy) > ((HEX_TO_CORNER - HEX_EDGE_GRADIENT * ABS(dx)) * VERTICAL_MULTIP_INV)) {
197  int8_t ddx, ddy;
198  if (dx>0) ddx = -1;
199  else ddx = 0;
200 
201  if (dy>0) ddy = -1;
202  else ddy = 1;
203 
204  if (y & 1) {
205  ddx = -ddx;
206  ddy = -ddy;
207  }
208 
209  x += ddx;
210  y += ddy;
211  }
212 
213  if (m_axial) {
214  if (y >= 0)
215  x -= y / 2;
216  else
217  x -= (y - 1) / 2;
218  }
219 
220  return ModelCoordinate(x,y,z);
221  }
222 
223  void HexGrid::getVertices(std::vector<ExactModelCoordinate>& vtx, const ModelCoordinate& cell) {
224  FL_DBG(_log, LMsg("===============\ngetting vertices for ") << cell);
225  vtx.clear();
226  double x = static_cast<double>(cell.x);
227  double y = static_cast<double>(cell.y);
228  double horiz_shift;
229  if (m_axial) {
230  horiz_shift = HEX_TO_EDGE * cell.y;
231  } else {
232  horiz_shift = 0;
233  if (cell.y % 2 != 0) {
234  horiz_shift = HEX_TO_EDGE;
235  FL_DBG(_log, "on uneven row");
236  }
237  }
238  double tx, ty;
239 
240  #define ADD_PT(_x, _y) vtx.push_back(ExactModelCoordinate(_x, _y));
241  // FL_DBG(_log, LMsg("Added point ") << _x << ", " << _y)
242  ty = y - VERTICAL_MULTIP_INV * HEX_EDGE_HALF;
243  tx = x - HEX_TO_EDGE - getXZigzagOffset(ty) + horiz_shift;
244  ADD_PT(tx, ty);
245 
246  ty = y - VERTICAL_MULTIP_INV * HEX_TO_CORNER;
247  tx = x - getXZigzagOffset(ty) + horiz_shift;
248  ADD_PT(tx, ty);
249 
250  ty = y - VERTICAL_MULTIP_INV * HEX_EDGE_HALF;
251  tx = x + HEX_TO_EDGE - getXZigzagOffset(ty) + horiz_shift;
252  ADD_PT(tx, ty);
253 
254  ty = y + VERTICAL_MULTIP_INV * HEX_EDGE_HALF;
255  tx = x + HEX_TO_EDGE - getXZigzagOffset(ty) + horiz_shift;
256  ADD_PT(tx, ty);
257 
258  ty = y + VERTICAL_MULTIP_INV * HEX_TO_CORNER;
259  tx = x - getXZigzagOffset(ty) + horiz_shift;
260  ADD_PT(tx, ty);
261 
262  ty = y + VERTICAL_MULTIP_INV * HEX_EDGE_HALF;
263  tx = x - HEX_TO_EDGE - getXZigzagOffset(ty) + horiz_shift;
264  ADD_PT(tx, ty);
265  }
266 
267  std::vector<ModelCoordinate> HexGrid::toMultiCoordinates(const ModelCoordinate& position, const std::vector<ModelCoordinate>& orig, bool reverse) {
268  std::vector<ModelCoordinate> coords;
269  std::vector<ModelCoordinate>::const_iterator it = orig.begin();
270  if (reverse) {
271  for (; it != orig.end(); ++it) {
272  ModelCoordinate mc = position;
273  if (mc.y % 2 != 0) {
274  mc.x -= (*it).x;
275  mc.y -= (*it).y;
276  if (mc.y % 2 == 0) {
277  mc.x -= 1;
278  }
279  } else {
280  mc.x -= (*it).x;
281  mc.y -= (*it).y;
282  }
283  coords.push_back(mc);
284  }
285  } else {
286  for (; it != orig.end(); ++it) {
287  ModelCoordinate mc = position;
288  if (mc.y % 2 != 0) {
289  mc.x += (*it).x;
290  mc.y += (*it).y;
291  if (mc.y % 2 == 0) {
292  mc.x += 1;
293  }
294  } else {
295  mc.x += (*it).x;
296  mc.y += (*it).y;
297  }
298  coords.push_back(mc);
299  }
300  }
301  return coords;
302  }
303 
304  std::vector<ModelCoordinate> HexGrid::getCoordinatesInLine(const ModelCoordinate& start, const ModelCoordinate& end) {
305  std::vector<ModelCoordinate> coords;
306  int32_t doubleDeltaX = 2*(end.x - start.x) + ABS(end.y % 2) - ABS(start.y % 2);
307  int32_t deltaX = (end.x - start.x) + ABS(end.y % 2) - ABS(start.y % 2);
308  int32_t deltaY = end.y - start.y;
309 
310  //int8_t signX = (deltaX >= 0) ? 1 : -1;
311  //int8_t signY = (deltaY >= 0) ? 1 : -1;
312  int8_t signX = (start.x < end.x) ? 1 : -1;
313  int8_t signY = (start.y < end.y) ? 1 : -1;
314  ModelCoordinate current(start);
315  coords.push_back(current);
316  int32_t err = 0;
317  if (ABS(deltaY) < ABS(doubleDeltaX)) {
318  int32_t errX = 3 * ABS(doubleDeltaX);
319  int32_t errY = 3 * ABS(deltaY);
320  while (current.x != end.x || current.y != end.y) {
321  err += errY;
322  if (err > ABS(doubleDeltaX)) {
323  if (signX == -1) {
324  if (signY == -1) {
325  // down left
326  if (current.y % 2 == 0 && current.x != end.x) {
327  current.x -= 1;
328  }
329  current.y -= 1;
330  } else {
331  // up left
332  if (current.y % 2 == 0 && current.x != end.x) {
333  current.x -= 1;
334  }
335  current.y += 1;
336  }
337  } else {
338  if (signY == -1) {
339  // down right
340  if (current.y % 2 != 0 && current.x != end.x) {
341  current.x += 1;
342  }
343  current.y -= 1;
344  } else {
345  // up right
346  if (current.y % 2 != 0 && current.x != end.x) {
347  current.x += 1;
348  }
349  current.y += 1;
350  }
351  }
352  err -= errX;
353  } else {
354  if (signX == -1) {
355  // left
356  current.x -= 1;
357  } else {
358  // right
359  current.x += 1;
360  }
361  err += errY;
362  }
363  coords.push_back(current);
364  }
365  } else {
366  int32_t errX = ABS(doubleDeltaX);
367  int32_t errY = ABS(deltaY);
368  while (current.x != end.x || current.y != end.y) {
369  err += errX;
370  if (err > 0) {
371  if (signX == -1) {
372  if (signY == -1) {
373  // down left
374  if (current.y % 2 == 0 && current.x != end.x) {
375  current.x -= 1;
376  }
377  current.y -= 1;
378  } else {
379  // up left
380  if (current.y % 2 == 0 && current.x != end.x) {
381  current.x -= 1;
382  }
383  current.y += 1;
384  }
385  } else if (signX == 1) {
386  if (signY == -1) {
387  // down right
388  if (current.y % 2 != 0 && current.x != end.x) {
389  current.x += 1;
390  }
391  current.y -= 1;
392  } else {
393  // up right
394  if (current.y % 2 != 0 && current.x != end.x) {
395  current.x += 1;
396  }
397  current.y += 1;
398  }
399  }
400  err -= errY;
401  } else {
402  signX = -signX;
403  if (signX == -1) {
404  if (signY == -1) {
405  // down left
406  if (current.y % 2 == 0 && current.x != end.x) {
407  current.x -= 1;
408  }
409  current.y -= 1;
410  } else {
411  // up left
412  if (current.y % 2 == 0 && current.x != end.x) {
413  current.x -= 1;
414  }
415  current.y += 1;
416  }
417  } else if (signX == 1) {
418  if (signY == -1) {
419  // down right
420  if (current.y % 2 != 0 && current.x != end.x) {
421  current.x += 1;
422  }
423  current.y -= 1;
424  } else {
425  // up right
426  if (current.y % 2 != 0 && current.x != end.x) {
427  current.x += 1;
428  }
429  current.y += 1;
430  }
431  }
432  signX = -signX;
433  err += errY;
434  }
435  coords.push_back(current);
436  }
437  }
438  return coords;
439  }
440 }
double m_xscale
Definition: cellgrid.h:255
virtual ~HexGrid()
Definition: hexgrid.cpp:71
static const double VERTICAL_MULTIP_INV
Definition: hexgrid.cpp:44
static T Cos(T _val)
Definition: fife_math.h:217
const std::string & getType() const
Type of cellgrid.
Definition: hexgrid.cpp:104
#define ABS(x)
Definition: fife_math.h:41
static T Sqrt(T _val)
Definition: fife_math.h:277
double getXZigzagOffset(double y)
Definition: hexgrid.cpp:124
Helper class to create log strings out from separate parts Usage: LMsg("some text") << variable << "...
Definition: logger.h:82
void setZShift(const double zshift)
Set the cellgrid z shift.
Definition: cellgrid.h:168
double m_yshift
Definition: cellgrid.h:253
#define ADD_PT(_x, _y)
double getAdjacentCost(const ModelCoordinate &curpos, const ModelCoordinate &target)
Returns distance const from curpos to target point only cells adjacent to curpos are considered in th...
Definition: hexgrid.cpp:93
ExactModelCoordinate toExactLayerCoordinates(const ExactModelCoordinate &map_coord)
Transforms given point from map coordinates to layer coordinates.
Definition: hexgrid.cpp:149
std::vector< ModelCoordinate > toMultiCoordinates(const ModelCoordinate &position, const std::vector< ModelCoordinate > &orig, bool reverse)
Returns point vector with coordinates for a multi object.
Definition: hexgrid.cpp:267
static const double HEX_EDGE_GRADIENT
Definition: hexgrid.cpp:45
static Logger _log(LM_AUDIO)
std::vector< ModelCoordinate > getCoordinatesInLine(const ModelCoordinate &start, const ModelCoordinate &end)
Returns point vector with coordinates for a line from start to end.
Definition: hexgrid.cpp:304
DoubleMatrix m_inverse_matrix
Definition: cellgrid.h:251
void setXShift(const double &xshift)
Set the cellgrid x shift.
Definition: cellgrid.h:142
HexGrid(bool axial=false)
Definition: hexgrid.cpp:47
void setYScale(const double scale)
Set the cellgrid y-scaling.
Definition: cellgrid.h:189
ExactModelCoordinate toMapCoordinates(const ExactModelCoordinate &layer_coords)
Transforms given point from layer coordinates to map coordinates.
Definition: hexgrid.cpp:140
void setXScale(const double scale)
Set the cellgrid x-scaling.
Definition: cellgrid.h:181
bool m_axial
Definition: hexgrid.h:62
static const double HEX_TO_EDGE
Definition: hexgrid.cpp:40
static const double HEX_WIDTH
Definition: hexgrid.cpp:39
void setYShift(const double yshift)
Set the cellgrid y shift.
Definition: cellgrid.h:155
const std::string & getName() const
Name of the cellgrid (DEPRECATED? -jwt)
Definition: hexgrid.cpp:114
Point3D ModelCoordinate
Definition: modelcoords.h:38
static T Sin(T _val)
Definition: fife_math.h:267
bool m_allow_diagonals
Definition: cellgrid.h:259
CellGrid * clone()
Returns clone of this cellgrid.
Definition: hexgrid.cpp:58
double m_rotation
Definition: cellgrid.h:258
DoubleMatrix m_matrix
Definition: cellgrid.h:250
double getHeuristicCost(const ModelCoordinate &curpos, const ModelCoordinate &target)
Returns distance const from curpos to target point.
Definition: hexgrid.cpp:100
void setAllowDiagonals(const bool allow_diagonals)
Set whether diagonal cell access is allowed.
Definition: cellgrid.h:233
ModelCoordinate toLayerCoordinatesFromExactLayerCoordinates(const ExactModelCoordinate &exact_layer_coords)
Transforms given point from exact layer coordinates to cell precision layer coordinates.
Definition: hexgrid.cpp:164
DoublePoint3D ExactModelCoordinate
Definition: modelcoords.h:37
static const double HEX_TO_CORNER
Definition: hexgrid.cpp:41
double m_zshift
Definition: cellgrid.h:254
void getVertices(std::vector< ExactModelCoordinate > &vtx, const ModelCoordinate &cell)
Fills given point vector with vertices from selected cell.
Definition: hexgrid.cpp:223
A 3D Point.
Definition: point.h:205
double m_yscale
Definition: cellgrid.h:256
static num_type pi()
Definition: fife_math.h:134
void setRotation(const double rotation)
Set the cellgrid rotation.
Definition: cellgrid.h:220
static const double VERTICAL_MULTIP
Definition: hexgrid.cpp:43
double m_xshift
Definition: cellgrid.h:252
static const double HEX_EDGE_HALF
Definition: hexgrid.cpp:42
ModelCoordinate toLayerCoordinates(const ExactModelCoordinate &map_coord)
Transforms given point from map coordinates to layer coordinates.
Definition: hexgrid.cpp:157
bool isAccessible(const ModelCoordinate &curpos, const ModelCoordinate &target)
Tells if given target point is accessible from curpos only cells adjacent to curpos are considered in...
Definition: hexgrid.cpp:74
ModelCoordinate toLayerCoordinatesHelper(const ExactModelCoordinate &coords)
Definition: hexgrid.cpp:170
#define FL_DBG(logger, msg)
Definition: logger.h:70