00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #include <cassert>
00024
00025
00026
00027
00028
00029
00030
00031 #include "util/math/fife_math.h"
00032 #include "util/log/logger.h"
00033
00034 #include "hexgrid.h"
00035
00036 namespace FIFE {
00037 static Logger _log(LM_HEXGRID);
00038
00039 static const double HEX_WIDTH = 1;
00040 static const double HEX_TO_EDGE = HEX_WIDTH / 2;
00041 static const double HEX_TO_CORNER = 0.5 / cos(M_PI / 6);
00042 static const double HEX_EDGE_HALF = HEX_TO_CORNER * sin(M_PI / 6);
00043 static const double VERTICAL_MULTIP = sqrt(HEX_WIDTH*HEX_WIDTH - HEX_TO_EDGE*HEX_TO_EDGE);
00044 static const double VERTICAL_MULTIP_INV = 1 / VERTICAL_MULTIP;
00045
00046 HexGrid::HexGrid(bool allow_diagonals): CellGrid(allow_diagonals) {
00047 FL_DBG(_log, "Constructing new HexGrid");
00048 FL_DBG(_log, LMsg("HEX_WIDTH ") << HEX_WIDTH);
00049 FL_DBG(_log, LMsg("HEX_TO_EDGE ") << HEX_TO_EDGE);
00050 FL_DBG(_log, LMsg("HEX_TO_CORNER ") << HEX_TO_CORNER);
00051 FL_DBG(_log, LMsg("HEX_EDGE_HALF ") << HEX_EDGE_HALF);
00052 FL_DBG(_log, LMsg("VERTICAL_MULTIP ") << VERTICAL_MULTIP);
00053 }
00054
00055 CellGrid* HexGrid::clone() {
00056 return new HexGrid(this);
00057 }
00058
00059 HexGrid::~HexGrid() {
00060 }
00061
00062 bool HexGrid::isAccessible(const ModelCoordinate& curpos, const ModelCoordinate& target) {
00063 if (curpos == target) {
00064 return true;
00065 }
00066
00067 if(curpos.y % 2) {
00068
00069 if((curpos.x == target.x) && (curpos.y - 1 == target.y)) {
00070 return true;
00071 }
00072
00073 if((curpos.x + 1 == target.x) && (curpos.y - 1 == target.y)) {
00074 return true;
00075 }
00076
00077 if((curpos.x + 1 == target.x) && (curpos.y == target.y)) {
00078 return true;
00079 }
00080
00081 if((curpos.x + 1 == target.x) && (curpos.y + 1 == target.y)) {
00082 return true;
00083 }
00084
00085 if((curpos.x == target.x) && (curpos.y + 1 == target.y)) {
00086 return true;
00087 }
00088
00089 if((curpos.x - 1 == target.x) && (curpos.y == target.y)) {
00090 return true;
00091 }
00092
00093 } else {
00094
00095 if((curpos.x - 1 == target.x) && (curpos.y - 1 == target.y)) {
00096 return true;
00097 }
00098
00099 if((curpos.x == target.x) && (curpos.y - 1 == target.y)) {
00100 return true;
00101 }
00102
00103 if((curpos.x + 1 == target.x) && (curpos.y == target.y)) {
00104 return true;
00105 }
00106
00107 if((curpos.x == target.x) && (curpos.y + 1 == target.y)) {
00108 return true;
00109 }
00110
00111 if((curpos.x - 1 == target.x) && (curpos.y + 1 == target.y)) {
00112 return true;
00113 }
00114
00115 if((curpos.x - 1 == target.x) && (curpos.y == target.y)) {
00116 return true;
00117 }
00118 }
00119
00120 return false;
00121
00122 }
00123
00124 float HexGrid::getAdjacentCost(const ModelCoordinate& curpos, const ModelCoordinate& target) {
00125 assert(isAccessible(curpos, target));
00126 if (curpos == target) {
00127 return 0;
00128 } else if (curpos.y == target.y) {
00129 return m_xscale;
00130 } else {
00131 double a = VERTICAL_MULTIP * m_yscale;
00132 double b = HEX_TO_EDGE * m_xscale;
00133 return sqrt((a * a) + (b * b));
00134 }
00135 }
00136
00137 const std::string& HexGrid::getType() const {
00138 static std::string type("hexagonal");
00139 return type;
00140 }
00141
00142 const std::string& HexGrid::getName() const {
00143 static std::string hexGrid("Hex Grid");
00144 return hexGrid;
00145 }
00146
00147 double HexGrid::getXZigzagOffset(double y) {
00148
00149
00150 double ay = ABS(y);
00151 int i_layer_y = static_cast<int>(ay);
00152 double offset = ay - static_cast<double>(i_layer_y);
00153 if ((i_layer_y % 2) == 1) {
00154 offset = 1 - offset;
00155 }
00156 return HEX_TO_EDGE * offset;
00157 }
00158
00159 ExactModelCoordinate HexGrid::toMapCoordinates(const ExactModelCoordinate& layer_coords) {
00160 ExactModelCoordinate tranformed_coords(layer_coords);
00161 tranformed_coords.x += getXZigzagOffset(layer_coords.y);
00162 tranformed_coords.y *= VERTICAL_MULTIP;
00163 ExactModelCoordinate result = m_matrix * tranformed_coords;
00164 FL_DBG(_log, LMsg("layercoords ") << layer_coords << " converted to map: " << result);
00165 return result;
00166 }
00167
00168 ExactModelCoordinate HexGrid::toExactLayerCoordinates(const ExactModelCoordinate& map_coord) {
00169 ExactModelCoordinate layer_coords = m_inverse_matrix * map_coord;
00170 layer_coords.y /= VERTICAL_MULTIP;
00171 layer_coords.x -= getXZigzagOffset(layer_coords.y);
00172 FL_DBG(_log, LMsg("mapcoords ") << map_coord << " converted to layer: " << layer_coords);
00173 return layer_coords;
00174 }
00175
00176 ModelCoordinate HexGrid::toLayerCoordinates(const ExactModelCoordinate& map_coord) {
00177 FL_DBG(_log, LMsg("==============\nConverting map coords ") << map_coord << " to int layer coords...");
00178 ExactModelCoordinate elc = m_inverse_matrix * map_coord;
00179 elc.y *= VERTICAL_MULTIP_INV;
00180 ExactModelCoordinate lc = ExactModelCoordinate(floor(elc.x), floor(elc.y));
00181 double dx = elc.x - lc.x;
00182 double dy = elc.y - lc.y;
00183 int x = static_cast<int>(lc.x);
00184 int y = static_cast<int>(lc.y);
00185 FL_DBG(_log, LMsg("elc=") << elc << ", lc=" << lc);
00186 FL_DBG(_log, LMsg("x=") << x << ", y=" << y << ", dx=" << dx << ", dy=" << dy);
00187 ModelCoordinate result;
00188
00189 if ((y % 2) == 0) {
00190 FL_DBG(_log, "In even row");
00191 if ((1 - dy) < HEX_EDGE_HALF) {
00192 FL_DBG(_log, "In lower rect area");
00193 result = ModelCoordinate(x, y+1);
00194 }
00195 else if (dy < HEX_EDGE_HALF) {
00196 FL_DBG(_log, "In upper rect area");
00197 if (dx > 0.5) {
00198 FL_DBG(_log, "...on right");
00199 result = ModelCoordinate(x+1, y);
00200 }
00201 else {
00202 FL_DBG(_log, "...on left");
00203 result = ModelCoordinate(x, y);
00204 }
00205 }
00206
00207 else {
00208 FL_DBG(_log, "In middle triangle area");
00209 if (dx < 0.5) {
00210 FL_DBG(_log, "In left triangles");
00211 if (ptInTriangle(ExactModelCoordinate(dx, dy),
00212 ExactModelCoordinate(0, VERTICAL_MULTIP * HEX_EDGE_HALF),
00213 ExactModelCoordinate(0, VERTICAL_MULTIP * (1-HEX_EDGE_HALF)),
00214 ExactModelCoordinate(0.5, VERTICAL_MULTIP * HEX_EDGE_HALF)
00215 )) {
00216 FL_DBG(_log, "..upper part");
00217 result = ModelCoordinate(x, y);
00218 } else {
00219 FL_DBG(_log, "..lower part");
00220 result = ModelCoordinate(x, y+1);
00221 }
00222 } else {
00223 FL_DBG(_log, "In right triangles");
00224 if (ptInTriangle(ExactModelCoordinate(dx, dy),
00225 ExactModelCoordinate(1, VERTICAL_MULTIP * HEX_EDGE_HALF),
00226 ExactModelCoordinate(1, VERTICAL_MULTIP * (1-HEX_EDGE_HALF)),
00227 ExactModelCoordinate(0.5, VERTICAL_MULTIP * HEX_EDGE_HALF)
00228 )) {
00229 FL_DBG(_log, "..upper part");
00230 result = ModelCoordinate(x+1, y);
00231 } else {
00232 FL_DBG(_log, "..lower part");
00233 result = ModelCoordinate(x, y+1);
00234 }
00235 }
00236 }
00237 }
00238 else {
00239 FL_DBG(_log, "In uneven row");
00240 if (dy < HEX_EDGE_HALF) {
00241 FL_DBG(_log, "In upper rect area");
00242 result = ModelCoordinate(x, y);
00243 }
00244 else if ((1 - dy) < HEX_EDGE_HALF) {
00245 FL_DBG(_log, "In lower rect area");
00246 if (dx > 0.5) {
00247 FL_DBG(_log, "...on right");
00248 result = ModelCoordinate(x+1, y+1);
00249 }
00250 else {
00251 FL_DBG(_log, "...on left");
00252 result = ModelCoordinate(x, y+1);
00253 }
00254 }
00255 else {
00256 FL_DBG(_log, "In middle triangle area");
00257 if (dx < 0.5) {
00258 FL_DBG(_log, "In left triangles");
00259 if (ptInTriangle(ExactModelCoordinate(dx, dy),
00260 ExactModelCoordinate(0, VERTICAL_MULTIP * HEX_EDGE_HALF),
00261 ExactModelCoordinate(0, VERTICAL_MULTIP * (1-HEX_EDGE_HALF)),
00262 ExactModelCoordinate(0.5, VERTICAL_MULTIP * (1-HEX_EDGE_HALF))
00263 )) {
00264 FL_DBG(_log, "..lower part");
00265 result = ModelCoordinate(x, y+1);
00266 } else {
00267 FL_DBG(_log, "..upper part");
00268 result = ModelCoordinate(x, y);
00269 }
00270 } else {
00271 FL_DBG(_log, "In right triangles");
00272 if (ptInTriangle(ExactModelCoordinate(dx, dy),
00273 ExactModelCoordinate(1, VERTICAL_MULTIP * HEX_EDGE_HALF),
00274 ExactModelCoordinate(1, VERTICAL_MULTIP * (1-HEX_EDGE_HALF)),
00275 ExactModelCoordinate(0.5, VERTICAL_MULTIP * (1-HEX_EDGE_HALF))
00276 )) {
00277 FL_DBG(_log, "..lower part");
00278 result = ModelCoordinate(x+1, y+1);
00279 } else {
00280 FL_DBG(_log, "..upper part");
00281 result = ModelCoordinate(x, y);
00282 }
00283 }
00284 }
00285 }
00286 FL_DBG(_log, LMsg(" result = ") << result);
00287 return result;
00288 }
00289
00290 void HexGrid::getVertices(std::vector<ExactModelCoordinate>& vtx, const ModelCoordinate& cell) {
00291 FL_DBG(_log, LMsg("===============\ngetting vertices for ") << cell);
00292 vtx.clear();
00293 double x = static_cast<double>(cell.x);
00294 double y = static_cast<double>(cell.y);
00295 double horiz_shift = 0;
00296 if (cell.y % 2 != 0) {
00297 horiz_shift = HEX_TO_EDGE;
00298 FL_DBG(_log, "on uneven row");
00299 }
00300 double tx, ty;
00301
00302 #define ADD_PT(_x, _y) vtx.push_back(ExactModelCoordinate(_x, _y));
00303
00304 ty = y - VERTICAL_MULTIP_INV * HEX_EDGE_HALF;
00305 tx = x - HEX_TO_EDGE - getXZigzagOffset(ty) + horiz_shift;
00306 ADD_PT(tx, ty);
00307
00308 ty = y - VERTICAL_MULTIP_INV * HEX_TO_CORNER;
00309 tx = x - getXZigzagOffset(ty) + horiz_shift;
00310 ADD_PT(tx, ty);
00311
00312 ty = y - VERTICAL_MULTIP_INV * HEX_EDGE_HALF;
00313 tx = x + HEX_TO_EDGE - getXZigzagOffset(ty) + horiz_shift;
00314 ADD_PT(tx, ty);
00315
00316 ty = y + VERTICAL_MULTIP_INV * HEX_EDGE_HALF;
00317 tx = x + HEX_TO_EDGE - getXZigzagOffset(ty) + horiz_shift;
00318 ADD_PT(tx, ty);
00319
00320 ty = y + VERTICAL_MULTIP_INV * HEX_TO_CORNER;
00321 tx = x - getXZigzagOffset(ty) + horiz_shift;
00322 ADD_PT(tx, ty);
00323
00324 ty = y + VERTICAL_MULTIP_INV * HEX_EDGE_HALF;
00325 tx = x - HEX_TO_EDGE - getXZigzagOffset(ty) + horiz_shift;
00326 ADD_PT(tx, ty);
00327 }
00328 }