FIFE  2008.0
 All Classes Namespaces Functions Variables Enumerations Enumerator Pages
hexgrid.cpp
1 /***************************************************************************
2  * Copyright (C) 2005-2008 by the FIFE team *
3  * http://www.fifengine.de *
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 
46  HexGrid::HexGrid(bool allow_diagonals): CellGrid(allow_diagonals) {
47  FL_DBG(_log, "Constructing new HexGrid");
48  FL_DBG(_log, LMsg("HEX_WIDTH ") << HEX_WIDTH);
49  FL_DBG(_log, LMsg("HEX_TO_EDGE ") << HEX_TO_EDGE);
50  FL_DBG(_log, LMsg("HEX_TO_CORNER ") << HEX_TO_CORNER);
51  FL_DBG(_log, LMsg("HEX_EDGE_HALF ") << HEX_EDGE_HALF);
52  FL_DBG(_log, LMsg("VERTICAL_MULTIP ") << VERTICAL_MULTIP);
53  }
54 
55  CellGrid* HexGrid::clone() {
56  HexGrid* nGrid = new HexGrid(m_allow_diagonals);
57  nGrid->setRotation(m_rotation);
58  nGrid->setXScale(m_xscale);
59  nGrid->setYScale(m_yscale);
60  nGrid->setXShift(m_xshift);
61  nGrid->setYShift(m_yshift);
62  nGrid->setZShift(m_zshift);
63 
64  return nGrid;
65  }
66 
67  HexGrid::~HexGrid() {
68  }
69 
70  bool HexGrid::isAccessible(const ModelCoordinate& curpos, const ModelCoordinate& target) {
71  if (curpos == target) {
72  return true;
73  }
74 
75  if(curpos.y % 2) {
76 
77  if((curpos.x == target.x) && (curpos.y - 1 == target.y)) {
78  return true;
79  }
80 
81  if((curpos.x + 1 == target.x) && (curpos.y - 1 == target.y)) {
82  return true;
83  }
84 
85  if((curpos.x + 1 == target.x) && (curpos.y == target.y)) {
86  return true;
87  }
88 
89  if((curpos.x + 1 == target.x) && (curpos.y + 1 == target.y)) {
90  return true;
91  }
92 
93  if((curpos.x == target.x) && (curpos.y + 1 == target.y)) {
94  return true;
95  }
96 
97  if((curpos.x - 1 == target.x) && (curpos.y == target.y)) {
98  return true;
99  }
100 
101  } else {
102 
103  if((curpos.x - 1 == target.x) && (curpos.y - 1 == target.y)) {
104  return true;
105  }
106 
107  if((curpos.x == target.x) && (curpos.y - 1 == target.y)) {
108  return true;
109  }
110 
111  if((curpos.x + 1 == target.x) && (curpos.y == target.y)) {
112  return true;
113  }
114 
115  if((curpos.x == target.x) && (curpos.y + 1 == target.y)) {
116  return true;
117  }
118 
119  if((curpos.x - 1 == target.x) && (curpos.y + 1 == target.y)) {
120  return true;
121  }
122 
123  if((curpos.x - 1 == target.x) && (curpos.y == target.y)) {
124  return true;
125  }
126  }
127 
128  return false;
129 
130  }
131 
132  double HexGrid::getAdjacentCost(const ModelCoordinate& curpos, const ModelCoordinate& target) {
133  assert(isAccessible(curpos, target));
134  if (curpos == target) {
135  return 0;
136  } else if (curpos.y == target.y) {
137  return m_xscale;
138  } else {
139  double a = VERTICAL_MULTIP * m_yscale;
140  double b = HEX_TO_EDGE * m_xscale;
141  return Mathd::Sqrt((a * a) + (b * b));
142  }
143  }
144 
145  const std::string& HexGrid::getType() const {
146  static std::string type("hexagonal");
147  return type;
148  }
149 
150  const std::string& HexGrid::getName() const {
151  static std::string hexGrid("Hex Grid");
152  return hexGrid;
153  }
154 
155  double HexGrid::getXZigzagOffset(double y) {
156  // each uneven row has shifted coordinate of 0.5 horizontally
157  // shift has to be gradual on vertical axis
158  double ay = ABS(y);
159  int32_t i_layer_y = static_cast<int32_t>(ay);
160  double offset = ay - static_cast<double>(i_layer_y);
161  if ((i_layer_y % 2) == 1) {
162  offset = 1 - offset;
163  }
164  return HEX_TO_EDGE * offset;
165  }
166 
167  ExactModelCoordinate HexGrid::toMapCoordinates(const ExactModelCoordinate& layer_coords) {
168  ExactModelCoordinate tranformed_coords(layer_coords);
169  tranformed_coords.x += getXZigzagOffset(layer_coords.y);
170  tranformed_coords.y *= VERTICAL_MULTIP;
171  ExactModelCoordinate result = m_matrix * tranformed_coords;
172  FL_DBG(_log, LMsg("layercoords ") << layer_coords << " converted to map: " << result);
173  return result;
174  }
175 
176  ExactModelCoordinate HexGrid::toExactLayerCoordinates(const ExactModelCoordinate& map_coord) {
177  ExactModelCoordinate layer_coords = m_inverse_matrix * map_coord;
178  layer_coords.y /= VERTICAL_MULTIP;
179  layer_coords.x -= getXZigzagOffset(layer_coords.y);
180  FL_DBG(_log, LMsg("mapcoords ") << map_coord << " converted to layer: " << layer_coords);
181  return layer_coords;
182  }
183 
184  ModelCoordinate HexGrid::toLayerCoordinates(const ExactModelCoordinate& map_coord) {
185  FL_DBG(_log, LMsg("==============\nConverting map coords ") << map_coord << " to int32_t layer coords...");
186  ExactModelCoordinate elc = m_inverse_matrix * map_coord;
187  elc.y *= VERTICAL_MULTIP_INV;
188  ExactModelCoordinate lc = ExactModelCoordinate(floor(elc.x), floor(elc.y), floor(elc.z));
189  double dx = elc.x - lc.x;
190  double dy = elc.y - lc.y;
191  double dz = elc.z - lc.z;
192  int32_t x = static_cast<int32_t>(lc.x);
193  int32_t y = static_cast<int32_t>(lc.y);
194  int32_t z = static_cast<int32_t>(lc.z);
195 // FL_DBG(_log, LMsg("elc=") << elc << ", lc=" << lc);
196 // FL_DBG(_log, LMsg("x=") << x << ", y=" << y << ", dx=" << dx << ", dy=" << dy);
197  ModelCoordinate result;
198 
199  if ((y % 2) == 0) {
200 // FL_DBG(_log, "In even row");
201  if ((1 - dy) < HEX_EDGE_HALF) {
202  FL_DBG(_log, "In lower rect area");
203  result = ModelCoordinate(x, y+1, z);
204  }
205  else if (dy < HEX_EDGE_HALF) {
206 // FL_DBG(_log, "In upper rect area");
207  if (dx > 0.5) {
208 // FL_DBG(_log, "...on right");
209  result = ModelCoordinate(x+1, y, z);
210  }
211  else {
212 // FL_DBG(_log, "...on left");
213  result = ModelCoordinate(x, y, z);
214  }
215  }
216  // in middle triangle area
217  else {
218 // FL_DBG(_log, "In middle triangle area");
219  if (dx < 0.5) {
220 // FL_DBG(_log, "In left triangles");
221  if (ptInTriangle(ExactModelCoordinate(dx, dy),
222  ExactModelCoordinate(0, VERTICAL_MULTIP * HEX_EDGE_HALF),
223  ExactModelCoordinate(0, VERTICAL_MULTIP * (1-HEX_EDGE_HALF)),
224  ExactModelCoordinate(0.5, VERTICAL_MULTIP * HEX_EDGE_HALF)
225  )) {
226 // FL_DBG(_log, "..upper part");
227  result = ModelCoordinate(x, y, z);
228  } else {
229 // FL_DBG(_log, "..lower part");
230  result = ModelCoordinate(x, y+1, z);
231  }
232  } else {
233 // FL_DBG(_log, "In right triangles");
234  if (ptInTriangle(ExactModelCoordinate(dx, dy),
235  ExactModelCoordinate(1, VERTICAL_MULTIP * HEX_EDGE_HALF),
236  ExactModelCoordinate(1, VERTICAL_MULTIP * (1-HEX_EDGE_HALF)),
237  ExactModelCoordinate(0.5, VERTICAL_MULTIP * HEX_EDGE_HALF)
238  )) {
239 // FL_DBG(_log, "..upper part");
240  result = ModelCoordinate(x+1, y, z);
241  } else {
242 // FL_DBG(_log, "..lower part");
243  result = ModelCoordinate(x, y+1, z);
244  }
245  }
246  }
247  }
248  else {
249 // FL_DBG(_log, "In uneven row");
250  if (dy < HEX_EDGE_HALF) {
251 // FL_DBG(_log, "In upper rect area");
252  result = ModelCoordinate(x, y, z);
253  }
254  else if ((1 - dy) < HEX_EDGE_HALF) {
255 // FL_DBG(_log, "In lower rect area");
256  if (dx > 0.5) {
257 // FL_DBG(_log, "...on right");
258  result = ModelCoordinate(x+1, y+1, z);
259  }
260  else {
261 // FL_DBG(_log, "...on left");
262  result = ModelCoordinate(x, y+1, z);
263  }
264  }
265  else {
266 // FL_DBG(_log, "In middle triangle area");
267  if (dx < 0.5) {
268 // FL_DBG(_log, "In left triangles");
269  if (ptInTriangle(ExactModelCoordinate(dx, dy),
270  ExactModelCoordinate(0, VERTICAL_MULTIP * HEX_EDGE_HALF),
271  ExactModelCoordinate(0, VERTICAL_MULTIP * (1-HEX_EDGE_HALF)),
272  ExactModelCoordinate(0.5, VERTICAL_MULTIP * (1-HEX_EDGE_HALF))
273  )) {
274 // FL_DBG(_log, "..lower part");
275  result = ModelCoordinate(x, y+1, z);
276  } else {
277 // FL_DBG(_log, "..upper part");
278  result = ModelCoordinate(x, y, z);
279  }
280  } else {
281 // FL_DBG(_log, "In right triangles");
282  if (ptInTriangle(ExactModelCoordinate(dx, dy),
283  ExactModelCoordinate(1, VERTICAL_MULTIP * HEX_EDGE_HALF),
284  ExactModelCoordinate(1, VERTICAL_MULTIP * (1-HEX_EDGE_HALF)),
285  ExactModelCoordinate(0.5, VERTICAL_MULTIP * (1-HEX_EDGE_HALF))
286  )) {
287 // FL_DBG(_log, "..lower part");
288  result = ModelCoordinate(x+1, y+1, z);
289  } else {
290 // FL_DBG(_log, "..upper part");
291  result = ModelCoordinate(x, y, z);
292  }
293  }
294  }
295  }
296 // FL_DBG(_log, LMsg(" result = ") << result);
297  return result;
298  }
299 
300  void HexGrid::getVertices(std::vector<ExactModelCoordinate>& vtx, const ModelCoordinate& cell) {
301  FL_DBG(_log, LMsg("===============\ngetting vertices for ") << cell);
302  vtx.clear();
303  double x = static_cast<double>(cell.x);
304  double y = static_cast<double>(cell.y);
305  double horiz_shift = 0;
306  if (cell.y % 2 != 0) {
307  horiz_shift = HEX_TO_EDGE;
308  FL_DBG(_log, "on uneven row");
309  }
310  double tx, ty;
311 
312  #define ADD_PT(_x, _y) vtx.push_back(ExactModelCoordinate(_x, _y));
313  // FL_DBG(_log, LMsg("Added point ") << _x << ", " << _y)
314  ty = y - VERTICAL_MULTIP_INV * HEX_EDGE_HALF;
315  tx = x - HEX_TO_EDGE - getXZigzagOffset(ty) + horiz_shift;
316  ADD_PT(tx, ty);
317 
318  ty = y - VERTICAL_MULTIP_INV * HEX_TO_CORNER;
319  tx = x - getXZigzagOffset(ty) + horiz_shift;
320  ADD_PT(tx, ty);
321 
322  ty = y - VERTICAL_MULTIP_INV * HEX_EDGE_HALF;
323  tx = x + HEX_TO_EDGE - getXZigzagOffset(ty) + horiz_shift;
324  ADD_PT(tx, ty);
325 
326  ty = y + VERTICAL_MULTIP_INV * HEX_EDGE_HALF;
327  tx = x + HEX_TO_EDGE - getXZigzagOffset(ty) + horiz_shift;
328  ADD_PT(tx, ty);
329 
330  ty = y + VERTICAL_MULTIP_INV * HEX_TO_CORNER;
331  tx = x - getXZigzagOffset(ty) + horiz_shift;
332  ADD_PT(tx, ty);
333 
334  ty = y + VERTICAL_MULTIP_INV * HEX_EDGE_HALF;
335  tx = x - HEX_TO_EDGE - getXZigzagOffset(ty) + horiz_shift;
336  ADD_PT(tx, ty);
337  }
338 }