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