OpenTTD Source  20241108-master-g80f628063a
map_func.h
Go to the documentation of this file.
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 
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 
25 class Tile {
26 private:
27  friend struct Map;
32  struct TileBase {
33  uint8_t type;
34  uint8_t height;
35  uint16_t m2;
36  uint8_t m1;
37  uint8_t m3;
38  uint8_t m4;
39  uint8_t m5;
40  };
41 
42  static_assert(sizeof(TileBase) == 8);
43 
48  struct TileExtended {
49  uint8_t m6;
50  uint8_t m7;
51  uint16_t m8;
52  };
53 
54  static TileBase *base_tiles;
56 
58 
59 public:
64  debug_inline Tile(TileIndex tile) : tile(tile) {}
65 
70  Tile(uint tile) : tile(tile) {}
71 
75  debug_inline constexpr operator TileIndex() const { return tile; }
76 
80  debug_inline constexpr operator uint() const { return tile.base(); }
81 
89  debug_inline uint8_t &type()
90  {
91  return base_tiles[tile.base()].type;
92  }
93 
101  debug_inline uint8_t &height()
102  {
103  return base_tiles[tile.base()].height;
104  }
105 
113  debug_inline uint8_t &m1()
114  {
115  return base_tiles[tile.base()].m1;
116  }
117 
125  debug_inline uint16_t &m2()
126  {
127  return base_tiles[tile.base()].m2;
128  }
129 
137  debug_inline uint8_t &m3()
138  {
139  return base_tiles[tile.base()].m3;
140  }
141 
149  debug_inline uint8_t &m4()
150  {
151  return base_tiles[tile.base()].m4;
152  }
153 
161  debug_inline uint8_t &m5()
162  {
163  return base_tiles[tile.base()].m5;
164  }
165 
173  debug_inline uint8_t &m6()
174  {
175  return extended_tiles[tile.base()].m6;
176  }
177 
185  debug_inline uint8_t &m7()
186  {
187  return extended_tiles[tile.base()].m7;
188  }
189 
197  debug_inline uint16_t &m8()
198  {
199  return extended_tiles[tile.base()].m8;
200  }
201 };
202 
206 struct Map {
207 private:
211  struct Iterator {
212  typedef Tile value_type;
213  typedef Tile *pointer;
214  typedef Tile &reference;
215  typedef size_t difference_type;
216  typedef std::forward_iterator_tag iterator_category;
217 
218  explicit Iterator(TileIndex index) : index(index) {}
219  bool operator==(const Iterator &other) const { return this->index == other.index; }
220  bool operator!=(const Iterator &other) const { return !(*this == other); }
221  Tile operator*() const { return this->index; }
222  Iterator & operator++() { this->index++; return *this; }
223  private:
224  TileIndex index;
225  };
226 
227  /*
228  * Iterable ensemble of all Tiles
229  */
230  struct IterateWrapper {
231  Iterator begin() { return Iterator(0); }
232  Iterator end() { return Iterator(Map::Size()); }
233  bool empty() { return false; }
234  };
235 
236  static uint log_x;
237  static uint log_y;
238  static uint size_x;
239  static uint size_y;
240  static uint size;
241  static uint tile_mask;
242 
243 public:
244  static void Allocate(uint size_x, uint size_y);
245 
251  debug_inline static uint LogX()
252  {
253  return Map::log_x;
254  }
255 
261  static inline uint LogY()
262  {
263  return Map::log_y;
264  }
265 
270  debug_inline static uint SizeX()
271  {
272  return Map::size_x;
273  }
274 
279  static inline uint SizeY()
280  {
281  return Map::size_y;
282  }
283 
288  debug_inline static uint Size()
289  {
290  return Map::size;
291  }
292 
297  debug_inline static uint MaxX()
298  {
299  return Map::SizeX() - 1;
300  }
301 
306  static inline uint MaxY()
307  {
308  return Map::SizeY() - 1;
309  }
310 
311 
317  static inline TileIndex WrapToMap(TileIndex tile)
318  {
319  return tile.base() & Map::tile_mask;
320  }
321 
328  static inline uint ScaleBySize(uint n)
329  {
330  /* Subtract 12 from shift in order to prevent integer overflow
331  * for large values of n. It's safe since the min mapsize is 64x64. */
332  return CeilDiv(n << (Map::LogX() + Map::LogY() - 12), 1 << 4);
333  }
334 
341  static inline uint ScaleBySize1D(uint n)
342  {
343  /* Normal circumference for the X+Y is 256+256 = 1<<9
344  * Note, not actually taking the full circumference into account,
345  * just half of it. */
346  return CeilDiv((n << Map::LogX()) + (n << Map::LogY()), 1 << 9);
347  }
348 
354  static bool IsInitialized()
355  {
356  return Tile::base_tiles != nullptr;
357  }
358 
363  static IterateWrapper Iterate() { return IterateWrapper(); }
364 };
365 
373 debug_inline static TileIndex TileXY(uint x, uint y)
374 {
375  return (y << Map::LogX()) + x;
376 }
377 
389 inline TileIndexDiff TileDiffXY(int x, int y)
390 {
391  /* Multiplication gives much better optimization on MSVC than shifting.
392  * 0 << shift isn't optimized to 0 properly.
393  * Typically x and y are constants, and then this doesn't result
394  * in any actual multiplication in the assembly code.. */
395  return (y * Map::SizeX()) + x;
396 }
397 
404 debug_inline static TileIndex TileVirtXY(uint x, uint y)
405 {
406  return (y >> 4 << Map::LogX()) + (x >> 4);
407 }
408 
409 
415 debug_inline static uint TileX(TileIndex tile)
416 {
417  return tile.base() & Map::MaxX();
418 }
419 
425 debug_inline static uint TileY(TileIndex tile)
426 {
427  return tile.base() >> Map::LogX();
428 }
429 
441 {
442  return TileDiffXY(tidc.x, tidc.y);
443 }
444 
445 
453 #ifndef _DEBUG
454  constexpr TileIndex TileAdd(TileIndex tile, TileIndexDiff offset) { return tile + offset; }
455 #else
457 #endif
458 
467 inline TileIndex TileAddXY(TileIndex tile, int x, int y)
468 {
469  return TileAdd(tile, TileDiffXY(x, y));
470 }
471 
472 TileIndex TileAddWrap(TileIndex tile, int addx, int addy);
473 
481 {
483 
484  assert(IsValidDiagDirection(dir));
485  return _tileoffs_by_diagdir[dir];
486 }
487 
495 {
497 
498  assert(IsValidDirection(dir));
499  return _tileoffs_by_dir[dir];
500 }
501 
513 {
514  int x = TileX(tile) + diff.x;
515  int y = TileY(tile) + diff.y;
516  /* Negative value will become big positive value after cast */
517  if ((uint)x >= Map::SizeX() || (uint)y >= Map::SizeY()) return INVALID_TILE;
518  return TileXY(x, y);
519 }
520 
529 {
530  TileIndexDiffC difference;
531 
532  difference.x = TileX(tile_a) - TileX(tile_b);
533  difference.y = TileY(tile_a) - TileY(tile_b);
534 
535  return difference;
536 }
537 
538 /* Functions to calculate distances */
545 
553 {
554  extern const TileIndexDiffC _tileoffs_by_axis[];
555 
556  assert(IsValidAxis(axis));
557  return ToTileIndexDiff(_tileoffs_by_axis[axis]);
558 }
559 
568 {
570 
571  assert(IsValidDiagDirection(dir));
573 }
574 
582 {
584 
585  assert(IsValidDirection(dir));
586  return ToTileIndexDiff(_tileoffs_by_dir[dir]);
587 }
588 
597 {
598  return TileAdd(tile, TileOffsByDir(dir));
599 }
600 
609 {
610  return TileAdd(tile, TileOffsByDiagDir(dir));
611 }
612 
621 {
622  int dx = (int)TileX(tile_to) - (int)TileX(tile_from);
623  int dy = (int)TileY(tile_to) - (int)TileY(tile_from);
624  if (dx == 0) {
625  if (dy == 0) return INVALID_DIAGDIR;
626  return (dy < 0 ? DIAGDIR_NW : DIAGDIR_SE);
627  } else {
628  if (dy != 0) return INVALID_DIAGDIR;
629  return (dx < 0 ? DIAGDIR_NE : DIAGDIR_SW);
630  }
631 }
632 
640 typedef bool TestTileOnSearchProc(TileIndex tile, void *user_data);
641 
642 bool CircularTileSearch(TileIndex *tile, uint size, TestTileOnSearchProc proc, void *user_data);
643 bool CircularTileSearch(TileIndex *tile, uint radius, uint w, uint h, TestTileOnSearchProc proc, void *user_data);
644 
650 inline TileIndex RandomTileSeed(uint32_t r)
651 {
652  return Map::WrapToMap(r);
653 }
654 
661 #define RandomTile() RandomTileSeed(Random())
662 
663 uint GetClosestWaterDistance(TileIndex tile, bool water);
664 
665 #endif /* MAP_FUNC_H */
Wrapper class to abstract away the way the tiles are stored.
Definition: map_func.h:25
static TileBase * base_tiles
Pointer to the tile-array.
Definition: map_func.h:54
debug_inline uint16_t & m8()
General purpose.
Definition: map_func.h:197
debug_inline uint8_t & m7()
Primarily used for newgrf support.
Definition: map_func.h:185
debug_inline Tile(TileIndex tile)
Create the tile wrapper for the given tile.
Definition: map_func.h:64
debug_inline uint8_t & type()
The type (bits 4..7), bridges (2..3), rainforest/desert (0..1)
Definition: map_func.h:89
debug_inline uint8_t & m5()
General purpose.
Definition: map_func.h:161
debug_inline uint8_t & m1()
Primarily used for ownership information.
Definition: map_func.h:113
debug_inline uint8_t & m4()
General purpose.
Definition: map_func.h:149
debug_inline uint8_t & height()
The height of the northern corner.
Definition: map_func.h:101
debug_inline uint16_t & m2()
Primarily used for indices to towns, industries and stations.
Definition: map_func.h:125
Tile(uint tile)
Create the tile wrapper for the given tile.
Definition: map_func.h:70
static TileExtended * extended_tiles
Pointer to the extended tile-array.
Definition: map_func.h:55
debug_inline uint8_t & m6()
General purpose.
Definition: map_func.h:173
debug_inline uint8_t & m3()
General purpose.
Definition: map_func.h:137
TileIndex tile
The tile to access the map data for.
Definition: map_func.h:57
Different functions related to conversions between directions.
bool IsValidAxis(Axis d)
Checks if an integer value is a valid Axis.
bool IsValidDiagDirection(DiagDirection d)
Checks if an integer value is a valid DiagDirection.
bool IsValidDirection(Direction d)
Checks if an integer value is a valid Direction.
Direction
Defines the 8 directions on the map.
@ DIR_END
Used to iterate.
Axis
Allow incrementing of DiagDirDiff variables.
DiagDirection
Enumeration for diagonal directions.
@ DIAGDIR_NE
Northeast, upper right on your monitor.
@ DIAGDIR_NW
Northwest.
@ DIAGDIR_SE
Southeast.
@ DIAGDIR_END
Used for iterations.
@ INVALID_DIAGDIR
Flag for an invalid DiagDirection.
@ DIAGDIR_SW
Southwest.
const TileIndexDiffC _tileoffs_by_axis[]
'Lookup table' for tile offsets given an Axis
const TileIndexDiffC _tileoffs_by_dir[]
'Lookup table' for tile offsets given a Direction
const TileIndexDiffC _tileoffs_by_diagdir[]
'Lookup table' for tile offsets given a DiagDirection
bool CircularTileSearch(TileIndex *tile, uint size, TestTileOnSearchProc proc, void *user_data)
Function performing a search around a center tile and going outward, thus in circle.
Definition: map.cpp:247
DiagDirection DiagdirBetweenTiles(TileIndex tile_from, TileIndex tile_to)
Determines the DiagDirection to get from one tile to another.
Definition: map_func.h:620
TileIndex TileAddXY(TileIndex tile, int x, int y)
Adds a given offset to a tile.
Definition: map_func.h:467
uint DistanceMaxPlusManhattan(TileIndex, TileIndex)
Max + Manhattan.
Definition: map.cpp:194
TileIndex AddTileIndexDiffCWrap(TileIndex tile, TileIndexDiffC diff)
Add a TileIndexDiffC to a TileIndex and returns the new one.
Definition: map_func.h:512
TileIndex TileAddByDir(TileIndex tile, Direction dir)
Adds a Direction to a tile.
Definition: map_func.h:596
static debug_inline TileIndex TileXY(uint x, uint y)
Returns the TileIndex of a coordinate.
Definition: map_func.h:373
TileIndexDiff ToTileIndexDiff(TileIndexDiffC tidc)
Return the offset between two tiles from a TileIndexDiffC struct.
Definition: map_func.h:440
TileIndex TileAddByDiagDir(TileIndex tile, DiagDirection dir)
Adds a DiagDir to a tile.
Definition: map_func.h:608
uint DistanceMax(TileIndex, TileIndex)
also known as L-Infinity-Norm
Definition: map.cpp:178
TileIndex RandomTileSeed(uint32_t r)
Get a random tile out of a given seed.
Definition: map_func.h:650
TileIndexDiff TileDiffXY(int x, int y)
Calculates an offset for the given coordinate(-offset).
Definition: map_func.h:389
TileIndexDiff TileOffsByAxis(Axis axis)
Convert an Axis to a TileIndexDiff.
Definition: map_func.h:552
uint DistanceFromEdgeDir(TileIndex, DiagDirection)
distance from the map edge in given direction
Definition: map.cpp:223
uint DistanceFromEdge(TileIndex)
shortest distance from any edge of the map
Definition: map.cpp:206
TileIndex TileAddWrap(TileIndex tile, int addx, int addy)
This function checks if we add addx/addy to tile, if we do wrap around the edges.
Definition: map.cpp:97
uint DistanceSquare(TileIndex, TileIndex)
euclidian- or L2-Norm squared
Definition: map.cpp:163
TileIndexDiffC TileIndexDiffCByDiagDir(DiagDirection dir)
Returns the TileIndexDiffC offset from a DiagDirection.
Definition: map_func.h:480
uint GetClosestWaterDistance(TileIndex tile, bool water)
Finds the distance for the closest tile with water/land given a tile.
Definition: map.cpp:329
uint DistanceManhattan(TileIndex, TileIndex)
also known as L1-Norm. Is the shortest distance one could go over diagonal tracks (or roads)
Definition: map.cpp:146
constexpr TileIndex TileAdd(TileIndex tile, TileIndexDiff offset)
Adds a given offset to a tile.
Definition: map_func.h:454
bool TestTileOnSearchProc(TileIndex tile, void *user_data)
A callback function type for searching tiles.
Definition: map_func.h:640
TileIndexDiffC TileIndexDiffCByDir(Direction dir)
Returns the TileIndexDiffC offset from a Direction.
Definition: map_func.h:494
TileIndexDiff TileOffsByDir(Direction dir)
Convert a Direction to a TileIndexDiff.
Definition: map_func.h:581
static debug_inline uint TileY(TileIndex tile)
Get the Y component of a tile.
Definition: map_func.h:425
static debug_inline uint TileX(TileIndex tile)
Get the X component of a tile.
Definition: map_func.h:415
TileIndexDiff TileOffsByDiagDir(DiagDirection dir)
Convert a DiagDirection to a TileIndexDiff.
Definition: map_func.h:567
TileIndexDiffC TileIndexToTileIndexDiffC(TileIndex tile_a, TileIndex tile_b)
Returns the diff between two tiles.
Definition: map_func.h:528
static debug_inline TileIndex TileVirtXY(uint x, uint y)
Get a tile from the virtual XY-coordinate.
Definition: map_func.h:404
Types related to maps.
int32_t TileIndexDiff
An offset value between two tiles.
Definition: map_type.h:23
Integer math functions.
constexpr uint CeilDiv(uint a, uint b)
Computes ceil(a / b) for non-negative a and b.
Definition: math_func.hpp:320
Iterator to iterate all Tiles.
Definition: map_func.h:211
Size related data of the map.
Definition: map_func.h:206
static TileIndex WrapToMap(TileIndex tile)
'Wraps' the given "tile" so it is within the map.
Definition: map_func.h:317
static uint ScaleBySize(uint n)
Scales the given value by the map size, where the given value is for a 256 by 256 map.
Definition: map_func.h:328
static uint SizeY()
Get the size of the map along the Y.
Definition: map_func.h:279
static IterateWrapper Iterate()
Returns an iterable ensemble of all Tiles.
Definition: map_func.h:363
static uint size
The number of tiles on the map.
Definition: map_func.h:240
static debug_inline uint SizeX()
Get the size of the map along the X.
Definition: map_func.h:270
static debug_inline uint LogX()
Logarithm of the map size along the X side.
Definition: map_func.h:251
static uint size_x
Size of the map along the X.
Definition: map_func.h:238
static uint tile_mask
_map_size - 1 (to mask the mapsize)
Definition: map_func.h:241
static uint size_y
Size of the map along the Y.
Definition: map_func.h:239
static uint ScaleBySize1D(uint n)
Scales the given value by the maps circumference, where the given value is for a 256 by 256 map.
Definition: map_func.h:341
static uint LogY()
Logarithm of the map size along the y side.
Definition: map_func.h:261
static bool IsInitialized()
Check whether the map has been initialized, as to not try to save the map during crashlog when the ma...
Definition: map_func.h:354
static uint MaxY()
Gets the maximum Y coordinate within the map, including MP_VOID.
Definition: map_func.h:306
static uint log_y
2^_map_log_y == _map_size_y
Definition: map_func.h:237
static uint log_x
2^_map_log_x == _map_size_x
Definition: map_func.h:236
static void Allocate(uint size_x, uint size_y)
(Re)allocates a map with the given dimension
Definition: map.cpp:36
static debug_inline uint Size()
Get the size of the map.
Definition: map_func.h:288
static debug_inline uint MaxX()
Gets the maximum X coordinate within the map, including MP_VOID.
Definition: map_func.h:297
A pair-construct of a TileIndexDiff.
Definition: map_type.h:31
int16_t x
The x value of the coordinate.
Definition: map_type.h:32
int16_t y
The y value of the coordinate.
Definition: map_type.h:33
Data that is stored per tile.
Definition: map_func.h:32
uint8_t m3
General purpose.
Definition: map_func.h:37
uint8_t m4
General purpose.
Definition: map_func.h:38
uint8_t type
The type (bits 4..7), bridges (2..3), rainforest/desert (0..1)
Definition: map_func.h:33
uint8_t m5
General purpose.
Definition: map_func.h:39
uint8_t height
The height of the northern corner.
Definition: map_func.h:34
uint8_t m1
Primarily used for ownership information.
Definition: map_func.h:36
uint16_t m2
Primarily used for indices to towns, industries and stations.
Definition: map_func.h:35
Data that is stored per tile.
Definition: map_func.h:48
uint8_t m6
General purpose.
Definition: map_func.h:49
uint8_t m7
Primarily used for newgrf support.
Definition: map_func.h:50
uint16_t m8
General purpose.
Definition: map_func.h:51
Types related to tiles.
constexpr TileIndex INVALID_TILE
The very nice invalid tile marker.
Definition: tile_type.h:95
StrongType::Typedef< uint32_t, struct TileIndexTag, StrongType::Compare, StrongType::Integer, StrongType::Compatible< int32_t >, StrongType::Compatible< int64_t > > TileIndex
The index/ID of a Tile.
Definition: tile_type.h:87