src/tilearea.cpp

   1 /*
   2  * This file is part of OpenTTD.
   3  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
   4  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   5  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   6  */
   7
   8 /** @file tilearea.cpp Handling of tile areas. */
   9
  10 #include "stdafx.h"
  11
  12 #include "tilearea_type.h"
  13
  14 #include "safeguards.h"
  15
  16 /**
  17  * Construct this tile area based on two points.
  18  * @param start the start of the area
  19  * @param end   the end of the area
  20  */
  21 OrthogonalTileArea::OrthogonalTileArea(TileIndex start, TileIndex end)
  22 {
  23         assert(start < MapSize());
  24         assert(end < MapSize());
  25
  26         uint sx = TileX(start);
  27         uint sy = TileY(start);
  28         uint ex = TileX(end);
  29         uint ey = TileY(end);
  30
  31         if (sx > ex) Swap(sx, ex);
  32         if (sy > ey) Swap(sy, ey);
  33
  34         this->tile = TileXY(sx, sy);
  35         this->w    = ex - sx + 1;
  36         this->h    = ey - sy + 1;
  37 }
  38
  39 /**
  40  * Add a single tile to a tile area; enlarge if needed.
  41  * @param to_add The tile to add
  42  */
  43 void OrthogonalTileArea::Add(TileIndex to_add)
  44 {
  45         if (this->tile == INVALID_TILE) {
  46                 this->tile = to_add;
  47                 this->w = 1;
  48                 this->h = 1;
  49                 return;
  50         }
  51
  52         uint sx = TileX(this->tile);
  53         uint sy = TileY(this->tile);
  54         uint ex = sx + this->w - 1;
  55         uint ey = sy + this->h - 1;
  56
  57         uint ax = TileX(to_add);
  58         uint ay = TileY(to_add);
  59
  60         sx = std::min(ax, sx);
  61         sy = std::min(ay, sy);
  62         ex = std::max(ax, ex);
  63         ey = std::max(ay, ey);
  64
  65         this->tile = TileXY(sx, sy);
  66         this->w    = ex - sx + 1;
  67         this->h    = ey - sy + 1;
  68 }
  69
  70 /**
  71  * Does this tile area intersect with another?
  72  * @param ta the other tile area to check against.
  73  * @return true if they intersect.
  74  */
  75 bool OrthogonalTileArea::Intersects(const OrthogonalTileArea &ta) const
  76 {
  77         if (ta.w == 0 || this->w == 0) return false;
  78
  79         assert(ta.w != 0 && ta.h != 0 && this->w != 0 && this->h != 0);
  80
  81         uint left1   = TileX(this->tile);
  82         uint top1    = TileY(this->tile);
  83         uint right1  = left1 + this->w - 1;
  84         uint bottom1 = top1  + this->h - 1;
  85
  86         uint left2   = TileX(ta.tile);
  87         uint top2    = TileY(ta.tile);
  88         uint right2  = left2 + ta.w - 1;
  89         uint bottom2 = top2  + ta.h - 1;
  90
  91         return !(
  92                         left2   > right1  ||
  93                         right2  < left1   ||
  94                         top2    > bottom1 ||
  95                         bottom2 < top1
  96                 );
  97 }
  98
  99 /**
 100  * Does this tile area contain a tile?
 101  * @param tile Tile to test for.
 102  * @return True if the tile is inside the area.
 103  */
 104 bool OrthogonalTileArea::Contains(TileIndex tile) const
 105 {
 106         if (this->w == 0) return false;
 107
 108         assert(this->w != 0 && this->h != 0);
 109
 110         uint left   = TileX(this->tile);
 111         uint top    = TileY(this->tile);
 112         uint tile_x = TileX(tile);
 113         uint tile_y = TileY(tile);
 114
 115         return IsInsideBS(tile_x, left, this->w) && IsInsideBS(tile_y, top, this->h);
 116 }
 117
 118 /**
 119  * Expand a tile area by rad tiles in each direction, keeping within map bounds.
 120  * @param rad Number of tiles to expand
 121  * @return The OrthogonalTileArea.
 122  */
 123 OrthogonalTileArea &OrthogonalTileArea::Expand(int rad)
 124 {
 125         int x = TileX(this->tile);
 126         int y = TileY(this->tile);
 127
 128         int sx = std::max<int>(x - rad, 0);
 129         int sy = std::max<int>(y - rad, 0);
 130         int ex = std::min<int>(x + this->w + rad, MapSizeX());
 131         int ey = std::min<int>(y + this->h + rad, MapSizeY());
 132
 133         this->tile = TileXY(sx, sy);
 134         this->w    = ex - sx;
 135         this->h    = ey - sy;
 136         return *this;
 137 }
 138
 139 /**
 140  * Clamp the tile area to map borders.
 141  */
 142 void OrthogonalTileArea::ClampToMap()
 143 {
 144         assert(this->tile < MapSize());
 145         this->w = std::min<int>(this->w, MapSizeX() - TileX(this->tile));
 146         this->h = std::min<int>(this->h, MapSizeY() - TileY(this->tile));
 147 }
 148
 149 /**
 150  * Returns an iterator to the beginning of the tile area.
 151  * @return The OrthogonalTileIterator.
 152  */
 153 OrthogonalTileIterator OrthogonalTileArea::begin() const
 154 {
 155         return OrthogonalTileIterator(*this);
 156 }
 157
 158 /**
 159  * Returns an iterator to the end of the tile area.
 160  * @return The OrthogonalTileIterator.
 161  */
 162 OrthogonalTileIterator OrthogonalTileArea::end() const
 163 {
 164         return OrthogonalTileIterator(OrthogonalTileArea());
 165 }
 166
 167 /**
 168  * Create a diagonal tile area from two corners.
 169  * @param start First corner of the area.
 170  * @param end Second corner of the area.
 171  */
 172 DiagonalTileArea::DiagonalTileArea(TileIndex start, TileIndex end) : tile(start)
 173 {
 174         assert(start < MapSize());
 175         assert(end < MapSize());
 176
 177         /* Unfortunately we can't find a new base and make all a and b positive because
 178          * the new base might be a "flattened" corner where there actually is no single
 179          * tile. If we try anyway the result is either inaccurate ("one off" half of the
 180          * time) or the code gets much more complex;
 181          *
 182          * We also need to increment/decrement a and b here to have one-past-end semantics
 183          * for a and b, just the way the orthogonal tile area does it for w and h. */
 184
 185         this->a = TileY(end) + TileX(end) - TileY(start) - TileX(start);
 186         this->b = TileY(end) - TileX(end) - TileY(start) + TileX(start);
 187         if (this->a > 0) {
 188                 this->a++;
 189         } else {
 190                 this->a--;
 191         }
 192
 193         if (this->b > 0) {
 194                 this->b++;
 195         } else {
 196                 this->b--;
 197         }
 198 }
 199
 200 /**
 201  * Does this tile area contain a tile?
 202  * @param tile Tile to test for.
 203  * @return True if the tile is inside the area.
 204  */
 205 bool DiagonalTileArea::Contains(TileIndex tile) const
 206 {
 207         int a = TileY(tile) + TileX(tile);
 208         int b = TileY(tile) - TileX(tile);
 209
 210         int start_a = TileY(this->tile) + TileX(this->tile);
 211         int start_b = TileY(this->tile) - TileX(this->tile);
 212
 213         int end_a = start_a + this->a;
 214         int end_b = start_b + this->b;
 215
 216         /* Swap if necessary, preserving the "one past end" semantics. */
 217         if (start_a > end_a) {
 218                 int tmp = start_a;
 219                 start_a = end_a + 1;
 220                 end_a = tmp + 1;
 221         }
 222         if (start_b > end_b) {
 223                 int tmp = start_b;
 224                 start_b = end_b + 1;
 225                 end_b = tmp + 1;
 226         }
 227
 228         return (a >= start_a && a < end_a && b >= start_b && b < end_b);
 229 }
 230
 231 /**
 232  * Move ourselves to the next tile in the rectangle on the map.
 233  */
 234 TileIterator &DiagonalTileIterator::operator++()
 235 {
 236         assert(this->tile != INVALID_TILE);
 237
 238         /* Determine the next tile, while clipping at map borders */
 239         bool new_line = false;
 240         do {
 241                 /* Iterate using the rotated coordinates. */
 242                 if (this->a_max == 1 || this->a_max == -1) {
 243                         /* Special case: Every second column has zero length, skip them completely */
 244                         this->a_cur = 0;
 245                         if (this->b_max > 0) {
 246                                 this->b_cur = std::min(this->b_cur + 2, this->b_max);
 247                         } else {
 248                                 this->b_cur = std::max(this->b_cur - 2, this->b_max);
 249                         }
 250                 } else {
 251                         /* Every column has at least one tile to process */
 252                         if (this->a_max > 0) {
 253                                 this->a_cur += 2;
 254                                 new_line = this->a_cur >= this->a_max;
 255                         } else {
 256                                 this->a_cur -= 2;
 257                                 new_line = this->a_cur <= this->a_max;
 258                         }
 259                         if (new_line) {
 260                                 /* offset of initial a_cur: one tile in the same direction as a_max
 261                                  * every second line.
 262                                  */
 263                                 this->a_cur = abs(this->a_cur) % 2 ? 0 : (this->a_max > 0 ? 1 : -1);
 264
 265                                 if (this->b_max > 0) {
 266                                         ++this->b_cur;
 267                                 } else {
 268                                         --this->b_cur;
 269                                 }
 270                         }
 271                 }
 272
 273                 /* And convert the coordinates back once we've gone to the next tile. */
 274                 uint x = this->base_x + (this->a_cur - this->b_cur) / 2;
 275                 uint y = this->base_y + (this->b_cur + this->a_cur) / 2;
 276                 /* Prevent wrapping around the map's borders. */
 277                 this->tile = x >= MapSizeX() || y >= MapSizeY() ? INVALID_TILE : TileXY(x, y);
 278         } while (this->tile > MapSize() && this->b_max != this->b_cur);
 279
 280         if (this->b_max == this->b_cur) this->tile = INVALID_TILE;
 281         return *this;
 282 }