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