src/game/CellImpl.h

   1 /*
   2  * Copyright (C) 2005-2010 MaNGOS <http://getmangos.com/>
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17  */
  18
  19 #ifndef MANGOS_CELLIMPL_H
  20 #define MANGOS_CELLIMPL_H
  21
  22 #include "Cell.h"
  23 #include "Map.h"
  24 #include <cmath>
  25
  26 inline Cell::Cell(CellPair const& p)
  27 {
  28     data.Part.grid_x = p.x_coord / MAX_NUMBER_OF_CELLS;
  29     data.Part.grid_y = p.y_coord / MAX_NUMBER_OF_CELLS;
  30     data.Part.cell_x = p.x_coord % MAX_NUMBER_OF_CELLS;
  31     data.Part.cell_y = p.y_coord % MAX_NUMBER_OF_CELLS;
  32     data.Part.nocreate = 0;
  33     data.Part.reserved = 0;
  34 }
  35
  36 template<class T, class CONTAINER>
  37 inline void
  38 Cell::Visit(const CellPair &standing_cell, TypeContainerVisitor<T, CONTAINER> &visitor, Map &m) const
  39 {
  40     if (standing_cell.x_coord >= TOTAL_NUMBER_OF_CELLS_PER_MAP || standing_cell.y_coord >= TOTAL_NUMBER_OF_CELLS_PER_MAP)
  41         return;
  42
  43     uint16 district = (District)this->data.Part.reserved;
  44     if(district == CENTER_DISTRICT)
  45     {
  46         m.Visit(*this, visitor);
  47         return;
  48     }
  49
  50     // set up the cell range based on the district
  51     // the overloaded operators handle range checking
  52     CellPair begin_cell = standing_cell;
  53     CellPair end_cell = standing_cell;
  54
  55     switch( district )
  56     {
  57         case ALL_DISTRICT:
  58         {
  59             begin_cell << 1; begin_cell -= 1;               // upper left
  60             end_cell >> 1; end_cell += 1;                   // lower right
  61             break;
  62         }
  63         case UPPER_LEFT_DISTRICT:
  64         {
  65             begin_cell << 1; begin_cell -= 1;               // upper left
  66             break;
  67         }
  68         case UPPER_RIGHT_DISTRICT:
  69         {
  70             begin_cell -= 1;                                // up
  71             end_cell >> 1;                                  // right
  72             break;
  73         }
  74         case LOWER_LEFT_DISTRICT:
  75         {
  76             begin_cell << 1;                                // left
  77             end_cell += 1;                                  // down
  78             break;
  79         }
  80         case LOWER_RIGHT_DISTRICT:
  81         {
  82             end_cell >> 1; end_cell += 1;                   // lower right
  83             break;
  84         }
  85         case LEFT_DISTRICT:
  86         {
  87             begin_cell -= 1;                                // up
  88             end_cell >> 1; end_cell += 1;                   // lower right
  89             break;
  90         }
  91         case RIGHT_DISTRICT:
  92         {
  93             begin_cell << 1; begin_cell -= 1;               // upper left
  94             end_cell += 1;                                  // down
  95             break;
  96         }
  97         case UPPER_DISTRICT:
  98         {
  99             begin_cell << 1; begin_cell -= 1;               // upper left
 100             end_cell >> 1;                                  // right
 101             break;
 102         }
 103         case LOWER_DISTRICT:
 104         {
 105             begin_cell << 1;                                // left
 106             end_cell >> 1; end_cell += 1;                   // lower right
 107             break;
 108         }
 109         default:
 110         {
 111             assert( false );
 112             break;
 113         }
 114     }
 115
 116     // loop the cell range
 117     for(uint32 x = begin_cell.x_coord; x <= end_cell.x_coord; x++)
 118     {
 119         for(uint32 y = begin_cell.y_coord; y <= end_cell.y_coord; y++)
 120         {
 121             CellPair cell_pair(x,y);
 122             Cell r_zone(cell_pair);
 123             r_zone.data.Part.nocreate = data.Part.nocreate;
 124             m.Visit(r_zone, visitor);
 125         }
 126     }
 127 }
 128
 129 inline int CellHelper(const float radius)
 130 {
 131     if(radius < 1.0f)
 132         return 0;
 133
 134     return (int)ceilf(radius/SIZE_OF_GRID_CELL);
 135 }
 136
 137 inline CellArea Cell::CalculateCellArea(const WorldObject &obj, float radius)
 138 {
 139     if(radius <= 0.0f)
 140         return CellArea();
 141
 142     //we should increase search radius by object's radius, otherwise
 143     //we could have problems with huge creatures, which won't attack nearest players etc
 144     radius += obj.GetObjectSize();
 145     //lets calculate object coord offsets from cell borders.
 146     //TODO: add more correct/generic method for this task
 147     const float x_offset = (obj.GetPositionX() - CENTER_GRID_CELL_OFFSET)/SIZE_OF_GRID_CELL;
 148     const float y_offset = (obj.GetPositionY() - CENTER_GRID_CELL_OFFSET)/SIZE_OF_GRID_CELL;
 149
 150     const float x_val = floor(x_offset + CENTER_GRID_CELL_ID + 0.5f);
 151     const float y_val = floor(y_offset + CENTER_GRID_CELL_ID + 0.5f);
 152
 153     const float x_off = (x_offset - x_val + CENTER_GRID_CELL_ID) * SIZE_OF_GRID_CELL;
 154     const float y_off = (y_offset - y_val + CENTER_GRID_CELL_ID) * SIZE_OF_GRID_CELL;
 155
 156     const float tmp_diff = radius - CENTER_GRID_CELL_OFFSET;
 157     //lets calculate upper/lower/right/left corners for cell search
 158     int right = CellHelper(tmp_diff + x_off);
 159     int left  = CellHelper(tmp_diff - x_off);
 160     int upper = CellHelper(tmp_diff + y_off);
 161     int lower = CellHelper(tmp_diff - y_off);
 162
 163     return CellArea(right, left, upper, lower);
 164 }
 165
 166 template<class T, class CONTAINER>
 167 inline void
 168 Cell::Visit(const CellPair &standing_cell, TypeContainerVisitor<T, CONTAINER> &visitor, Map &m, const WorldObject &obj, float radius) const
 169 {
 170     if (standing_cell.x_coord >= TOTAL_NUMBER_OF_CELLS_PER_MAP || standing_cell.y_coord >= TOTAL_NUMBER_OF_CELLS_PER_MAP)
 171         return;
 172
 173     //no jokes here... Actually placing ASSERT() here was good idea, but
 174     //we had some problems with DynamicObjects, which pass radius = 0.0f (DB issue?)
 175     //maybe it is better to just return when radius <= 0.0f?
 176     if(radius <= 0.0f)
 177     {
 178         m.Visit(*this, visitor);
 179         return;
 180     }
 181     //lets limit the upper value for search radius
 182     if(radius > 333.0f)
 183         radius = 333.0f;
 184
 185     //lets calculate object coord offsets from cell borders.
 186     CellArea area = Cell::CalculateCellArea(obj, radius);
 187     //if radius fits inside standing cell
 188     if(!area)
 189     {
 190         m.Visit(*this, visitor);
 191         return;
 192     }
 193
 194     CellPair begin_cell = standing_cell;
 195     CellPair end_cell = standing_cell;
 196
 197     area.ResizeBorders(begin_cell, end_cell);
 198     //visit all cells, found in CalculateCellArea()
 199     //if radius is known to reach cell area more than 4x4 then we should call optimized VisitCircle
 200     //currently this technique works with MAX_NUMBER_OF_CELLS 16 and higher, with lower values
 201     //there are nothing to optimize because SIZE_OF_GRID_CELL is too big...
 202     if(((end_cell.x_coord - begin_cell.x_coord) > 4) && ((end_cell.y_coord - begin_cell.y_coord) > 4))
 203     {
 204         VisitCircle(visitor, m, begin_cell, end_cell);
 205         return;
 206     }
 207
 208     //ALWAYS visit standing cell first!!! Since we deal with small radiuses
 209     //it is very essential to call visitor for standing cell firstly...
 210     m.Visit(*this, visitor);
 211
 212     // loop the cell range
 213     for(uint32 x = begin_cell.x_coord; x <= end_cell.x_coord; x++)
 214     {
 215         for(uint32 y = begin_cell.y_coord; y <= end_cell.y_coord; y++)
 216         {
 217             CellPair cell_pair(x,y);
 218             //lets skip standing cell since we already visited it
 219             if(cell_pair != standing_cell)
 220             {
 221                 Cell r_zone(cell_pair);
 222                 r_zone.data.Part.nocreate = data.Part.nocreate;
 223                 m.Visit(r_zone, visitor);
 224             }
 225         }
 226     }
 227 }
 228
 229 template<class T, class CONTAINER>
 230 inline void
 231 Cell::VisitCircle(TypeContainerVisitor<T, CONTAINER> &visitor, Map &m, const CellPair& begin_cell, const CellPair& end_cell) const
 232 {
 233     //here is an algorithm for 'filling' circum-squared octagon
 234     uint32 x_shift = (uint32)ceilf((end_cell.x_coord - begin_cell.x_coord) * 0.3f - 0.5f);
 235     //lets calculate x_start/x_end coords for central strip...
 236     const uint32 x_start = begin_cell.x_coord + x_shift;
 237     const uint32 x_end = end_cell.x_coord - x_shift;
 238
 239     //visit central strip with constant width...
 240     for(uint32 x = x_start; x <= x_end; ++x)
 241     {
 242         for(uint32 y = begin_cell.y_coord; y <= end_cell.y_coord; ++y)
 243         {
 244             CellPair cell_pair(x,y);
 245             Cell r_zone(cell_pair);
 246             r_zone.data.Part.nocreate = data.Part.nocreate;
 247             m.Visit(r_zone, visitor);
 248         }
 249     }
 250
 251     //if x_shift == 0 then we have too small cell area, which were already
 252     //visited at previous step, so just return from procedure...
 253     if(x_shift == 0)
 254         return;
 255
 256     uint32 y_start = end_cell.y_coord;
 257     uint32 y_end = begin_cell.y_coord;
 258     //now we are visiting borders of an octagon...
 259     for (uint32 step = 1; step <= (x_start - begin_cell.x_coord); ++step)
 260     {
 261         //each step reduces strip height by 2 cells...
 262         y_end += 1;
 263         y_start -= 1;
 264         for (uint32 y = y_start; y >= y_end; --y)
 265         {
 266             //we visit cells symmetrically from both sides, heading from center to sides and from up to bottom
 267             //e.g. filling 2 trapezoids after filling central cell strip...
 268             CellPair cell_pair_left(x_start - step, y);
 269             Cell r_zone_left(cell_pair_left);
 270             r_zone_left.data.Part.nocreate = data.Part.nocreate;
 271             m.Visit(r_zone_left, visitor);
 272
 273             //right trapezoid cell visit
 274             CellPair cell_pair_right(x_end + step, y);
 275             Cell r_zone_right(cell_pair_right);
 276             r_zone_right.data.Part.nocreate = data.Part.nocreate;
 277             m.Visit(r_zone_right, visitor);
 278         }
 279     }
 280 }
 281
 282 #endif