OpenTTD Source  20241120-master-g6d3adc6169
map.cpp
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 #include "stdafx.h"
11 #include "debug.h"
12 #include "core/alloc_func.hpp"
13 #include "water_map.h"
14 #include "error_func.h"
15 #include "string_func.h"
17 
18 #include "safeguards.h"
19 
20 /* static */ uint Map::log_x;
21 /* static */ uint Map::log_y;
22 /* static */ uint Map::size_x;
23 /* static */ uint Map::size_y;
24 /* static */ uint Map::size;
25 /* static */ uint Map::tile_mask;
26 
27 /* static */ Tile::TileBase *Tile::base_tiles = nullptr;
28 /* static */ Tile::TileExtended *Tile::extended_tiles = nullptr;
29 
30 
36 /* static */ void Map::Allocate(uint size_x, uint size_y)
37 {
38  /* Make sure that the map size is within the limits and that
39  * size of both axes is a power of 2. */
42  (size_x & (size_x - 1)) != 0 ||
43  (size_y & (size_y - 1)) != 0) {
44  FatalError("Invalid map size");
45  }
46 
47  Debug(map, 1, "Allocating map of size {}x{}", size_x, size_y);
48 
55 
58 
59  Tile::base_tiles = CallocT<Tile::TileBase>(Map::size);
60  Tile::extended_tiles = CallocT<Tile::TileExtended>(Map::size);
61 
63 }
64 
65 
66 #ifdef _DEBUG
68 {
69  int dx = offset & Map::MaxX();
70  if (dx >= (int)Map::SizeX() / 2) dx -= Map::SizeX();
71  int dy = (offset - dx) / (int)Map::SizeX();
72 
73  uint32_t x = TileX(tile) + dx;
74  uint32_t y = TileY(tile) + dy;
75 
76  assert(x < Map::SizeX());
77  assert(y < Map::SizeY());
78  assert(TileXY(x, y) == Map::WrapToMap(tile + offset));
79 
80  return TileXY(x, y);
81 }
82 #endif
83 
97 TileIndex TileAddWrap(TileIndex tile, int addx, int addy)
98 {
99  uint x = TileX(tile) + addx;
100  uint y = TileY(tile) + addy;
101 
102  /* Disallow void tiles at the north border. */
103  if ((x == 0 || y == 0) && _settings_game.construction.freeform_edges) return INVALID_TILE;
104 
105  /* Are we about to wrap? */
106  if (x >= Map::MaxX() || y >= Map::MaxY()) return INVALID_TILE;
107 
108  return TileXY(x, y);
109 }
110 
112 extern const TileIndexDiffC _tileoffs_by_axis[] = {
113  { 1, 0},
114  { 0, 1},
115 };
116 
118 extern const TileIndexDiffC _tileoffs_by_diagdir[] = {
119  {-1, 0},
120  { 0, 1},
121  { 1, 0},
122  { 0, -1}
123 };
124 
126 extern const TileIndexDiffC _tileoffs_by_dir[] = {
127  {-1, -1},
128  {-1, 0},
129  {-1, 1},
130  { 0, 1},
131  { 1, 1},
132  { 1, 0},
133  { 1, -1},
134  { 0, -1}
135 };
136 
147 {
148  const uint dx = Delta(TileX(t0), TileX(t1));
149  const uint dy = Delta(TileY(t0), TileY(t1));
150  return dx + dy;
151 }
152 
153 
164 {
165  const int dx = TileX(t0) - TileX(t1);
166  const int dy = TileY(t0) - TileY(t1);
167  return dx * dx + dy * dy;
168 }
169 
170 
179 {
180  const uint dx = Delta(TileX(t0), TileX(t1));
181  const uint dy = Delta(TileY(t0), TileY(t1));
182  return std::max(dx, dy);
183 }
184 
185 
195 {
196  const uint dx = Delta(TileX(t0), TileX(t1));
197  const uint dy = Delta(TileY(t0), TileY(t1));
198  return dx > dy ? 2 * dx + dy : 2 * dy + dx;
199 }
200 
207 {
208  const uint xl = TileX(tile);
209  const uint yl = TileY(tile);
210  const uint xh = Map::SizeX() - 1 - xl;
211  const uint yh = Map::SizeY() - 1 - yl;
212  const uint minl = std::min(xl, yl);
213  const uint minh = std::min(xh, yh);
214  return std::min(minl, minh);
215 }
216 
224 {
225  switch (dir) {
226  case DIAGDIR_NE: return TileX(tile) - (_settings_game.construction.freeform_edges ? 1 : 0);
227  case DIAGDIR_NW: return TileY(tile) - (_settings_game.construction.freeform_edges ? 1 : 0);
228  case DIAGDIR_SW: return Map::MaxX() - TileX(tile) - 1;
229  case DIAGDIR_SE: return Map::MaxY() - TileY(tile) - 1;
230  default: NOT_REACHED();
231  }
232 }
233 
247 bool CircularTileSearch(TileIndex *tile, uint size, TestTileOnSearchProc proc, void *user_data)
248 {
249  assert(proc != nullptr);
250  assert(size > 0);
251 
252  if (size % 2 == 1) {
253  /* If the length of the side is uneven, the center has to be checked
254  * separately, as the pattern of uneven sides requires to go around the center */
255  if (proc(*tile, user_data)) return true;
256 
257  /* If tile test is not successful, get one tile up,
258  * ready for a test in first circle around center tile */
259  *tile = TileAddByDir(*tile, DIR_N);
260  return CircularTileSearch(tile, size / 2, 1, 1, proc, user_data);
261  } else {
262  return CircularTileSearch(tile, size / 2, 0, 0, proc, user_data);
263  }
264 }
265 
285 bool CircularTileSearch(TileIndex *tile, uint radius, uint w, uint h, TestTileOnSearchProc proc, void *user_data)
286 {
287  assert(proc != nullptr);
288  assert(radius > 0);
289 
290  uint x = TileX(*tile) + w + 1;
291  uint y = TileY(*tile);
292 
293  const uint extent[DIAGDIR_END] = { w, h, w, h };
294 
295  for (uint n = 0; n < radius; n++) {
296  for (DiagDirection dir = DIAGDIR_BEGIN; dir < DIAGDIR_END; dir++) {
297  /* Is the tile within the map? */
298  for (uint j = extent[dir] + n * 2 + 1; j != 0; j--) {
299  if (x < Map::SizeX() && y < Map::SizeY()) {
300  TileIndex t = TileXY(x, y);
301  /* Is the callback successful? */
302  if (proc(t, user_data)) {
303  /* Stop the search */
304  *tile = t;
305  return true;
306  }
307  }
308 
309  /* Step to the next 'neighbour' in the circular line */
310  x += _tileoffs_by_diagdir[dir].x;
311  y += _tileoffs_by_diagdir[dir].y;
312  }
313  }
314  /* Jump to next circle to test */
315  x += _tileoffs_by_dir[DIR_W].x;
316  y += _tileoffs_by_dir[DIR_W].y;
317  }
318 
319  *tile = INVALID_TILE;
320  return false;
321 }
322 
329 uint GetClosestWaterDistance(TileIndex tile, bool water)
330 {
331  if (HasTileWaterGround(tile) == water) return 0;
332 
333  uint max_dist = water ? 0x7F : 0x200;
334 
335  int x = TileX(tile);
336  int y = TileY(tile);
337 
338  uint max_x = Map::MaxX();
339  uint max_y = Map::MaxY();
340  uint min_xy = _settings_game.construction.freeform_edges ? 1 : 0;
341 
342  /* go in a 'spiral' with increasing manhattan distance in each iteration */
343  for (uint dist = 1; dist < max_dist; dist++) {
344  /* next 'diameter' */
345  y--;
346 
347  /* going counter-clockwise around this square */
348  for (DiagDirection dir = DIAGDIR_BEGIN; dir < DIAGDIR_END; dir++) {
349  static const int8_t ddx[DIAGDIR_END] = { -1, 1, 1, -1};
350  static const int8_t ddy[DIAGDIR_END] = { 1, 1, -1, -1};
351 
352  int dx = ddx[dir];
353  int dy = ddy[dir];
354 
355  /* each side of this square has length 'dist' */
356  for (uint a = 0; a < dist; a++) {
357  /* MP_VOID tiles are not checked (interval is [min; max) for IsInsideMM())*/
358  if (IsInsideMM(x, min_xy, max_x) && IsInsideMM(y, min_xy, max_y)) {
359  TileIndex t = TileXY(x, y);
360  if (HasTileWaterGround(t) == water) return dist;
361  }
362  x += dx;
363  y += dy;
364  }
365  }
366  }
367 
368  if (!water) {
369  /* no land found - is this a water-only map? */
370  for (TileIndex t = 0; t < Map::Size(); t++) {
371  if (!IsTileType(t, MP_VOID) && !IsTileType(t, MP_WATER)) return 0x1FF;
372  }
373  }
374 
375  return max_dist;
376 }
Functions related to the allocation of memory.
constexpr uint8_t FindFirstBit(T x)
Search the first set bit in a value.
static TileBase * base_tiles
Pointer to the tile-array.
Definition: map_func.h:54
static TileExtended * extended_tiles
Pointer to the extended tile-array.
Definition: map_func.h:55
Functions related to debugging.
#define Debug(category, level, format_string,...)
Ouptut a line of debugging information.
Definition: debug.h:37
@ DIR_N
North.
@ DIR_W
West.
DiagDirection
Enumeration for diagonal directions.
@ DIAGDIR_NE
Northeast, upper right on your monitor.
@ DIAGDIR_NW
Northwest.
@ DIAGDIR_SE
Southeast.
@ DIAGDIR_END
Used for iterations.
@ DIAGDIR_BEGIN
Used for iterations.
@ DIAGDIR_SW
Southwest.
Error reporting related functions.
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
uint DistanceSquare(TileIndex t0, TileIndex t1)
Gets the 'Square' distance between the two given tiles.
Definition: map.cpp:163
const TileIndexDiffC _tileoffs_by_axis[]
'Lookup table' for tile offsets given an Axis
uint DistanceFromEdge(TileIndex tile)
Param the minimum distance to an edge.
Definition: map.cpp:206
uint DistanceMax(TileIndex t0, TileIndex t1)
Gets the biggest distance component (x or y) between the two given tiles.
Definition: map.cpp:178
uint DistanceFromEdgeDir(TileIndex tile, DiagDirection dir)
Gets the distance to the edge of the map in given direction.
Definition: map.cpp:223
uint DistanceMaxPlusManhattan(TileIndex t0, TileIndex t1)
Gets the biggest distance component (x or y) between the two given tiles plus the Manhattan distance,...
Definition: map.cpp:194
const TileIndexDiffC _tileoffs_by_dir[]
'Lookup table' for tile offsets given a Direction
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 DistanceManhattan(TileIndex t0, TileIndex t1)
Gets the Manhattan distance between the two given tiles.
Definition: map.cpp:146
uint GetClosestWaterDistance(TileIndex tile, bool water)
Finds the distance for the closest tile with water/land given a tile.
Definition: map.cpp:329
const TileIndexDiffC _tileoffs_by_diagdir[]
'Lookup table' for tile offsets given a DiagDirection
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
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
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
static const uint MAX_MAP_SIZE
Maximal map size = 4096.
Definition: map_type.h:40
static const uint MIN_MAP_SIZE
Minimal map size = 64.
Definition: map_type.h:39
int32_t TileIndexDiff
An offset value between two tiles.
Definition: map_type.h:23
constexpr T Delta(const T a, const T b)
Returns the (absolute) difference between two (scalar) variables.
Definition: math_func.hpp:234
constexpr bool IsInsideMM(const T x, const size_t min, const size_t max) noexcept
Checks if a value is in an interval.
Definition: math_func.hpp:268
A number of safeguards to prevent using unsafe methods.
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition: settings.cpp:57
Definition of base types and functions in a cross-platform compatible way.
void free(const void *ptr)
Version of the standard free that accepts const pointers.
Definition: stdafx.h:334
Functions related to low-level strings.
bool freeform_edges
allow terraforming the tiles at the map edges
ConstructionSettings construction
construction of things in-game
static TileIndex WrapToMap(TileIndex tile)
'Wraps' the given "tile" so it is within the map.
Definition: map_func.h:317
static uint SizeY()
Get the size of the map along the Y.
Definition: map_func.h:279
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 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 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
Data that is stored per tile.
Definition: map_func.h:48
static debug_inline bool IsTileType(Tile tile, TileType type)
Checks if a tile is a given tiletype.
Definition: tile_map.h:150
constexpr TileIndex INVALID_TILE
The very nice invalid tile marker.
Definition: tile_type.h:95
@ MP_WATER
Water tile.
Definition: tile_type.h:54
@ MP_VOID
Invisible tiles at the SW and SE border.
Definition: tile_type.h:55
Map accessors for water tiles.
bool HasTileWaterGround(Tile t)
Checks whether the tile has water at the ground.
Definition: water_map.h:350
void AllocateWaterRegions()
Allocates the appropriate amount of water regions for the current map size.
Handles dividing the water in the map into regions to assist pathfinding.