FIFE 2008.0
|
00001 /*************************************************************************** 00002 * Copyright (C) 2005-2008 by the FIFE team * 00003 * http://www.fifengine.de * 00004 * This file is part of FIFE. * 00005 * * 00006 * FIFE is free software; you can redistribute it and/or * 00007 * modify it under the terms of the GNU Lesser General Public * 00008 * License as published by the Free Software Foundation; either * 00009 * version 2.1 of the License, or (at your option) any later version. * 00010 * * 00011 * This library is distributed in the hope that it will be useful, * 00012 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 00013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * 00014 * Lesser General Public License for more details. * 00015 * * 00016 * You should have received a copy of the GNU Lesser General Public * 00017 * License along with this library; if not, write to the * 00018 * Free Software Foundation, Inc., * 00019 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * 00020 ***************************************************************************/ 00021 00022 // Standard C++ library includes 00023 #include <cassert> 00024 00025 // 3rd party library includes 00026 00027 // FIFE includes 00028 // These includes are split up in two parts, separated by one empty line 00029 // First block: files included from the FIFE root src directory 00030 // Second block: files included from the same folder 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 / Mathd::Cos(Mathd::pi() / 6); 00042 static const double HEX_EDGE_HALF = HEX_TO_CORNER * Mathd::Sin(Mathd::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 // each uneven row has shifted coordinate of 0.5 horizontally 00149 // shift has to be gradual on vertical axis 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 // in middle triangle area 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 // FL_DBG(_log, LMsg("Added point ") << _x << ", " << _y) 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 }