src/map.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 map.cpp Base functions related to the map and distances on them. */
   9
  10 #include "stdafx.h"
  11 #include "debug.h"
  12 #include "core/alloc_func.hpp"
  13 #include "water_map.h"
  14 #include "error_func.h"
  15 #include "string_func.h"
  16 #include "pathfinder/water_regions.h"
  17
  18 #include "safeguards.h"
  19
  20 /* static */ uint Map::log_x;     ///< 2^_map_log_x == _map_size_x
  21 /* static */ uint Map::log_y;     ///< 2^_map_log_y == _map_size_y
  22 /* static */ uint Map::size_x;    ///< Size of the map along the X
  23 /* static */ uint Map::size_y;    ///< Size of the map along the Y
  24 /* static */ uint Map::size;      ///< The number of tiles on the map
  25 /* static */ uint Map::tile_mask; ///< _map_size - 1 (to mask the mapsize)
  26
  27 /* static */ Tile::TileBase *Tile::base_tiles = nullptr;         ///< Base tiles of the map
  28 /* static */ Tile::TileExtended *Tile::extended_tiles = nullptr; ///< Extended tiles of the map
  29
  30
  31 /**
  32  * (Re)allocates a map with the given dimension
  33  * @param size_x the width of the map along the NE/SW edge
  34  * @param size_y the 'height' of the map along the SE/NW edge
  35  */
  36 /* static */ void Map::Allocate(uint size_x, uint size_y)
  37 {
  38         /* Make sure that the map size is within the limits and that
  39          * size of both axes is a power of 2. */
  40         if (!IsInsideMM(size_x, MIN_MAP_SIZE, MAX_MAP_SIZE + 1) ||
  41                         !IsInsideMM(size_y, MIN_MAP_SIZE, MAX_MAP_SIZE + 1) ||
  42                         (size_x & (size_x - 1)) != 0 ||
  43                         (size_y & (size_y - 1)) != 0) {
  44                 FatalError("Invalid map size");
  45         }
  46
  47         Debug(map, 1, "Allocating map of size {}x{}", size_x, size_y);
  48
  49         Map::log_x = FindFirstBit(size_x);
  50         Map::log_y = FindFirstBit(size_y);
  51         Map::size_x = size_x;
  52         Map::size_y = size_y;
  53         Map::size = size_x * size_y;
  54         Map::tile_mask = Map::size - 1;
  55
  56         free(Tile::base_tiles);
  57         free(Tile::extended_tiles);
  58
  59         Tile::base_tiles = CallocT<Tile::TileBase>(Map::size);
  60         Tile::extended_tiles = CallocT<Tile::TileExtended>(Map::size);
  61
  62         AllocateWaterRegions();
  63 }
  64
  65
  66 #ifdef _DEBUG
  67 TileIndex TileAdd(TileIndex tile, TileIndexDiff offset)
  68 {
  69         int dx = offset & Map::MaxX();
  70         if (dx >= (int)Map::SizeX() / 2) dx -= Map::SizeX();
  71         int dy = (offset - dx) / (int)Map::SizeX();
  72
  73         uint32_t x = TileX(tile) + dx;
  74         uint32_t y = TileY(tile) + dy;
  75
  76         assert(x < Map::SizeX());
  77         assert(y < Map::SizeY());
  78         assert(TileXY(x, y) == Map::WrapToMap(tile + offset));
  79
  80         return TileXY(x, y);
  81 }
  82 #endif
  83
  84 /**
  85  * This function checks if we add addx/addy to tile, if we
  86  * do wrap around the edges. For example, tile = (10,2) and
  87  * addx = +3 and addy = -4. This function will now return
  88  * INVALID_TILE, because the y is wrapped. This is needed in
  89  * for example, farmland. When the tile is not wrapped,
  90  * the result will be tile + TileDiffXY(addx, addy)
  91  *
  92  * @param tile the 'starting' point of the adding
  93  * @param addx the amount of tiles in the X direction to add
  94  * @param addy the amount of tiles in the Y direction to add
  95  * @return translated tile, or INVALID_TILE when it would've wrapped.
  96  */
  97 TileIndex TileAddWrap(TileIndex tile, int addx, int addy)
  98 {
  99         uint x = TileX(tile) + addx;
 100         uint y = TileY(tile) + addy;
 101
 102         /* Disallow void tiles at the north border. */
 103         if ((x == 0 || y == 0) && _settings_game.construction.freeform_edges) return INVALID_TILE;
 104
 105         /* Are we about to wrap? */
 106         if (x >= Map::MaxX() || y >= Map::MaxY()) return INVALID_TILE;
 107
 108         return TileXY(x, y);
 109 }
 110
 111 /** 'Lookup table' for tile offsets given an Axis */
 112 extern const TileIndexDiffC _tileoffs_by_axis[] = {
 113         { 1,  0}, ///< AXIS_X
 114         { 0,  1}, ///< AXIS_Y
 115 };
 116
 117 /** 'Lookup table' for tile offsets given a DiagDirection */
 118 extern const TileIndexDiffC _tileoffs_by_diagdir[] = {
 119         {-1,  0}, ///< DIAGDIR_NE
 120         { 0,  1}, ///< DIAGDIR_SE
 121         { 1,  0}, ///< DIAGDIR_SW
 122         { 0, -1}  ///< DIAGDIR_NW
 123 };
 124
 125 /** 'Lookup table' for tile offsets given a Direction */
 126 extern const TileIndexDiffC _tileoffs_by_dir[] = {
 127         {-1, -1}, ///< DIR_N
 128         {-1,  0}, ///< DIR_NE
 129         {-1,  1}, ///< DIR_E
 130         { 0,  1}, ///< DIR_SE
 131         { 1,  1}, ///< DIR_S
 132         { 1,  0}, ///< DIR_SW
 133         { 1, -1}, ///< DIR_W
 134         { 0, -1}  ///< DIR_NW
 135 };
 136
 137 /**
 138  * Gets the Manhattan distance between the two given tiles.
 139  * The Manhattan distance is the sum of the delta of both the
 140  * X and Y component.
 141  * Also known as L1-Norm
 142  * @param t0 the start tile
 143  * @param t1 the end tile
 144  * @return the distance
 145  */
 146 uint DistanceManhattan(TileIndex t0, TileIndex t1)
 147 {
 148         const uint dx = Delta(TileX(t0), TileX(t1));
 149         const uint dy = Delta(TileY(t0), TileY(t1));
 150         return dx + dy;
 151 }
 152
 153
 154 /**
 155  * Gets the 'Square' distance between the two given tiles.
 156  * The 'Square' distance is the square of the shortest (straight line)
 157  * distance between the two tiles.
 158  * Also known as euclidian- or L2-Norm squared.
 159  * @param t0 the start tile
 160  * @param t1 the end tile
 161  * @return the distance
 162  */
 163 uint DistanceSquare(TileIndex t0, TileIndex t1)
 164 {
 165         const int dx = TileX(t0) - TileX(t1);
 166         const int dy = TileY(t0) - TileY(t1);
 167         return dx * dx + dy * dy;
 168 }
 169
 170
 171 /**
 172  * Gets the biggest distance component (x or y) between the two given tiles.
 173  * Also known as L-Infinity-Norm.
 174  * @param t0 the start tile
 175  * @param t1 the end tile
 176  * @return the distance
 177  */
 178 uint DistanceMax(TileIndex t0, TileIndex t1)
 179 {
 180         const uint dx = Delta(TileX(t0), TileX(t1));
 181         const uint dy = Delta(TileY(t0), TileY(t1));
 182         return std::max(dx, dy);
 183 }
 184
 185
 186 /**
 187  * Gets the biggest distance component (x or y) between the two given tiles
 188  * plus the Manhattan distance, i.e. two times the biggest distance component
 189  * and once the smallest component.
 190  * @param t0 the start tile
 191  * @param t1 the end tile
 192  * @return the distance
 193  */
 194 uint DistanceMaxPlusManhattan(TileIndex t0, TileIndex t1)
 195 {
 196         const uint dx = Delta(TileX(t0), TileX(t1));
 197         const uint dy = Delta(TileY(t0), TileY(t1));
 198         return dx > dy ? 2 * dx + dy : 2 * dy + dx;
 199 }
 200
 201 /**
 202  * Param the minimum distance to an edge
 203  * @param tile the tile to get the distance from
 204  * @return the distance from the edge in tiles
 205  */
 206 uint DistanceFromEdge(TileIndex tile)
 207 {
 208         const uint xl = TileX(tile);
 209         const uint yl = TileY(tile);
 210         const uint xh = Map::SizeX() - 1 - xl;
 211         const uint yh = Map::SizeY() - 1 - yl;
 212         const uint minl = std::min(xl, yl);
 213         const uint minh = std::min(xh, yh);
 214         return std::min(minl, minh);
 215 }
 216
 217 /**
 218  * Gets the distance to the edge of the map in given direction.
 219  * @param tile the tile to get the distance from
 220  * @param dir the direction of interest
 221  * @return the distance from the edge in tiles
 222  */
 223 uint DistanceFromEdgeDir(TileIndex tile, DiagDirection dir)
 224 {
 225         switch (dir) {
 226                 case DIAGDIR_NE: return             TileX(tile) - (_settings_game.construction.freeform_edges ? 1 : 0);
 227                 case DIAGDIR_NW: return             TileY(tile) - (_settings_game.construction.freeform_edges ? 1 : 0);
 228                 case DIAGDIR_SW: return Map::MaxX() - TileX(tile) - 1;
 229                 case DIAGDIR_SE: return Map::MaxY() - TileY(tile) - 1;
 230                 default: NOT_REACHED();
 231         }
 232 }
 233
 234 /**
 235  * Function performing a search around a center tile and going outward, thus in circle.
 236  * Although it really is a square search...
 237  * Every tile will be tested by means of the callback function proc,
 238  * which will determine if yes or no the given tile meets criteria of search.
 239  * @param tile to start the search from. Upon completion, it will return the tile matching the search
 240  * @param size: number of tiles per side of the desired search area
 241  * @param proc: callback testing function pointer.
 242  * @param user_data to be passed to the callback function. Depends on the implementation
 243  * @return result of the search
 244  * @pre proc != nullptr
 245  * @pre size > 0
 246  */
 247 bool CircularTileSearch(TileIndex *tile, uint size, TestTileOnSearchProc proc, void *user_data)
 248 {
 249         assert(proc != nullptr);
 250         assert(size > 0);
 251
 252         if (size % 2 == 1) {
 253                 /* If the length of the side is uneven, the center has to be checked
 254                  * separately, as the pattern of uneven sides requires to go around the center */
 255                 if (proc(*tile, user_data)) return true;
 256
 257                 /* If tile test is not successful, get one tile up,
 258                  * ready for a test in first circle around center tile */
 259                 *tile = TileAddByDir(*tile, DIR_N);
 260                 return CircularTileSearch(tile, size / 2, 1, 1, proc, user_data);
 261         } else {
 262                 return CircularTileSearch(tile, size / 2, 0, 0, proc, user_data);
 263         }
 264 }
 265
 266 /**
 267  * Generalized circular search allowing for rectangles and a hole.
 268  * Function performing a search around a center rectangle and going outward.
 269  * The center rectangle is left out from the search. To do a rectangular search
 270  * without a hole, set either h or w to zero.
 271  * Every tile will be tested by means of the callback function proc,
 272  * which will determine if yes or no the given tile meets criteria of search.
 273  * @param tile to start the search from. Upon completion, it will return the tile matching the search.
 274  *  This tile should be directly north of the hole (if any).
 275  * @param radius How many tiles to search outwards. Note: This is a radius and thus different
 276  *                from the size parameter of the other CircularTileSearch function, which is a diameter.
 277  * @param w the width of the inner rectangle
 278  * @param h the height of the inner rectangle
 279  * @param proc callback testing function pointer.
 280  * @param user_data to be passed to the callback function. Depends on the implementation
 281  * @return result of the search
 282  * @pre proc != nullptr
 283  * @pre radius > 0
 284  */
 285 bool CircularTileSearch(TileIndex *tile, uint radius, uint w, uint h, TestTileOnSearchProc proc, void *user_data)
 286 {
 287         assert(proc != nullptr);
 288         assert(radius > 0);
 289
 290         uint x = TileX(*tile) + w + 1;
 291         uint y = TileY(*tile);
 292
 293         const uint extent[DIAGDIR_END] = { w, h, w, h };
 294
 295         for (uint n = 0; n < radius; n++) {
 296                 for (DiagDirection dir = DIAGDIR_BEGIN; dir < DIAGDIR_END; dir++) {
 297                         /* Is the tile within the map? */
 298                         for (uint j = extent[dir] + n * 2 + 1; j != 0; j--) {
 299                                 if (x < Map::SizeX() && y < Map::SizeY()) {
 300                                         TileIndex t = TileXY(x, y);
 301                                         /* Is the callback successful? */
 302                                         if (proc(t, user_data)) {
 303                                                 /* Stop the search */
 304                                                 *tile = t;
 305                                                 return true;
 306                                         }
 307                                 }
 308
 309                                 /* Step to the next 'neighbour' in the circular line */
 310                                 x += _tileoffs_by_diagdir[dir].x;
 311                                 y += _tileoffs_by_diagdir[dir].y;
 312                         }
 313                 }
 314                 /* Jump to next circle to test */
 315                 x += _tileoffs_by_dir[DIR_W].x;
 316                 y += _tileoffs_by_dir[DIR_W].y;
 317         }
 318
 319         *tile = INVALID_TILE;
 320         return false;
 321 }
 322
 323 /**
 324  * Finds the distance for the closest tile with water/land given a tile
 325  * @param tile  the tile to find the distance too
 326  * @param water whether to find water or land
 327  * @return distance to nearest water (max 0x7F) / land (max 0x1FF; 0x200 if there is no land)
 328  */
 329 uint GetClosestWaterDistance(TileIndex tile, bool water)
 330 {
 331         if (HasTileWaterGround(tile) == water) return 0;
 332
 333         uint max_dist = water ? 0x7F : 0x200;
 334
 335         int x = TileX(tile);
 336         int y = TileY(tile);
 337
 338         uint max_x = Map::MaxX();
 339         uint max_y = Map::MaxY();
 340         uint min_xy = _settings_game.construction.freeform_edges ? 1 : 0;
 341
 342         /* go in a 'spiral' with increasing manhattan distance in each iteration */
 343         for (uint dist = 1; dist < max_dist; dist++) {
 344                 /* next 'diameter' */
 345                 y--;
 346
 347                 /* going counter-clockwise around this square */
 348                 for (DiagDirection dir = DIAGDIR_BEGIN; dir < DIAGDIR_END; dir++) {
 349                         static const int8_t ddx[DIAGDIR_END] = { -1,  1,  1, -1};
 350                         static const int8_t ddy[DIAGDIR_END] = {  1,  1, -1, -1};
 351
 352                         int dx = ddx[dir];
 353                         int dy = ddy[dir];
 354
 355                         /* each side of this square has length 'dist' */
 356                         for (uint a = 0; a < dist; a++) {
 357                                 /* MP_VOID tiles are not checked (interval is [min; max) for IsInsideMM())*/
 358                                 if (IsInsideMM(x, min_xy, max_x) && IsInsideMM(y, min_xy, max_y)) {
 359                                         TileIndex t = TileXY(x, y);
 360                                         if (HasTileWaterGround(t) == water) return dist;
 361                                 }
 362                                 x += dx;
 363                                 y += dy;
 364                         }
 365                 }
 366         }
 367
 368         if (!water) {
 369                 /* no land found - is this a water-only map? */
 370                 for (TileIndex t = 0; t < Map::Size(); t++) {
 371                         if (!IsTileType(t, MP_VOID) && !IsTileType(t, MP_WATER)) return 0x1FF;
 372                 }
 373         }
 374
 375         return max_dist;
 376 }