src/game/CellImpl.h

   1 /*
   2  * Copyright (C) 2005-2013 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 "Common.h"
  23 #include "Cell.h"
  24 #include "Map.h"
  25 #include <cmath>
  26
  27 inline Cell::Cell(CellPair const& p)
  28 {
  29     data.Part.grid_x = p.x_coord / MAX_NUMBER_OF_CELLS;
  30     data.Part.grid_y = p.y_coord / MAX_NUMBER_OF_CELLS;
  31     data.Part.cell_x = p.x_coord % MAX_NUMBER_OF_CELLS;
  32     data.Part.cell_y = p.y_coord % MAX_NUMBER_OF_CELLS;
  33     data.Part.nocreate = 0;
  34     data.Part.reserved = 0;
  35 }
  36
  37 inline CellArea Cell::CalculateCellArea(float x, float y, float radius)
  38 {
  39     if (radius <= 0.0f)
  40     {
  41         CellPair center = MaNGOS::ComputeCellPair(x, y).normalize();
  42         return CellArea(center, center);
  43     }
  44
  45     return CellArea
  46            (
  47                MaNGOS::ComputeCellPair(x - radius, y - radius).normalize(),
  48                MaNGOS::ComputeCellPair(x + radius, y + radius).normalize()
  49            );
  50 }
  51
  52 template<class T, class CONTAINER>
  53 inline void
  54 Cell::Visit(const CellPair& standing_cell, TypeContainerVisitor<T, CONTAINER>& visitor, Map& m, const WorldObject& obj, float radius) const
  55 {
  56     Cell::Visit(standing_cell, visitor, m, obj.GetPositionX(), obj.GetPositionY(), radius + obj.GetObjectBoundingRadius());
  57 }
  58
  59
  60 template<class T, class CONTAINER>
  61 inline void
  62 Cell::Visit(const CellPair& standing_cell, TypeContainerVisitor<T, CONTAINER>& visitor, Map& m, float x, float y, float radius) const
  63 {
  64     if (standing_cell.x_coord >= TOTAL_NUMBER_OF_CELLS_PER_MAP || standing_cell.y_coord >= TOTAL_NUMBER_OF_CELLS_PER_MAP)
  65         return;
  66
  67     // no jokes here... Actually placing ASSERT() here was good idea, but
  68     // we had some problems with DynamicObjects, which pass radius = 0.0f (DB issue?)
  69     // maybe it is better to just return when radius <= 0.0f?
  70     if (radius <= 0.0f)
  71     {
  72         m.Visit(*this, visitor);
  73         return;
  74     }
  75     // lets limit the upper value for search radius
  76     if (radius > 333.0f)
  77         radius = 333.0f;
  78
  79     // lets calculate object coord offsets from cell borders.
  80     CellArea area = Cell::CalculateCellArea(x, y, radius);
  81     // if radius fits inside standing cell
  82     if (!area)
  83     {
  84         m.Visit(*this, visitor);
  85         return;
  86     }
  87
  88     CellPair& begin_cell = area.low_bound;
  89     CellPair& end_cell = area.high_bound;
  90     // visit all cells, found in CalculateCellArea()
  91     // if radius is known to reach cell area more than 4x4 then we should call optimized VisitCircle
  92     // currently this technique works with MAX_NUMBER_OF_CELLS 16 and higher, with lower values
  93     // there are nothing to optimize because SIZE_OF_GRID_CELL is too big...
  94     if (((end_cell.x_coord - begin_cell.x_coord) > 4) && ((end_cell.y_coord - begin_cell.y_coord) > 4))
  95     {
  96         VisitCircle(visitor, m, begin_cell, end_cell);
  97         return;
  98     }
  99
 100     // ALWAYS visit standing cell first!!! Since we deal with small radiuses
 101     // it is very essential to call visitor for standing cell firstly...
 102     m.Visit(*this, visitor);
 103
 104     // loop the cell range
 105     for (uint32 x = begin_cell.x_coord; x <= end_cell.x_coord; ++x)
 106     {
 107         for (uint32 y = begin_cell.y_coord; y <= end_cell.y_coord; ++y)
 108         {
 109             CellPair cell_pair(x, y);
 110             // lets skip standing cell since we already visited it
 111             if (cell_pair != standing_cell)
 112             {
 113                 Cell r_zone(cell_pair);
 114                 r_zone.data.Part.nocreate = data.Part.nocreate;
 115                 m.Visit(r_zone, visitor);
 116             }
 117         }
 118     }
 119 }
 120
 121 template<class T, class CONTAINER>
 122 inline void
 123 Cell::VisitCircle(TypeContainerVisitor<T, CONTAINER>& visitor, Map& m, const CellPair& begin_cell, const CellPair& end_cell) const
 124 {
 125     // here is an algorithm for 'filling' circum-squared octagon
 126     uint32 x_shift = (uint32)ceilf((end_cell.x_coord - begin_cell.x_coord) * 0.3f - 0.5f);
 127     // lets calculate x_start/x_end coords for central strip...
 128     const uint32 x_start = begin_cell.x_coord + x_shift;
 129     const uint32 x_end = end_cell.x_coord - x_shift;
 130
 131     // visit central strip with constant width...
 132     for (uint32 x = x_start; x <= x_end; ++x)
 133     {
 134         for (uint32 y = begin_cell.y_coord; y <= end_cell.y_coord; ++y)
 135         {
 136             CellPair cell_pair(x, y);
 137             Cell r_zone(cell_pair);
 138             r_zone.data.Part.nocreate = data.Part.nocreate;
 139             m.Visit(r_zone, visitor);
 140         }
 141     }
 142
 143     // if x_shift == 0 then we have too small cell area, which were already
 144     // visited at previous step, so just return from procedure...
 145     if (x_shift == 0)
 146         return;
 147
 148     uint32 y_start = end_cell.y_coord;
 149     uint32 y_end = begin_cell.y_coord;
 150     // now we are visiting borders of an octagon...
 151     for (uint32 step = 1; step <= (x_start - begin_cell.x_coord); ++step)
 152     {
 153         // each step reduces strip height by 2 cells...
 154         y_end += 1;
 155         y_start -= 1;
 156         for (uint32 y = y_start; y >= y_end; --y)
 157         {
 158             // we visit cells symmetrically from both sides, heading from center to sides and from up to bottom
 159             // e.g. filling 2 trapezoids after filling central cell strip...
 160             CellPair cell_pair_left(x_start - step, y);
 161             Cell r_zone_left(cell_pair_left);
 162             r_zone_left.data.Part.nocreate = data.Part.nocreate;
 163             m.Visit(r_zone_left, visitor);
 164
 165             // right trapezoid cell visit
 166             CellPair cell_pair_right(x_end + step, y);
 167             Cell r_zone_right(cell_pair_right);
 168             r_zone_right.data.Part.nocreate = data.Part.nocreate;
 169             m.Visit(r_zone_right, visitor);
 170         }
 171     }
 172 }
 173
 174 template<class T>
 175 inline void Cell::VisitGridObjects(const WorldObject* center_obj, T& visitor, float radius, bool dont_load)
 176 {
 177     CellPair p(MaNGOS::ComputeCellPair(center_obj->GetPositionX(), center_obj->GetPositionY()));
 178     Cell cell(p);
 179     if (dont_load)
 180         cell.SetNoCreate();
 181     TypeContainerVisitor<T, GridTypeMapContainer > gnotifier(visitor);
 182     cell.Visit(p, gnotifier, *center_obj->GetMap(), *center_obj, radius);
 183 }
 184
 185 template<class T>
 186 inline void Cell::VisitWorldObjects(const WorldObject* center_obj, T& visitor, float radius, bool dont_load)
 187 {
 188     CellPair p(MaNGOS::ComputeCellPair(center_obj->GetPositionX(), center_obj->GetPositionY()));
 189     Cell cell(p);
 190     if (dont_load)
 191         cell.SetNoCreate();
 192     TypeContainerVisitor<T, WorldTypeMapContainer > gnotifier(visitor);
 193     cell.Visit(p, gnotifier, *center_obj->GetMap(), *center_obj, radius);
 194 }
 195
 196 template<class T>
 197 inline void Cell::VisitAllObjects(const WorldObject* center_obj, T& visitor, float radius, bool dont_load)
 198 {
 199     CellPair p(MaNGOS::ComputeCellPair(center_obj->GetPositionX(), center_obj->GetPositionY()));
 200     Cell cell(p);
 201     if (dont_load)
 202         cell.SetNoCreate();
 203     TypeContainerVisitor<T, GridTypeMapContainer > gnotifier(visitor);
 204     TypeContainerVisitor<T, WorldTypeMapContainer > wnotifier(visitor);
 205     cell.Visit(p, gnotifier, *center_obj->GetMap(), *center_obj, radius);
 206     cell.Visit(p, wnotifier, *center_obj->GetMap(), *center_obj, radius);
 207 }
 208
 209 template<class T>
 210 inline void Cell::VisitGridObjects(float x, float y, Map* map, T& visitor, float radius, bool dont_load)
 211 {
 212     CellPair p(MaNGOS::ComputeCellPair(x, y));
 213     Cell cell(p);
 214     if (dont_load)
 215         cell.SetNoCreate();
 216     TypeContainerVisitor<T, GridTypeMapContainer > gnotifier(visitor);
 217     cell.Visit(p, gnotifier, *map, x, y, radius);
 218 }
 219
 220 template<class T>
 221 inline void Cell::VisitWorldObjects(float x, float y, Map* map, T& visitor, float radius, bool dont_load)
 222 {
 223     CellPair p(MaNGOS::ComputeCellPair(x, y));
 224     Cell cell(p);
 225     if (dont_load)
 226         cell.SetNoCreate();
 227     TypeContainerVisitor<T, WorldTypeMapContainer > gnotifier(visitor);
 228     cell.Visit(p , gnotifier, *map, x, y, radius);
 229 }
 230
 231 template<class T>
 232 inline void Cell::VisitAllObjects(float x, float y, Map* map, T& visitor, float radius, bool dont_load)
 233 {
 234     CellPair p(MaNGOS::ComputeCellPair(x, y));
 235     Cell cell(p);
 236     if (dont_load)
 237         cell.SetNoCreate();
 238     TypeContainerVisitor<T, GridTypeMapContainer > gnotifier(visitor);
 239     TypeContainerVisitor<T, WorldTypeMapContainer > wnotifier(visitor);
 240     cell.Visit(p, gnotifier, *map, x, y, radius);
 241     cell.Visit(p, wnotifier, *map, x, y, radius);
 242 }
 243
 244 #endif