Debian Codegraph @

engine/core/model/metamodel/grids/hexgrid.cpp

raw
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
58 CellGrid* HexGrid::clone() {
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);
66 nGrid->setAllowDiagonals(m_allow_diagonals);
67
68 return nGrid;
69 }
70
71 HexGrid::~HexGrid() {
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
140 ExactModelCoordinate HexGrid::toMapCoordinates(const ExactModelCoordinate& layer_coords) {
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
149 ExactModelCoordinate HexGrid::toExactLayerCoordinates(const ExactModelCoordinate& map_coord) {
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
157 ModelCoordinate HexGrid::toLayerCoordinates(const ExactModelCoordinate& map_coord) {
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
164 ModelCoordinate HexGrid::toLayerCoordinatesFromExactLayerCoordinates(const ExactModelCoordinate& exact_layer_coords) {
165 ExactModelCoordinate elc = exact_layer_coords;
166 elc.x += getXZigzagOffset(elc.y);
167 return toLayerCoordinatesHelper(elc);
168 }
169
170 ModelCoordinate HexGrid::toLayerCoordinatesHelper(const ExactModelCoordinate& coords) {
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 }