src/map.cpp

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