src/map_func.h

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