src/map/coord.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/coord.h Map coordinate system. */
   9
  10 #ifndef MAP_COORD_H
  11 #define MAP_COORD_H
  12
  13 #include "../stdafx.h"
  14 #include "../core/math_func.hpp"
  15 #include "map.h"
  16 #include "../direction_type.h"
  17 #include "../direction_func.h"
  18 #include "../settings_type.h"
  19
  20 /**
  21  * The index/ID of a Tile.
  22  */
  23 typedef uint32 TileIndex;
  24
  25 /**
  26  * The very nice invalid tile marker
  27  */
  28 static const TileIndex INVALID_TILE = (TileIndex)-1;
  29
  30 /**
  31  * Get the X component of a tile
  32  * @param tile the tile to get the X component of
  33  * @return the X component
  34  */
  35 static inline uint TileX(TileIndex tile)
  36 {
  37         return tile & MapMaxX();
  38 }
  39
  40 /**
  41  * Get the Y component of a tile
  42  * @param tile the tile to get the Y component of
  43  * @return the Y component
  44  */
  45 static inline uint TileY(TileIndex tile)
  46 {
  47         return tile >> MapLogX();
  48 }
  49
  50 /**
  51  * Returns the TileIndex of a coordinate.
  52  *
  53  * @param x The x coordinate of the tile
  54  * @param y The y coordinate of the tile
  55  * @return The TileIndex calculated by the coordinate
  56  */
  57 static inline TileIndex TileXY(uint x, uint y)
  58 {
  59         return (y << MapLogX()) + x;
  60 }
  61
  62 /**
  63  * Check if a tile is within the map (not a border)
  64  *
  65  * @param x The x coordinate of the tile
  66  * @param y The y coordinate of the tile
  67  * @return Whether the tile is in the interior of the map
  68  */
  69 static inline bool IsInnerTileXY(uint x, uint y)
  70 {
  71         return x < MapMaxX() && y < MapMaxY() && ((x > 0 && y > 0) || !_settings_game.construction.freeform_edges);
  72 }
  73
  74 /**
  75  * Check if a tile is within the map (not a border)
  76  *
  77  * @param tile The tile to check
  78  * @return Whether the tile is in the interior of the map
  79  * @pre tile < MapSize()
  80  */
  81 static inline bool IsInnerTile(TileIndex tile)
  82 {
  83         assert(tile < MapSize());
  84
  85         return IsInnerTileXY(TileX(tile), TileY(tile));
  86 }
  87
  88
  89 /**
  90  * An offset value between two tiles.
  91  *
  92  * This value is used for the difference between
  93  * two tiles. It can be added to a tileindex to get
  94  * the resulting tileindex of the start tile applied
  95  * with this saved difference.
  96  *
  97  * @see TileDiffXY(int, int)
  98  */
  99 typedef int32 TileIndexDiff;
 100
 101 /**
 102  * Calculates an offset for the given coordinate(-offset).
 103  *
 104  * This function calculate an offset value which can be added to an
 105  * #TileIndex. The coordinates can be negative.
 106  *
 107  * @param x The offset in x direction
 108  * @param y The offset in y direction
 109  * @return The resulting offset value of the given coordinate
 110  * @see ToTileIndexDiff(CoordDiff)
 111  */
 112 static inline TileIndexDiff TileDiffXY(int x, int y)
 113 {
 114         /* Multiplication gives much better optimization on MSVC than shifting.
 115          * 0 << shift isn't optimized to 0 properly.
 116          * Typically x and y are constants, and then this doesn't result
 117          * in any actual multiplication in the assembly code.. */
 118         return (y * MapSizeX()) + x;
 119 }
 120
 121 #ifndef _DEBUG
 122         /**
 123          * Adds two tiles together.
 124          *
 125          * @param x One tile
 126          * @param y Another tile to add
 127          * @return The resulting tile(index)
 128          */
 129         #define TILE_ADD(x, y) ((x) + (y))
 130 #else
 131         extern TileIndex TileAdd(TileIndex tile, TileIndexDiff add,
 132                 const char *exp, const char *file, int line);
 133         #define TILE_ADD(x, y) (TileAdd((x), (y), #x " + " #y, __FILE__, __LINE__))
 134 #endif
 135
 136 /**
 137  * Adds a given offset to a tile.
 138  *
 139  * @param tile The tile to add an offset on it
 140  * @param x The x offset to add to the tile
 141  * @param y The y offset to add to the tile
 142  */
 143 #define TILE_ADDXY(tile, x, y) TILE_ADD(tile, TileDiffXY(x, y))
 144
 145 TileIndex TileAddWrap(TileIndex tile, int addx, int addy);
 146
 147
 148 /**
 149  * A pair-construct of a TileIndexDiff.
 150  *
 151  * This can be used to save the difference between to
 152  * tiles as a pair of x and y value.
 153  */
 154 struct CoordDiff {
 155         int16 x;        ///< The x value of the coordinate
 156         int16 y;        ///< The y value of the coordinate
 157 };
 158
 159 /**
 160  * Return the offset between to tiles from a CoordDiff struct.
 161  *
 162  * This function works like #TileDiffXY(int, int) and returns the
 163  * difference between two tiles.
 164  *
 165  * @param diff The coordinate of the offset as CoordDiff
 166  * @return The difference between two tiles.
 167  * @see TileDiffXY(int, int)
 168  */
 169 static inline TileIndexDiff ToTileIndexDiff(CoordDiff diff)
 170 {
 171         return (diff.y << MapLogX()) + diff.x;
 172 }
 173
 174 /**
 175  * Add a CoordDiff to a TileIndex and returns the new one.
 176  *
 177  * Returns tile + the diff given in diff. If the result tile would end up
 178  * outside of the map, INVALID_TILE is returned instead.
 179  *
 180  * @param tile The base tile to add the offset on
 181  * @param diff The offset to add on the tile
 182  * @return The resulting TileIndex
 183  */
 184 static inline TileIndex AddCoordDiffWrap(TileIndex tile, CoordDiff diff)
 185 {
 186         int x = TileX(tile) + diff.x;
 187         int y = TileY(tile) + diff.y;
 188         /* Negative value will become big positive value after cast */
 189         if ((uint)x >= MapSizeX() || (uint)y >= MapSizeY()) return INVALID_TILE;
 190         return TileXY(x, y);
 191 }
 192
 193 /**
 194  * Returns the diff between two tiles
 195  *
 196  * @param tile_a from tile
 197  * @param tile_b to tile
 198  * @return the difference between tila_a and tile_b
 199  */
 200 static inline CoordDiff TileCoordDiff(TileIndex tile_a, TileIndex tile_b)
 201 {
 202         CoordDiff difference;
 203
 204         difference.x = TileX(tile_a) - TileX(tile_b);
 205         difference.y = TileY(tile_a) - TileY(tile_b);
 206
 207         return difference;
 208 }
 209
 210 /**
 211  * Returns the CoordDiff offset from a DiagDirection.
 212  *
 213  * @param dir The given direction
 214  * @return The offset as CoordDiff value
 215  */
 216 static inline CoordDiff CoordDiffByDiagDir(DiagDirection dir)
 217 {
 218         extern const CoordDiff _tileoffs_by_diagdir[DIAGDIR_END];
 219
 220         assert(IsValidDiagDirection(dir));
 221         return _tileoffs_by_diagdir[dir];
 222 }
 223
 224 /**
 225  * Returns the CoordDiff offset from a Direction.
 226  *
 227  * @param dir The given direction
 228  * @return The offset as CoordDiff value
 229  */
 230 static inline CoordDiff CoordDiffByDir(Direction dir)
 231 {
 232         extern const CoordDiff _tileoffs_by_dir[DIR_END];
 233
 234         assert(IsValidDirection(dir));
 235         return _tileoffs_by_dir[dir];
 236 }
 237
 238
 239 /**
 240  * Convert a DiagDirection to a TileIndexDiff
 241  *
 242  * @param dir The DiagDirection
 243  * @return The resulting TileIndexDiff
 244  * @see CoordDiffByDiagDir
 245  */
 246 static inline TileIndexDiff TileOffsByDiagDir(DiagDirection dir)
 247 {
 248         extern MapSizeParams map_size;
 249
 250         assert(IsValidDiagDirection(dir));
 251         return map_size.diffs[DiagDirToDir(dir)];
 252 }
 253
 254 /**
 255  * Convert a Direction to a TileIndexDiff.
 256  *
 257  * @param dir The direction to convert from
 258  * @return The resulting TileIndexDiff
 259  */
 260 static inline TileIndexDiff TileOffsByDir(Direction dir)
 261 {
 262         extern MapSizeParams map_size;
 263
 264         assert(IsValidDirection(dir));
 265         return map_size.diffs[dir];
 266 }
 267
 268 /**
 269  * Adds a DiagDir to a tile.
 270  *
 271  * @param tile The current tile
 272  * @param dir The direction in which we want to step
 273  * @return the moved tile
 274  */
 275 static inline TileIndex TileAddByDiagDir(TileIndex tile, DiagDirection dir)
 276 {
 277         return TILE_ADD(tile, TileOffsByDiagDir(dir));
 278 }
 279
 280
 281 /**
 282  * Determines the DiagDirection to get from one tile to another.
 283  * The tiles do not necessarily have to be adjacent.
 284  * @param tile_from Origin tile
 285  * @param tile_to Destination tile
 286  * @return DiagDirection from tile_from towards tile_to, or INVALID_DIAGDIR if the tiles are not on an axis
 287  */
 288 static inline DiagDirection DiagdirBetweenTiles(TileIndex tile_from, TileIndex tile_to)
 289 {
 290         int dx = (int)TileX(tile_to) - (int)TileX(tile_from);
 291         int dy = (int)TileY(tile_to) - (int)TileY(tile_from);
 292         if (dx == 0) {
 293                 if (dy == 0) return INVALID_DIAGDIR;
 294                 return (dy < 0 ? DIAGDIR_NW : DIAGDIR_SE);
 295         } else {
 296                 if (dy != 0) return INVALID_DIAGDIR;
 297                 return (dx < 0 ? DIAGDIR_NE : DIAGDIR_SW);
 298         }
 299 }
 300
 301
 302 /* Functions to calculate distances */
 303 uint DistanceManhattan(TileIndex, TileIndex); ///< also known as L1-Norm. Is the shortest distance one could go over diagonal tracks (or roads)
 304 uint DistanceSquare(TileIndex, TileIndex); ///< euclidian- or L2-Norm squared
 305 uint DistanceMax(TileIndex, TileIndex); ///< also known as L-Infinity-Norm
 306 uint DistanceMaxPlusManhattan(TileIndex, TileIndex); ///< Max + Manhattan
 307 uint DistanceFromEdge(TileIndex); ///< shortest distance from any edge of the map
 308 uint DistanceFromEdgeDir(TileIndex, DiagDirection); ///< distance from the map edge in given direction
 309
 310 /**
 311  * Compute the distance between two tiles, when the difference between
 312  * the tiles is parallel to one of the axes.
 313  */
 314 static inline uint DistanceAlongAxis(TileIndex t1, TileIndex t2)
 315 {
 316         int x1 = TileX(t1);
 317         int y1 = TileY(t1);
 318         int x2 = TileX(t2);
 319         int y2 = TileY(t2);
 320
 321         assert((x1 == x2) || (y1 == y2));
 322
 323         return abs(x2 + y2 - x1 - y1);
 324 }
 325
 326
 327 /**
 328  * Calculate a hash value from a tile position
 329  *
 330  * @param x The X coordinate
 331  * @param y The Y coordinate
 332  * @return The hash of the tile
 333  */
 334 static inline uint TileHash(uint x, uint y)
 335 {
 336         uint hash = x >> 4;
 337         hash ^= x >> 6;
 338         hash ^= y >> 4;
 339         hash -= y >> 6;
 340         return hash;
 341 }
 342
 343 /**
 344  * Get the last two bits of the TileHash
 345  *  from a tile position.
 346  *
 347  * @see TileHash()
 348  * @param x The X coordinate
 349  * @param y The Y coordinate
 350  * @return The last two bits from hash of the tile
 351  */
 352 static inline uint TileHash2Bit(uint x, uint y)
 353 {
 354         return GB(TileHash(x, y), 0, 2);
 355 }
 356
 357 /**
 358  * Get a random tile out of a given seed.
 359  * @param r the random 'seed'
 360  * @return a valid tile
 361  */
 362 static inline TileIndex RandomTileSeed(uint32 r)
 363 {
 364         return TILE_MASK(r);
 365 }
 366
 367 /**
 368  * Get a valid random tile.
 369  * @note a define so 'random' gets inserted in the place where it is actually
 370  *       called, thus making the random traces more explicit.
 371  * @return a valid tile
 372  */
 373 #define RandomTile() RandomTileSeed(Random())
 374
 375 #endif /* MAP_COORD_H */