OpenTTD Source  1.11.0-beta2
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 "string_func.h"
15 
16 #include "safeguards.h"
17 
18 #if defined(_MSC_VER)
19 /* Why the hell is that not in all MSVC headers?? */
20 extern "C" _CRTIMP void __cdecl _assert(void *, void *, unsigned);
21 #endif
22 
23 uint _map_log_x;
24 uint _map_log_y;
27 uint _map_size;
29 
30 Tile *_m = nullptr;
31 TileExtended *_me = nullptr;
32 
33 
39 void AllocateMap(uint size_x, uint size_y)
40 {
41  /* Make sure that the map size is within the limits and that
42  * size of both axes is a power of 2. */
43  if (!IsInsideMM(size_x, MIN_MAP_SIZE, MAX_MAP_SIZE + 1) ||
44  !IsInsideMM(size_y, MIN_MAP_SIZE, MAX_MAP_SIZE + 1) ||
45  (size_x & (size_x - 1)) != 0 ||
46  (size_y & (size_y - 1)) != 0) {
47  error("Invalid map size");
48  }
49 
50  DEBUG(map, 1, "Allocating map of size %dx%d", size_x, size_y);
51 
52  _map_log_x = FindFirstBit(size_x);
53  _map_log_y = FindFirstBit(size_y);
54  _map_size_x = size_x;
55  _map_size_y = size_y;
56  _map_size = size_x * size_y;
58 
59  free(_m);
60  free(_me);
61 
62  _m = CallocT<Tile>(_map_size);
63  _me = CallocT<TileExtended>(_map_size);
64 }
65 
66 
67 #ifdef _DEBUG
68 TileIndex TileAdd(TileIndex tile, TileIndexDiff add,
69  const char *exp, const char *file, int line)
70 {
71  int dx;
72  int dy;
73  uint x;
74  uint y;
75 
76  dx = add & MapMaxX();
77  if (dx >= (int)MapSizeX() / 2) dx -= MapSizeX();
78  dy = (add - dx) / (int)MapSizeX();
79 
80  x = TileX(tile) + dx;
81  y = TileY(tile) + dy;
82 
83  if (x >= MapSizeX() || y >= MapSizeY()) {
84  char buf[512];
85 
86  seprintf(buf, lastof(buf), "TILE_ADD(%s) when adding 0x%.4X and 0x%.4X failed",
87  exp, tile, add);
88 #if !defined(_MSC_VER)
89  fprintf(stderr, "%s:%d %s\n", file, line, buf);
90 #else
91  _assert(buf, (char*)file, line);
92 #endif
93  }
94 
95  assert(TileXY(x, y) == TILE_MASK(tile + add));
96 
97  return TileXY(x, y);
98 }
99 #endif
100 
114 TileIndex TileAddWrap(TileIndex tile, int addx, int addy)
115 {
116  uint x = TileX(tile) + addx;
117  uint y = TileY(tile) + addy;
118 
119  /* Disallow void tiles at the north border. */
120  if ((x == 0 || y == 0) && _settings_game.construction.freeform_edges) return INVALID_TILE;
121 
122  /* Are we about to wrap? */
123  if (x >= MapMaxX() || y >= MapMaxY()) return INVALID_TILE;
124 
125  return TileXY(x, y);
126 }
127 
129 extern const TileIndexDiffC _tileoffs_by_diagdir[] = {
130  {-1, 0},
131  { 0, 1},
132  { 1, 0},
133  { 0, -1}
134 };
135 
137 extern const TileIndexDiffC _tileoffs_by_dir[] = {
138  {-1, -1},
139  {-1, 0},
140  {-1, 1},
141  { 0, 1},
142  { 1, 1},
143  { 1, 0},
144  { 1, -1},
145  { 0, -1}
146 };
147 
158 {
159  const uint dx = Delta(TileX(t0), TileX(t1));
160  const uint dy = Delta(TileY(t0), TileY(t1));
161  return dx + dy;
162 }
163 
164 
175 {
176  const int dx = TileX(t0) - TileX(t1);
177  const int dy = TileY(t0) - TileY(t1);
178  return dx * dx + dy * dy;
179 }
180 
181 
190 {
191  const uint dx = Delta(TileX(t0), TileX(t1));
192  const uint dy = Delta(TileY(t0), TileY(t1));
193  return std::max(dx, dy);
194 }
195 
196 
206 {
207  const uint dx = Delta(TileX(t0), TileX(t1));
208  const uint dy = Delta(TileY(t0), TileY(t1));
209  return dx > dy ? 2 * dx + dy : 2 * dy + dx;
210 }
211 
218 {
219  const uint xl = TileX(tile);
220  const uint yl = TileY(tile);
221  const uint xh = MapSizeX() - 1 - xl;
222  const uint yh = MapSizeY() - 1 - yl;
223  const uint minl = std::min(xl, yl);
224  const uint minh = std::min(xh, yh);
225  return std::min(minl, minh);
226 }
227 
235 {
236  switch (dir) {
237  case DIAGDIR_NE: return TileX(tile) - (_settings_game.construction.freeform_edges ? 1 : 0);
238  case DIAGDIR_NW: return TileY(tile) - (_settings_game.construction.freeform_edges ? 1 : 0);
239  case DIAGDIR_SW: return MapMaxX() - TileX(tile) - 1;
240  case DIAGDIR_SE: return MapMaxY() - TileY(tile) - 1;
241  default: NOT_REACHED();
242  }
243 }
244 
258 bool CircularTileSearch(TileIndex *tile, uint size, TestTileOnSearchProc proc, void *user_data)
259 {
260  assert(proc != nullptr);
261  assert(size > 0);
262 
263  if (size % 2 == 1) {
264  /* If the length of the side is uneven, the center has to be checked
265  * separately, as the pattern of uneven sides requires to go around the center */
266  if (proc(*tile, user_data)) return true;
267 
268  /* If tile test is not successful, get one tile up,
269  * ready for a test in first circle around center tile */
270  *tile = TileAddByDir(*tile, DIR_N);
271  return CircularTileSearch(tile, size / 2, 1, 1, proc, user_data);
272  } else {
273  return CircularTileSearch(tile, size / 2, 0, 0, proc, user_data);
274  }
275 }
276 
296 bool CircularTileSearch(TileIndex *tile, uint radius, uint w, uint h, TestTileOnSearchProc proc, void *user_data)
297 {
298  assert(proc != nullptr);
299  assert(radius > 0);
300 
301  uint x = TileX(*tile) + w + 1;
302  uint y = TileY(*tile);
303 
304  const uint extent[DIAGDIR_END] = { w, h, w, h };
305 
306  for (uint n = 0; n < radius; n++) {
307  for (DiagDirection dir = DIAGDIR_BEGIN; dir < DIAGDIR_END; dir++) {
308  /* Is the tile within the map? */
309  for (uint j = extent[dir] + n * 2 + 1; j != 0; j--) {
310  if (x < MapSizeX() && y < MapSizeY()) {
311  TileIndex t = TileXY(x, y);
312  /* Is the callback successful? */
313  if (proc(t, user_data)) {
314  /* Stop the search */
315  *tile = t;
316  return true;
317  }
318  }
319 
320  /* Step to the next 'neighbour' in the circular line */
321  x += _tileoffs_by_diagdir[dir].x;
322  y += _tileoffs_by_diagdir[dir].y;
323  }
324  }
325  /* Jump to next circle to test */
326  x += _tileoffs_by_dir[DIR_W].x;
327  y += _tileoffs_by_dir[DIR_W].y;
328  }
329 
330  *tile = INVALID_TILE;
331  return false;
332 }
333 
340 uint GetClosestWaterDistance(TileIndex tile, bool water)
341 {
342  if (HasTileWaterGround(tile) == water) return 0;
343 
344  uint max_dist = water ? 0x7F : 0x200;
345 
346  int x = TileX(tile);
347  int y = TileY(tile);
348 
349  uint max_x = MapMaxX();
350  uint max_y = MapMaxY();
351  uint min_xy = _settings_game.construction.freeform_edges ? 1 : 0;
352 
353  /* go in a 'spiral' with increasing manhattan distance in each iteration */
354  for (uint dist = 1; dist < max_dist; dist++) {
355  /* next 'diameter' */
356  y--;
357 
358  /* going counter-clockwise around this square */
359  for (DiagDirection dir = DIAGDIR_BEGIN; dir < DIAGDIR_END; dir++) {
360  static const int8 ddx[DIAGDIR_END] = { -1, 1, 1, -1};
361  static const int8 ddy[DIAGDIR_END] = { 1, 1, -1, -1};
362 
363  int dx = ddx[dir];
364  int dy = ddy[dir];
365 
366  /* each side of this square has length 'dist' */
367  for (uint a = 0; a < dist; a++) {
368  /* MP_VOID tiles are not checked (interval is [min; max) for IsInsideMM())*/
369  if (IsInsideMM(x, min_xy, max_x) && IsInsideMM(y, min_xy, max_y)) {
370  TileIndex t = TileXY(x, y);
371  if (HasTileWaterGround(t) == water) return dist;
372  }
373  x += dx;
374  y += dy;
375  }
376  }
377  }
378 
379  if (!water) {
380  /* no land found - is this a water-only map? */
381  for (TileIndex t = 0; t < MapSize(); t++) {
382  if (!IsTileType(t, MP_VOID) && !IsTileType(t, MP_WATER)) return 0x1FF;
383  }
384  }
385 
386  return max_dist;
387 }
_map_log_y
uint _map_log_y
2^_map_log_y == _map_size_y
Definition: map.cpp:24
DIAGDIR_SE
@ DIAGDIR_SE
Southeast.
Definition: direction_type.h:80
TileIndex
uint32 TileIndex
The index/ID of a Tile.
Definition: tile_type.h:78
_tileoffs_by_dir
const TileIndexDiffC _tileoffs_by_dir[]
'Lookup table' for tile offsets given a Direction
MIN_MAP_SIZE
static const uint MIN_MAP_SIZE
Minimal map size = 64.
Definition: map_type.h:65
TestTileOnSearchProc
bool TestTileOnSearchProc(TileIndex tile, void *user_data)
A callback function type for searching tiles.
Definition: map_func.h:414
_map_size
uint _map_size
The number of tiles on the map.
Definition: map.cpp:27
GetClosestWaterDistance
uint GetClosestWaterDistance(TileIndex tile, bool water)
Finds the distance for the closest tile with water/land given a tile.
Definition: map.cpp:340
TileAddByDir
static TileIndex TileAddByDir(TileIndex tile, Direction dir)
Adds a Direction to a tile.
Definition: map_func.h:370
DIAGDIR_END
@ DIAGDIR_END
Used for iterations.
Definition: direction_type.h:83
_me
TileExtended * _me
Extended Tiles of the map.
Definition: map.cpp:31
TileY
static uint TileY(TileIndex tile)
Get the Y component of a tile.
Definition: map_func.h:215
DIAGDIR_NW
@ DIAGDIR_NW
Northwest.
Definition: direction_type.h:82
DIR_W
@ DIR_W
West.
Definition: direction_type.h:32
TILE_MASK
#define TILE_MASK(x)
'Wraps' the given tile to it is within the map.
Definition: map_func.h:26
_tileoffs_by_diagdir
const TileIndexDiffC _tileoffs_by_diagdir[]
'Lookup table' for tile offsets given a DiagDirection
DIR_N
@ DIR_N
North.
Definition: direction_type.h:26
TileX
static uint TileX(TileIndex tile)
Get the X component of a tile.
Definition: map_func.h:205
IsInsideMM
static bool IsInsideMM(const T x, const size_t min, const size_t max)
Checks if a value is in an interval.
Definition: math_func.hpp:204
MapSizeX
static uint MapSizeX()
Get the size of the map along the X.
Definition: map_func.h:72
_map_size_x
uint _map_size_x
Size of the map along the X.
Definition: map.cpp:25
DistanceManhattan
uint DistanceManhattan(TileIndex t0, TileIndex t1)
Gets the Manhattan distance between the two given tiles.
Definition: map.cpp:157
DIAGDIR_SW
@ DIAGDIR_SW
Southwest.
Definition: direction_type.h:81
TileIndexDiffC::y
int16 y
The y value of the coordinate.
Definition: map_type.h:59
MapSize
static uint MapSize()
Get the size of the map.
Definition: map_func.h:92
TileAddWrap
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:114
HasTileWaterGround
static bool HasTileWaterGround(TileIndex t)
Checks whether the tile has water at the ground.
Definition: water_map.h:344
CircularTileSearch
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:258
TileIndexDiff
int32 TileIndexDiff
An offset value between to tiles.
Definition: map_func.h:154
DEBUG
#define DEBUG(name, level,...)
Output a line of debugging information.
Definition: debug.h:35
DistanceFromEdge
uint DistanceFromEdge(TileIndex tile)
Param the minimum distance to an edge.
Definition: map.cpp:217
MP_WATER
@ MP_WATER
Water tile.
Definition: tile_type.h:47
_settings_game
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition: settings.cpp:80
safeguards.h
DistanceFromEdgeDir
uint DistanceFromEdgeDir(TileIndex tile, DiagDirection dir)
Gets the distance to the edge of the map in given direction.
Definition: map.cpp:234
ConstructionSettings::freeform_edges
bool freeform_edges
allow terraforming the tiles at the map edges
Definition: settings_type.h:319
DiagDirection
DiagDirection
Enumeration for diagonal directions.
Definition: direction_type.h:77
MapSizeY
static uint MapSizeY()
Get the size of the map along the Y.
Definition: map_func.h:82
stdafx.h
_map_log_x
uint _map_log_x
2^_map_log_x == _map_size_x
Definition: map.cpp:23
Tile
Data that is stored per tile.
Definition: map_type.h:17
IsTileType
static bool IsTileType(TileIndex tile, TileType type)
Checks if a tile is a given tiletype.
Definition: tile_map.h:150
DistanceMax
uint DistanceMax(TileIndex t0, TileIndex t1)
Gets the biggest distance component (x or y) between the two given tiles.
Definition: map.cpp:189
TileIndexDiffC
A pair-construct of a TileIndexDiff.
Definition: map_type.h:57
water_map.h
DistanceSquare
uint DistanceSquare(TileIndex t0, TileIndex t1)
Gets the 'Square' distance between the two given tiles.
Definition: map.cpp:174
string_func.h
MapMaxY
static uint MapMaxY()
Gets the maximum Y coordinate within the map, including MP_VOID.
Definition: map_func.h:111
MP_VOID
@ MP_VOID
Invisible tiles at the SW and SE border.
Definition: tile_type.h:48
TileXY
static TileIndex TileXY(uint x, uint y)
Returns the TileIndex of a coordinate.
Definition: map_func.h:163
alloc_func.hpp
TileExtended
Data that is stored per tile.
Definition: map_type.h:33
DIAGDIR_BEGIN
@ DIAGDIR_BEGIN
Used for iterations.
Definition: direction_type.h:78
seprintf
int CDECL seprintf(char *str, const char *last, const char *format,...)
Safer implementation of snprintf; same as snprintf except:
Definition: string.cpp:442
_map_tile_mask
uint _map_tile_mask
_map_size - 1 (to mask the mapsize)
Definition: map.cpp:28
MapMaxX
static uint MapMaxX()
Gets the maximum X coordinate within the map, including MP_VOID.
Definition: map_func.h:102
error
void CDECL error(const char *s,...)
Error handling for fatal non-user errors.
Definition: openttd.cpp:129
INVALID_TILE
static const TileIndex INVALID_TILE
The very nice invalid tile marker.
Definition: tile_type.h:83
GameSettings::construction
ConstructionSettings construction
construction of things in-game
Definition: settings_type.h:551
DistanceMaxPlusManhattan
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:205
MAX_MAP_SIZE
static const uint MAX_MAP_SIZE
Maximal map size = 4096.
Definition: map_type.h:66
free
static void free(const void *ptr)
Version of the standard free that accepts const pointers.
Definition: stdafx.h:454
_map_size_y
uint _map_size_y
Size of the map along the Y.
Definition: map.cpp:26
DIAGDIR_NE
@ DIAGDIR_NE
Northeast, upper right on your monitor.
Definition: direction_type.h:79
lastof
#define lastof(x)
Get the last element of an fixed size array.
Definition: stdafx.h:383
AllocateMap
void AllocateMap(uint size_x, uint size_y)
(Re)allocates a map with the given dimension
Definition: map.cpp:39
_m
Tile * _m
Tiles of the map.
Definition: map.cpp:30
FindFirstBit
uint8 FindFirstBit(uint32 x)
Search the first set bit in a 32 bit variable.
Definition: bitmath_func.cpp:37
Delta
static T Delta(const T a, const T b)
Returns the (absolute) difference between two (scalar) variables.
Definition: math_func.hpp:170
debug.h
TileIndexDiffC::x
int16 x
The x value of the coordinate.
Definition: map_type.h:58