src/map_func.h

   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_func.h Functions related to maps. */
   9
  10 #ifndef MAP_FUNC_H
  11 #define MAP_FUNC_H
  12
  13 #include "core/math_func.hpp"
  14 #include "tile_type.h"
  15 #include "map_type.h"
  16 #include "direction_func.h"
  17
  18 extern uint _map_tile_mask;
  19
  20 /**
  21  * 'Wraps' the given tile to it is within the map. It does
  22  * this by masking the 'high' bits of.
  23  * @param x the tile to 'wrap'
  24  */
  25
  26 #define TILE_MASK(x) ((x) & _map_tile_mask)
  27
  28 /**
  29  * Pointer to the tile-array.
  30  *
  31  * This variable points to the tile-array which contains the tiles of
  32  * the map.
  33  */
  34 extern Tile *_m;
  35
  36 /**
  37  * Pointer to the extended tile-array.
  38  *
  39  * This variable points to the extended tile-array which contains the tiles
  40  * of the map.
  41  */
  42 extern TileExtended *_me;
  43
  44 void AllocateMap(uint size_x, uint size_y);
  45
  46 /**
  47  * Logarithm of the map size along the X side.
  48  * @note try to avoid using this one
  49  * @return 2^"return value" == MapSizeX()
  50  */
  51 static inline uint MapLogX()
  52 {
  53         extern uint _map_log_x;
  54         return _map_log_x;
  55 }
  56
  57 /**
  58  * Logarithm of the map size along the y side.
  59  * @note try to avoid using this one
  60  * @return 2^"return value" == MapSizeY()
  61  */
  62 static inline uint MapLogY()
  63 {
  64         extern uint _map_log_y;
  65         return _map_log_y;
  66 }
  67
  68 /**
  69  * Get the size of the map along the X
  70  * @return the number of tiles along the X of the map
  71  */
  72 static inline uint MapSizeX()
  73 {
  74         extern uint _map_size_x;
  75         return _map_size_x;
  76 }
  77
  78 /**
  79  * Get the size of the map along the Y
  80  * @return the number of tiles along the Y of the map
  81  */
  82 static inline uint MapSizeY()
  83 {
  84         extern uint _map_size_y;
  85         return _map_size_y;
  86 }
  87
  88 /**
  89  * Get the size of the map
  90  * @return the number of tiles of the map
  91  */
  92 static inline uint MapSize()
  93 {
  94         extern uint _map_size;
  95         return _map_size;
  96 }
  97
  98 /**
  99  * Gets the maximum X coordinate within the map, including MP_VOID
 100  * @return the maximum X coordinate
 101  */
 102 static inline uint MapMaxX()
 103 {
 104         return MapSizeX() - 1;
 105 }
 106
 107 /**
 108  * Gets the maximum Y coordinate within the map, including MP_VOID
 109  * @return the maximum Y coordinate
 110  */
 111 static inline uint MapMaxY()
 112 {
 113         return MapSizeY() - 1;
 114 }
 115
 116 /**
 117  * Scales the given value by the map size, where the given value is
 118  * for a 256 by 256 map.
 119  * @param n the value to scale
 120  * @return the scaled size
 121  */
 122 static inline uint ScaleByMapSize(uint n)
 123 {
 124         /* Subtract 12 from shift in order to prevent integer overflow
 125          * for large values of n. It's safe since the min mapsize is 64x64. */
 126         return CeilDiv(n << (MapLogX() + MapLogY() - 12), 1 << 4);
 127 }
 128
 129
 130 /**
 131  * Scales the given value by the maps circumference, where the given
 132  * value is for a 256 by 256 map
 133  * @param n the value to scale
 134  * @return the scaled size
 135  */
 136 static inline uint ScaleByMapSize1D(uint n)
 137 {
 138         /* Normal circumference for the X+Y is 256+256 = 1<<9
 139          * Note, not actually taking the full circumference into account,
 140          * just half of it. */
 141         return CeilDiv((n << MapLogX()) + (n << MapLogY()), 1 << 9);
 142 }
 143
 144 /**
 145  * An offset value between to tiles.
 146  *
 147  * This value is used for the difference between
 148  * two tiles. It can be added to a tileindex to get
 149  * the resulting tileindex of the start tile applied
 150  * with this saved difference.
 151  *
 152  * @see TileDiffXY(int, int)
 153  */
 154 typedef int32 TileIndexDiff;
 155
 156 /**
 157  * Returns the TileIndex of a coordinate.
 158  *
 159  * @param x The x coordinate of the tile
 160  * @param y The y coordinate of the tile
 161  * @return The TileIndex calculated by the coordinate
 162  */
 163 static inline TileIndex TileXY(uint x, uint y)
 164 {
 165         return (y << MapLogX()) + x;
 166 }
 167
 168 /**
 169  * Calculates an offset for the given coordinate(-offset).
 170  *
 171  * This function calculate an offset value which can be added to an
 172  * #TileIndex. The coordinates can be negative.
 173  *
 174  * @param x The offset in x direction
 175  * @param y The offset in y direction
 176  * @return The resulting offset value of the given coordinate
 177  * @see ToTileIndexDiff(TileIndexDiffC)
 178  */
 179 static inline TileIndexDiff TileDiffXY(int x, int y)
 180 {
 181         /* Multiplication gives much better optimization on MSVC than shifting.
 182          * 0 << shift isn't optimized to 0 properly.
 183          * Typically x and y are constants, and then this doesn't result
 184          * in any actual multiplication in the assembly code.. */
 185         return (y * MapSizeX()) + x;
 186 }
 187
 188 /**
 189  * Get a tile from the virtual XY-coordinate.
 190  * @param x The virtual x coordinate of the tile.
 191  * @param y The virtual y coordinate of the tile.
 192  * @return The TileIndex calculated by the coordinate.
 193  */
 194 static inline TileIndex TileVirtXY(uint x, uint y)
 195 {
 196         return (y >> 4 << MapLogX()) + (x >> 4);
 197 }
 198
 199
 200 /**
 201  * Get the X component of a tile
 202  * @param tile the tile to get the X component of
 203  * @return the X component
 204  */
 205 static inline uint TileX(TileIndex tile)
 206 {
 207         return tile & MapMaxX();
 208 }
 209
 210 /**
 211  * Get the Y component of a tile
 212  * @param tile the tile to get the Y component of
 213  * @return the Y component
 214  */
 215 static inline uint TileY(TileIndex tile)
 216 {
 217         return tile >> MapLogX();
 218 }
 219
 220 /**
 221  * Return the offset between to tiles from a TileIndexDiffC struct.
 222  *
 223  * This function works like #TileDiffXY(int, int) and returns the
 224  * difference between two tiles.
 225  *
 226  * @param tidc The coordinate of the offset as TileIndexDiffC
 227  * @return The difference between two tiles.
 228  * @see TileDiffXY(int, int)
 229  */
 230 static inline TileIndexDiff ToTileIndexDiff(TileIndexDiffC tidc)
 231 {
 232         return (tidc.y << MapLogX()) + tidc.x;
 233 }
 234
 235
 236 #ifndef _DEBUG
 237         /**
 238          * Adds to tiles together.
 239          *
 240          * @param x One tile
 241          * @param y Another tile to add
 242          * @return The resulting tile(index)
 243          */
 244         #define TILE_ADD(x, y) ((x) + (y))
 245 #else
 246         extern TileIndex TileAdd(TileIndex tile, TileIndexDiff add,
 247                 const char *exp, const char *file, int line);
 248         #define TILE_ADD(x, y) (TileAdd((x), (y), #x " + " #y, __FILE__, __LINE__))
 249 #endif
 250
 251 /**
 252  * Adds a given offset to a tile.
 253  *
 254  * @param tile The tile to add an offset on it
 255  * @param x The x offset to add to the tile
 256  * @param y The y offset to add to the tile
 257  */
 258 #define TILE_ADDXY(tile, x, y) TILE_ADD(tile, TileDiffXY(x, y))
 259
 260 TileIndex TileAddWrap(TileIndex tile, int addx, int addy);
 261
 262 /**
 263  * Returns the TileIndexDiffC offset from a DiagDirection.
 264  *
 265  * @param dir The given direction
 266  * @return The offset as TileIndexDiffC value
 267  */
 268 static inline TileIndexDiffC TileIndexDiffCByDiagDir(DiagDirection dir)
 269 {
 270         extern const TileIndexDiffC _tileoffs_by_diagdir[DIAGDIR_END];
 271
 272         assert(IsValidDiagDirection(dir));
 273         return _tileoffs_by_diagdir[dir];
 274 }
 275
 276 /**
 277  * Returns the TileIndexDiffC offset from a Direction.
 278  *
 279  * @param dir The given direction
 280  * @return The offset as TileIndexDiffC value
 281  */
 282 static inline TileIndexDiffC TileIndexDiffCByDir(Direction dir)
 283 {
 284         extern const TileIndexDiffC _tileoffs_by_dir[DIR_END];
 285
 286         assert(IsValidDirection(dir));
 287         return _tileoffs_by_dir[dir];
 288 }
 289
 290 /**
 291  * Add a TileIndexDiffC to a TileIndex and returns the new one.
 292  *
 293  * Returns tile + the diff given in diff. If the result tile would end up
 294  * outside of the map, INVALID_TILE is returned instead.
 295  *
 296  * @param tile The base tile to add the offset on
 297  * @param diff The offset to add on the tile
 298  * @return The resulting TileIndex
 299  */
 300 static inline TileIndex AddTileIndexDiffCWrap(TileIndex tile, TileIndexDiffC diff)
 301 {
 302         int x = TileX(tile) + diff.x;
 303         int y = TileY(tile) + diff.y;
 304         /* Negative value will become big positive value after cast */
 305         if ((uint)x >= MapSizeX() || (uint)y >= MapSizeY()) return INVALID_TILE;
 306         return TileXY(x, y);
 307 }
 308
 309 /**
 310  * Returns the diff between two tiles
 311  *
 312  * @param tile_a from tile
 313  * @param tile_b to tile
 314  * @return the difference between tila_a and tile_b
 315  */
 316 static inline TileIndexDiffC TileIndexToTileIndexDiffC(TileIndex tile_a, TileIndex tile_b)
 317 {
 318         TileIndexDiffC difference;
 319
 320         difference.x = TileX(tile_a) - TileX(tile_b);
 321         difference.y = TileY(tile_a) - TileY(tile_b);
 322
 323         return difference;
 324 }
 325
 326 /* Functions to calculate distances */
 327 uint DistanceManhattan(TileIndex, TileIndex); ///< also known as L1-Norm. Is the shortest distance one could go over diagonal tracks (or roads)
 328 uint DistanceSquare(TileIndex, TileIndex); ///< euclidian- or L2-Norm squared
 329 uint DistanceMax(TileIndex, TileIndex); ///< also known as L-Infinity-Norm
 330 uint DistanceMaxPlusManhattan(TileIndex, TileIndex); ///< Max + Manhattan
 331 uint DistanceFromEdge(TileIndex); ///< shortest distance from any edge of the map
 332 uint DistanceFromEdgeDir(TileIndex, DiagDirection); ///< distance from the map edge in given direction
 333
 334 /**
 335  * Convert a DiagDirection to a TileIndexDiff
 336  *
 337  * @param dir The DiagDirection
 338  * @return The resulting TileIndexDiff
 339  * @see TileIndexDiffCByDiagDir
 340  */
 341 static inline TileIndexDiff TileOffsByDiagDir(DiagDirection dir)
 342 {
 343         extern const TileIndexDiffC _tileoffs_by_diagdir[DIAGDIR_END];
 344
 345         assert(IsValidDiagDirection(dir));
 346         return ToTileIndexDiff(_tileoffs_by_diagdir[dir]);
 347 }
 348
 349 /**
 350  * Convert a Direction to a TileIndexDiff.
 351  *
 352  * @param dir The direction to convert from
 353  * @return The resulting TileIndexDiff
 354  */
 355 static inline TileIndexDiff TileOffsByDir(Direction dir)
 356 {
 357         extern const TileIndexDiffC _tileoffs_by_dir[DIR_END];
 358
 359         assert(IsValidDirection(dir));
 360         return ToTileIndexDiff(_tileoffs_by_dir[dir]);
 361 }
 362
 363 /**
 364  * Adds a Direction to a tile.
 365  *
 366  * @param tile The current tile
 367  * @param dir The direction in which we want to step
 368  * @return the moved tile
 369  */
 370 static inline TileIndex TileAddByDir(TileIndex tile, Direction dir)
 371 {
 372         return TILE_ADD(tile, TileOffsByDir(dir));
 373 }
 374
 375 /**
 376  * Adds a DiagDir to a tile.
 377  *
 378  * @param tile The current tile
 379  * @param dir The direction in which we want to step
 380  * @return the moved tile
 381  */
 382 static inline TileIndex TileAddByDiagDir(TileIndex tile, DiagDirection dir)
 383 {
 384         return TILE_ADD(tile, TileOffsByDiagDir(dir));
 385 }
 386
 387 /**
 388  * Determines the DiagDirection to get from one tile to another.
 389  * The tiles do not necessarily have to be adjacent.
 390  * @param tile_from Origin tile
 391  * @param tile_to Destination tile
 392  * @return DiagDirection from tile_from towards tile_to, or INVALID_DIAGDIR if the tiles are not on an axis
 393  */
 394 static inline DiagDirection DiagdirBetweenTiles(TileIndex tile_from, TileIndex tile_to)
 395 {
 396         int dx = (int)TileX(tile_to) - (int)TileX(tile_from);
 397         int dy = (int)TileY(tile_to) - (int)TileY(tile_from);
 398         if (dx == 0) {
 399                 if (dy == 0) return INVALID_DIAGDIR;
 400                 return (dy < 0 ? DIAGDIR_NW : DIAGDIR_SE);
 401         } else {
 402                 if (dy != 0) return INVALID_DIAGDIR;
 403                 return (dx < 0 ? DIAGDIR_NE : DIAGDIR_SW);
 404         }
 405 }
 406
 407 /**
 408  * A callback function type for searching tiles.
 409  *
 410  * @param tile The tile to test
 411  * @param user_data additional data for the callback function to use
 412  * @return A boolean value, depend on the definition of the function.
 413  */
 414 typedef bool TestTileOnSearchProc(TileIndex tile, void *user_data);
 415
 416 bool CircularTileSearch(TileIndex *tile, uint size, TestTileOnSearchProc proc, void *user_data);
 417 bool CircularTileSearch(TileIndex *tile, uint radius, uint w, uint h, TestTileOnSearchProc proc, void *user_data);
 418
 419 /**
 420  * Get a random tile out of a given seed.
 421  * @param r the random 'seed'
 422  * @return a valid tile
 423  */
 424 static inline TileIndex RandomTileSeed(uint32 r)
 425 {
 426         return TILE_MASK(r);
 427 }
 428
 429 /**
 430  * Get a valid random tile.
 431  * @note a define so 'random' gets inserted in the place where it is actually
 432  *       called, thus making the random traces more explicit.
 433  * @return a valid tile
 434  */
 435 #define RandomTile() RandomTileSeed(Random())
 436
 437 uint GetClosestWaterDistance(TileIndex tile, bool water);
 438
 439 #endif /* MAP_FUNC_H */