FIFE  2008.0
 All Classes Namespaces Functions Variables Enumerations Enumerator
hexgrid.cpp
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 }