src/map.cpp

   1 /* $Id$ */
   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 /**
 151  * Gets the Manhattan distance between the two given tiles.
 152  * The Manhattan distance is the sum of the delta of both the
 153  * X and Y component.
 154  * Also known as L1-Norm
 155  * @param t0 the start tile
 156  * @param t1 the end tile
 157  * @return the distance
 158  */
 159 uint DistanceManhattan(TileIndex t0, TileIndex t1)
 160 {
 161         const uint dx = Delta(TileX(t0), TileX(t1));
 162         const uint dy = Delta(TileY(t0), TileY(t1));
 163         return dx + dy;
 164 }
 165
 166
 167 /**
 168  * Gets the 'Square' distance between the two given tiles.
 169  * The 'Square' distance is the square of the shortest (straight line)
 170  * distance between the two tiles.
 171  * Also known as euclidian- or L2-Norm squared.
 172  * @param t0 the start tile
 173  * @param t1 the end tile
 174  * @return the distance
 175  */
 176 uint DistanceSquare(TileIndex t0, TileIndex t1)
 177 {
 178         const int dx = TileX(t0) - TileX(t1);
 179         const int dy = TileY(t0) - TileY(t1);
 180         return dx * dx + dy * dy;
 181 }
 182
 183
 184 /**
 185  * Gets the biggest distance component (x or y) between the two given tiles.
 186  * Also known as L-Infinity-Norm.
 187  * @param t0 the start tile
 188  * @param t1 the end tile
 189  * @return the distance
 190  */
 191 uint DistanceMax(TileIndex t0, TileIndex t1)
 192 {
 193         const uint dx = Delta(TileX(t0), TileX(t1));
 194         const uint dy = Delta(TileY(t0), TileY(t1));
 195         return max(dx, dy);
 196 }
 197
 198
 199 /**
 200  * Gets the biggest distance component (x or y) between the two given tiles
 201  * plus the Manhattan distance, i.e. two times the biggest distance component
 202  * and once the smallest component.
 203  * @param t0 the start tile
 204  * @param t1 the end tile
 205  * @return the distance
 206  */
 207 uint DistanceMaxPlusManhattan(TileIndex t0, TileIndex t1)
 208 {
 209         const uint dx = Delta(TileX(t0), TileX(t1));
 210         const uint dy = Delta(TileY(t0), TileY(t1));
 211         return dx > dy ? 2 * dx + dy : 2 * dy + dx;
 212 }
 213
 214 /**
 215  * Param the minimum distance to an edge
 216  * @param tile the tile to get the distance from
 217  * @return the distance from the edge in tiles
 218  */
 219 uint DistanceFromEdge(TileIndex tile)
 220 {
 221         const uint xl = TileX(tile);
 222         const uint yl = TileY(tile);
 223         const uint xh = MapSizeX() - 1 - xl;
 224         const uint yh = MapSizeY() - 1 - yl;
 225         const uint minl = min(xl, yl);
 226         const uint minh = min(xh, yh);
 227         return min(minl, minh);
 228 }
 229
 230 /**
 231  * Gets the distance to the edge of the map in given direction.
 232  * @param tile the tile to get the distance from
 233  * @param dir the direction of interest
 234  * @return the distance from the edge in tiles
 235  */
 236 uint DistanceFromEdgeDir(TileIndex tile, DiagDirection dir)
 237 {
 238         switch (dir) {
 239                 case DIAGDIR_NE: return             TileX(tile) - (_settings_game.construction.freeform_edges ? 1 : 0);
 240                 case DIAGDIR_NW: return             TileY(tile) - (_settings_game.construction.freeform_edges ? 1 : 0);
 241                 case DIAGDIR_SW: return MapMaxX() - TileX(tile) - 1;
 242                 case DIAGDIR_SE: return MapMaxY() - TileY(tile) - 1;
 243                 default: NOT_REACHED();
 244         }
 245 }
 246
 247 /**
 248  * Function performing a search around a center tile and going outward, thus in circle.
 249  * Although it really is a square search...
 250  * Every tile will be tested by means of the callback function proc,
 251  * which will determine if yes or no the given tile meets criteria of search.
 252  * @param tile to start the search from. Upon completion, it will return the tile matching the search
 253  * @param size: number of tiles per side of the desired search area
 254  * @param proc: callback testing function pointer.
 255  * @param user_data to be passed to the callback function. Depends on the implementation
 256  * @return result of the search
 257  * @pre proc != NULL
 258  * @pre size > 0
 259  */
 260 bool CircularTileSearch(TileIndex *tile, uint size, TestTileOnSearchProc proc, void *user_data)
 261 {
 262         assert(proc != NULL);
 263         assert(size > 0);
 264
 265         if (size % 2 == 1) {
 266                 /* If the length of the side is uneven, the center has to be checked
 267                  * separately, as the pattern of uneven sides requires to go around the center */
 268                 if (proc(*tile, user_data)) return true;
 269
 270                 /* If tile test is not successful, get one tile up,
 271                  * ready for a test in first circle around center tile */
 272                 *tile = TILE_ADD(*tile, TileOffsByDir(DIR_N));
 273                 return CircularTileSearch(tile, size / 2, 1, 1, proc, user_data);
 274         } else {
 275                 return CircularTileSearch(tile, size / 2, 0, 0, proc, user_data);
 276         }
 277 }
 278
 279 /**
 280  * Generalized circular search allowing for rectangles and a hole.
 281  * Function performing a search around a center rectangle and going outward.
 282  * The center rectangle is left out from the search. To do a rectangular search
 283  * without a hole, set either h or w to zero.
 284  * Every tile will be tested by means of the callback function proc,
 285  * which will determine if yes or no the given tile meets criteria of search.
 286  * @param tile to start the search from. Upon completion, it will return the tile matching the search.
 287  *  This tile should be directly north of the hole (if any).
 288  * @param radius How many tiles to search outwards. Note: This is a radius and thus different
 289  *                from the size parameter of the other CircularTileSearch function, which is a diameter.
 290  * @param w the width of the inner rectangle
 291  * @param h the height of the inner rectangle
 292  * @param proc callback testing function pointer.
 293  * @param user_data to be passed to the callback function. Depends on the implementation
 294  * @return result of the search
 295  * @pre proc != NULL
 296  * @pre radius > 0
 297  */
 298 bool CircularTileSearch(TileIndex *tile, uint radius, uint w, uint h, TestTileOnSearchProc proc, void *user_data)
 299 {
 300         assert(proc != NULL);
 301         assert(radius > 0);
 302
 303         uint x = TileX(*tile) + w + 1;
 304         uint y = TileY(*tile);
 305
 306         const uint extent[DIAGDIR_END] = { w, h, w, h };
 307
 308         for (uint n = 0; n < radius; n++) {
 309                 for (DiagDirection dir = DIAGDIR_BEGIN; dir < DIAGDIR_END; dir++) {
 310                         /* Is the tile within the map? */
 311                         for (uint j = extent[dir] + n * 2 + 1; j != 0; j--) {
 312                                 if (x < MapSizeX() && y < MapSizeY()) {
 313                                         TileIndex t = TileXY(x, y);
 314                                         /* Is the callback successful? */
 315                                         if (proc(t, user_data)) {
 316                                                 /* Stop the search */
 317                                                 *tile = t;
 318                                                 return true;
 319                                         }
 320                                 }
 321
 322                                 /* Step to the next 'neighbour' in the circular line */
 323                                 x += _tileoffs_by_diagdir[dir].x;
 324                                 y += _tileoffs_by_diagdir[dir].y;
 325                         }
 326                 }
 327                 /* Jump to next circle to test */
 328                 x += _tileoffs_by_dir[DIR_W].x;
 329                 y += _tileoffs_by_dir[DIR_W].y;
 330         }
 331
 332         *tile = INVALID_TILE;
 333         return false;
 334 }
 335
 336 /**
 337  * Finds the distance for the closest tile with water/land given a tile
 338  * @param tile  the tile to find the distance too
 339  * @param water whether to find water or land
 340  * @return distance to nearest water (max 0x7F) / land (max 0x1FF; 0x200 if there is no land)
 341  */
 342 uint GetClosestWaterDistance(TileIndex tile, bool water)
 343 {
 344         if (HasTileWaterGround(tile) == water) return 0;
 345
 346         uint max_dist = water ? 0x7F : 0x200;
 347
 348         int x = TileX(tile);
 349         int y = TileY(tile);
 350
 351         uint max_x = MapMaxX();
 352         uint max_y = MapMaxY();
 353         uint min_xy = _settings_game.construction.freeform_edges ? 1 : 0;
 354
 355         /* go in a 'spiral' with increasing manhattan distance in each iteration */
 356         for (uint dist = 1; dist < max_dist; dist++) {
 357                 /* next 'diameter' */
 358                 y--;
 359
 360                 /* going counter-clockwise around this square */
 361                 for (DiagDirection dir = DIAGDIR_BEGIN; dir < DIAGDIR_END; dir++) {
 362                         static const int8 ddx[DIAGDIR_END] = { -1,  1,  1, -1};
 363                         static const int8 ddy[DIAGDIR_END] = {  1,  1, -1, -1};
 364
 365                         int dx = ddx[dir];
 366                         int dy = ddy[dir];
 367
 368                         /* each side of this square has length 'dist' */
 369                         for (uint a = 0; a < dist; a++) {
 370                                 /* MP_VOID tiles are not checked (interval is [min; max) for IsInsideMM())*/
 371                                 if (IsInsideMM(x, min_xy, max_x) && IsInsideMM(y, min_xy, max_y)) {
 372                                         TileIndex t = TileXY(x, y);
 373                                         if (HasTileWaterGround(t) == water) return dist;
 374                                 }
 375                                 x += dx;
 376                                 y += dy;
 377                         }
 378                 }
 379         }
 380
 381         if (!water) {
 382                 /* no land found - is this a water-only map? */
 383                 for (TileIndex t = 0; t < MapSize(); t++) {
 384                         if (!IsTileType(t, MP_VOID) && !IsTileType(t, MP_WATER)) return 0x1FF;
 385                 }
 386         }
 387
 388         return max_dist;
 389 }